エントロピーを可逆圧縮率

Question

から シャノンの源符号化定理 このエントロピー圧縮文字列を囲のエントロピーの元となる文字列はこのように:

H(X) <= L < H(X) + 1/N 

H(X)はエントロピーのソース文字列の長さのソース文字列、Lとさせていただく予定の長さに圧縮文字列です。

このずと限界があり可逆圧縮。

何を教えてください：

• できるのは直接関係のエントロピーを一部の予圧縮率?

• 利用できるので、エントロピーあたりの上限の圧縮率?

Answer 1

あなたは直接ソース文字列の長さを知らなくても圧縮率にエントロピーを関連付けることはできませんが、あなたは、この制限を使用することができL.の可能な最小値を解くことにより、最大圧縮率への理論的限界を見ることができますあなたの圧縮アルゴリズムの効率化のためのメトリック、悪いメトリックは、より良いアルゴリズムが発見された、あるいは存在していることを意味するものではありませんが。

だから、はい。あなたは理論上の最大可逆圧縮率を見つけるためにエントロピーを使用することができますが、いいえ、あなたは、任意の圧縮アルゴリズムのためのあなたの予想圧縮率を決定するためにそれを使用することはできません。

Answer 2

シャノンの定理によって定義されるランダムなデータ及び確率.同様に、 エントロピー 文字列が定義されたランダムな文字列のエントロピーは財産の分配は、文字列です。この枠シャノンの定理の非公式など:

の場合ランダムに選択文字列から指定の確率分布、その平均圧縮率を取得できる文字列で与えられ、エントロピー率の確率分布。

与えられてランダムな文字列で簡単に書く必要のない圧縮アルゴリズムを圧縮する文字列に1ビットが、私のアルゴリズムは必ずしも増加の長さの文字列です。私の圧縮アルゴリズムは以下のようになる:

1. 入力された場合は等しい文字列 一部の前に選ばれたランダム文字列, のときに、出力では、1ビット文字列"0"
2. そうしないと、出力はN+1ビットの文字列を"1"に続いて、入力文字列

に対応する減圧アルゴリズムは:

1. 入力された場合は"0"のときに、出力は 当社の前事前に選ばれたランダム文字列
2. そうしないと、出力を除くすべての入力ビット

のビジネスモデルでビジネスできませんので記入 一つ アルゴリズムは、すべての文字列から配布、圧縮し すべての 高率の平均値。が多すぎるという面があります。

また確率分布の文字列を計算することができ、エントロピーの配布、その場合ランダムに選文字列 に応じて流通 み圧縮する使用 他の アルゴリズムの相対的なサイズの圧縮文字列が、平均することはできないが、以下のエントロピー。これがシャノンの定理と言います。

Answer 3

はい。英語ののエントロピーレートは、の、多くの場合、文字（与えるか、または取る）あたり1.5ビットとして引用されています。典型的なエンコーディングは、文字あたり8ビットを使用します。だから、最大限に圧縮されたテキストは、元のサイズ1.5 / 8（〜19％）でなければなりません。ジェーン・オースティンの高慢と偏見のプレーンテキストバージョンのための実際の結果：ORIG = 701K、BZIP2 = 178K、〜25％のための

Answer 4

有！と思い この論文 う点では正しい方向を向いている。

ETA のように見える必要があり，会員の実績。だれかが一般に利用可能なリソース(又は説明し算引き算など余計な計算はこちら）は、どちらかというとりのコース！