【はふまんふごうか】
ハフマン符号化 とは？
最終更新:
💡 頻度に合わせて、区切り不要の符号を作る
記号の頻度に応じた可変長の接頭符号を作る方法。出現の少ない2つの重みを繰り返しまとめ、平均符号長を小さくします。所定の記号と確率の条件での最適性で、あらゆる圧縮方式の中で最小になる保証ではありません。
📌 このページのポイント
- 対象は文字に限らず、符号化したい記号とその頻度・確率
- 通常の二進ハフマン木は、最小の2つの重みを繰り返しまとめて作る
- 葉までの0・1の経路を符号にし、ほかの符号の接頭部にはならない
- 与えられた確率の、記号ごとの接頭符号で平均長を最小にする
- 符号表などの追加情報も必要で、短いデータが必ず縮むとは限らない
ひよこ ハフマン符号化はどう圧縮するの？
ペンギン先生 よく出る記号へ短い符号を割り当て、全体の平均の長さを小さくする方法だよ。記号は文字だけではない。たとえばAが50%、Bが30%、Cが20%なら、Aを0、Bを10、Cを11とする例があるんだ。
ひよこ どうやってその符号を作る？
ペンギン先生 頻度や確率が最も小さい2つをまとめ、その合計を新しい重みとして戻す。1つの木になるまで繰り返すんだ。枝に0と1を付け、根から各記号の葉までたどった経路を符号にするよ。
ひよこ 0の後に10が来ても区切れる？
ペンギン先生 この例では0、10、11のどれも、ほかの符号の先頭部分にならない。これを接頭符号というよ。符号表を知っていれば、010を0と10に一意に分けられる。01と011のような組を同じ符号表には使わないんだ。
ひよこ ハフマンならいつも最小サイズ？
ペンギン先生 与えた記号の確率に対する、記号ごとの接頭符号で平均長が最適という意味だよ。あらゆる圧縮方法で最小という意味ではない。符号表やヘッダーなどの分もあるので、実際のファイルが必ず縮むわけでもないんだ。
ひよこ 実際の圧縮形式ではどう使う？
ペンギン先生 DEFLATEは繰り返しを扱うLZ77とハフマン符号化を組み合わせる。PNGもDEFLATEを使うよ。圧縮形式全体がハフマンだけでできているわけではなく、方式やブロックによって非圧縮や固定の符号も使われるんだ。
もっと詳しく知りたい人へ
同じ頻度なら符号も必ず同じ？
同じ重みの結合順や枝の0・1の割り当てによって、符号の形が異なることがあります。平均長の最適性と符号表の一意性は別です。復号側と同じ符号表や構築規則を共有する必要があります。
まとめ：ざっくりこれだけ覚えればOK！
「ハフマン符号化」って出てきたら「よく出るものに短い符号を割り当て、平均の符号長を小さくする方法」と思えばだいたいOK！
📖 おまけ：英語の意味
「Huffman Coding」 ＝ ハフマン符号化
💬 David A. Huffmanが1952年に発表した「A Method for the Construction of Minimum-Redundancy Codes」に由来します。課題や教授の逸話と、原論文の手法の説明は分けます。