6

私は1億以上の文字列のセットを持っており、それぞれの長さは最大63文字です。ディスク容量が多く、メモリが非常に少ない（512MB）。存在のみを照会する必要があり、追加のメタデータは保存しません。

私の事実上の解決策はBDBbtreeです。望ましい選択肢はありますか？私はleveldbとKyotoCabinetを知っていますが、利点を特定するのに十分な知識がありません。

4

2 に答える 2

5

誤検知が許容される場合、考えられる解決策の1つは、ブルームフィルターを使用することです。ブルームフィルターはハッシュテーブルに似ていますが、1つのハッシュ値を使用してバケットのテーブルにインデックスを付ける代わりに、複数のハッシュを使用してビット配列にインデックスを付けます。それらのインデックスに対応するビットが設定されます。次に、文字列がフィルター内にあるかどうかをテストするために、文字列が再度ハッシュされ、対応するインデックスが設定されている場合、文字列はフィルター内にあります。

文字列に関する情報は保存されないため、メモリの使用量はごくわずかですが、2つの文字列が衝突した場合、衝突を解決することはできません。これは、誤検知が発生する可能性があることを意味します（フィルターにない文字列は、フィルターにある文字列と同じインデックスにハッシュされる可能性があるため）。ただし、フォールスネガティブはあり得ません。実際にセットに含まれている文字列はすべて、ブルームフィルターで検出されます。

Pythonの実装がいくつか あります。自分でロールするのも難しくありません。かなりうまく機能したsを使用して、すばやく汚れたブルームフィルターを自分でコーディングしたことを思い出します。 bitarray

于 2012-11-15T20:47:02.470 に答える
1

ディスクがたくさんあると言いましたよね？1 つのオプションは、ネストされたサブディレクトリにファイル名として文字列を保存することです。文字列を直接使用することもできます。

  • 「ドリュー シアーズ」を格納するd/r/e/w/ sears

または、文字列のハッシュを取得し、同様のプロセスに従います。

  • MD5('シアーズを描いた') = 'f010fe6e20d12ed895c10b93b2f81c6e'
  • という名前の空のファイルを作成しますf0/10/fe/6e/20d12ed895c10b93b2f81c6e。

OS に最適化された、ハッシュ テーブル ベースのインデックス付き NoSQL データベースと考えてください。

副次的な利点:

  • 後で気が変わって、データをファイルに保存することができます。
  • rsync を使用して、データベースを別のシステムに複製できます。
于 2012-11-15T21:00:41.807 に答える