허프만 부호화

소프트웨어 통계 마지막 수정: 2026-09-02 04:13:28

1. 개요[편집]

허프만 부호화 Huffman Coding
고안	David A. Huffman, 1952 (MIT 대학원 기말 과제)
정체	주어진 확률분포에 최적인 접두 부호
구성	최소 확률 둘을 합치는 그리디 병합, $O(m\log m)$
성능	$H \le L < H+1$ — 기호당 정수 비트의 대가
약점	한 기호 확률이 클 때. $p=0.9$ 면 6배 낭비
실무	DEFLATE(PNG·gzip·zip) · JPEG · bzip2 · zstd 리터럴

자주 나오는 놈에게 짧은 이름을 준다 — 까지는 누구나 안다. 허프만의 공은 그걸 어떻게 하면 최적인지를 증명한 것이다.

허프만 부호화(Huffman coding)는 각 기호의 확률이 주어졌을 때 평균 부호 길이를 최소로 만드는 접두 부호를, 확률이 가장 작은 두 기호를 반복해서 병합하는 상향식 그리디 절차로 구성하는 알고리즘이다. 1952년 데이비드 허프만이 로버트 파노의 수업 기말 과제로 만들었고,¹ 70년이 지난 지금도 PNG를 열 때마다, JPEG을 디코딩할 때마다 CPU 안에서 돌고 있다.

이 문서는 허프만 부호 자체를 다룬다. 압축 파이프라인에서 이놈이 어디에 앉는지, 산술 부호화·ANS가 어떻게 그 자리를 뺏어 갔는지는 엔트로피 부호화가 이미 정리해 두었으니 그쪽을 먼저 보는 것도 좋다.

2. 접두 부호와 크래프트 부등식[편집]

부호 $C$ 가 접두 부호(prefix code, prefix-free code)라는 것은 어떤 부호어도 다른 부호어의 접두사가 아니라는 뜻이다. 이 성질 덕분에 구분자 없이 붙여 보낸 비트열을 왼쪽부터 읽어 나가다 부호어가 완성되는 순간 바로 끊어 읽을 수 있다 — 순간 복호 가능(instantaneous). 이진 접두 부호는 곧 잎에만 기호가 붙은 이진 트리와 같고, 부호어는 루트에서 잎까지의 좌/우 경로, 부호 길이 $\ell(x)$ 는 잎의 깊이다.

길이 집합 $\{\ell(x)\}$ 가 실제로 어떤 접두 부호로 실현될 수 있는지는 크래프트 부등식이 판정한다.

\sum_{x \in \mathcal{X}} 2^{-\ell(x)} \;\le\; 1

트리로 보면 자명하다. 깊이 $\ell$ 인 잎 하나는 깊이 $L_{\max}$ 의 완전 이진 트리에서 $2^{L_{\max}-\ell}$ 개의 자리를 차지하고, 그 자리들이 서로 겹치지 않으므로 전체 $2^{L_{\max}}$ 을 넘을 수 없다. 등호는 트리에 놀고 있는 잎이 하나도 없을 때(완전 이진 트리) 성립하며, 허프만 트리는 항상 이 경우다.² 맥밀런(1956)이 “유일 복호 가능하기만 하면 접두 부호가 아니어도 같은 부등식이 성립한다”를 보였으므로, 접두 부호를 고집해서 잃는 것은 없다.

3. 그리디 병합 — 알고리즘[편집]

$m$ 개 기호와 확률 $p_1,\dots,p_m$ 이 주어졌을 때:

각 기호를 무게 p_i 의 단일 노드로 만들어 우선순위 큐에 넣는다
while 큐에 노드가 2개 이상:
    무게가 가장 작은 노드 두 개 a, b 를 꺼낸다
    무게 (w_a + w_b) 의 새 내부 노드를 만들어 a, b 를 자식으로 붙인다
    새 노드를 큐에 넣는다
남은 하나가 루트. 왼쪽 간선=0, 오른쪽 간선=1 로 읽으면 부호어

병합이 정확히 $m-1$ 번 일어나고, 우선순위 큐를 이진 힙으로 두면 $O(m \log m)$ 이다. 확률이 이미 정렬되어 있다면 $O(m)$ 으로 떨어진다 — 정렬된 원본 큐 하나와 새로 만든 내부 노드 큐 하나를 두면, 내부 노드는 만들어지는 순서 그대로 무게가 비감소하므로 두 큐의 앞머리만 비교하면 되기 때문이다(van Leeuwen, 1976). 힙도 정렬도 없이 큐 두 개로 끝난다는 점이 은근히 예쁘다.

주의할 것 하나. 허프만 트리는 유일하지 않다. 동점인 무게를 어느 쪽에서 꺼내느냐, 자식을 좌우 어디에 붙이느냐에 따라 다른 부호가 나오고, 심지어 길이 다중집합 자체가 달라질 수도 있다(예: $\{0.4, 0.2, 0.2, 0.1, 0.1\}$ ). 평균 길이는 어느 쪽이든 같지만, 부호기와 복호기가 서로 다른 규칙으로 트리를 지으면 그 순간 파일이 깨진다. 실무에서 정준 허프만이 사실상 강제되는 첫 번째 이유가 이것이다.

지프 분포 p_i ∝ i^−s 위에서 이진 최소힙 우선순위 큐로 실제 허프만 트리를 지어 부호길이를 트리 깊이에서 읽는다. 균등 8심볼에서는 L = H = 3 비트로 잉여가 정확히 0이고, 치우침 s 를 12까지 올리면 H = 0.0033 인데 L = 1.0002 라 잉여가 상한 1비트의 0.9969 까지 붙는다.

4. 왜 최적인가[편집]

증명의 뼈대는 교환 논증이고, 그리디 알고리즘이 최적해를 주는 교과서 사례로 늘 인용된다. 두 보조정리로 나뉜다.

보조정리 1(형제 정리). 확률이 가장 작은 두 기호 $x, y$ 에 대해, 이 둘이 최대 깊이에서 형제인 최적 접두 부호가 존재한다.

근거. 최적 부호의 트리에서 가장 깊은 잎은 반드시 형제를 갖는다(형제가 없으면 그 잎을 부모 자리로 끌어올려 길이를 1 줄일 수 있으니 최적이 아니다). 그 형제 쌍을 $a, b$ 라 하고 $p_a \ge p_x$ , $p_b \ge p_y$ 라 하자. $x \leftrightarrow a$ 를 맞바꾸면 평균 길이 변화는 $(p_a - p_x)(\ell_x - \ell_a) \le 0$ — 확률이 큰 놈이 더 얕은 자리로 갔으니 결코 나빠지지 않는다. $y \leftrightarrow b$ 도 마찬가지. 최적이었으므로 변화는 정확히 0이고, 교환 후에도 최적이다. $\square$

보조정리 2(축약). $x, y$ 를 합쳐 확률 $p_x + p_y$ 인 가상 기호 $z$ 로 대체한 축약 문제를 생각하자. 원 문제의 트리에서 $x,y$ 가 형제라면 두 문제의 평균 길이는

L \;=\; L' + (p_x + p_y)

라는 관계로 묶인다( $z$ 의 깊이를 $\ell_z$ 라 하면 $x,y$ 의 깊이는 $\ell_z+1$ 이므로 차이가 정확히 $p_x+p_y$ ). 이 항은 트리 모양과 무관한 상수다. 따라서 $L$ 을 최소화하는 것과 $L'$ 을 최소화하는 것이 완전히 같은 문제가 되고, 기호 수에 대한 귀납으로 알고리즘의 최적성이 따라온다. $\square$

즉 허프만의 그리디가 통하는 이유는 “가장 작은 둘을 합쳐도 손해가 없다”(보조정리 1)와 “합치고 나면 같은 종류의 더 작은 문제”(보조정리 2)가 동시에 성립하기 때문이다. 이 둘이 각각 그리디의 교환 논증과 최적 부분구조에 대응한다.³

5. 정수 비트의 대가[편집]

크래프트 부등식 아래 $L = \sum p_i \ell_i$ 를 실수 길이로 최소화하면 $\ell_i^* = -\log_2 p_i$ 에서 $L^* = H$ 가 나온다. 허프만은 이 실수해를 정수로 반올림해야 하는 최적화를 푸는 셈이고, 그 대가가 딱 이만큼이다.

H(X) \;\le\; L_{\text{Huffman}} \;<\; H(X) + 1

상한은 $\ell_i = \lceil -\log_2 p_i \rceil$ 라는 (허프만이 아닌) 섀넌 부호가 크래프트 부등식을 만족한다는 것에서 나온다 — 이 부호의 평균 길이가 이미 $H+1$ 미만인데, 허프만은 그보다 나쁠 수 없다. 하한은 물론 섀넌의 소스 부호화 정리다.

$+1$ 은 최악의 경우이고 실제 손해는 최대 확률 $p_{\max}$ 가 지배한다. 갤러거(1978)의 더 날카로운 상한은 $p_{\max} < 0.5$ 일 때 $L - H < p_{\max} + 0.086$ 이다. 결론은 명확하다.

분포가 평평하면 허프만은 거의 최적이다. 균등분포이고 $m$ 이 2의 거듭제곱이면 손해가 정확히 0이다.
한 기호가 지배적이면 처참하다. $p = 0.9$ 인 이진 소스의 엔트로피는 $0.469$ 비트인데 허프만은 기호당 1비트를 준다. $p=0.99$ 면 $H = 0.081$ 비트에 1비트, 12배 낭비다. 애초에 이진 알파벳에서 허프만은 할 수 있는 일이 없다 — 부호어가 0과 1뿐이다.

우회로는 결국 하나, 기호를 묶어 알파벳을 키우는 것이다. $n$ 개씩 묶으면 낭비가 $1/n$ 로 줄지만 표 크기가 $m^n$ 으로 터진다. JPEG의 (런길이, 크기) 쌍이나 bzip2의 MTF+RLE처럼 앞단에서 미리 접어 주는 것도 사실 같은 트릭의 실용판이다. 근본적인 해결은 기호당 분수 비트를 허용하는 산술 부호화와 ANS 쪽에 있고, 그 이야기는 엔트로피 부호화가 다룬다. 이진 결정을 쏟아내는 현대 비디오 코덱이 CABAC으로 갈아탄 이유가 정확히 위의 12배다.

6. 정준 허프만 — 표를 보내지 않는 법[편집]

비적응형 허프만은 부호표를 헤더에 실어야 한다. 알파벳 256개짜리 트리를 그대로 직렬화하면 수백 바이트고, 짧은 파일에서는 배보다 배꼽이 크다.

정준 허프만(canonical Huffman)은 여기에 규칙을 하나 강제한다. 부호어를 (길이 오름차순, 같은 길이 안에서는 기호 인덱스 오름차순)으로 나열하고, 첫 부호어를 0으로 시작해 하나씩 증가시키되 길이가 1 늘어날 때마다 왼쪽 시프트한다.

기호	길이	정준 부호어
A	2	00
B	2	01
C	3	100
D	3	101
E	3	110

이러면 부호어 길이 배열만 보내도 표가 유일하게 복원된다. 트리도, 부호어 비트열도 보낼 필요가 없다. DEFLATE는 여기서 한 발 더 나가, 길이 배열 자체를 런길이로 접은 뒤 또 허프만으로 압축해서 보낸다(길이-부호 알파벳 19개). 덤으로 복호도 빨라진다 — 길이별 첫 부호어와 첫 인덱스만 있으면 비트를 하나씩 밀어 넣으며 산술 비교로 기호를 찾을 수 있고, 상위 $k$ 비트를 인덱스로 쓰는 조회표를 구우면 대부분의 기호가 메모리 참조 한 번에 복호된다. 허프만이 아직 죽지 않은 이유는 압축률이 아니라 이 속도다.

부호 길이 제한도 실무 필수다. 확률이 극단적으로 치우치면 트리가 피보나치 수열처럼 자라 부호어가 수십 비트가 되는데, 그러면 복호 조회표가 감당이 안 된다. DEFLATE는 15비트, JPEG은 16비트로 상한을 둔다.⁴ 상한을 지키면서 평균 길이를 최소화하는 문제는 패키지-병합 알고리즘(Larmore & Hirschberg, 1990)으로 $O(mL)$ 에 정확히 풀리지만, 실무에서는 트리를 지은 뒤 넘치는 잎을 끌어올리고 크래프트 예산을 다른 잎에서 갚는 근사 보정으로 때우는 경우가 더 많다.

7. 실제로 어디서 도는가[편집]

DEFLATE(RFC 1951 — PNG, gzip, zip). LZ77 사전 매칭이 만든 리터럴/길이·거리 스트림을 두 개의 정준 허프만 표로 부호화한다. 리터럴/길이 알파벳 286개, 거리 알파벳 30개. 블록마다 “저장(무압축) / 고정 표 / 동적 표” 중 하나를 고르는데, 고정 표는 표 전송 비용이 0이라 작은 블록에서 이기고, 동적 표는 데이터에 맞춘 대신 헤더를 문다. 인코더가 매 블록 둘 다 계산해 보고 짧은 쪽을 고르는 것이 표준이다.
JPEG 베이스라인. DC 계수는 이전 블록과의 차분을 크기 범주(0~11)로 나눠 그 범주만 허프만으로 보내고 실제 값은 범주가 지정한 비트 수만큼 원시 비트로 붙인다. AC 계수는 (앞선 0의 런길이, 크기 범주) 쌍을 한 바이트로 묶어 허프만한다. 즉 허프만이 부호화하는 것은 계수 값이 아니라 값의 크기 등급이고, 이 2단 구조가 알파벳을 256개 이하로 묶어 준다. 베이스라인은 표를 최대 4개(DC 2, AC 2)까지 쓸 수 있다. 표준의 부호 생성 절차는 전부 1인 부호어를 금지하는데, 마커 검출과의 충돌을 피하기 위한 장치다.
bzip2. BWT + MTF + RLE 뒤에 허프만이 앉는데, 표를 최대 6개까지 두고 50기호 단위로 표를 전환한다. 국소적으로 통계가 바뀌는 데이터를 정적 허프만으로 따라가려는 타협.
Zstandard. 리터럴은 허프만, 시퀀스(길이·거리·매치)는 FSE(tANS)를 쓴다. 21세기 코덱이 허프만을 완전히 버리지 않은 이유가 여기 보인다 — 리터럴처럼 분포가 비교적 평평한 스트림에서는 허프만의 손해가 미미하고 복호가 더 빠르다.
골룸-라이스 부호는 기하분포에 대한 허프만 부호를 파라미터 하나로 즉석 생성하는 특수 케이스다. 표도 트리도 없이 시프트와 비교만으로 만들어지므로 FLAC·JPEG-LS 같은 하드웨어 친화 코덱이 애용한다.

8. 적응형 허프만[편집]

파일을 두 번 훑을 수 없거나(스트리밍) 표를 보낼 여유가 없을 때, 부호기와 복호기가 지금까지 본 기호의 빈도로 트리를 함께 갱신하는 방식이 적응형 허프만이다. 핵심 도구는 갤러거의 형제 성질(sibling property) — 모든 노드를 무게 비내림차순으로 나열했을 때 형제가 이웃해 있으면, 그 트리가 곧 허프만 트리라는 판정 조건이다. 기호 하나의 무게를 1 올릴 때, 같은 무게를 가진 노드 중 나열 순서상 가장 앞선 것과 자리를 바꿔 준 뒤 부모로 올라가며 반복하면 형제 성질이 유지된다. 트리를 통째로 다시 짓지 않고 경로 하나만 손보면 되므로 기호당 $O(\ell)$ 이다.

FGK(Faller 1973, Gallager 1978, Knuth 1985). 위 절차의 원형. 아직 안 나온 기호는 NYT(not yet transmitted) 잎 하나로 대표하고, 새 기호가 나오면 그 잎을 쪼갠다.
비터 알고리즘(Vitter, 1987). 갱신 규칙을 다듬어 부호 길이 합에 대한 더 강한 보장을 얻는다. 같은 입력에서 FGK보다 트리가 얌전하다.

그럼에도 적응은 산술 부호화나 ANS 쪽이 훨씬 편하다. 저쪽은 빈도 카운터 하나만 올리면 끝인데 이쪽은 트리를 재배치해야 하기 때문이다. 그래서 적응형 허프만은 교과서에서는 유명하지만 현대 코덱에서는 보기 드물다.

9. 알아 두면 좋은 사촌들[편집]

섀넌-파노 부호. 확률을 정렬해 위에서 아래로 절반씩 쪼개는 하향식 방법. 파노 본인의 것이고, 최적이 아니다. 허프만이 상향식으로 뒤집은 것이 결정적 차이였다.
Hu-Tucker 알고리즘. 기호의 원래 순서를 유지하는 최적 접두 부호(알파벳 부호)를 $O(m \log m)$ 에 구한다. 순서 제약이 붙으면 형제 정리가 깨져 허프만을 그대로 쓸 수 없다.
최적 이진 탐색 트리. 겉보기에 비슷하지만 내부 노드에도 기호가 앉으므로 그리디가 통하지 않고, 동적 계획법( $O(m^3)$ , 크누스 최적화로 $O(m^2)$ )이 필요하다. 어디까지 그리디가 통하는지의 경계를 보여주는 대조군으로 좋다.

10. 관련 문서[편집]

파노가 “최적 부호를 증명하거나 기말고사를 보거나 골라라”라고 했고, 허프만은 몇 달을 헤매다 포기하고 노트를 버리려는 순간 아이디어가 떠올랐다고 회고했다. 논문은 Huffman, D. A. (1952). “A Method for the Construction of Minimum-Redundancy Codes”. Proceedings of the IRE 40(9), 1098–1101. 참고로 그가 갈아엎은 섀넌-파노 부호의 공저자가 바로 채점자였다. 기말고사를 피하려다 지도교수 방법을 폐기시킨 셈. ↩
놀고 있는 잎이 있으면 그 형제를 부모 자리로 끌어올려 길이를 1 줄일 수 있으니 최적일 리가 없다. 그래서 허프만 트리에는 자식이 하나뿐인 내부 노드가 절대 없다. 코드 리뷰에서 if (node->left && !node->right) 같은 분기를 보면 그 사람은 트리를 잘못 짓고 있는 것이다. ↩
“허프만이 최적인데 왜 더 나은 압축기가 있느냐”는 질문이 매년 반복된다. 최적성의 단서는 「독립 기호를 하나씩, 알려진 고정 분포로, 접두 부호로」 부호화한다는 세 조건 안에서다. 실제 압축기는 이 세 조건을 전부 깨고 이긴다 — 문맥으로 분포를 바꾸고, 기호를 묶고, 분수 비트를 쓴다. 정리의 가정을 읽지 않고 결론만 외우면 이런 일이 생긴다. ↩
DEFLATE의 15비트 상한 덕분에 zlib 복호 조회표는 1차 9비트 + 2차 테이블 구조로 캐시에 얌전히 들어간다. 반대로 상한이 없었다면 병적인 입력 하나로 수 MB짜리 표를 요구하는 서비스 거부 공격이 가능했을 것이다. 부호 길이 제한은 압축률 규격이 아니라 보안 규격에 가깝다. ↩