높이 제한 또는 깊이 제한 허프만 트리의 다이어그램은 다음과 같습니다.
트리 깊이 제한은 대부분의 실제 Huffman 구현에서 처리해야 하는 사소한 문제입니다.
Huffman 구조는 높이나 깊이를 제한하지 않습니다. 그렇다면 "최적"이 될 수 없습니다. 물론, 허프만 트리의 가장 큰 깊이는 피보나치 수열에 의해 제한되지만 원하는 것보다 더 큰 깊이를 위한 충분한 공간을 남깁니다.
Huffman 트리 깊이를 제한하는 이유는 무엇입니까? Fast Huffman 디코더는 룩업 테이블을 구현합니다. 메모리 비용을 줄이기 위해 여러 테이블 수준을 구현하는 것이 가능하지만 Huff0과 같은 매우 빠른 디코더는 단순성과 속도 모두를 위해 단일 테이블을 사용합니다. 이 경우 테이블 크기는 트리 깊이의 직접 곱으로 처리됩니다(tablesize =1 <
속도와 메모리 관리의 이점을 위해 제한을 선택해야 했습니다. 디코딩 테이블에 대해 8KB로, Intel의 L1 캐시에 잘 맞고 필요한 경우 다른 테이블과 결합할 수 있는 공간을 남겨둡니다. 최신 디코딩 테이블은 셀당 2바이트를 사용하므로 4K 셀로 변환되므로 최대 트리 깊이는 12비트입니다.
리터럴 압축을 위한 12비트는 적어도 최적의 Huffman 구성에 따르면 일반적으로 너무 짧습니다.
따라서 깊이 제한 트리를 구성하는 것은 해결해야 할 실질적인 문제입니다.
깊이가 제한된 허프만 나무는 1960년대부터 연구되어 왔으며 이용 가능한 문헌이 너무 많습니다.