최적 코드

주어진 빈도에 대해 평균 코드 길이가 가장 짧도록 코드를 생성합니다.

프리픽스 프리

어떤 코드도 다른 코드의 접두사가 아니므로, 모호함 없이 복호화할 수 있습니다.

빈도 기반

자주 등장하는 문자는 자동으로 더 짧은 코드를 받아 압축 효율을 높입니다.

Huffman 코딩의 동작 원리

Huffman 코딩은 문자 빈도로부터 이진 트리를 하향식이 아니라 상향식으로 구성합니다. 가장 빈도가 낮은 두 노드를 반복적으로 하나의 부모 노드로 합치면서, 최종적으로 루트 노드 하나만 남을 때까지 진행합니다. 왼쪽 가지는 '0', 오른쪽 가지는 '1'을 의미하며, 더 자주 등장하는 문자는 루트에 더 가까운 위치에 배치되어 더 짧은 코드를 가지게 됩니다. 그 결과 주어진 빈도 분포에 대해 거의 최적의 압축률을 얻을 수 있습니다.

Huffman 코딩 예시

Text: "AABBBCCCC"

Frequencies:
A: 2
B: 3
C: 4

Tree Building:
1. Combine A(2) + B(3) = AB(5)
2. Combine C(4) + AB(5) = Root(9)

Tree:
     Root(9)
    /      \
   C(4)    AB(5)
          /     \
        A(2)    B(3)

Codes:
C: 0
A: 10
B: 11

Encoded: 10 10 11 11 11 0 0 0 0
= 1010111111 0000