多数の整数配列があります。それぞれに数千の整数が含まれており、各整数は通常、その前の整数と同じか、1 ビットか 2 ビットだけ異なっています。ディスク IO を削減するために、各アレイをできるだけ小さく縮小したいと考えています。
Zlib は、元のサイズの約 25% に縮小します。それはいいことですが、そのアルゴリズムがこの問題に特に適しているとは思いません。このタイプの情報に対してより適切に実行できる圧縮ライブラリまたは単純なアルゴリズムを知っている人はいますか?
更新: xor デルタの配列に変換した後の zlib は、元のサイズの約 20% に縮小します。
ほとんどの整数が実際に前のものと同じであり、シンボル間の違いが通常 1 つのビット フリップとして表現できる場合、これは XOR の仕事のように思えます。
次のような入力ストリームを取ります。
1101
1101
1110
1110
0110
そして出力：
1101
0000
0010
0000
1000
少しの疑似コード
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 とは対照的に) 非常に少ないメモリで実行されます。
おそらく答えは、小さな PNG 画像を作成するために使用されるフィルタリングに似た方法で、配列を事前にフィルタリングすることです。ここに私の頭のすぐ上にあるいくつかのアイデアがあります。私はこれらのアプローチを試したことはありませんが、プレイする気があれば面白いかもしれません。
int をそれぞれ 4 バイトに分割すると、 i 0、 i 1、 i 2、 ...、 i 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 i,0を書き出し、その後に b i,1、b i,2、および b i,3を書き出します。秒。ほとんどの場合、数値が 1 つか 2 つしか違わない場合は、連続するバイトがうまく長く続くはずです。これは、ランレングス エンコーディングや zlib などを使用して非常にうまく圧縮されます。これは、私が紹介する方法の中で私のお気に入りです。
各配列の整数が前の整数と密接に関連している場合は、元の整数を格納し、その後に前のエントリとの差分を格納することができます。これにより、抽出する値のセットが小さくなり、通常はより圧縮されます。形。
さまざまなビットが異なる場合でも、大きな違いがある可能性がありますが、(通常) 1 つまたは 2 つのビットの違いに対応する大きな数値の違いがある可能性が高い場合は、ahebyte を作成するスキームを使用する方がよい場合があります。配列 - 最初の 4 バイトを使用して最初の整数をエンコードし、その後の各エントリに対して、0、1、2、...、または 31 をバイトに格納する、反転する必要があるビットを示すために 0 以上のバイトを使用します。完了したことを示すセンチネル (たとえば 32) を使用します。これにより、表現するために必要な生のバイト数と、平均で 2 に近い整数になる可能性があり、ほとんどのバイトは限定されたセット (0 ～ 32) からのものです。そのストリームを zlib で実行すると、うれしい驚きが得られるかもしれません。
データを前処理する必要があります。最初に、バックエンドのデータ圧縮方法により適した形式にデータを可逆的に変換します。詳細は、バックエンドの圧縮方法と、(より重要なことに) 圧縮するデータに期待されるプロパティの両方に依存します。
あなたの場合、zlib はバイト単位の圧縮方法ですが、データは (32 ビット?) 整数になります。自分で zlib を再実装する必要はありませんが、zlib がどのように機能するかを読む必要があります。そうすれば、簡単に圧縮できるデータで zlib を提示する方法や、目的に適しているかどうかを判断できます。
Zlib は、ある種の Lempel-Ziv コーディングを実装しています。JPG やその他の多くは、バックエンドにハフマン コーディングを使用しています。ランレングス エンコーディングは、アドホックな用途でよく使われます。などなど・・・
「Zlib は約 4 分の 1 に縮小します。」100K のファイルがマイナス300K を占めるようになったことを意味します。それはどの定義から見てもかなり印象的です:-)。75%、つまり元のサイズの 1/4 に縮小することを意味していると思います。
最適化された圧縮の 1 つの可能性は次のとおりです (32 ビットの整数と、要素ごとに変化する最大 3 ビットを想定しています)。
この圧縮の最悪のケースは、元のサイズの 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ビットです。
これは、これを価値のあるものにするために、平均が整数あたり 1.2 ビットの変更である必要があることを意味します。
私が見ることをお勧めするのは 7zip です - これには非常に自由なライセンスがあり、あなたのコードにリンクすることができます (ソースも利用できると思います)。
Windows プラットフォームでは WinZip よりもはるかに優れたパフォーマンスを発揮するため、 zlibよりもパフォーマンスが優れている可能性があります。
これのためにbzip2を試しましたか？ http://bzip.org/
私にとっては、常にzlibよりもうまく機能しています。
あなたの懸念はディスク IO を減らすことなので、他の整数配列を参照せずに、各整数配列を個別に圧縮する必要があります。
シナリオの一般的な手法は、差分を格納することです。これは、少数の差分は短いコードワードでエンコードできるためです。おそらく次のような8ビットバイトを出発点として使用して、マルチビットの違いであるため、違いに対して独自のコーディングスキームを考え出す必要があるようです。
4 ビット以上異なる場合は、整数を格納します。
4 バイトではなく 5 バイトを使用するため、完全に異なるコードが多数ある場合、このスキームは適切ではない可能性があります。