Huffman 코딩 원리: 압축 알고리즘의 핵심 상세 설명

결론 먼저: Huffman 코딩은 최적의 접두사 가변 길이 코딩 방식이며, 핵심 사상은 "고빈도 문자는 짧은 코드, 저빈도 문자는 긴 코드"입니다. 허프만 트리를 구성하여 코드표를 생성하고 전체 코드 길이를 최소화합니다. "ABRACADABRA"라는 11개 문자 예시에서, 고정 길이 코딩은 33 bit가 필요하지만 Huffman 코딩은 23 bit만 필요하여 30%를 절약합니다. Huffman 코딩은 DEFLATE(ZIP/GZIP/PNG) 등 주류 압축 형식의 핵심 구성 요소로, 거의 모든 무손실 압축 알고리즘에 이 단계가 포함됩니다. 아래에서는 빈도 통계부터 시작하여 허프만 트리 구성과 코드 생성 과정을 점차 설명합니다.

무손실 압축과 손실 압축의 차이에 익숙하지 않다면, 먼저 무손실 압축 vs 손실 압축: 핵심 차이을 읽어보시기 바랍니다.

1. 왜 가변 길이 코딩이 필요한가

컴퓨터가 문자를 저장할 때 보통 고정 길이 코딩을 사용합니다. 예: ASCII는 문자당 8 bit, Unicode는 문자당 16-32 bit. 고정 길이 코딩의 장점은 무작위 접근이 편리하다는 것이지만 낭비가 심합니다. 영어 텍스트에서 e의 출현 빈도는 약 12.7%인 반면 z는 0.07%에 불과하며, 두 문자에 동일한 길이의 코드를 사용하는 것은 명백히 비합리적입니다. 가변 길이 코딩은 문자 출현 빈도에 따라 다른 길이의 코드워드를 할당하며, 빈도가 높을수록 코드워드가 짧아져 전체 용량을 압축합니다.

코딩 방식	원리	코드워드 길이	디코딩 모호성	전형적 응용
고정 길이 코딩	각 문자 고정 N bit	고정	모호성 없음	ASCII, Unicode
가변 길이 코딩(비접두사)	빈도에 따라 다른 길이 할당	가변	모호성 가능	비실용적
Huffman 접두사 코딩	빈도 할당 + 접두사 코드 제약	가변	모호성 없음	DEFLATE, JPEG
산술 코딩	전체 메시지를 하나의 수에 매핑	분수 단위	모호성 없음	ZSTD, brotli

Huffman 코딩의 핵심 제약은 "접두사 코드"입니다. 즉, 어떤 문자의 코드도 다른 문자의 코드 접두사가 아닙니다. 예를 들어 문자 A의 코드가 "0"이라면, 다른 문자의 코드는 모두 "0"으로 시작할 수 없으며 "1"로만 시작할 수 있습니다. 이렇게 하면 디코딩 시 bit를 순차적으로 읽다가 완전한 코드워드를 만나면 즉시 디코딩되어 모호성이 발생하지 않습니다.

2. Huffman 코딩 원리 상세 설명

Huffman 코딩 생성은 세 단계로 나뉩니다: 빈도 통계, 허프만 트리 구성, 코드표 생성. 전체 과정은 그리디 알고리즘입니다. 매번 가장 낮은 빈도를 가진 두 노드를 선택하여 병합하고, 최종적으로 최적의 이진 트리를 형성합니다.

2.1 빈도 통계

첫 번째 단계는 입력 데이터에서 각 문자의 출현 빈도를 통계하는 것입니다. "ABRACADABRA"를 예로 들어, 먼저 각 문자의 출현 횟수를 통계합니다.

문자	출현 횟수	빈도(%)	고정 길이 코드(3bit)
A	5	45.5%	000
B	2	18.2%	001
R	2	18.2%	010
C	1	9.1%	011
D	1	9.1%	100

5종 문자에 대해, 고정 길이 코딩은 ceil(log2(5))=3 bit/문자가 필요하며, 11개 문자 합계 33 bit입니다. 참고로 ASCII 코딩에서는 11×8=88 bit가 필요한데, 고정 길이 3 bit로 이미 70%를 절약했지만 Huffman은 더 압축할 수 있습니다.

2.2 허프만 트리 구성

허프만 트리의 구성은 그리디 과정입니다: 매번 모든 노드에서 가장 낮은 빈도를 가진 두 개를 선택하여 새로운 노드로 병합하며, 새 노드의 빈도는 두 노드 빈도의 합입니다. 루트 노드 하나만 남을 때까지 반복합니다.

단계	작업	병합 전 가장 낮은 두 노드	병합 후 새 노드	남은 노드
1	C(1)와 D(1) 병합	C:1, D:1	CD:2	A:5, B:2, R:2, CD:2
2	B(2)와 R(2) 병합	B:2, R:2	BR:4	A:5, CD:2, BR:4
3	CD(2)와 BR(4) 병합	CD:2, BR:4	CDBR:6	A:5, CDBR:6
4	A(5)와 CDBR(6) 병합	A:5, CDBR:6	Root:11	완료

구성이 완료된 후, 루트 노드에서 출발하여 왼쪽 가지에 0, 오른쪽 가지에 1을 표시하고, 각 리프 노드까지의 경로가 해당 문자의 Huffman 코드입니다. 빈도가 가장 높은 A(5회)는 트리의 두 번째 레이어에 위치하여 코드가 단 1 bit이고, 빈도가 가장 낮은 C와 D는 가장 깊은 레이어에 위치하여 코드가 3 bit입니다.

2.3 코드표 생성

허프만 트리 루트 노드에서 각 리프 노드까지 탐색하고, 경로상의 0/1 시퀀스를 기록하면 코드표가 됩니다.

문자	빈도	Huffman 코드	코드 길이	코드 기여(bit)
A	5회	0	1	5×1=5
B	2회	100	3	2×3=6
R	2회	101	3	2×3=6
C	1회	110	3	1×3=3
D	1회	111	3	1×3=3

접두사 코드 특성 검증: A의 코드 "0"은 어떤 다른 코드의 접두사도 아니며, B"100", R"101", C"110", D"111"도 서로 접두사가 아닙니다. 디코딩 시 bit를 순차적으로 읽다가 "0"을 만나면 A이고, "1"을 만나면 두 bit를 더 읽어 B/R/C/D를 구분할 수 있어 모호성이 없습니다.

3. 실전 사례: "ABRACADABRA" 코딩 비교

이제 생성된 코드표를 사용하여 "ABRACADABRA"에 대한 완전한 코딩을 수행하고, 고정 길이 코딩과 Huffman 코딩의 용량 차이를 비교합니다.

원문: A B R A C A D A B R A(11개 문자)

코딩 과정:

위치	문자	Huffman 코드	누적 bit
1	A	0	1
2	B	100	4
3	R	101	7
4	A	0	8
5	C	110	11
6	A	0	12
7	D	111	15
8	A	0	16
9	B	100	19
10	R	101	22
11	A	0	23

코딩 효율 비교:

코딩 방식	문자당 bit	총 bit 수	총 바이트	ASCII 대비 압축률
ASCII 코딩	8	88	11	—(기준)
고정 길이 3bit 코딩	3	33	5	62.5%
Huffman 코딩	2.09(평균)	23	3	73.9%
이론적 엔트로피 하한	2.04	22.5	3	74.4%

결과: Huffman 코딩은 11개 문자를 ASCII의 88 bit에서 23 bit로 압축하여 73.9%를 절약했습니다. 고정 길이 3 bit 코딩과 비교해도 30%를 절약했습니다. 이론적 엔트로피 하한이 22.5 bit인 반면, Huffman 코딩은 이론적 최적보다 0.5 bit만 더 사용하여 효율 97.8%를 달성했습니다. 이것이 Huffman 코딩이 "최적 접두사 코드"로 불리는 이유입니다.

4. Huffman 코딩의 주류 압축 알고리즘 응용

Huffman 코딩은 단독으로 사용되는 경우가 드물며, 보통 압축 파이프라인의 마지막 단계인 엔트로피 코딩으로 사용됩니다. 먼저 LZ77 등의 사전 알고리즘으로 중복 패턴을 제거한 후, Huffman 코딩으로 잔차 데이터에 대해 빈도 압축을 수행합니다. 아래 표는 주류 압축 형식에서 Huffman의 응용 방식을 정리한 것입니다.

압축 형식	사전 단계	엔트로피 코딩 단계	Huffman 변형	전형적 압축률
DEFLATE (ZIP/GZIP)	LZ77	Huffman	정적+동적 Huffman	50%–70%
PNG	LZ77	Huffman	DEFLATE 내장 Huffman	50%–75%
JPEG	DCT 변환	Huffman	DC/AC 계수별 코딩	10:1(시각적 무손실)
ZSTD	LZ77 변형	FSE/Huffman	유한 상태 엔트로피+Huffman 혼합	60%–80%
brotli	LZ77+문맥	Huffman+산술	문맥 Huffman	65%–85%
BZIP2	BWT 변환	Huffman	다중 표 Huffman	70%–85%

LZ77 사전 압축의 상세 원리는 LZ77 알고리즘 상세 설명: 사전 압축은 어떻게 작동하는가?를 참조하시기 바랍니다. PNG 형식에서 DEFLATE의 구체적 응용은 PNG 압축 원리 상세 설명을 참조하시기 바랍니다.

5. 자주 묻는 질문(FAQ)

Q1: Huffman 코딩이란 무엇입니까?

Huffman 코딩은 최적의 접두사 가변 길이 코딩 방식으로, David Huffman이 1952년에 제안했습니다. 핵심 사상은: 출현 빈도가 높은 문자는 짧은 코드를, 빈도가 낮은 문자는 긴 코드를 사용하여 전체 코드 길이를 최소화하는 것입니다. 허프만 트리를 구성하여 코드표를 생성하며, 어떤 문자의 코드도 다른 문자의 코드 접두사가 아님을 보장하여(접두사 코드 특성), 디코딩 시 모호성이 발생하지 않습니다.

Q2: Huffman 코딩이 왜 최적의 접두사 코드입니까?

Huffman 코딩의 최적성은 그리디 전략에 기반합니다: 매번 가장 낮은 빈도를 가진 두 노드를 병합하며, 빈도가 낮은 노드는 트리의 깊은 레이어에(코드가 길고), 빈도가 높은 노드는 얕은 레이어에(코드가 짧음) 위치합니다. 수학적으로 주어진 문자 빈도 분포에 대해, Huffman 코딩의 기대 코드 길이는 다른 어떤 접두사 코딩의 기대 코드 길이보다 작지 않음을 증명할 수 있으며, 이는 엔트로피 코딩의 이론적 하한(소스 엔트로피 H)에 도달합니다. ABRACADABRA 예시에서 Huffman 코딩은 23 bit, 이론적 엔트로피 하한은 22.5 bit로, 효율은 97.8%입니다.

Q3: Huffman 코딩과 산술 코딩의 차이는 무엇입니까?

Huffman 코딩은 문자 단위로 코딩하며, 각 문자에 독립적인 가변 길이 코드워드를 할당합니다. 산술 코딩은 전체 메시지를 [0,1) 구간의 소수 하나에 매핑하며, 코딩 입도가 더 세밀합니다. Huffman 코딩은 구현이 간단하고 속도가 빠르지만, 문자 단위 코딩의 한계로 인해 소스 엔트로피에 근접할 수 없습니다. 산술 코딩은 압축률이 더 높고(엔트로피 값에 근접 가능), 계산 복잡도가 더 높습니다. DEFLATE는 Huffman을 사용하고, 현대 ZSTD/brotli는 둘을 결합하여 사용합니다.

Q4: Huffman 코딩은 어떤 압축 형식에서 사용됩니까?

Huffman 코딩은 DEFLATE(ZIP/GZIP/PNG)의 핵심 구성 요소로 LZ77와 함께 사용됩니다. ZSTD는 Huffman의 대안으로 FSE(유한 상태 엔트로피 코딩)를 사용하지만 원리는 서로 통합니다. brotli와 JPEG(DC/AC 계수)도 Huffman 코딩을 사용합니다. 거의 모든 주류 무손실 압축 형식이 엔트로피 코딩 단계로 Huffman 또는 그 변형을 포함합니다.

결론

Huffman 코딩은 압축 알고리즘의 핵심으로, "고빈도 단코드, 저빈도 장코드"라는 핵심 원리를 통해 허프만 트리를 구성하여 최적의 접두사 코드를 생성합니다. "ABRACADABRA"를 예로 들면, 11개 문자를 ASCII의 88 bit에서 23 bit로 압축하여 이론적 엔트로피 하한의 97.8% 효율을 달성했습니다. Huffman 코딩은 거의 모든 주류 무손실 압축 형식에 존재하며, LZ77 사전 알고리즘과 결합하여 DEFLATE/ZSTD 등 고전적인 압축 파이프라인을 구성합니다.

Huffman 코딩을 이해하는 데 있어 세 가지 핵심이 있습니다: 첫째, 빈도 통계가 코드 길이 할당을 결정합니다. 둘째, 허프만 트리의 그리디 구성이 최적성을 보장합니다. 셋째, 접두사 코드 제약이 디코딩의 모호성 없음을 보장합니다. Huffman 코딩을 마스터하면 모든 현대 압축 알고리즘을 이해하는 열쇠를 쥐게 됩니다.