허프만 코드 길이

Question

나는 허프만 트리를 만들고 그 빈도에 따라 255 바이트의 모든 값에 코드를 할당하려고합니다. 하지만 내 응용 프로그램에 대한 해시 테이블을 일정 시간에 바이트 코드를 얻을 필요가있다. 그러나 최악의 경우 트리가 너무 불균형하여 특정 바이트가 매우 큰 키 (심지어 254 비트 길이)를 가질 수 있습니다. 그러므로 해쉬 테이블을 유지하는 것은 매우 어렵습니다. 코드에는 고성능이 필요하므로 문자열로 스트링을 쓰면 작동하지 않습니다. 문제를 어떻게 해결할 수 있습니까?

Answer 1

왜 256 값의 해시 테이블이 필요합니까? 각 바이트의 코드를 직접 인덱싱하는 256 개 항목 테이블 만 있으면됩니다.

각 코드의 길이는 최대 32 바이트이므로 256 개 항목의 테이블이 있으며 각 항목 당 고정 된 수는 33 바이트입니다. 8448 바이트. 33의 첫 번째 바이트는 코드의 길이 (비트)이고 나머지 바이트는 코드 (필요한 비트 수만 사용)입니다.