java - 一連の整数を圧縮するにはどうすればよいですか?

Question

-255 から +255 の範囲内のデータを含む配列があります。例: 配列は次のようになります。

  int data[]={234,56,-4,24,56,78,23,89,234,68,-12,-253,45,128};

ここでは、解凍中に順序を維持する必要があります。たとえば、第 1 項の後に 234、56 が来なければなりません。

では、繰り返しパターンが観察できない任意の数列を圧縮する方法は何ですか?

Answer 1

-255 から 255 の範囲は、511 個の値 -> 9 ビットを意味します。符号を別々に取る場合、符号は 1 ビット、値は 1 バイトです。

配列をバイト配列として記述することができます。各バイト値は、関連する int の絶対値になります。

別のゾーン (長い、またはおそらくバイト配列) に、符号ビットを格納します。

Answer 2

データにまったくパターンがない場合、有用な圧縮アルゴリズムは不可能です。気にしないでください！

もちろん、この場合、すべての数値が制限された範囲 n にあるため、ビットにパターンがあります。つまり、上位ビットはすべて 0 (正) またはすべて 1 (負) です。

したがって、合理的に効果的に圧縮したい場合は、zip などの標準的な圧縮アルゴリズムが機能します (十分な長さの数値の配列があると仮定すると)。

あるいは、9 ビットの数値を効果的に使用しているという事実を利用することもできます。したがって、数値を 9 ビット チャンクの長いストリームとして配置し、これをバイト配列に入れることで、独自の圧縮アルゴリズムを展開できます。

Answer 3

あなたの状況（繰り返しパターンが観察できない場合）では、可変長コーディングが役立つ場合があります。

たとえば、Elias ガンマ コーディングやExponential-Golomb コーディングなどです。一般的な考え方 - 小さい数値はエンコードするのに数ビットしか必要ないということです。Exp-Golomb コーディングは、H.264/MPEG-4 AVC ビデオ圧縮規格で使用されます。それを使用してシーケンスをエンコードおよびデコードするのは非常に簡単で、このコーディングの実装もそれほど難しくありません。

すべての整数をコーディングする方法は、整数 (0, 1, -1, 2, -2, 3, -3, ...) を (1, 2, 3, 4, 5, 6) にマッピングする全単射を設定することです。 、7、...) コーディング前。

例えば：

シーケンス (全単射後)は次の[ 0, 2, 5, 8, 5, 2 ]ようにエンコードされ ます。ご覧のとおり、このシーケンスには繰り返しパターンはありませんが、24 ビットのみでエンコードされています。101100110000100100110011

デコード処理の簡単な説明:

1. 入力ストリームから読み取り、先頭のゼロ ビットをカウントします (非ゼロ ビットが見つかるまで) -> zero_bits_count

2. 入力ストリームから次の( zero_bits_count + 1 )ビットを読み取る ->バイナリ

3. 2 進数を10 進数に変換する

4. 戻り値(10 進数 - 1)

1... -> no leading zeros, zero_bits_count = 0 -> read next 1 bit -> [1]... -> [1] is 1 -> 1 - 1 = 0

011... -> [0] - one leading zero, zero_bits_count = 1 -> read next 2 bits -> [11]... -> [11] is 3 -> 3 - 1 = 2

00110... -> [00] - two leading zeros, zero_bits_count = 2 -> read next 3 bits -> [110]... -> [110] is 6 -> 6 - 1 = 5

等

Answer 4

数値が基本的にランダムで一様に分布しており、順序を維持する場合、シンボルあたり約 9 ビットが最適です。9 ビットでは、単一の 9 ビット値は使用されません。つまり、2 の補数表現の -256 です。リストの終わりを示す終了記号として使用できるため、便利です。次に、とにかく必要になるリストの長さもコーディングしました。