最適な符号

与えられた頻度に対して、平均符号長が最短となる符号を生成します。

プレフィックスフリー

どの符号も他の符号の前方一致にならないため、曖昧さなく復号できます。

頻度ベース

よく現れる文字ほど短い符号になり、自動的に効率の良い圧縮が行われます。

Huffman 符号化の仕組み

Huffman 符号化は、文字の出現頻度から二分木を下から上へ構築します。もっとも頻度の低い 2 つのノードを繰り返し親ノードとして結合し、最終的に 1 つの根ノードだけが残るまで続けます。左の枝を '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