7.22 허프만 부호(Huffman Coding)와 최적 접두사 부호의 구성

1. 허프만 부호화의 역사적 배경

데이비드 허프만(David A. Huffman)은 1952년 MIT 대학원생 시절, 로버트 파노(Robert Fano) 교수의 정보 이론 수업에서 최적 이진 접두어 부호의 구성 문제를 학기말 과제로 받았다. 허프만은 최적 부호를 구성하는 체계적 알고리즘을 발견하였으며, 그 결과를 “A Method for the Construction of Minimum-Redundancy Codes“라는 제목으로 발표하였다. 이 알고리즘은 주어진 확률 분포에 대해 평균 부호 길이를 최소화하는 접두어 부호를 탐욕적(greedy) 방법으로 구성하며, 기호 단위(symbol-by-symbol) 접두어 부호 중에서 최적임이 증명되었다.

2. 허프만 알고리즘

2.1 알고리즘의 절차

이산 정보원의 알파벳 \mathcal{X} = \{x_1, x_2, \ldots, x_q\}과 확률 분포 \{p_1, p_2, \ldots, p_q\}가 주어졌을 때, 이진 허프만 부호의 구성 알고리즘은 다음과 같다:

1. q개의 기호를 각각 하나의 잎 노드(leaf node)로 초기화한다. 각 노드의 가중치(weight)는 해당 기호의 확률이다.
2. 가중치가 가장 작은 두 노드를 선택한다.
3. 선택된 두 노드를 자식으로 하는 새로운 부모 노드를 생성한다. 부모 노드의 가중치는 두 자식의 가중치의 합이다.
4. 한 자식 가지에 0을, 다른 자식 가지에 1을 할당한다.
5. 두 자식 노드를 노드 집합에서 제거하고, 부모 노드를 추가한다.
6. 노드가 하나만 남을 때까지 2~5를 반복한다.
7. 루트(root)에서 각 잎 노드까지의 경로에 할당된 비트를 연결하면 해당 기호의 부호어가 된다.

2.2 구체적 사례

확률 분포 \{A: 0.4, B: 0.2, C: 0.2, D: 0.1, E: 0.1\}에 대한 허프만 부호 구성:

단계 1: D(0.1)과 E(0.1)을 결합 → 새 노드 DE(0.2)

단계 2: B(0.2)와 C(0.2)를 결합 → 새 노드 BC(0.4) (또는 C와 DE를 결합할 수도 있다)

단계 3: DE(0.2)와 BC(0.4)에서, DE(0.2)와 A(0.4) 중 가중치가 작은 DE(0.2)와 다음으로 작은 것을 결합. 동률이 있으므로 선택에 따라 트리 구조가 달라질 수 있다.

최종 부호의 한 예:

평균 부호 길이: \bar{L} = 0.4(1) + 0.2(2) + 0.2(3) + 0.1(4) + 0.1(4) = 2.2 bits

엔트로피: H = -0.4\log_2 0.4 - 0.2\log_2 0.2 - 0.2\log_2 0.2 - 0.1\log_2 0.1 - 0.1\log_2 0.1 \approx 2.122 bits

잉여성(redundancy): \bar{L} - H \approx 0.078 bits

3. 최적성 증명

3.1 정리의 진술

정리: 허프만 알고리즘으로 구성된 부호는 주어진 확률 분포에 대해 모든 접두어 부호 중 평균 부호 길이가 최소이다.

3.2 증명의 핵심 구조

증명은 알파벳 크기 q에 대한 수학적 귀납법으로 진행된다.

기저 사례: q = 2일 때, 부호어 ’0’과 ’1’을 할당하는 것이 유일한 비자명(non-trivial) 접두어 부호이며, 이는 허프만 알고리즘의 출력과 일치한다.

귀납 단계: q - 1개의 기호에 대해 허프만 부호가 최적이라 가정한다. q개의 기호에 대해:

(a) 최적 부호에서 확률이 가장 작은 두 기호가 가장 긴 부호어를 가지며, 이 두 부호어는 마지막 비트만 다른 형제 쌍임을 보인다 (최적 부호의 성질로부터).

(b) 이 두 기호를 하나의 새 기호(확률의 합)로 합쳐 q - 1개의 기호 문제로 축소한다.

(c) 귀납 가정에 의해 축소된 문제에서 허프만 부호가 최적이다.

(d) 축소된 문제의 최적 부호에서 합쳐진 기호를 다시 두 기호로 분리하면, 원래 q개 기호에 대한 허프만 부호를 복원하며, 이것이 최적임이 보장된다.

3.3 비유일성

허프만 부호는 유일하지 않을 수 있다. 동률(tie) 발생 시 가중치가 같은 노드 중 어느 것을 선택하느냐에 따라 트리 구조가 달라진다. 그러나 모든 허프만 부호는 동일한 최소 평균 부호 길이를 달성한다.

4. 허프만 부호의 성능 분석

4.1 평균 부호 길이의 범위

허프만 부호의 평균 부호 길이 \bar{L}_H는 다음을 만족한다:

H(X) \leq \bar{L}_H < H(X) + 1

하한은 무잡음 부호화 정리에 의한 것이고, 상한은 섀넌 부호(l_i = \lceil -\log_2 p_i \rceil)의 평균 부호 길이가 H(X) + 1 미만이며 허프만 부호가 이보다 짧거나 같다는 데서 도출된다.

4.2 더 정밀한 상한

갈라거(Robert Gallager)는 허프만 부호의 평균 부호 길이에 대해 더 정밀한 상한을 증명하였다:

\bar{L}_H < H(X) + p_{\max}

여기서 p_{\max} = \max_i p_i이다. p_{\max} < 1이므로 이 상한은 H(X) + 1보다 엄격하다. 특히, 확률 분포가 비교적 균등할 때(모든 확률이 작을 때) 허프만 부호가 엔트로피에 매우 가깝게 접근함을 보여준다.

4.3 잉여성의 범위

허프만 부호의 잉여성(redundancy) R = \bar{L}_H - H(X)는:

0 \leq R < \min(1, p_{\max} + 0.086)

카파르디(Capocelli), 지안칼로(Giancarlo), 탄제(Taneja) 등의 연구에 의해 잉여성의 상한에 대한 정밀한 결과가 알려져 있다.

5. 허프만 부호의 한계와 확장

5.1 정수 길이 제약의 한계

허프만 부호는 각 기호에 정수 길이의 부호어를 할당한다. 이상적 부호어 길이 -\log_2 p_i가 정수가 아닌 경우, 올림에 의한 비효율이 발생한다. 이 비효율은 확률이 2^{-k} 꼴이 아닌 기호가 존재할 때 불가피하다.

5.2 확장 허프만 부호

블록 허프만 부호(extended Huffman code)는 n개 기호의 블록에 대해 허프만 부호를 구성한다. 기호 당 잉여성이 1/n 이하로 줄어들어 엔트로피에 더 가깝게 접근한다. 그러나 알파벳 크기가 q^n으로 지수적으로 증가하여 실용적 구현에 한계가 있다.

5.3 D진 허프만 부호

이진 부호를 D진 부호로 일반화할 수 있다. D진 알파벳 \{0, 1, \ldots, D-1\}에 대한 허프만 부호의 구성은 이진의 경우와 유사하되, 각 단계에서 D개의 노드를 결합한다. q가 (q - 1) / (D - 1)이 정수가 아닌 경우, 첫 단계에서 더미(dummy) 기호를 추가하여 조정한다.

6. 구현 고려 사항

6.1 시간 복잡도

허프만 알고리즘의 시간 복잡도는 최소 가중치 노드를 효율적으로 추출하는 자료 구조에 의존한다. 최소 힙(min-heap)을 사용하면 각 추출 및 삽입이 O(\log q)이므로, 총 q - 1회의 합병에 대해 O(q \log q)이다. 확률이 사전 정렬되어 있는 경우, 두 개의 큐(queue)를 사용하는 방법으로 O(q)에 수행할 수 있다.

6.2 적응적 허프만 부호화

정보원의 확률 분포가 사전에 알려져 있지 않거나 시간에 따라 변하는 경우, 적응적 허프만 부호화(adaptive Huffman coding)가 사용된다. 비터(Vitter)의 알고리즘은 각 기호가 처리될 때마다 허프만 트리를 점진적으로 갱신한다. 이 방법은 분포의 사전 전송을 필요로 하지 않으므로, 부호화기와 복호화기가 동일한 초기 트리에서 출발하여 동일한 갱신 규칙을 적용함으로써 동기화를 유지한다.

7. 결론

허프만 부호화는 기호 단위 접두어 부호 중 평균 부호 길이를 최소화하는 최적 알고리즘이다. 탐욕적 합병 전략에 의한 구성은 개념적으로 단순하면서도 최적성이 증명되며, O(q \log q)의 효율적 시간 복잡도를 가진다. 허프만 부호의 평균 부호 길이는 엔트로피보다 최대 1비트(또는 p_{\max}비트) 길며, 블록 부호화에 의해 이 간극을 줄일 수 있다. 허프만 부호화는 파일 압축(ZIP, GZIP), 이미지 압축(JPEG), 통신 프로토콜 등에서 널리 사용되며, 정보 이론의 이론적 결과가 실용적 기술로 구현된 대표적 사례이다.