8

数千万ビットのビット配列を作成する情報検索アプリケーションがあります。配列内の「セット」ビットの数は、すべてクリアからすべてセットまで、大きく異なります。現在、私は単純なビット配列（java.util.BitSet）を使用しているので、各ビット配列は数メガバイトかかります。

私の計画は、最初のNビットのカーディナリティを調べてから、残りのデータ構造に使用するデータ構造を決定することです。明らかに、一部のデータ構造は非常にスパースなビット配列に適していますが、他のデータ構造はビットの約半分が設定されている場合に適しています（ほとんどのビットが設定されている場合、否定を使用してスパースなゼロのセットとして扱うことができます）。

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

ここにいくつかの制約またはヒントがあります：

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

オープンソースのJava実装を備えたものは役に立ちますが、厳密には必要ではありません。ファンダメンタルズにもっと興味があります。

4

7 に答える 7

16

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

注: ハフマン スキームは、データがランダムであっても、1/0 分布が完全に均等でない限り、うまく機能します。つまり、分布が少ないほど、圧縮率が高くなります。

最後に、ビットが本当にランダムで均等に分布している場合、Claude Shannon 氏によると、どのスキームを使用しても、ビットを大幅に圧縮することはできません。

于 2008-08-30T20:05:37.723 に答える
4

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

于 2008-09-18T01:06:15.460 に答える
2

手遅れかもしれませんが、スパースビット配列（ロスレス）や試行に基づく他のデータ型用の非常に高速でメモリ効率の高いライブラリがあります。ジュディ配列を見てください

于 2009-06-17T17:16:28.493 に答える
1

もう1つの圧縮の考え：

ビット配列が長く狂っていない場合は、ハフマンなどの繰り返しエンコーディングを使用する前に、 Burrows-Wheeler変換を適用してみてください。単純な実装では、（解凍）圧縮中にO（n ^ 2）メモリが必要になり、解凍にO（n ^ 2 log n）時間がかかります。ほぼ確実にショートカットもあります。しかし、データにシーケンシャル構造がある場合、これはハフマン符号化に本当に役立ちます。

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

于 2008-08-31T21:23:45.487 に答える
1

答えてくれてありがとう。これは、適切な方法を動的に選択するために試みるものです。

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

  • サンプルが非常に非対称である場合は、設定されたビット (または次のビットまでの距離) へのインデックスをリストに格納するだけです。
  • サンプルの対称性が高い場合は、従来のビット配列を使用し続けます。
  • サンプルが適度に対称的である場合は、InSciTekJeff が提案するハフマン コーディングのような可逆圧縮方法を使用します。

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

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

于 2008-08-31T16:23:31.197 に答える
0

あなたが本当に多くのスペースを節約することができないという簡単な組み合わせの証明：

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

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

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

于 2008-08-31T11:16:13.463 に答える
0

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

于 2008-08-31T09:58:23.073 に答える