7. 허프만 코딩 (Huffman Coding) — 가변길이 최적 코드

핵심 인사이트 (3줄 요약)

본질: 허프만 코딩 (Huffman Coding)은 빈도가 높은 기호에 짧은 코드, 낮은 기호에 긴 코드를 부여하는 그리디 기반 가변 길이 접두사 코드 (Prefix-free Code)로, 섀넌 엔트로피에 근접하는 최적 무손실 압축을 달성한다.

가치: 프리픽스 코드(어떤 코드도 다른 코드의 접두사가 아님) 특성으로 구분자 없이 복호화가 가능하며, JPEG·MP3·DEFLATE(ZIP·gzip·PNG·HTTP/2)의 핵심 압축 레이어로 현대 디지털 통신의 표준이다.

판단 포인트: 기호 빈도 분포가 불균일할수록 압축 효율이 높으며, 빈도가 균등(엔트로피 최대)하면 허프만도 효과가 없다. 고정 코드 대비 평균 코드 길이 감소가 직접적인 압축률이다.

Ⅰ. 개요 및 필요성

ASCII로 'a'를 8비트로 저장한다면, 영어 텍스트에서 40%를 차지하는 'e'도 'z'도 같은 8비트다. 허프만 코딩은 'e'에 2비트, 'z'에 12비트를 부여하여 전체 평균 코드 길이를 최소화한다. 1952년 데이비드 허프만(David Huffman)이 고안했으며, 70년이 지난 현재도 JPEG·MP3·ZIP·gzip·PNG의 핵심 압축 알고리즘으로 사용된다.

섀넌 엔트로피와 허프만의 관계

엔트로피 H(S) = -Σ p_i × log₂(p_i)  ← 이론적 최소 평균 코드 길이

허프만 코드의 평균 길이 L:
  H(S) ≤ L < H(S) + 1

즉, 허프만은 엔트로피 하한에 1비트 이내로 근접하는 최적 코드

📢 섹션 요약 비유: 허프만 코딩은 모스 부호의 과학적 버전—자주 쓰는 'E'는 짧은 "·", 드물게 쓰는 'Q'는 긴 "──·──"처럼 빈도에 따라 코드 길이를 최적화한다.

Ⅱ. 아키텍처 및 핵심 원리

허프만 트리 구축 (그리디 알고리즘)

빈도: A=5, B=2, C=1, D=3, E=4

단계 1: 우선순위 큐(최소 힙) 초기화
  [C:1, B:2, D:3, E:4, A:5]

단계 2: 두 개 최소 노드 병합 반복
  [C:1] + [B:2] → [CB:3]
  큐: [CB:3, D:3, E:4, A:5]

  [CB:3] + [D:3] → [CBD:6]
  큐: [E:4, A:5, CBD:6]

  [E:4] + [A:5] → [EA:9]
  큐: [CBD:6, EA:9]

  [CBD:6] + [EA:9] → [root:15]

단계 3: 허프만 트리 완성
        [root:15]
       /          \
   [CBD:6]       [EA:9]
   /    \         /    \
[CB:3] [D:3]  [E:4]  [A:5]
 /   \
[C:1][B:2]

코드 (왼쪽=0, 오른쪽=1):
  A: 11    (2비트)
  B: 001   (3비트)
  C: 000   (3비트)
  D: 01    (2비트)
  E: 10    (2비트)

프리픽스 코드 (Prefix-free Code) 특성

허프만 코드:  A=11, B=001, C=000, D=01, E=10

디코딩 "001011":
  0 → 진행
  00 → 진행
  001 → B (완성!)
  0 → 진행
  01 → D (완성!)
  1 → 진행
  11 → A (완성!)
  결과: B D A

구분자(공백) 없이도 유일 복호화 가능 ← 프리픽스 코드의 핵심

정적 vs 적응형 허프만 코딩

방식	특징	활용
정적 (Static)	빈도 사전 계산 후 코드표 전송	JPEG, ZIP
적응형 (Adaptive)	실시간 빈도 갱신, 코드표 불필요	스트리밍 압축

📢 섹션 요약 비유: 허프만 트리는 가장 가벼운 두 사람을 반복해서 팀으로 묶는 팀 구성 게임—최종 팀 구조가 최적 코드표가 된다.

Ⅲ. 비교 및 연결

허프만 코딩이 적용된 실제 포맷

포맷/시스템	허프만 위치	결합 알고리즘
JPEG	DC/AC 계수 인코딩	DCT + 양자화 + 허프만
MP3	주파수 계수 인코딩	MDCT + 허프만
DEFLATE	리터럴/거리 인코딩	LZ77 + 허프만
ZIP / gzip / zlib	DEFLATE 내부	위 동일
PNG	필터링 후 DEFLATE	필터 + LZ77 + 허프만
HTTP/2 HPACK	헤더 압축	허프만 (정적 테이블)

알고리즘 복잡도

코드 구축: O(n log n) — 우선순위 큐 (최소 힙) 활용
인코딩:    O(L) — L = 출력 길이
디코딩:    O(L) — 트리 순회

📢 섹션 요약 비유: DEFLATE는 두 선수의 콤비 플레이—LZ77이 반복 패턴을 찾아 "저기랑 같아요"라고 표시하면, 허프만이 그 표시들을 또 짧은 코드로 변환한다.

Ⅳ. 실무 적용 및 기술사 판단

주요 활용 사례

이미지 압축 (JPEG): 양자화된 DCT 계수의 허프만 엔트로피 코딩
오디오 압축 (MP3): 서브밴드 코딩 계수 인코딩
데이터 압축 (ZIP/gzip): DEFLATE 알고리즘의 두 번째 단계
네트워크 프로토콜 (HTTP/2 HPACK): 헤더 필드 반복 압축
데이터베이스: 컬럼 저장 포맷에서 저카디널리티 컬럼 압축

기술사 판단 기준

단순 반복 데이터                       →  RLE 우선
빈도 불균일 데이터 (텍스트)            →  허프만 코딩
반복 패턴 + 빈도 불균일 (일반 파일)   →  DEFLATE = LZ77 + 허프만
극고압축 텍스트                        →  bzip2 (BWT + 허프만)
실시간 스트리밍 압축                   →  적응형 허프만 또는 Zstandard

📢 섹션 요약 비유: 허프만 코딩만으로는 반복 패턴을 못 잡지만, LZ77이 반복을 없애고 허프만이 남은 기호를 최적 코드로 압축하면 ZIP이 탄생한다.

Ⅴ. 기대효과 및 결론

허프만 코딩은 섀넌 엔트로피에 1비트 이내로 근접하는 이론적 최적 접두사 코드다. 단독으로도 강력하지만 LZ77(반복 제거)과 결합한 DEFLATE가 현대 데이터 압축의 사실상 표준이 된 이유다. 프리픽스 코드 특성으로 구분자 없이 고속 복호화가 가능하며, 정적·적응형 두 변형으로 다양한 사용 시나리오를 커버한다.

결론: 빈도 기반 최적 가변 길이 코드가 필요한 모든 압축 시스템에서 허프만 코딩은 기본 구성 요소이며, 현대 인터넷 트래픽의 대부분이 이 알고리즘 위에서 압축되어 전달된다.

📌 관련 개념 맵

개념	관계
섀넌 엔트로피 (Shannon Entropy)	허프만 코드의 이론적 하한
프리픽스 코드 (Prefix-free Code)	허프만 코드의 핵심 특성
LZ77 / LZ78	DEFLATE에서 허프만과 결합
DEFLATE	LZ77 + 허프만 = ZIP/gzip/PNG
최소 힙 (Min-Heap)	허프만 트리 구축 자료구조
적응형 허프만	실시간 빈도 갱신 버전

📈 관련 키워드 및 발전 흐름도

[데이터 표현 (Data Representation)]
    │
    ▼
[가변 길이 코드 (Variable-Length Code)]
    │
    ▼
[허프만 코딩 (Huffman Coding)]
    │
    ▼
[엔트로피 압축 (Entropy Compression)]
    │
    ▼
[산술 코딩 (Arithmetic Coding)]
    │
    ▼
[LZ77/DEFLATE 압축 (Lempel-Ziv Compression)]

문자 빈도를 기반으로 최적 가변 길이 코드를 생성하는 허프만 코딩에서 현대 압축 표준으로 이어지는 흐름이다.

👶 어린이를 위한 3줄 비유 설명

허프만 코딩은 모스 부호처럼 자주 쓰는 글자는 짧은 신호, 드물게 쓰는 글자는 긴 신호로 바꾸는 방법이야.
트리를 만들 때는 가장 드물게 쓰이는 두 글자를 반복해서 짝짓는데, 그게 자동으로 최적 코드가 돼.
ZIP 파일이나 인터넷 사진이 작은 이유 중 하나가 바로 이 허프만 마법 덕분이야!