허프만 코딩

문자의 등장 빈도에 따라 가변 길이의 접두어 코드를 부여해, 빈도가 높은 문자에는 짧은 비트열을, 낮은 문자에는 긴 비트열을 할당하는 무손실 압축 알고리즘입니다.

동작 과정

문자별 빈도가 a:5, b:2, c:1, d:1일 때 허프만 트리를 만드는 과정입니다.

[ 1단계 ] 모든 문자를 빈도 기준 최소 힙에 삽입
힙: c(1), d(1), b(2), a(5)

[ 2단계 ] 가장 작은 두 노드를 꺼내 합치고, 합쳐진 노드를 다시 힙에 삽입
  꺼냄: c(1), d(1) → 합침: cd(2)
       c(1)  d(1)
         \   /
         cd(2)
  힙: b(2), cd(2), a(5)

  꺼냄: b(2), cd(2) → 합침: bcd(4)
       b(2)  cd(2)
         \    /
         bcd(4)
  힙: a(5), bcd(4)

  꺼냄: bcd(4), a(5) → 합침: root(9)
  힙: root(9) → 노드가 1개 남아 종료

[ 완성된 허프만 트리 ] (왼쪽 간선=0, 오른쪽 간선=1)
            root(9)
           /       \
        bcd(4)      a(5)
       /     \
     b(2)   cd(2)
            /    \
          c(1)   d(1)

[ 루트에서 리프까지 경로 = 코드 ]
a   = 1
b   = 00
c   = 010
d   = 011

가장 빈도가 높은 a가 루트에서 가장 가까운 리프가 되어 가장 짧은 코드(1)를 받고, 빈도가 낮은 c, d는 더 깊은 리프가 되어 긴 코드를 받습니다. 매 단계 "현재 가장 작은 두 노드를 합친다"는 지역 선택만으로 전체 최적 코드 길이를 얻는 그리디 알고리즘입니다.

구현

class Node implements Comparable<Node> {
    char ch;
    int freq;
    Node left, right;

    Node(char ch, int freq) {
        this.ch = ch;
        this.freq = freq;
    }

    Node(int freq, Node left, Node right) {
        this.freq = freq;
        this.left = left;
        this.right = right;
    }

    boolean isLeaf() {
        return left == null && right == null;
    }

    @Override
    public int compareTo(Node other) {
        return Integer.compare(this.freq, other.freq);
    }
}

Node buildHuffmanTree(Map<Character, Integer> freq) {
    PriorityQueue<Node> pq = new PriorityQueue<>();
    for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
        pq.offer(new Node(entry.getKey(), entry.getValue()));
    }

    while (pq.size() > 1) {
        Node left = pq.poll();
        Node right = pq.poll();
        pq.offer(new Node(left.freq + right.freq, left, right));
    }
    return pq.poll();  // 루트
}

void generateCodes(Node node, String code, Map<Character, String> codes) {
    if (node == null) return;
    if (node.isLeaf()) {
        codes.put(node.ch, code.isEmpty() ? "0" : code);  // 문자가 하나뿐인 경우 대비
        return;
    }
    generateCodes(node.left, code + "0", codes);
    generateCodes(node.right, code + "1", codes);
}

복잡도

공간복잡도는 O(n)으로, 리프 n개와 내부 노드 n−1개로 이루어진 트리를 저장합니다.

주의사항

• 빈도가 같은 노드의 병합 순서는 트리 모양에 영향을 주지만 평균 코드 길이(압축률)는 바꾸지 않는다. 최적성은 빈도 분포에만 의존한다
• 문자 종류가 1개뿐이면 코드 길이가 0이 되는 문제가 생기므로, 위 구현처럼 최소 코드 길이를 1로 강제해야 한다
• 접두어 코드(prefix code)라는 점이 핵심이다. 어떤 코드도 다른 코드의 접두사가 되지 않으므로, 디코딩할 때 구분자 없이 비트열만으로 원래 문자를 복원할 수 있다
• 실제 응용에서는 트리 구조 자체도 압축 파일에 함께 저장해야 디코딩이 가능하다

핵심 정리

• 빈도 기반 가변 길이 접두어 코드로 데이터를 무손실 압축하는 알고리즘
• 가장 빈도가 낮은 두 노드를 반복적으로 합쳐 트리를 상향식으로 구성한다
• PriorityQueue(Heap 기반)로 최소 두 노드를 O(log n)에 꺼내며 O(n log n)에 트리를 완성한다
• 매 단계의 지역 최적 병합이 전체 최적 압축률로 이어지는 그리디의 대표 사례

→ 그리디