2

私はIntの非常に大きなリスト(おそらくlarge ) を使用して Scala に取り組んでおり、それらを圧縮してメモリに保持する必要があります。

唯一の要件は、リストの残りの部分に触れることなく、作業するリストの最初の番号をプル (および圧縮解除) できることです。

私には多くの良いアイデアがありますが、それらのほとんどは数値をビットに変換します。例：

タプル |log(x)|,x-|log(x)| として任意の数値xを記述できます。最初の要素は 1 と末尾の 0 の文字列 (単項コード) として右に並べ、2 番目の要素はバイナリで表します。例えば：

1 -> 0,1 -> 0 1

...

5 -> 2,1 -> 110 01

...

8 -> 3,0 -> 1110 000

9 -> 3,1 -> 1110 001

...

Int は固定の 32 ビットのメモリと long 64 ビットを使用しますが、この圧縮ではxはストレージに2log(x)ビットを必要とし、無限に大きくなる可能性があります。ほとんどの場合、この圧縮によりメモリが削減されます。

このような種類のデータをどのように処理しますか? bitarray とか何かありますか？

そのようなデータを Scala で圧縮する他の方法はありますか?

ありがとう

4

1 に答える 1

2

データセットのまばらさと範囲によっては、データを数値ではなくデルタのリストとして保持する場合があります。たとえば、これはサウンド圧縮に使用され、必要に応じて非可逆または可逆の両方にすることができます。

たとえば、Int数値はあるが、(符号付き)Byte離れていることはほとんどないとわかっている場合は、次のバイトのリストのようにすることができます。

-1           // Use -1 to imply the next number cannot be computed as a byte delta
0, 0, 4, 0   // 1024 encoded as bytes
1            // 1025 as a delta
-5           // 1020 as a delta
-1           // Next number can't be computed as a byte delta
0, 0, -1, -1 // 65535 encoded as bytes -- -1 doesn't have special meaning here
10           // 65545 as a delta

したがって、この特定のエンコーディングを使用してビットを処理する必要はありません。しかし、実際には、特定の問題やデータの特性などを明確に示さなければ、良い答えは得られません。

あなたの質問を読み直すと、データをビットに変換する圧縮技術を破棄していないようです。そうでない場合は、Huffman (必要に応じて予測) または Lempel-Ziv ファミリーの何かをお勧めします。

残念ながら、Scala にはバイナリ データを処理するためのライブラリがありません。paulp はおそらくコンパイラ自体にそのようなものを持っていますが。

于 2010-06-29T14:34:00.977 に答える