非常に短い数値/バイナリ文字列の圧縮を知っている人はいますか?
たとえば、任意の数値 (0 ～ 9) または 3、2、6、4 のバイナリを圧縮したい、
または
2、1、3、6、1、4、13 の数値またはバイナリを圧縮したい
ピック 4 とユーロミリオンズの調査に適用されます。
質問する
159 次
1 に答える
0
EuroMillions と Pick 4 を調べました。前者は 1 ～ 50、後者は 0 ～ 9 の範囲であることがわかります。どの数も同じ確率であると仮定できると思います (一部の圧縮方式では、特定の数が他の数よりも発生する可能性が高いという事実を利用しています)。
どのプラットフォームでコーディングしていますか? Python や JavaScript のような高級言語ですか? それとも C や C++ のような低レベル言語ですか? 多数の数列を保存したいと考えていますか? それとも、効率的なインメモリ表現を考え出そうとしているだけですか?
メモリ内の大きなセットを操作する場合に行うことができる最も合理的なトレードオフは、各文字が 1 バイトを超えないようにすることです (0 ～ 255 の値を保持できます)。多くの場合、より細かい粒度のない「数値」タイプのみを持つ高レベル言語では、これを行うのが難しい場合があります。しかし、C/C++ または Java でさえ、これを行うことができるはずです。
これらの等確率の数値をディスクに大量に保存する場合は、数値を保存するのに必要な最小ビット数を調べてください。EuroMillions の場合、数値を格納するには 6 ビットが必要です (2^6 = 64)。次に、数値ごとに 2 ビットを節約するために、それらをビットストリームに格納します。Pick 4 を使用すると、2 つの数値を 1 バイトにエンコードできます。
于 2013-03-14T17:14:14.533 に答える