> shannon | fano | entropy <
// Shannon-Fano – データ圧縮のためのトップダウン型エントロピー符号化
エントロピーに基づく
情報理論に基づき、効率的な可変長符号を生成します。
トップダウン方式
類似した確率をもつ記号のグループに再帰的に分割します。
歴史的アルゴリズム
現代の多くの圧縮アルゴリズムに影響を与えた先駆的手法です。
>> 技術情報
Shannon-Fano の仕組み:
Shannon-Fano 符号化では、記号を出現頻度順に並べ、合計確率ができるだけ近くなるように2つのグループへ再帰的に分割します。各分割でコードに 1 ビットを追加します（左側に 0、右側に 1）。その結果、可変長のプレフィックス符号列が得られます。
符号化プロセス:
テキスト: "AAABBCD" 出現回数: A:3, B:2, C:1, D:1 分割: [A] | [B,C,D] コード: A: 0 B: 10 C: 110 D: 111 符号化結果: 0 0 0 10 10 110 111
Shannon-Fano を使う理由:
- >実装が簡単
- >良好な圧縮率
- >歴史的に重要
- >教育用途に最適
- >プレフィックス符号を生成
>> よくある質問
Shannon-Fano 符号化とは？
Shannon-Fano 符号化は、1940年代に Claude Shannon と Robert Fano によって開発されたエントロピー符号化方式です。記号の出現確率に基づく可変長符号を用いた、最初期のアルゴリズムの一つです。
Shannon-Fano と Huffman の違いは？
どちらも可変長符号を生成しますが、Huffman 符号は最適であり、平均コード長を最小化します。Shannon-Fano はよりシンプルですが、やや長い符号になることがあります。Huffman はボトムアップで木を構築し、Shannon-Fano はトップダウンで構築します。
分割処理はどのように行われますか？
記号を頻度順に並べ、合計確率がほぼ等しくなるように2つのグループに分けます。この処理を各グループに対して再帰的に繰り返し、最終的に各グループに1つの記号だけが残るまで続けます。
現在でも Shannon-Fano は使われていますか？
Shannon-Fano は実用システムでは、最適性を保証する Huffman 符号化にほぼ置き換えられています。現在は主に歴史的・教育的な目的で利用されますが、圧縮アルゴリズムの基本概念を理解するうえで非常に有用です。
// 計算例
| Symbol | Freq | Code | Bits |
|---|---|---|---|
| A | 15 | 00 | 2 |
| B | 7 | 01 | 2 |
| C | 6 | 10 | 2 |
| D | 6 | 110 | 3 |
| E | 5 | 111 | 3 |
// コード例
Frequencies A=15 B=7 C=6 D=6 E=5 (39 symbols)
1. Sort symbols by frequency (descending).
2. Split the list where the two halves' totals are closest:
{A,B}=22 | {C,D,E}=17 -> first bit 0 / 1
3. Recurse on each half until single symbols remain:
{A}|{B} -> 00, 01 {C}|{D,E} -> 10, 11.. then {D}|{E} -> 110, 111
Total 15*2 + 7*2 + 6*2 + 6*3 + 5*3 = 89 bits
Huffman on the same data: A=1 bit, others 3 bits -> 87 bits
>> その他の質問
Q: Shannon-FanoとHuffmanの違いは？
A: Shannon-Fanoは整列した記号列を上から下へ、頻度の合計がなるべく等しい2つに分割します。Huffmanは最も稀な記号を併合して下から木を作ります。Huffmanは最適であることが証明されていますが、Shannon-Fanoは常にそうとは限りません。
Q: Shannon-Fanoは常に最適ですか？
A: いいえ。例ではHuffmanの87ビットに対し89ビットです。どちらも語頭条件を満たしますが、Shannon-Fanoの分割規則は不利な分け方を選ぶことがあります。
Q: Shannon-Fanoはどこで使われますか？
A: 主に歴史的・教育的な手法です（Claude ShannonとRobert Fano、1948/49年）。ZIPのIMPLODEアルゴリズムに変種があり、現代の圧縮器はHuffmanや算術符号を使います。