独自のデータストリームの圧縮

https://stackoverflow.com/questions/274196

07-07-2019
|

質問

多数の整数配列があります。それぞれの整数には数千の整数が含まれており、各整数は通常、その前の整数と同じか、1 ～ 2 ビットだけ異なります。ディスク IO を削減するために、各アレイをできるだけ小さく縮小したいと考えています。

Zlib は元のサイズの約 25% に縮小します。それはいいことですが、そのアルゴリズムがこの問題に特に適しているとは思えません。この種の情報に対してより優れたパフォーマンスを発揮する可能性のある圧縮ライブラリまたは単純なアルゴリズムを知っている人はいますか?

アップデート：zlib を xor デルタの配列に変換すると、元のサイズの約 20% に縮小されます。

解決

ほとんどの整数が実際に前のものと同じであり、シンボル間の差が通常1ビットのフリップとして表現できる場合、これはXORの仕事のように聞こえます。

次のような入力ストリームを取得します：

および出力：

ちょっとした擬似コード

compressed[0] = uncompressed[0]
loop
  compressed[i] = uncompressed[i-1] ^ uncompressed[i]

上位ビットが変更された場合でも、出力のほとんどを0に減らしました。使用する他のツールでのRLE圧縮には、これに関する実地試験があります。 32ビット整数でさらに機能し、ストリームにポップアップする根本的に異なる整数をエンコードできます。すべてがintサイズの量のままなので、ビットパッキングを自分で処理する手間が省けます。

解凍する場合：

uncompressed[0] = compressed[0]
loop
  uncompressed[i] = uncompressed[i-1] ^ compressed[i]

これには、単純なアルゴリズムであるという利点もあります。これは、XORであるため、非常に高速に実行されます。

他のヒント

ランレングスエンコーディングを検討しましたか？

またはこれを試してください：数値自体を保存する代わりに、数値間の差を保存します。 1 1 2 2 2 3 5は1 0 1 0 0 1 2になります。エンコードする必要がある数値のほとんどは非常に小さくなっています。小さな整数を保存するには、ほとんどのプラットフォームでエンコードする32ビットの整数ではなく、8ビットの整数を使用します。それはすぐそこに4倍です。それよりも大きなギャップに備える必要がある場合は、8ビット整数の上位ビットを「この数値には次の8ビットも必要です」と指定します。

これをランレングスエンコーディングと組み合わせて、データに応じてさらに優れた圧縮率を実現できます。

これらのオプションはどちらも実装するのが特に難しくなく、すべてが非常に高速で実行され、メモリがほとんどありません（bzipなどとは対照的です）。

データを前処理します。まず、バックエンドのデータ圧縮方法により適した形式にデータを可逆的に変換します。詳細は、バックエンドの圧縮方法、および（より重要なことですが）圧縮するデータに期待されるプロパティの両方に依存します。

あなたの場合、zlibはバイト単位の圧縮方法ですが、データは（32ビット？）整数になります。 zlibを自分で再実装する必要はありませんが、zlibがどのように機能するかを調べる必要があるので、簡単に圧縮可能なデータを表示する方法を理解したり、目的に適しているかどうかを判断したりできます。

Zlibは、Lempel-Zivコーディングの形式を実装しています。 JPGおよびその他の多くのユーザーは、バックエンドにハフマンコーディングを使用しています。ランレングスエンコーディングは、多くのアドホック使用で一般的です。などなど...

おそらく答えは、次のような方法で配列を事前にフィルタリングすることです。小さな PNG 画像の作成に使用されるフィルタリング. 。ここに私の頭の中に浮かんだいくつかのアイデアがあります。私はこれらのアプローチを試したことはありませんが、プレイしたい場合は興味深いかもしれません。

int をそれぞれ 4 バイトに分割します。₀, 、私₁, 、私₂, 、 ...、私_n bになる_0,0, 、b_0,1, 、b_0,2, 、b_0,3, 、b_1,0, 、b_1,1, 、b_1,2, 、b_1,3, 、...、b_n,0, 、b_n,1, 、b_n,2, 、b_n,3. 。次に、b をすべて書き出します。_私、0sの後にbが続きます_私、1s、b_私、2s、およびb_私、3s.ほとんどの場合、数値が 1 ～ 2 ビットしか違わない場合は、繰り返されるバイトの長いランが得られるはずです。ランレングスエンコーディングや zlib などを使用すると、非常にうまく圧縮されるはずです。これは、私が紹介する方法の中で私のお気に入りです。
各配列内の整数が前の整数と密接に関連している場合は、元の整数を保存し、その後に前のエントリとの差分を保存することもできます。これにより、抽出する値のセットが少なくなり、通常はより圧縮された値が得られます。形状。
さまざまなビットが異なる場合でも、大きな違いがある可能性がありますが、(通常は) 1 ビットまたは 2 ビットの違いに対応する大きな数値の違いがある可能性が高い場合は、ahebyte を作成するスキームを使用したほうがよいかもしれません。配列 - 最初の 4 バイトを使用して最初の整数をエンコードし、後続の各エントリで 0 バイト以上を使用してどのビットを反転するかを示します - バイトに 0、1、2、...、または 31 を格納します。監視員 (たとえば 32) を使用して、作業が完了したことを示します。これにより、表現に必要な生のバイト数と整数が平均して 2 に近くなる可能性があり、そのほとんどのバイトは限られたセット (0 ～ 32) から得られます。そのストリームを zlib 経由で実行すると、おそらく嬉しい驚きが得られるでしょう。

このためにbzip2を試しましたか？ http://bzip.org/

それは私にとって常にzlibよりもうまく機能しています。

ディスクIOの削減が懸念されるため、他の整数配列を参照せずに、各整数配列を個別に圧縮する必要があります。

シナリオの一般的な手法は、短いコードワードで少数の違いをエンコードできるため、違いを保存することです。多ビットの違いであるため、独自のコーディングスキームを考え出す必要があるようです。おそらく8ビットバイトを出発点として使用しています。

1ビット。完全な新しい整数が続くこと、またはこのバイトが最後の整数との差をエンコードすることを示します。
後続のバイト数が多いことを示す1ビット。同じ整数に対してより多くの単一ビットの差を記録します。
以前の整数から切り替えるビット数を記録する6ビット。

4ビット以上異なる場合は、整数を保存します。

このスキームは、完全に異なるコードも多数ある場合には適切ではない可能性があります。これらは4バイトではなく、それぞれ5バイトずつかかるためです。

＆quot; Zlibは約4倍に縮小します。＆quot; 100Kのファイルがネガティブ 300Kを占めるようになりました。それはどんな定義でもかなり印象的です:-)。私はあなたがそれを75％、つまり元のサイズの1/4に縮小することを意味すると仮定します。

最適化された圧縮の可能性の1つは、次のとおりです（32ビット整数と最大3ビットが要素ごとに変化することを想定しています）。

最初の整数（32ビット）を出力します。
ビット変更の数を出力します（n = 0-3、2ビット）。
nビット指定子（0〜31、各5ビット）を出力します。

この圧縮の最悪のケースは、元のサイズの17/32（46.875％圧縮）に向かう傾向があるすべての整数（2 + 5 + 5 + 5ビット）の3ビットの変更です。

「次の傾向」と言います最初の整数は常に32ビットですが、まともなサイズの配列の場合、その最初の整数は無視できます。

最良のケースは、同一の整数のファイルです（すべての整数にビット変更はなく、2つのゼロビットのみ）-これは、元のサイズの2/32（93.75％圧縮）に向かう傾向があります。

連続する整数ごとに平均して2ビット異なる場合（一般的なケースです）、整数あたり2 + 5 + 5ビットが得られ、12/32または62.5％の圧縮になります。

あなたの損益分岐点（zlibが75％の圧縮を提供する場合）は、整数あたり8ビットです。

単一ビットの変更（2 + 5 = 7ビット）：遷移の80％。
ダブルビットの変更（2 + 5 + 5 = 12ビット）：遷移の20％。

これは、これを価値のあるものにするために、平均が整数ごとに1.2ビットの変更でなければならないことを意味します。

7zipを参照することをお勧めします-これは非常に寛大なライセンスであり、コードとリンクできます（ソースも利用できると思います）。

（とにかく）WindowsプラットフォームでのWinZipよりもパフォーマンスが非常に優れているため、zlibよりも優れていることに気付きました。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow