Huffman Coding: 최적 접두 부호

Huffman Coding, 허프만 코딩, Huffman code, prefix code

정의

Huffman Coding 은 문자의 빈도가 주어졌을 때 평균 부호 길이를 최소화 하는 접두 부호 (prefix code) 를 만드는 그리디 알고리즘. David Huffman (1952) 이 MIT 학생 시절 발표.

접두 부호: 어떤 부호도 다른 부호의 접두어가 아님. 구분자 없이 디코딩 가능.

알고리즘

1. 각 문자를 리프 노드로 하고 빈도를 우선순위로 하는 min-heap 준비.
2. Heap 에서 최소 두 노드를 pop, 두 빈도의 합을 값으로 하는 새 내부 노드 생성 (두 노드를 자식으로).
3. 새 노드를 heap 에 push.
4. Heap 크기가 1 이 될 때까지 반복.
5. 완성된 트리의 루트에서 각 리프까지의 경로가 부호 (왼쪽=0, 오른쪽=1).

#include <queue>
struct Node { char ch; int freq; Node *l, *r; };
struct Cmp { bool operator()(Node* a, Node* b) { return a->freq > b->freq; } };

Node* build(map<char, int>& freq) {
    priority_queue<Node*, vector<Node*>, Cmp> pq;
    for (auto [c, f] : freq) pq.push(new Node{c, f, nullptr, nullptr});
    while (pq.size() > 1) {
        Node* a = pq.top(); pq.pop();
        Node* b = pq.top(); pq.pop();
        pq.push(new Node{0, a->freq + b->freq, a, b});
    }
    return pq.top();
}

O(N log N) - N 은 문자 종류 수.

예시

빈도: a=5, b=9, c=12, d=13, e=16, f=45

결과 부호 (평균 길이 ~2.24 bit):

• f: 0
• c: 100
• d: 101
• a: 1100
• b: 1101
• e: 111

최적성 증명

Sibling property: 같은 부모의 두 자식은 항상 heap 에서 가장 낮은 두 원소. 이 성질이 최적 부호를 그리디하게 유도.

응용

• DEFLATE (gzip, PNG): LZ77 + Huffman
• JPEG: DCT 계수 부호화
• HTTP/2 HPACK: 헤더 압축에 정적 Huffman table
• MP3: 오디오 부호화

한계

• 문자 하나씩 부호화. 확률이 극단적 (0.9 인 문자) 이면 손실 큼 → Arithmetic Coding 이 더 최적
• 정적 빈도: 스트리밍은 Adaptive Huffman 이 필요

참고

• 관련 Priority Queue
• 관련 HPACK (HTTP/2 헤더 압축)
• 관련 Greedy