10

約 100 万のドキュメントを含む MongoDB があります。これらのドキュメントにはすべて、次のような 1 と 0 の 256 ビット ビンを表す文字列があります。

0110101010101010110101010101

理想的には、バイナリに近い一致を照会したいと思います。これは、2 つのドキュメントに次の番号がある場合を意味します。はい、これがハミング距離です。

これは現在、Mongo ではサポートされていません。そのため、アプリケーション層でやることを余儀なくされています。

したがって、これを考慮して、ドキュメント間で個々のハミング距離を比較する必要がないようにする方法を見つけようとしています。そのため、これを行う時間が基本的に不可能になります。

私はたくさんのRAMを持っています。また、Ruby には、多数のツリーを作成できる優れた gem (アルゴリズム) があるようですが、作成する必要があるクエリの数を減らすような作業を (まだ) 行うことができないようです。

理想的には、100 万件のクエリを作成し、重複に近い文字列を見つけて、それを反映するように更新できるようにしたいと考えています。

誰の考えも大歓迎です。

4

4 に答える 4

6

すべてのドキュメントをメモリに取得することになりました..（IDと文字列のサブセット）。

次に、BK ツリーを使用して文字列を比較しました。

于 2012-01-05T19:13:33.350 に答える
4

ハミング距離はメトリック空間を定義するため、O(n log n) アルゴリズムを使用して最も近い点のペアを見つけることができます。これは典型的な分割統治の性質です。

「十分な」ペアになるまで、これを繰り返し適用できます。

編集:ウィキペディアは実際にはアルゴリズムを提供していないことがわかりました。そのため、ここに 1 つの説明を示します。

編集 2:未満の距離にペアがない場合、アルゴリズムを変更してあきらめることができますn。ハミング距離の場合: 現在の再帰のレベルを単純に数えます。どのブランチでも同じレベルの何かが見つからない場合はn、あきらめます (つまり、 に入らないでn + 1ください)。1 つの次元で分割しても必ずしも の距離が得られないメトリックを使用している場合は、1あきらめる再帰のレベルを調整する必要があります。

于 2012-01-04T21:18:11.430 に答える
2

私が理解できる限り、あなたは入力文字列を持っていて、との間のハミング距離がいくつかの小さな数値よりも小さいようなX文字列フィールドを含むドキュメントをデータベースに照会したいと考えています。bXdocument.bd

=1M ドキュメントをすべてスキャンして距離を計算するだけで、線形時間でこれを行うことができますN(ドキュメントごとに一定の時間がかかります)。距離が より小さいドキュメントのみが必要なためd、文字が一致しない場合は比較をあきらめることができますd。256 文字すべてを比較する必要があるのは、それらのほとんどが一致する場合のみです。

Nドキュメントよりも少ないスキャンを試みることができます。つまり、線形時間よりも優れたものにすることができます。

をstring内ones(s)の の数と1しますs。ドキュメントごとones(document.b)に、新しいインデックス付きフィールドとして保存しますones_count。次に、1 の数が に十分近いドキュメントのみをクエリできますones(X)。具体的には、ones(X)- d<= document.ones_count<= ones(X)+dです。Mongo インデックスはここで開始する必要があります。

セット内の十分に近いペアをすべて見つけたい場合は、@ Philippeの回答を参照してください。

于 2012-01-04T22:27:48.383 に答える
1

これは、ある種のアルゴリズム問題のように聞こえます。最初に同じ数の1ビットまたは0ビットのものを比較してから、そこからリストを調べてみてください。もちろん、同じものが一番上に出てきます。大量のRAMがここで役立つとは思いません。

また、小さなチャンクを試して作業することもできます。256ビットシーケンスを処理する代わりに、32個の8ビットシーケンスとして扱うことができますか？16 16ビットシーケンス？その時点で、ルックアップテーブルの差異を計算し、それを一種のインデックスとして使用できます。

一致させたい「違い」に応じて、ソースバイナリ値の変更を並べ替え、キー検索を実行して、一致する他の値を見つけることができます。

于 2012-01-04T21:20:28.223 に答える