ハフマン符号化
ハフマン符号化は頻度から最適な二進接頭語符号を作ります。最も軽い二つの木を繰り返し併合し、低頻度を深く、高頻度を短い符号へ配置します。既定の ABRACADABRA はペイロード 23 ビットで、同じ文字集合の固定長は 33 ビットです。
モールスも頻繁な E を一点、Q を四信号にしますが、文字間の休止が必要です。通常のビット列には休止がないため、どの符号も他の接頭辞にならないようにします。符号を木の葉だけに割り当てれば成立します。
ハフマン符号化の仕組み
頻度を数え、各記号を重み付きの一ノード木として最小優先度キューへ入れます。最軽量の二木を取り、和の重みの新しい親へつなぎ、キューへ戻します。一木まで繰り返します。
根から記号の葉まで、左を 0、右を 1 と読んだ経路が符号語です。深さが長さで、併合順が長い符号を負担する記号を決めます。
最小二つの併合が安全な理由
最適な接頭語木の最深部の兄弟葉へ、最も低頻度の二記号を交換します。低頻度を深くする増分は、高頻度を浅くする節約を超えず、総費用は増えません。よって最低頻度二つが兄弟である最適木が少なくとも一つ存在します。
二つを重みの和の一記号へ縮め、同じ論証を繰り返して展開します。この帰納が各最小併合を正当化します。
同じ重みは作成順で決め、同じテキストに同じ木を作ります。別の一貫した規則なら木や符号は変わっても、最適な総ビット数は同じです。
画面のキューは左から重み順の棚で、最小二つを見せます。Python の heapq の内部配列は全順序ではありません。その内部はヒープのレッスンで扱います。
符号化をステップで追う
既定は ABRACADABRA、11 文字、5 種類です。
- 頻度：A が 5、B と R が 2、C と D が 1。
- キュー：
C(1) · D(1) · B(2) · R(2) · A(5)。 - 第一併合：C と D を重み 2 の
[CD]へ。同点の古い木が先なのでB(2) · R(2) · [CD](2) · A(5)。 - 第二併合：B と R を 4 へ。
[CD](2) · [BR](4) · A(5)。 - 第三併合：CD と BR を 6 へ。
A(5) · [CDBR](6)。 - 第四併合：5 と 6 を合わせ、根は全文字数の 11。
- 符号：左 0、右 1。A は一辺で
0。残りは深さ三で、C=100、D=101、B=110、R=111。 - 出力：
0 · 110 · 111 · 0 · 100 · 0 · 101 · 0 · 110 · 111 · 0、23 ビット。五記号の固定長は各⌈log₂ 5⌉ = 3、計 33。約 30% 減。五つの A が三ビットから一ビットになり、十ビットを節約する。
棚の左端二木を琥珀色の min pair 括弧で選びます。最後の緑 23 と灰 33 はペイロードだけで、符号表を含みません。実ファイルは規則も伝える必要があり、この短さではヘッダーが十ビットの節約を超える場合があります。
時間・空間計算量
n は文字数、k は異なる記号数です。
| 段階 | 通常の計数モデルでの費用 |
|---|---|
| 頻度計数 | O(n) |
| ヒープで k−1 回併合 | O(k log k) |
| 木を訪ねて経路を割り当てる | O(k) 回のノード訪問 |
| 符号化 | O(n) 回の記号検索 |
固定字母集合で符号語操作を定数とするモデルなら合計 O(n + k log k)、木と頻度表は O(k) 空間です。出力を一ビットずつ生成したり全符号語をコピーしたりするなら、出力ビット数と符号語長の合計も加算します。
併合数は k−1 に固定されても圧縮効果は頻度次第です。同じ二記号以上の集合の二進接頭語符号では固定長も合法候補なので、ハフマンのペイロードはそれより悪くなりません。最適平均長が ⌈log₂ k⌉ 未満なら節約できます。
境界ケース
- 一種類だけ：併合なしで根が葉、経路は空。この実装は
path or "0"の一ビットを使い、現在の復号規約で空出力にならないようにする。別形式なら長さを別保存するなど明示的な規約が必要。 - 二種類：偏っても各一ビット。記号単位の二進接頭語符号は半ビットを割り当てられない。算術符号は複数記号を通じて平均を下げられる。
- 固定長と同点：Uniform の四等頻度は各二ビットで 24 対 24。五等頻度なら 24 対 30 と節約し、3、3、2、2 の非一様頻度も 20 で同点。一様かどうかだけでは決まらない。
- 強い偏り：1、2、4、8 は鎖状になり、低頻度の長さは k−1 でも総量は少ない。Skewed は 25 対 30。
- 同点：作成順が再現性を与える。別規則は形と符号を変えても最適総費用を変えない。
よくある間違い
- 最初だけソートして隣同士を組む。 合成した親を戻し、新しい重みで競わせます。
- 順位だけで
0、1、01と割り当てる。 接頭辞が重なると、記号終了か継続か分かりません。 - 一記号の規約を忘れる。 ここでは
path or "0"が必要です。空経路だけでは現在の形式で回数を表せません。 - ペイロードだけを送る。 復号側には木、表、または再構築可能な頻度と規則が必要です。圧縮サイズにはヘッダーも数えます。
- 同点規則を共有しない。 両方最適でも別の符号へ対応する恐れがあります。頻度から復元するなら同じ規則を使います。