導入
Shannon-Fano コーディングは、Claude Shannon のアイデアに基づいて Robert Fano によって開発された可逆データ圧縮アルゴリズムです。
これは、ハフマン コードとは異なり最適ではありませんが、ハフマン コードに非常によく似たプレフィックス コードを生成するエントロピー コーディングです。
原理
各シンボルが圧縮される確率は既知である必要があります。ほとんどの場合、圧縮されるデータから計算された固定確率が使用されます。次に、半適応シャノン・ファノ符号化について説明します (これには、圧縮されるデータに対して 2 つの連続したパスが必要です。最初のパスで確率を計算し、 2 番目のパスで実際に圧縮します)。圧縮するデータに依存しない固定確率を使用する ( 静的コーディング) か、圧縮の進行に応じて変化する確率を使用する (適応コーディング) ことも可能です。
圧縮されるすべてのシンボルは確率に従ってソートされ、ソートされたシンボルのセットは、2 つの部分の確率が可能な限り等しくなるように 2 つの部分に分割されます (1 つの部分が合計に等しくなる確率)。この部分のさまざまなシンボルの確率)。最初の部分のすべてのシンボルは、最初の部分のシンボルのみを考慮した 0 の後にシャノン・ファノ コードが続き、2 番目の部分のすべてのシンボルは 1 の後にシャノン ファノ コードが続きます。 2 番目の部分のシンボルのみを再帰的に考慮して Fano を作成します。パーツにシンボルが 1 つだけ含まれている場合、それは空のコード (長さ0) で表されます。
用途
ハフマン符号化はシャノン・ファノ符号化に非常に似ており、より良い結果が得られるため、後者は現在では事実上使用されなくなりました。
シャノン・ファノ符号化は、LZ77 による圧縮後に、ZIP 形式で歴史的に使用されていた内破アルゴリズムのエントロピー符号化に使用されます。 implode アルゴリズムは deflate アルゴリズムによって王位を奪われ、シャノン・ファノ符号化がハフマン符号化に置き換えられました。
ハフマン符号化との比較
シャノン・ファノ符号化アプローチはトップダウンです。アルゴリズムはシンボルのセットから開始し、単一のシンボルのみを含む部分に到達するまでこのセットを再帰的に分割します。このアプローチの欠点は、シンボルのセットとほぼ等しい確率の 2 つのサブセットを分離できない場合 (つまり、サブセットの一方の可能性が他方よりはるかに高い場合)、積コードが最適ではないことです。
ハフマン コーディングはボトムアップ アプローチを採用しています。アルゴリズムはシンボルから開始し、すべてのシンボルがグループ化されるまで、最も確率の低いシンボルをグループ化します。このアプローチにより、シンボル レベルで体系的に最適なコードを取得することが可能になります。最悪の場合は同等のシャノン ファノ コードと同じ長さで、その他の場合はすべて短くなります。
ただし、シャノン・ファノ符号化とハフマン符号化はどちらも同じ欠点があります。つまり、整数のビットでシンボルを符号化します。ビットレベルで最適な算術符号化により、シンボルを任意の数のビット (0 を含む) で符号化し、シャノン エントロピーを達成することができます。
