8.12 허프만 부호화(Huffman Coding)의 설계 절차

1. 허프만 부호화의 개요

허프만 부호화(Huffman Coding)는 1952년 David A. Huffman이 MIT 대학원생 시절 “A Method for the Construction of Minimum-Redundancy Codes“에서 발표한 알고리즘이다. 이 알고리즘은 주어진 확률 분포에 대하여 평균 부호어 길이를 최소화하는 접두사 부호를 구성한다. 허프만 부호화는 탐욕적(greedy) 상향식(bottom-up) 트리 구성 방법에 기반하며, 단일 기호 접두사 부호 중에서 최적임이 엄밀히 증명되어 있다.

2. 허프만 알고리즘의 절차

입력: 정보원 기호 $x_1, x_2, \dots, x_M$ 과 확률 $p_1, p_2, \dots, p_M > 0$

출력: 최적 접두사 부호의 부호어 $c_1, c_2, \dots, c_M$

절차:

각 기호를 하나의 잎 노드로 하는 노드 집합 $\mathcal{N} = \{n_1, n_2, \dots, n_M\}$ 를 초기화한다. 각 노드 $n_i$ 의 가중치를 $w(n_i) = p_i$ 로 설정한다.
$\lvert \mathcal{N} \rvert \geq 2$ 인 동안 다음을 반복한다:

(a) $\mathcal{N}$ 에서 가중치가 가장 작은 두 노드 $n_a$ 와 $n_b$ 를 선택한다. ( $w(n_a) \leq w(n_b) \leq w(n_k)$ , $\forall k \neq a, b$ )
(b) 새 내부 노드 $n_{\text{new}}$ 를 생성하고, $n_a$ 를 왼쪽 자식(비트 $0$ ), $n_b$ 를 오른쪽 자식(비트 $1$ )으로 설정한다.
(c) $w(n_{\text{new}}) = w(n_a) + w(n_b)$ 로 가중치를 설정한다.
(d) $\mathcal{N}$ 에서 $n_a$ 와 $n_b$ 를 제거하고 $n_{\text{new}}$ 를 추가한다.

$\mathcal{N}$ 에 남은 유일한 노드가 트리의 근(root)이 된다. 근에서 각 잎 노드까지의 경로에서 왼쪽/오른쪽 분기에 따라 $0$ / $1$ 을 할당하여 부호어를 결정한다.

3. 구체적 예

알파벳 $\mathcal{X} = \{a, b, c, d, e\}$ 이고 확률이 $p(a) = 0.35$ , $p(b) = 0.25$ , $p(c) = 0.20$ , $p(d) = 0.12$ , $p(e) = 0.08$ 인 경우를 고려하자.

반복 1: 가중치가 가장 작은 두 노드는 $e(0.08)$ 와 $d(0.12)$ 이다. 이를 병합하여 새 노드 $[de](0.20)$ 을 생성한다.

$\mathcal{N} = \{a(0.35),\; b(0.25),\; c(0.20),\; [de](0.20)\}$

반복 2: 가중치가 가장 작은 두 노드는 $c(0.20)$ 와 $[de](0.20)$ 이다. 이를 병합하여 $[cde](0.40)$ 을 생성한다.

$\mathcal{N} = \{a(0.35),\; b(0.25),\; [cde](0.40)\}$

반복 3: 가중치가 가장 작은 두 노드는 $b(0.25)$ 와 $a(0.35)$ 이다. 이를 병합하여 $[ab](0.60)$ 을 생성한다.

$\mathcal{N} = \{[cde](0.40),\; [ab](0.60)\}$

반복 4: 남은 두 노드를 병합하여 근 $[abcde](1.00)$ 을 생성한다.

결과 부호:

기호	확률	부호어	길이
$a$	0.35	10	2
$b$	0.25	11	2
$c$	0.20	00	2
$d$	0.12	010	3
$e$	0.08	011	3

평균 부호어 길이는 $L = 0.35 \times 2 + 0.25 \times 2 + 0.20 \times 2 + 0.12 \times 3 + 0.08 \times 3 = 2.20$ 비트이다.

4. 알고리즘의 복잡도

허프만 알고리즘의 시간 복잡도를 분석하자. $M$ 개의 기호에 대하여 반복 횟수는 $M - 1$ 이다. 각 반복에서 최소 가중치 노드 두 개를 선택하는 연산이 필요하다.

단순 구현: 매 반복마다 전체 리스트를 탐색하면 각 반복이 $O(M)$ 이므로 전체 시간 복잡도는 $O(M^2)$ 이다.
최소 힙(min-heap) 구현: 이진 힙을 사용하면 최소 원소 추출에 $O(\log M)$ , 삽입에 $O(\log M)$ 이 소요되므로 전체 시간 복잡도는 $O(M \log M)$ 이다.
정렬 선행 시 두 큐 방법: 기호를 확률의 비증가 순서로 미리 정렬한 후, 원래 기호 큐와 병합 노드 큐의 두 큐를 운용하면, 각 반복에서 두 큐의 앞쪽만 비교하면 되므로 반복당 $O(1)$ 이며, 초기 정렬을 포함하여 전체 $O(M \log M)$ 이다.

공간 복잡도는 트리 구조를 저장하기 위해 $O(M)$ 이다.

5. $D$ -진 허프만 부호화

이진 부호 대신 $D$ -진 알파벳( $D \geq 2$ )을 사용하는 경우, 알고리즘을 일반화할 수 있다. 각 반복에서 가중치가 가장 작은 $D$ 개의 노드를 병합하여 하나의 내부 노드를 생성한다.

이때 주의할 점은, 최종 트리의 내부 노드가 모두 정확히 $D$ 개의 자식을 가져야 한다는 것이다. $M$ 개의 기호에 대하여, $(M - 1)$ 이 $(D - 1)$ 로 나누어떨어지지 않으면, 첫 번째 반복에서 $D$ 개가 아닌 $((M - 1) \mod (D - 1)) + 1$ 개의 노드를 병합한다. 이는 다음 조건을 만족시키기 위한 것이다:

$M' = M - ((M-1) \bmod (D-1))$

개의 노드가 남은 후부터는 매 반복마다 정확히 $D$ 개씩 병합이 가능하다. 또는 동등하게, 확률 $0$ 인 가상 기호(dummy symbol)를 추가하여 $(M - 1)$ 이 $(D - 1)$ 의 배수가 되도록 조정할 수 있다.

6. 허프만 부호의 비유일성

허프만 알고리즘에서 최소 가중치 노드의 선택에 동률(tie)이 발생할 수 있으며, 이 경우 서로 다른 허프만 트리가 구성될 수 있다. 그러나 모든 허프만 트리는 동일한 평균 부호어 길이를 갖는다. 즉, 허프만 부호는 유일하지 않을 수 있으나, 그 최적 평균 부호어 길이는 유일하게 결정된다.

동률 처리 방법에 따라 부호어 길이의 분산(variance)이 달라질 수 있다. 실용적으로는, 동률이 발생할 때 깊이가 더 작은(즉, 더 최근에 병합된) 노드를 우선 선택하면 최대 부호어 길이를 최소화하는 효과가 있다. 이는 버퍼 크기 제한이 있는 실시간 시스템에서 중요한 고려사항이다.