> huffman | 最適な | 符号 <
// Huffman 符号化 - プレフィックスフリーで最適な圧縮アルゴリズム
最適な符号
与えられた頻度に対して、平均符号長が最短となる符号を生成します。
プレフィックスフリー
どの符号も他の符号の前方一致にならないため、曖昧さなく復号できます。
頻度ベース
よく現れる文字ほど短い符号になり、自動的に効率の良い圧縮が行われます。
>> 技術情報
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
Huffman 符号化を使う理由:
- ▸理論的限界に近い圧縮率
- ▸実装が比較的シンプル
- ▸ZIP / JPEG など多くのフォーマットの基盤技術
- ▸可逆圧縮でデータ損失なし
- ▸実運用で実証された高い効率
>> よくある質問
Huffman 符号化とは何ですか？
Huffman 符号化は、1952 年に David A. Huffman によって提案された最適なプレフィックスフリー圧縮アルゴリズムです。文字の出現頻度に応じて可変長のビット列を割り当て、頻度の高い文字には短い符号を与えることで、平均符号長を最小化します.
なぜプレフィックスフリーと呼ばれるのですか？
ある符号が別の符号の先頭部分（プレフィックス）になっていないとき、その符号体系はプレフィックスフリーと呼ばれます。例えば 'A' の符号が '01' であれば、他のどの文字の符号も '01' で始まってはいけません。この性質により、区切り記号を挟まなくても、ビット列を左から順に読むだけで一意に復号できます。
Huffman 符号化の効率はどのくらいですか？
Huffman 符号化は、与えられた頻度分布に対して理論上のエントロピー限界から 1 ビット以内の圧縮率を達成できるとされています。英語テキストでは、一般的に 60〜70% 程度の圧縮が期待でき、文字の出現頻度に偏りがあるほど効果が高くなります。
Huffman 符号化はどこで使われていますか？
Huffman 符号化は JPEG 画像圧縮、ZIP ファイル圧縮（DEFLATE における LZ77 との組み合わせ）、MP3 オーディオなど、多くのフォーマットで利用されています。多くの場合、他のアルゴリズムと組み合わせて使われ、例えば JPEG では DCT と量子化の後に Huffman を適用し、ZIP では LZ77 の後段で Huffman を使用します。
// 計算例
| Symbol | Freq | Bits | Code |
|---|---|---|---|
| A | 4 | 1 | 0 |
| B | 2 | 2 | 10 |
| C | 1 | 2 | 11 |
// コード例
Input AAAABBC (7 symbols, 56 bits as 8-bit ASCII) Counts A=4 B=2 C=1 Merge C(1)+B(2) -> node(3); node(3)+A(4) -> root(7) Codes A=0 B=10 C=11 (0/1 on left/right branches; ties may swap) Encoded 0 0 0 0 10 10 11 = 4*1 + 2*2 + 1*2 = 10 bits
>> その他の質問
Q: ハフマン符号は一意ですか？
A: 必ずしもそうではありません。頻度が同じ場合、ノードの選び方や0と1の割り当てが変わり得ます。ただし符号長と総ビット数は、正しいハフマン木ならどれでも最適で同じです。
Q: 語頭条件（プレフィックスフリー）とは？
A: どの符号語も他の符号語の先頭部分にならないという性質です。区切りなしでビット列を復号でき、根から葉に着くまで辿れば1シンボルが決まります。
Q: ハフマン符号が最適でないのはどんなときですか？
A: 1シンボルに整数ビットを割り当てるため、確率が極端に偏る場合（例：0.99）は効率が落ちます。算術符号の方がエントロピーに近づきます。また復号側には符号表が必要です。