허프만 알고리즘의 기본 절차
허프만(Huffman) 알고리즘은 가중치(문자의 빈도)를 기반으로 최적의 코드 트리를 만들어내는 대표적인 알고리즘입니다. 그 동작 과정은 다음과 같이 단순하게 정리할 수 있습니다.
- n개의 초기 허프만 트리를 준비합니다. 각 트리는 하나의 리프(leaf) 노드로만 구성되며, 이 n개의 트리를 가중치(빈도)를 기준으로 정렬된 우선순위 큐(priority queue)에 넣어 관리합니다.
- 우선순위 큐에서 가장 작은 가중치를 가진 두 개의 트리를 꺼냅니다(삭제합니다). 이 두 트리를 결합해 새로운 트리를 만드는데, 새 트리의 루트는 두 트리를 자식 노드로 가지며, 그 가중치는 두 자식 트리의 가중치 합이 됩니다.
- 새로 만들어진 트리를 다시 우선순위 큐에 삽입합니다.
- 모든 부분 허프만 트리가 하나로 합쳐질 때까지 위의 2~3단계를 반복합니다.
그리디 알고리즘으로서의 허프만
허프만 알고리즘은 그리디(greedy) 알고리즘입니다. 즉, 매 반복 단계마다 '가장 작은 가중치를 가진 두 개의 부분 트리'를 병합하는 탐욕적 선택을 수행합니다. 그렇다면 이러한 지역적 선택이 항상 우리가 원하는 최적의 결과를 보장할 수 있을까요?
다음의 보조정리와 정리가 이를 이론적으로 뒷받침합니다.
- 보조정리(Lemma): x와 y를 빈도가 가장 낮은 두 문자라고 하자. x와 y가 서로 형제(sibling) 관계이면서 트리 내에서 다른 어떤 리프 노드보다도 깊은 위치, 즉 최대 깊이에 놓이는 최적 코드 트리(optimal code tree)가 반드시 존재한다.
- 정리(Theorem): 허프만 코드는 최적의 접두사 없는(prefix-free) 이진 코드이다. 다시 말해, 그리디 알고리즘은 주어진 문자 집합에 대해 최소 외부 경로 가중치(minimum external path weight)를 갖는 허프만 트리를 구성한다.
결국 허프만 알고리즘은 매 단계의 선택이 전체 트리의 외부 경로 길이를 최소화하도록 작동하기 때문에, 그리디 방식임에도 불구하고 전역적으로 최적해를 보장한다는 사실이 증명되어 있습니다.