높이 제한 허프만 트리란?
아래 그림은 높이 또는 깊이가 제한된(depth-limited) 허프만 트리의 구조를 보여줍니다.
트리 깊이 제한은 사소해 보이지만, 실제 환경에서 허프만 코딩을 구현하는 대부분의 시스템이 반드시 해결해야 하는 중요한 문제입니다.
허프만 트리 생성에는 깊이 제한이 없다
표준 허프만 트리 생성 알고리즘 자체는 트리의 높이나 깊이를 제한하지 않습니다. 오히려 깊이를 임의로 제한하면 트리가 더 이상 '최적(optimal)' 상태를 유지할 수 없게 됩니다.
다만 허프만 트리의 최대 깊이는 피보나치 수열(Fibonacci series)에 의해 상한이 정해집니다. 즉, 입력 데이터의 빈도 분포가 피보나치 수열 형태일 때 가장 깊은 트리가 만들어지는데, 그럼에도 불구하고 실제로 원하는 깊이보다 훨씬 깊은 트리가 생성될 여지는 충분히 남아 있습니다.
왜 허프만 트리의 깊이를 제한해야 할까?
그렇다면 왜 굳이 허프만 트리의 깊이를 제한해야 할까요? 그 답은 빠른 디코딩 성능에 있습니다.
고속 허프만 디코더는 룩업 테이블(lookup table) 방식을 사용합니다. 메모리 비용을 줄이기 위해 테이블을 여러 단계로 나누어 구현할 수도 있지만, Huff0처럼 극한의 속도를 추구하는 디코더는 단순성과 속도를 위해 단일 테이블(single table)을 선택합니다.
이 경우 테이블 크기는 트리 깊이에 직접적으로 비례합니다.
tableSize = 1 << treeDepth
즉, 트리가 깊어질수록 디코딩 테이블의 크기는 기하급수적으로 커지며, 메모리 사용량과 캐시 효율에 직접적인 영향을 미칩니다.
8KB 제한과 12비트 최대 깊이
속도와 메모리 관리 측면의 이점을 고려하여 제한값을 정해야 했고, 그 결과 디코딩 테이블 크기는 8KB로 결정되었습니다. 8KB는 인텔 CPU의 L1 캐시에 딱 맞게 들어가는 크기이며, 필요하다면 다른 테이블과 조합해서 사용할 여유 공간도 남깁니다.
최신 디코딩 테이블은 셀(cell)당 2바이트를 사용하므로, 8KB는 총 4K개의 셀에 해당합니다. 따라서 최대 트리 깊이는 12비트로 계산됩니다.
12비트 제한의 한계와 실용적 접근
문제는 리터럴(literal) 압축에 12비트라는 깊이 제한이 일반적으로 너무 짧다는 점입니다. 적어도 이론상 최적의 허프만 트리 구성 기준으로 보면 분명히 부족합니다.
따라서 깊이가 제한된 허프만 트리를 구성하는 것은 단순한 이론적 논의가 아니라, 실제로 반드시 해결해야 하는 실용적(practical) 과제가 됩니다.
다행히 깊이 제한 허프만 트리는 1960년대부터 꾸준히 연구되어 온 주제이기 때문에, 오늘날 이를 해결하기 위한 학술 문헌과 검증된 알고리즘이 매우 풍부하게 존재합니다.