8.14 적응적 허프만 부호화(Adaptive Huffman Coding)의 원리

1. 정적 허프만 부호화의 한계

표준 허프만 부호화(static Huffman coding)는 정보원의 확률 분포가 사전에 알려져 있어야 하며, 부호화에 앞서 전체 데이터를 두 번 스캔해야 한다. 첫 번째 스캔에서 각 기호의 빈도를 수집하고, 두 번째 스캔에서 구성된 허프만 부호를 이용하여 실제 부호화를 수행한다. 또한 복호기가 동일한 부호 테이블을 보유하도록 부호 테이블 자체를 부호화 데이터에 포함시켜야 하므로, 부가 비용(overhead)이 발생한다.

이러한 한계를 극복하기 위하여 적응적 허프만 부호화(adaptive Huffman coding) 또는 **동적 허프만 부호화(dynamic Huffman coding)**가 개발되었다. 적응적 허프만 부호화에서는 부호화기와 복호화기가 동일한 초기 상태에서 출발하여, 각 기호를 처리할 때마다 허프만 트리를 점진적으로 갱신한다. 이로써 사전 확률 분포 없이 단일 패스(single pass)로 부호화가 가능하며, 별도의 부호 테이블 전송이 불필요하다.

2. 적응적 허프만 부호화의 기본 원리

적응적 허프만 부호화의 핵심은 다음의 세 단계를 각 기호에 대하여 반복하는 것이다:

부호화/복호화: 현재의 허프만 트리를 사용하여 기호를 부호화(또는 복호화)한다.
빈도 갱신: 해당 기호의 빈도 카운터를 1 증가시킨다.
트리 갱신: 갱신된 빈도를 반영하여 허프만 트리를 재구성한다.

부호화기와 복호화기가 동일한 순서로 동일한 갱신 절차를 수행하므로, 양측의 허프만 트리는 항상 동기화된 상태를 유지한다.

3. 형제 성질(Sibling Property)

효율적인 트리 갱신의 이론적 기반은 **형제 성질(sibling property)**이다.

정의. 이진 트리의 노드에 가중치(빈도)가 부여되어 있을 때, 이 트리가 형제 성질을 만족한다 함은, 노드들을 가중치의 비감소 순서로 나열할 수 있되, 이 나열에서 인접한 쌍이 형제 관계에 있도록 할 수 있는 것이다.

정리 (Gallager, 1978). 이진 트리가 주어진 잎 노드 빈도에 대한 허프만 트리일 필요충분조건은 형제 성질을 만족하는 것이다.

이 정리는 적응적 허프만 부호화의 트리 갱신 절차가 형제 성질을 유지하도록 설계되어야 함을 시사한다.

4. FGK 알고리즘

Faller(1973), Gallager(1978), Knuth(1985)에 의해 각각 독립적으로 발전된 FGK 알고리즘은 적응적 허프만 부호화의 초기 형태이다.

4.1 노드 번호 부여

트리의 모든 노드에 번호를 부여한다. 번호 부여는 암묵적 번호(implicit numbering) 또는 **너비 우선 역순 번호(reverse breadth-first numbering)**를 사용한다. 잎 노드와 내부 노드를 모두 포함하여 가중치의 비감소 순서로 번호를 매기되, 같은 가중치의 노드 중 트리의 하단(높은 깊이)에 위치한 노드에 작은 번호를 부여한다.

4.2 트리 갱신 절차

기호 $x$ 가 입력되었을 때의 갱신 절차는 다음과 같다:

$x$ 에 대응하는 잎 노드 $v$ 를 찾는다.
$v$ 와 동일한 가중치를 갖는 노드 중 가장 큰 번호를 가진 노드 $u$ 를 찾는다.
$u \neq v$ 이고 $u$ 가 $v$ 의 조상이 아니면, $v$ 와 $u$ 를 교환(swap)한다.
$v$ 의 가중치를 1 증가시킨다.
$v$ 가 근이 아니면, $v$ 의 부모 노드에 대하여 단계 2-5를 반복한다.

이 교환 과정은 형제 성질을 유지하면서 가중치를 갱신하는 것으로, 각 갱신의 시간 복잡도는 트리의 높이에 비례하여 $O(l_{\max})$ 이다.

4.3 새 기호의 처리

아직 한 번도 출현하지 않은 기호가 입력된 경우, 특수 기호인 NYT(Not Yet Transmitted) 노드를 이용한다. NYT 노드는 가중치 $0$ 의 잎 노드로서, 아직 나타나지 않은 모든 기호를 대표한다. 새 기호가 나타나면:

NYT 노드의 부호어를 전송하고, 그 뒤에 새 기호의 고정 길이 이진 표현을 전송한다.
현재의 NYT 노드를 내부 노드로 변환하고, 두 자식으로 새 NYT 노드와 새 기호의 잎 노드를 생성한다.
새 기호의 잎 노드 가중치를 1로 설정하고, 부모 노드부터 갱신 절차를 수행한다.

5. Vitter 알고리즘

Vitter(1987)는 FGK 알고리즘을 개선하여, 각 시점에서의 적응적 부호가 정적 최적 허프만 부호에 더 가까운 성능을 보이도록 하였다. Vitter 알고리즘의 핵심 개선은 노드 교환 규칙의 정교화에 있다.

FGK 알고리즘에서는 가중치를 먼저 증가시킨 후 교환 여부를 판단하지만, Vitter 알고리즘에서는 교환을 먼저 수행한 후 가중치를 증가시킨다. 또한 노드 번호 부여 규칙에서, 동일 가중치의 잎 노드가 동일 가중치의 내부 노드보다 큰 번호를 갖도록 강제한다. 이를 통해 트리의 높이가 최소화되고, 결과적으로 평균 부호어 길이가 개선된다.

정리 (Vitter, 1987). Vitter 알고리즘에 의한 적응적 허프만 부호의 총 부호어 길이와, 각 시점의 빈도에 기반한 정적 최적 허프만 부호의 총 부호어 길이의 차이는 최대 $t - 1$ 이다. 여기서 $t$ 는 전송된 기호의 총 수이다. 즉, 기호 당 추가 비용이 최대 1비트 미만이다.

6. 적응적 허프만 부호화의 복잡도

적응적 허프만 부호화의 시간 및 공간 복잡도는 다음과 같다:

항목	FGK 알고리즘	Vitter 알고리즘
기호 당 시간	$O(l_{\max})$	$O(l_{\max})$
총 시간 ( $t$ 개 기호)	$O(t \cdot l_{\max})$	$O(t \cdot l_{\max})$
공간	$O(M)$	$O(M)$

여기서 $l_{\max}$ 는 현재 트리의 최대 깊이이며, 최악의 경우 $O(M)$ 이지만, 실제로는 $O(\log M)$ 에 가까운 경우가 많다.

7. 적응적 허프만 부호화의 실용적 의의

적응적 허프만 부호화는 다음과 같은 실용적 장점을 갖는다:

단일 패스 처리: 데이터를 한 번만 스캔하면 되므로, 스트리밍 환경이나 실시간 통신에 적합하다.

부호 테이블 전송 불필요: 부호화기와 복호화기가 동일한 갱신 절차를 공유하므로, 별도의 부호 테이블을 전송할 필요가 없다.

비정상 정보원에의 적응: 정보원의 통계적 특성이 시간에 따라 변화하는 경우, 적응적 방법은 최근의 빈도를 반영하여 부호를 갱신하므로 성능 저하가 완화된다. 오래된 빈도의 영향을 줄이기 위하여 윈도우 기법(sliding window) 또는 **가중치 감쇠(weight decay)**를 적용할 수 있다.

이러한 특성으로 인해 적응적 허프만 부호화는 UNIX compress 유틸리티, 일부 통신 프로토콜 등에서 실제로 사용되었다. 그러나 현대의 데이터 압축에서는 산술 부호화(arithmetic coding)나 ANS(Asymmetric Numeral Systems) 등 더 높은 압축 효율을 제공하는 방법이 주로 사용되며, 적응적 허프만 부호화는 구현의 단순성이 요구되는 제한된 환경에서 여전히 활용되고 있다.