ハフマン符号化によって文字列が圧縮できなくなるのはどのような条件下ですか？すべてのキャラクターが同じ頻度/確率で登場するときですか？もしそうなら、これが真実であることをどのように示すことができますか？
2551 次
3 に答える
8
一連のシンボルの単純なゼロ次エントロピーを計算できます。これにより、ハフマン符号化だけで大幅な圧縮の可能性があるかどうかがわかります。（stackoverflowにmath.stackexchange.comのようなTeXフォーマットがあればいいのにと思います。ここにまともな方程式を書くことはできません。）
あなたが持っている異なるシンボルの数を数え、それをnと呼び、シンボルには1..nの番号を付けます。各シンボルの確率を計算します。これは、各シンボルが発生する回数をシーケンスの長さで割ったものであり、それをp（k）と呼びます。次に、ゼロ次コーディングで実行できる最善の方法は、シンボルあたりの平均ビット数が次の値に等しいことです。-sum（p（k）log（p（k））、k = 1..n）/ log（2）。次に、結果をlog（n）/ log（2）と比較できます。これは、すべての確率が等しい場合（ 1 / n ）の答えであり、等しくない確率でどれだけ購入できるかを確認できます。結果を、たとえば8と比較することもできます。、現在シンボルをそれぞれ1バイトとして格納している場合（この場合、n <= 256）。
ハフマンコードは、そのエントロピーと同じかそれ以上のシンボルあたりのビットを持ちます。また、ハフマンコードを受信者にどのように伝達するかを考慮する必要があります。コードを説明するある種のヘッダーが必要になりますが、これにはさらに多くのビットが必要になります。算術コードまたは範囲コードは、特に非常に長いシーケンスの場合、ハフマンコードよりもエントロピーに近づく可能性があります。
一般に、ハフマンコードだけでは、満足のいく圧縮は生成されません。100M文字の英語テキストテストファイルenwik8での簡単なテストでは、テキストのハフマンコーディングと同様に、シンボルあたり約5ビットのエントロピーが得られます。ハフマン（または算術または範囲）コーディングは、入力データの高次モデルと組み合わせて使用する必要があります。これらのモデルは、deflateまたはLZMAで使用されるLZ77、Burrows-Wheeler変換、または部分一致による予測など、単純な文字列照合にすることができます。LZ77コンプレッサー（この場合はgzip）は、シンボルあたり3ビット未満を取得します。
エントロピーを確率に結び付ける彼の公式、本質的に上記の公式が刻まれたボルツマンの墓石の写真を含めることに抵抗することはできません。
于 2012-07-22T16:36:25.080 に答える
7
2つの要因が頭に浮かびます。
- 要素の確率が類似している場合、圧縮はほとんど不可能です。
- 小さな入力（たとえば、短いテキスト）を圧縮しようとすると、ハフマンルックアップテーブル（別名辞書-圧縮ファイルをデコードする必要がありますね）を添付するオーバーヘッドが最終的なサイズになる可能性があります元の入力よりもさらに大きくなります。
于 2012-07-22T15:37:50.547 に答える
7
一言で言えば、ハフマンエンコーディングは、より可能性の高いバイナリの組み合わせに小さいビット長のコードを割り当て、可能性の低いものに長いコードを割り当てます。すべてが同じように発生する可能性がある場合、同じように長いコードが原因で短いコードによる圧縮が失われるため、実際の利点はありません。
于 2012-07-22T15:18:24.263 に答える