多数の整数をファイルに保存する必要があります。整数の順序は重要ではないため、情報内容の合計は順序付けられたリストよりも低くなるはずです。任意に順序付けられた配列よりも、数値を格納するスペース効率の良い方法はありますか?
編集：整数は完全にランダムであると想定しています。順列を修正することによって導入される冗長な情報を絞り出す普遍的な方法を本当に探しています。
3 に答える
3
圧縮するには、実際にはより高度な情報コンテンツが必要です。通常、ランダム性を圧縮することはできません。幸いなことに、問題の仕様により、データを並べ替えることができます。したがって、データを並べ替えて、その情報コンテンツを増やすことができます。次に、整数のリストを保存する代わりに、最初の差分の最小値とシーケンスのみを保存する必要があります。最初の違いは数値自体よりも小さいため、より少ないビットに収まるはずです。
ソートされたランダムに生成されたシーケンス
sorted seq (173 218 257 490 618 638 715 815 856 929 932 996)
number of bits ( 6 6 6 7 7 7 7 7 7 7 7 7)
として保存できます
first diff (173 45 39 233 128 20 77 100 41 73 3 64)
number of bits ( 6 4 4 6 5 3 5 5 4 5 2 5)
たとえば、45 は 173 と 218 の差で、1 番目と 2 番目の要素です。これらの数値は、上記の 81 ビットに対して 54 ビットを必要とします。数字が抽出された範囲内で数値がかなり密集している場合、最初の差の最大ビット数がデータよりも低くなり、より小さな固定ビット長を使用できるようになる場合があります。固定サイズを使用しない場合は、区切り記号も格納するか、他の適応スキームを使用して、1 つの数値がどこで終了し、次の数値が始まるかを判断できるようにする必要があります。数値が比較的狭い範囲からランダムに抽出された場合に発生するように、データに多数の重複がある場合は、最初の差異のゼロをエンコードするランレングスを調べることもできます。
于 2013-01-28T01:23:14.950 に答える
1
一般的に、私はノーと言うでしょう。数値に何らかのパターンがあるか、または特異な方法で分布している場合は、それについて言及する必要があります。
于 2013-01-27T20:43:42.213 に答える