シャノン・ファノ符号化

シャノン・ファノ符号化とは、1948年にクロード・シャノンとロベルト・ファノによって考案された、データ圧縮のための可逆符号化方式です。この方法は、データ内の各記号の出現確率に基づいて、可変長の符号を割り当てることで、データサイズを削減します。

概要

シャノン・ファノ符号化は、各記号に最適な長さの符号を割り当てようとする手法です。ハフマン符号のように完全に最適化された符号とは異なり、必ずしも最短長の符号を生成するとは限りません。しかしながら、各記号の符号長は、理論上の最適な符号長（-log₂P(x) 、P(x)は記号xの確率）から1ビット以内におさまることが保証されています。この特性により、比較的効率の良い圧縮を実現できます。

シャノン・ファノ符号化は、シャノンの情報理論に関する論文『通信の数学的理論』(1948年)の中で提案されました。ファノはその後、この符号化法についてより詳細なテクニカルレポートを発表しています。なお、シャノン・ファノ符号化は、シャノンの情報源符号化定理の証明に使われたシャノン符号や、算術符号の前身であるシャノン・ファノ・イライアス符号とは異なる手法です。

符号化の原理

シャノン・ファノ符号化の手順は以下の通りです。

1. 記号の出現確率に基づいたソート: データに含まれる記号を、出現確率の高い順に並べ替えます。
2. 二分割: 記号の集合を、それぞれの集合の確率の合計がほぼ等しくなるように二分割します。
3. 符号の割り当て: 分割された一方の集合には「0」、もう一方の集合には「1」という符号を割り当てます。これが符号の最初の桁となります。
4. 再帰的分割: 分割によって得られた各集合を、さらに確率がほぼ等しくなるように二分割します。そして、同様に「0」と「1」を割り当てます。
5. 終端条件: 各集合に含まれる記号が1つになるまで、ステップ4を繰り返します。

このアルゴリズムによって、各記号に可変長の符号が割り当てられます。出現確率が高い記号には短い符号が、確率が低い記号には長い符号が割り当てられるため、データ全体の符号長を短縮できます。この分割によって作られる集合は、ほぼ等しい確率を持つように設計されているため、1ビットの情報は効率的に使用されます。

しかし、シャノン・ファノ符号化は常に最短符号長を保証するわけではありません。例えば、{0.35, 0.17, 0.17, 0.16, 0.15}という出現確率を持つ記号集合では、最適化されていない符号が生成される場合があります。このため、現在ではハフマン符号や算術符号、Range Coderといったより効率的な符号化方式が広く利用されています。

例

以下の例で、シャノン・ファノ符号化の具体的な手順を説明します。あるデータに5種類の記号A, B, C, D, Eが出現し、それぞれの出現回数が15, 7, 6, 6, 5であるとします。

まず、出現回数（確率）の高い順に記号を並べ替えます。次に、出現回数の合計がほぼ等しくなるように集合を分割し、一方に「0」、もう一方に「1」を割り当てます。この分割と符号割り当てを、各集合に1つの記号が残るまで繰り返します。この手順により、各記号に以下の符号が割り当てられます。

A: 00
B: 01
C: 100
D: 101
* E: 110

この例では、最も頻度の高い3つの記号（A, B, C）は2ビットの符号で、頻度の低い2つの記号（D, E）は3ビットの符号で表現されます。結果として、1文字あたりの平均符号長は約2.28ビットとなり、データの圧縮が行われています。

利点と欠点

シャノン・ファノ符号化は、比較的シンプルで理解しやすいアルゴリズムであるため、学習や実装が容易です。また、ハフマン符号に比べ、アルゴリズムの計算量が少なく済みます。しかし、必ずしも最適な符号長を生成するとは限らないため、ハフマン符号や算術符号に比べて圧縮率が劣る場合があります。そのため、近年では、より効率的な符号化方式が広く使われるようになっています。

結論

シャノン・ファノ符号化は、情報理論の基礎を築いた重要な符号化方式であり、その歴史的意義は非常に大きいです。しかし、圧縮効率の点では、より洗練された現代の符号化方式に劣るため、実用的な用途では限られています。

もう一度検索