5

ランダムなビットを設定してビットマップを生成できるビットマップ圧縮アルゴリズムを探していますが、ビットマップが RAM で使用するスペースの量が心配です。

1073741824 ビット (約 10 億ビット) を保存する圧縮されていないビットマップには、約 128 MB のスペースが必要ですが、それほど多くのスペースはありません。できるだけ少ないスペース（RAM）でこれを行いたいと思います。

WAH、EWAHなど（まだ論文を注意深く読んでいません）を他の人で見ましたが、それらはストリーム圧縮であり、ビットマップの圧縮形式でビットをランダムに設定する（作成中）ことは不可能です（非常に高価な操作）。 100 番目、200 番目、300 番目を設定したい場合は機能しますが、100 番目、200 番目、105 番目、3000 番目、1999 番目を設定する必要がある場合、それは不可能です。

どのビットが設定され、どのビットが設定されていないかという情報は、私の場合、すべてのビットに対してランダムにしか取得できません。昇順に。

これは正しいですか、代替手段はありますか?

概要: ビットをランダムに設定しながら圧縮ビットマップを作成するアルゴリズム。エントロピー/パターン情報はありません。配布は何でも構いません。

目的: メモリを節約するための最適なアルゴリズム。ランダムなビットを設定することにより、ビットマップの作成中にビットマップが使用するメモリを削減します。

4

2 に答える 2

4

Roaring ビットマップで良い結果が得られています: http://roaringbitmap.org/

于 2014-08-13T02:13:43.437 に答える
0

パターンが事前に知られておらず、作業メモリがほとんどない場合は、次の方法で問題ありません。

イメージを小さなセクション (線または長方形のタイル) に並べて表示します。セクションは、圧縮解除、ビットの設定、および圧縮をすばやく実行できるように、十分に小さくする必要があります。それらは、実際にエンコードするのに十分なデータをエンコーダーに提供するのに十分な大きさでなければなりません (64KB?)。Deflate や LZMA (7-zip) など、任意の圧縮アルゴリズムを使用できます。

着信ビットを一時的にリストに入れます。そのリストがいっぱいになったら (おそらく 1MB のスペースが取られますか?)、ビットをビットマップのセクションにコピーする必要があります。その後、リストをクリアできます。このリストは、セクションごとに多くの更新を 1 つの解凍/圧縮サイクルにまとめることを可能にする単なる一時的なバッファーです。

ビットを書き出す前に、セクションと位置でソートします。これにより、重複をクリアし、すべてのセクションを一度に処理できます。

圧縮が可能であることさえ保証できないことに注意してください。圧縮可能なパターンがなければ、圧縮することはできません。

于 2013-10-12T12:46:10.747 に答える