シャノンの情報源コーディング定理から、圧縮された文字列のエントロピーは、次のように元の文字列のエントロピーによって制限されることがわかります。
H(X) <= L < H(X) + 1/N
ここで、H（X）はソース文字列のエントロピー、Nはソース文字列の長さ、Lは圧縮された文字列の予想される長さです。
これは必然的に、可逆圧縮に制限があることを意味します。
私が知りたいのは：
エントロピーを予想される圧縮率に直接関連付けることはできますか？
エントロピーを使用して、圧縮率の上限を見つけることができますか？
シャノンの定理は、ランダム データと確率に関して定義されます。同様に、文字列のエントロピーは、ランダムな文字列に対してのみ定義されます。エントロピーは、文字列自体ではなく、分布のプロパティです。したがって、シャノンの定理を非公式に次のように言い換えることができます。
特定の確率分布から文字列をランダムに選択した場合、その文字列に対して取得できる最適な平均圧縮率は、確率分布のエントロピー レートによって決まります。
任意のランダムな文字列が与えられた場合、その文字列を 1 ビットに圧縮する圧縮アルゴリズムを簡単に書くことができますが、私のアルゴリズムは必然的に他の文字列の長さを増加させます。私の圧縮アルゴリズムは次のように機能します。
対応する解凍アルゴリズムは次のとおりです。
ここで重要なのは、特定のディストリビューションのすべての文字列を平均して高い速度で圧縮する1 つのアルゴリズムを書き留めることはできないということです。文字列が多すぎます。
文字列の特定の確率分布がある場合、分布のエントロピー率を計算できます。次に、分布に従って文字列をランダムに選択し、任意のアルゴリズムを使用して圧縮しようとすると、圧縮された文字列の相対的なサイズは次のようになります。平均であり、エントロピー率を下回ることはありません。これがシャノンの定理です。
はい。英語のエントロピー レートは、1 文字あたり 1.5 ビット (ギブ オア テイク) とよく言われます。一般的なエンコーディングでは、1 文字あたり 8 ビットが使用されます。したがって、最大に圧縮されたテキストは、元のサイズの 1.5/8 (~19%) になるはずです。Jane Austin の高慢と偏見のプレーン テキスト バージョンの実際の結果: orig = 701K、bzip2 = 178K、約 25%。
ソース文字列の長さを知らずにエントロピーを圧縮率に直接関連付けることはできませんが、L の可能な限り小さい値を解くことによって、最大圧縮率の理論上の限界を確認できます。圧縮アルゴリズムの効率。ただし、メトリックが悪いからといって、より優れたアルゴリズムが発見された、または存在することを意味するわけではありません。
あ、はい。エントロピーを使用して、理論上の最大ロスレス圧縮率を見つけることができますが、それを使用して、特定の圧縮アルゴリズムの予想される圧縮率を決定することはできません。
はい！この論文はあなたを正しい方向に導くと思います。
ETA実際の論文を読むには、IEEE のメンバーになる必要があるようです。誰かが公に利用可能なリソースを見つけることができれば (またはここで数学を説明することができれば)、もちろんそれははるかに良いでしょう!