理論的に証明された最適な圧縮アルゴリズムはありますか？

Question

ハフマンコーディングです いつも シャノンのアイデアを使用しているので最適ですか？テキスト、画像、ビデオ、...圧縮はどうですか？

この主題はまだ現場で活動していますか？どのような古典的または最新の参照を読むべきですか？

Answer 1

Huffmanコーディングは、すべてのシンボルの確率が独立しており、事前に知られているシンボル間コーディングに最適です。ただし、これらの条件が満たされていない場合（画像、ビデオのように）、LZW、JPEGなどの他のコーディング手法が使用されます。詳細については、Khalid Sayoodによる「Data Compressionの紹介」という本をご覧ください。

Answer 2

いくつかのシナリオで最適なLempel-ZIVアルゴリズムのバージョンがあります。つまり、入力がエルゴジックマルコフ連鎖から来る場合、Lempel-ZIVアルゴリズムの漸近速度はエントロピーに等しくなります。詳細については、CoverとThomasの第13章をご覧ください。

Answer 3

通常、実際のファイルには適用されない特定の仮定を伴うハフマン圧縮は、最適であることが証明されます。

いくつかの圧縮アルゴリズムは、いくつかの種類のファイルを圧縮します ハフマンアルゴリズムよりも小さい, したがって、ハフマンは最適ではありません。これらのアルゴリズムは、Huffmanの最適性の証明の警告のどちらかを悪用します。

（a）各シンボルを整数数のビットで独立してコーディングし、（b）各シンボルは、送信する他のシンボル（相互情報、統計的に独立していないなど）と「無関係」であり、（c）受信者は、可能なすべてのシンボルの確率分布を知っているため、ハフマン圧縮は最適です（最小圧縮ファイルを生成します）。

（a）シンボルごとのシンボル：各入力シンボルを整数数としてエンコードする必要があるというバイナリハフマン制限をリラックスすることにより、範囲コーディングなどのいくつかの圧縮アルゴリズムは、標準のハフマンよりも悪く、通常は優れています。

（b）無関係なシンボル：ほとんどの実際のデータファイルには、シンボル間に相互情報があります。シンボルを「非関連」し、これらの逆相関記号でハフマンアルゴリズムを使用することにより、プレーンハフマンよりも優れています。

（c）既知の確率分布：通常、受信機は正確な確率分布を知らない。したがって、典型的なHuffman圧縮アルゴリズムは、最初に周波数テーブルを送信し、次に圧縮データを送信します。極地のコーディングなどのいくつかの「適応」圧縮アルゴリズムは、確率分布に収束するか、周波数テーブルを明示的に送信することなく、変化する確率分布に適応するため、ハフマンよりも優れた圧縮を得ることができます。

このようなより良いハフマン圧縮についての本や論文：

• comp.compression FAQ
• マット・マホニー。 データ圧縮が説明されました
• Ian H. Witten、Alistair Moffat、およびTimothy C. Bell。ギガバイトの管理。
• Wikibooks：データ圧縮 大まかなドラフトです
• の脚注 ウィキペディア：データ圧縮

Answer 4

最適な圧縮率は、データのエントロピーに関連しています。

ウィキペディアの記事から http://en.wikipedia.org/wiki/shannon%27s_source_coding_theorem:

N IIDランダム変数は、それぞれエントロピーH（x）を使用して、NH（x）ビットを超えて情報損失のリスクを無視できるリスクで圧縮できます。これは、Nが無限になる傾向があるためです。しかし逆に、それらがNH（x）ビットより少ないものに圧縮されている場合、情報が失われることは事実上確実です。