ハフマン符号

ハフマン符号は、シンボルを可変長のビット列に対応付けます。接頭語自由符号では、 ある符号語が別の符号語の接頭語になることがないため、デコーダーは1つの二分木を たどり、葉に到達するとすぐにシンボルを出力できます。接頭語自由符号は一意復号 可能ですが、一意復号可能な符号がすべて接頭語自由というわけではありません。

接頭語自由符号とクラフトの不等式 #

符号語長が lᵢ である二元接頭語符号について、クラフトの不等式は次のように なります。

Σ 2^(-lᵢ) ≤ 1

この不等式は、各葉が占める二分木の割合を数えたものです。逆に、この不等式を 満たす正の整数からなる任意の長さの列は、二元接頭語符号として実現できます。 等号は完全な木を表し、狭義の不等号の場合は未使用の枝が残ります。

頻度木の構築 #

シンボルの頻度が与えられると、ハフマンアルゴリズムは重みが最小の2つのノードを 繰り返し取り出し、それらを重みの和を持つノードの下の兄弟にして、そのノードを 再挿入します。シンボルの深さが符号長になります。出現頻度の低いシンボルを木の 最も深い位置で併合することにより、最適性を直感的に示す交換論法が得られます。 つまり、出現頻度の高いシンボルを、それより低いシンボルの上に移しても、重み付き 経路長は増加しません。生成された木は、与えられた頻度に対する二元接頭語符号の 中で期待符号長を最小化します。

while more than one node remains:
    a, b = remove the two lowest-weight nodes
    insert node(weight(a) + weight(b), a, b)

重みが等しい場合、最適な木が複数存在し得ます。決定的な実装では、たとえば頻度の 次に安定したシンボル序数を比較するなど、同順位の処理方法を定義する必要があります。 期待ビット数は変わらないものの、再現可能な出力とテストには決定性が重要です。 最大符号長を規定するフォーマットでは、長さ制限付きハフマンアルゴリズムが必要です。 木を単純に切り詰めると、クラフトの不等式に違反したり、意図したシンボル順序が 変わったりする可能性があります。

短い入力やエントロピーの高い入力では、符号表のオーバーヘッドが圧縮による削減量を 上回る場合があります。ハフマン符号は表現方法の選択肢であり、すべての入力が小さく なることを保証するものではありません。

正準符号の再構築 #

多くのフォーマットでは、左右の木のポインターではなく符号長を伝送します。正準符号の 構築では、有効なシンボルを (length, symbol order) でソートし、各符号長の範囲内で 連続した整数符号を割り当て、符号長が増えるたびに次の符号を左シフトします。 デコーダーは同じ計算を繰り返した後、各符号をルックアップテーブルまたは復号木に 挿入します。したがって、木の形状を伝送しなくても、同一の符号長から同一の符号が 生成されます。

たとえば、符号長 (1, 2, 3, 3) をシンボル A から D に割り当てると、次の正準表が 生成されます。

この表は論理的な符号値を記録しています。ビット指向のフォーマットでは、それらの値を 異なる順序で直列化できます。たとえばDEFLATEは、ストリームに格納するときにハフマン 符号のビットを反転します。

デコーダーは検査付き算術で表を構築し、次の場合には拒否するべきです。

• 符号長が、それを包含するフォーマットの制限範囲外である。
• 長さの組み合わせが木に含まれる数を超える葉を必要とする、過剰割り当ての集合である。
• フォーマットが完全な木を要求しているにもかかわらず、不完全な集合である。
• シンボルが重複しているか範囲外である、繰り返し命令が不正である、または必須の ブロック終端シンボルが存在しない。
• ビット列が表の範囲を越えて進む、または符号の途中で終了する。

ルックアップテーブルでは一度に複数のビットを復号できますが、低速パスでも符号長と 残りの入力を検証する必要があります。無効な表エントリーをシンボルとして扱うと、 不正な入力が検出されないままデータ破損へと変わります。

具体的な正準形式については、DEFLATEとGzipの形式を参照してください。

参考文献 #

• D. A. Huffman, 「最小冗長符号の構築方法」, Proceedings of the IRE, 1952.
• RFC 1951: DEFLATE、3.2.1–3.2.2節