8.13 허프만 부호의 최적성 증명

1. 최적성 정리의 진술

정리 (허프만 부호의 최적성). 이산 무기억 정보원 $X$ 가 알파벳 $\mathcal{X} = \{x_1, x_2, \dots, x_M\}$ 위에서 확률 분포 $\{p_1, p_2, \dots, p_M\}$ , $p_i > 0$ 으로 정의되어 있을 때, 허프만 알고리즘이 생성하는 접두사 부호 $C^*$ 는 모든 접두사 부호 중에서 평균 부호어 길이를 최소화한다. 즉, 임의의 접두사 부호 $C$ 에 대하여

$L(C^*) \leq L(C)$

가 성립한다.

크래프트-맥밀런 정리에 의하여 고유 복호 가능 부호와 접두사 부호의 부호어 길이 집합이 동일하므로, 이 정리는 허프만 부호가 모든 고유 복호 가능 부호 중에서도 최적임을 함축한다.

2. 증명을 위한 보조 정리

최적성 증명은 수학적 귀납법에 기반하며, 다음의 보조 정리들이 필요하다.

2.1 보조 정리 1: 최적 부호의 부호어 길이 순서

보조 정리 1. $p_i > p_j$ 이면 최적 접두사 부호에서 $l_i \leq l_j$ 이다.

증명. 귀류법을 적용한다. $p_i > p_j$ 이면서 $l_i > l_j$ 인 최적 부호 $C$ 가 존재한다고 가정하자. $x_i$ 와 $x_j$ 의 부호어를 교환한 부호 $C'$ 을 구성하면,

$L(C') - L(C) = p_i l_j + p_j l_i - p_i l_i - p_j l_j = (p_i - p_j)(l_j - l_i) < 0$

이므로 $L(C') < L(C)$ 이다. 이는 $C$ 의 최적성에 모순된다. $\blacksquare$

2.2 보조 정리 2: 최적 부호에서 최장 부호어의 형제 존재

보조 정리 2. 최적 접두사 부호에서, 최대 길이의 부호어 중 적어도 두 개는 마지막 비트만 다른 형제 관계(sibling)에 있다.

증명. 최적 부호의 이진 트리에서 최대 깊이에 위치하는 잎 노드를 하나 골라 $c_j$ 라 하자. $c_j$ 의 형제 노드가 존재하지 않거나 잎 노드가 아니라면, $c_j$ 의 마지막 비트를 제거하여 한 단계 위의 부모 노드를 $c_j$ 의 새 부호어로 대체할 수 있다. 부모 노드에 다른 후손 잎 노드가 없으므로 접두사 조건은 유지되며, $l_j$ 가 1 감소하여 평균 부호어 길이가 감소한다. 이는 최적성에 모순이다.

따라서 최대 깊이의 잎 노드에는 반드시 형제 잎 노드가 존재한다. $\blacksquare$

2.3 보조 정리 3: 최소 확률 기호의 최장 부호어 배치

보조 정리 3. 확률이 가장 작은 두 기호 $x_a$ 와 $x_b$ ( $p_a \leq p_b \leq p_k$ , $\forall k \neq a, b$ )를 최대 길이의 형제 부호어에 대응시키는 최적 접두사 부호가 존재한다.

증명. 보조 정리 2에 의하여 최적 부호에는 최대 깊이에서 형제 관계인 두 잎 노드가 있다. 보조 정리 1에 의하여, 확률이 가장 작은 두 기호가 가장 긴 부호어를 가져야 한다. 만약 최대 깊이의 형제 위치에 $x_a$ 와 $x_b$ 가 아닌 다른 기호가 배치되어 있다면, 부호어를 교환하면 평균 부호어 길이가 감소하거나 같으므로, 교환 후에도 최적성이 유지된다. $\blacksquare$

3. 최적성의 귀납적 증명

기저 단계: $M = 2$ 인 경우, 유일한 접두사 부호는 $c_1 = 0$ , $c_2 = 1$ 이며, 허프만 알고리즘이 이 부호를 생성한다. 따라서 최적이다.

귀납 단계: $M - 1$ 개의 기호에 대하여 허프만 부호가 최적이라고 가정하자. $M$ 개의 기호에 대하여 최적임을 보인다.

확률의 비증가 순서로 $p_1 \geq p_2 \geq \cdots \geq p_M$ 이라 하자. 허프만 알고리즘의 첫 단계에서 확률이 가장 작은 두 기호 $x_{M-1}$ 과 $x_M$ 을 병합하여 새 기호 $x'$ 를 생성하며, $p' = p_{M-1} + p_M$ 으로 설정한다. 이는 $M - 1$ 개의 기호 $\{x_1, \dots, x_{M-2}, x'\}$ 에 대한 축소된 문제를 정의한다.

귀납 가정에 의하여, 축소된 문제에 대한 허프만 부호 $C'$ 은 $M - 1$ 개의 기호에 대하여 최적이다. 원래의 $M$ -기호 허프만 부호 $C^*$ 에서, $x_{M-1}$ 과 $x_M$ 의 부호어는 $x'$ 의 부호어에 각각 $0$ 과 $1$ 을 추가한 것이다. 따라서,

$L(C^*) = L(C') + p_{M-1} + p_M = L(C') + p'$

이제 $C^*$ 가 최적임을 증명한다. $C$ 를 $M$ 개의 기호에 대한 임의의 최적 접두사 부호라 하자. 보조 정리 3에 의하여, $x_{M-1}$ 과 $x_M$ 이 형제 관계에 배치된 최적 부호가 존재한다. 이 부호에서 $x_{M-1}$ 과 $x_M$ 을 합쳐 $x'$ 로 대체하면, $M - 1$ 개 기호에 대한 접두사 부호 $\tilde{C}$ 를 얻으며,

$L(C) = L(\tilde{C}) + p'$

이다. $C'$ 이 $M - 1$ 개 기호에 대하여 최적이므로 $L(C') \leq L(\tilde{C})$ 이다. 따라서,

$L(C^*) = L(C') + p' \leq L(\tilde{C}) + p' = L(C)$

임의의 최적 부호 $C$ 에 대하여 $L(C^*) \leq L(C)$ 이므로, 허프만 부호 $C^*$ 는 최적이다. $\blacksquare$

4. 허프만 부호의 성능 한계

허프만 부호가 최적 접두사 부호임에도 불구하고, 그 평균 부호어 길이에 대하여 다음의 범위가 성립한다:

$H(X) \leq L(C^*) < H(X) + 1$

하한은 섀넌의 하한 정리에서, 상한은 섀넌 부호가 이 범위 내에 있고 허프만 부호가 이보다 크지 않다는 사실에서 도출된다. 보다 정밀한 상한으로, Gallager(1978)는 다음을 증명하였다:

$L(C^*) < H(X) + p_{\max} + \frac{1}{M}$

여기서 $p_{\max} = \max_i p_i$ 이다. 또한 $p_{\max} \leq 0.5$ 이면,

$L(C^*) < H(X) + p_{\max}$

이 성립한다.

5. 최적성의 범위와 한계

허프만 부호의 최적성은 단일 기호(symbol-by-symbol) 접두사 부호 중에서의 최적성이다. 블록 부호화(여러 기호를 묶어 부호화)나 산술 부호화(arithmetic coding)와 같은 방법은 허프만 부호보다 더 짧은 기호 당 평균 비트 수를 달성할 수 있다.

블록 길이 $n$ 의 허프만 부호는 기호 당 평균 비트 수가 $H(X) + 1/n$ 미만이 되므로, $n \to \infty$ 일 때 엔트로피에 수렴한다. 그러나 블록 허프만 부호화는 알파벳 크기가 $M^n$ 으로 지수적으로 증가하여 실용적으로 제한이 있으며, 이 한계를 극복하기 위해 산술 부호화, 적응적 허프만 부호화 등의 기법이 발전하였다.