> 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 符号化にほぼ置き換えられています。現在は主に歴史的・教育的な目的で利用されますが、圧縮アルゴリズムの基本概念を理解するうえで非常に有用です。