ビット配列の代替となるものは何ですか?

Question

数千万ビットのオーダーでビット配列を作成する情報検索アプリケーションがあります。アレイ内の「セット」ビットの数は、すべてクリアからすべてセットまで大きく異なります。現在、私は単純なビット配列 (java.util.BitSet)、そのため、各ビット配列は数メガバイトを必要とします。

私の計画は、最初のカーディナリティを確認することです N ビットを取得したら、残りにどのデータ構造を使用するかを決定します。明らかに、一部のデータ構造は非常にまばらなビット配列に適しており、他のデータ構造はビットのおよそ半分が設定されている場合に適しています (ほとんどのビットが設定されている場合、否定を使用してそれをまばらなゼロのセットとして扱うことができます)。

• それぞれの極端な場合、どのような構造が適しているでしょうか?
• 真ん中に何かありますか？

以下にいくつかの制約またはヒントを示します。

1. ビットはインデックス順に 1 回だけ設定されます。
2. 100% の精度が必要なので、ブルーム フィルターのようなものでは十分ではありません。
3. セットが構築された後は、「セット」ビットを効率的に反復できる必要があります。
4. ビットはランダムに分散されるため、ランレングス エンコード アルゴリズムがビット インデックスの単純なリストより優れているとは考えられません。
5. メモリ使用率を最適化しようとしていますが、速度は依然として低下します いくつかの 重さ。

オープンソースの Java 実装を使用したものは便利ですが、厳密に必要というわけではありません。私は基礎的なことにもっと興味があります。

Answer 1

データが本当にランダムでない限り そして が対称 1/0 分布を持っている場合、これは単純に可逆データ圧縮の問題となり、白黒に使用される CCITT グループ 3 圧縮に非常に類似しています (つまり、次のようになります)。バイナリ）FAX 画像。CCITT グループ 3 はハフマン符号化方式を使用します。FAX の場合、ハフマン コードの固定セットが使用されますが、特定のデータ セットに対して、データ セットごとに特定のコード セットを生成して、達成される圧縮率を向上させることができます。示唆したように、ビットに順番にアクセスするだけでよい限り、これは非常に効率的なアプローチになります。ランダム アクセスでは追加の課題がいくつか発生しますが、配列内のさまざまなオフセット ポイントへの二分探索ツリー インデックスを生成すると、目的の場所に近づいてそこからアクセスできるようになります。

注記:データがランダムであっても、1/0 分布が完全に均一でない限り、ハフマン スキームは引き続き機能します。つまり、分布が均一でないほど、圧縮率は向上します。

最後に、ビットが本当にランダムで均等に分布している場合、次のようになります。 氏クロード・シャノン, 、どのようなスキームを使用しても、大幅に圧縮することはできません。

Answer 2

ハフマンコーディングの代わりにレンジエンコーディングを使用することを強く検討します。一般に、レンジ エンコーディングはハフマン コーディングよりも効果的に非対称性を利用できますが、アルファベットのサイズが非常に小さい場合は特にそうです。実際、「ネイティブ アルファベット」が単に 0 と 1 である場合、ハフマンが何らかの圧縮を実現できる唯一の方法は、それらの記号を組み合わせることです。これはまさに範囲エンコーディングがより効果的に行うことです。

Answer 3

あなたには遅すぎるかもしれませんが、スパース ビット配列 (ロスレス) や試行に基づくその他のデータ型用の、非常に高速でメモリ効率の高いライブラリがあります。見る ジュディアレイ

Answer 4

ご回答ありがとうございます。これは、適切な方法を動的に選択するために試してみることです。

最初のものは全部集めます N 従来のビット配列でヒットし、このサンプルの対称性に基づいて 3 つの方法のいずれかを選択します。

• サンプルが非常に非対称の場合は、リストにインデックスをセットビット（または次のビットまでの距離）に保存するだけです。
• サンプルが非常に対称な場合は、従来のビット配列を使用し続けます。
• サンプルが適度に対称な場合は、Huffmanコーディングのようなロスレス圧縮方法を使用します Inscitekjeffが提案.

非対称領域、中程度領域、および対称領域の間の境界は、必要な空間とバランスがとれたさまざまなアルゴリズムによって必要とされる時間に依存します。時間と空間の相対値が調整可能なパラメータとなります。ハフマンコーディングに必要なスペースは対称性の関数であり、テストによってそれをプロファイルします。また、3 つの方法すべてをテストして、実装の所要時間を決定します。

中間の圧縮方法がリストやビット配列、あるいはその両方よりも常に優れている可能性はあります (そして実際にそう願っています)。おそらく、より高いまたはより低い対称性に適応したハフマン コードのセットを選択することで、これを促進できるかもしれません。そうすれば、システムを単純化して 2 つの方法だけを使用できます。

Answer 5

圧縮に関するもう 1 つの考え方:

ビット配列がそれほど長くない場合は、 バロウズ・ウィーラー変換 ハフマンなどの繰り返しエンコードを使用する前に。単純な実装では、圧縮 (解凍) 中に O(n^2) メモリが必要になり、解凍には O(n^2 log n) 時間がかかります。同様に、ほぼ確実にショートカットが存在します。ただし、データに何らかのシーケンシャル構造がある場合、これはハフマン エンコーディングに非常に役立ちます。

このアイデアを一度に 1 つのブロックに適用して、時間とメモリの使用量をより実用的に保つこともできます。順次読み取り/書き込みを行う場合、一度に 1 つのブロックを使用すると、データ構造の大部分を常に圧縮したままにすることができます。

Answer 6

単純な可逆圧縮が最適な方法です。検索可能にするには、比較的小さなブロックを圧縮し、ブロックの配列にインデックスを作成する必要があります。このインデックスには、各ブロックの開始ビットのビット オフセットを含めることができます。

Answer 7

実際にはスペースをあまり節約できないことを、組み合わせで簡単に証明します。

n/2 ビットの任意のサブセットが合計 n ビットのうちの 1 に設定されているとします。(n から n/2 を選択) 可能性があります。使用する スターリングの公式, 、これはおよそ 2^n / sqrt(n) * sqrt(2/pi) です。すべての可能性の可能性が等しい場合、より可能性の高い選択肢をより短い表現で与える方法はありません。したがって、log_2 (n は n/2 を選択) ビットが必要です。これは、約 n - (1/2)log(n) ビットです。

これはメモリの節約としてはあまり良いとは言えません。たとえば、n=2^20 (1 メガ) で作業している場合、約 10 ビットしか節約できません。それは価値がありません。

そうは言っても、本当に有用なデータが本当にランダムである可能性は非常に低いように思えます。データにさらに構造がある場合には、おそらくもっと楽観的な答えがあるでしょう。