3

ZLIB特定の入力ストリームの圧縮に deflate アルゴリズムを使用する組み込みハードウェア コンプレッサー用の API のようなものを書いています。

先に進む前に、データ圧縮率について説明したいと思います。データ圧縮率は、非圧縮サイズと圧縮サイズの比率として定義されます。

ここに画像の説明を入力

通常、圧縮率は 1 より大きくなります。つまり、圧縮されたデータは通常、圧縮されていないデータよりも小さいということです。しかし、これは必ずしもそうではありません。たとえばZLIB、一部の Linux マシンで生成されたライブラリと疑似乱数データを使用すると、およそ 0.996 の圧縮率が得られます。これは、10000 バイトに圧縮された 9960 バイトを意味します。

タイプ 0 ブロックを使用してこの状況を処理することを知ってZLIBいます。このブロックでは、元の圧縮されていないデータを約 5 バイトのヘッダーで返すだけなので、最大 64KB のデータ ブロックまで 5 バイトのオーバーヘッドしか与えられません。これはこの問題のインテリジェントな解決策ですが、何らかの理由でこれを API で使用できません。この状況に対処するには、事前に追加の安全なスペースを確保する必要があります。

ここで、既知のデータ圧縮率の最小値がわかっている場合、提供する必要がある余分なスペースを簡単に計算できます。それ以外の場合は安全のために、組み込みシステムで重要になる可能性のある余分なスペースを必要以上に提供する必要があります。

データ圧縮率を計算している間、ヘッダー、フッター、非常に小さなデータセット、およびシステム固有の詳細は個別に処理しているため、気にしません。私が特に興味を持っているのは、最小サイズが 1K であり、0.99deflate アルゴリズムを使用するよりも低い圧縮率を提供できる実際のデータセットが存在することです。その場合の計算は次のようになります:
圧縮率 = 非圧縮サイズ/(ヘッダー、フッター、およびシステム固有のオーバーヘッドを除く deflate を使用した圧縮サイズ)

フィードバックをお寄せください。どんな助けでも大歓迎です。そのようなデータセットへの参照を提供できれば素晴らしいことです。

編集:
@MSalters コメントは、ハードウェア コンプレッサーが deflate 仕様に適切に従っていないことを示しており、これはマイクロコードのバグである可能性があります。

4

3 に答える 3

3

鳩の原理だから

http://en.wikipedia.org/wiki/Pigeonhole_principle

圧縮される文字列と展開される文字列が常に存在します

http://matt.might.net/articles/why-infinite-or-guaranteed-file-compression-is-impossible/

理論的には、0 のエントロピー データ (無限の圧縮率) で最高の圧縮を達成し、無限のエントロピー データ (AWGN ノイズ、つまり 0 の圧縮率) で最悪の圧縮を達成できます。

于 2013-09-24T10:23:48.507 に答える
2

deflate アルゴリズムには、ZLIB アルゴリズムと同様のアプローチがあります。これは 3 ビットのヘッダーを使用し、下位 2 ビットは00、次のブロックが長さのプレフィックス付きで格納されているが、それ以外の場合は圧縮されていないときのものです。

これは、1 バイトの入力が 6 バイト (ヘッダー 3 ビット、長さ 32 ビット、データ 8 ビット、パディング 5 ビット) になる最悪のケースであることを意味するため、最悪の比率は 1/6 = 0.16 です。

もちろん、これは最適なエンコーダーを想定しています。次善のエンコーダーは、その 1 バイトのハフマン テーブルを送信します。

于 2013-09-24T11:48:44.080 に答える