3

私は約100万の名前と住所を持つデータベースを持っています。このデータベースは、Webページでの「GoogleSuggest」のようなインスタント検索のために公開する必要があります。これを達成するのに役立つ効率的なアルゴリズム/データ構造を探しています。

TrieまたはGeneralizedSuffixTreeを使用するよりもこれを難しくしているのは、一部の名前が省略されたクエリをサポートする必要があることです。たとえば、ユーザーが「Elvis Pr」と入力した場合は、「ElvisAaronPresley」を提案する必要があります。

インデックス全体をメモリに格納したいと思っています（これに使用するRAMは約4GBです）。

アプリケーションはJavaで記述されているため、Javaベースのライブラリへのリンクは非常に役立つと見なされます。LuceneとMG4Jを少し調べてきましたが、問題にどのタイプのインデックスを使用できるかわかりません。

4

4 に答える 4

2

おそらく、実際に必要なのは、ユーザーが入力した各単語を連絡先の単語のプレフィックスとして表示する必要がある検索です。これは、一般的な部分文字列検索よりも少し簡単で高速です。

  1. 任意の連絡先に属するすべての単語の単一のソートされた配列を作成し、各単語の横に「連絡先ID」フィールドを格納します（例：[Aaron / 1、Aleksander / 2、Blomskøld/ 2、Elvis / 1、Presley / 1]）。
  2. ユーザーが入力した単語ごとに個別に、バイナリ検索を使用して、その単語で始まる名前の範囲を見つけます（これは、配列内のインデックスの連続した範囲である必要があります）。ユーザーは通常、キーストロークごとに1つの単語のみを調整するため、キーストロークごとにこれらの範囲の1つを再計算するだけで済みます。実際、この再計算ステップでさえ、追加の文字を入力する一般的なケースでより効率的に実行できます。これは一致する単語の範囲を狭めることしかできないからです。
  3. 最後に、連絡先IDのセットを交差させて、可能性のリストを作成します。可能性を示すために、連絡先IDでインデックス付けされ、フルネームを含む2番目の配列が必要になります。
于 2012-05-26T15:41:32.623 に答える
1

Solrは、フル機能のオートサジェスト機能OOTBを提供します。このリンクは、人気のあるクエリから生成するための背景を提供します。しかし、それを簡単に適応させて、説明するシナリオなどの先験的な知識を構築することができます。

于 2012-05-26T15:55:24.550 に答える
1

レーベンシュタインなどの文字列距離メトリックでbk-treeを使用してみることができます。http ：//blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Treesも参照してください。

編集： 距離メトリックを発明するのは難しいですが、情報の違いに基づく構造エントロピー距離と呼ばれる、使用できるものをたまたま知っています。次のように機能します。

x="ElvisPr"とy="ElvisAaronPresley"の2つの文字列を取ります

ユニグラムとバイグラムの多重集合を作成するたびに、次のようになります。

x = {e, l, v, i, s, _, p, r, el, lv, vi, is, s_,  _p, pr}
y = {ex3, lx2, v, i, sx2, _x2, ax2, rx2, o, n, p, y, el, lv, vi, is, s_, _a, aa, ar, ro, on, n_, _p, pr, re, es, sl, le, ey}

今両方にあるそれらの用語のために

{e, l, v, i, s, _, p, r, el, lv, vi, is, s_, _p, pr}

製品を計算する(f_x(t) / (f_x(t) + f_y(t)))^{f_x(t)/2} * (f_y(t) / (f_x(t) + f_y(t)))^{f_y(t)/2} ので

e  = ((1/15) / (1/15 + 3/37))^(1/30) * ((3/37) / (1/15 + 3/37))^(3/74)
l  = ((1/15) / (1/15 + 2/37))^(1/30) * ((2/37) / (1/15 + 2/37))^(2/74)
v  = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)
i  = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)
s  = ((1/15) / (1/15 + 2/37))^(1/30) * ((2/37) / (1/15 + 2/37))^(2/74)
_  = ((1/15) / (1/15 + 2/37))^(1/30) * ((2/37) / (1/15 + 2/37))^(2/74)
p  = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)
r  = ((1/15) / (1/15 + 2/37))^(1/30) * ((2/37) / (1/15 + 2/37))^(2/74)
el = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)
lv = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)
vi = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)
is = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)
s_ = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)
_p = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)
pr = ((1/15) / (1/15 + 1/37))^(1/30) * ((1/37) / (1/15 + 1/37))^(1/74)

これらすべてを掛け合わせると、[0.5、1]の範囲の数値が得られるはずです。これにより、2を掛けて1を引くことにより、これを[0,1]の範囲にさらに便利にスケーリングできます。

ただし、これは離散距離メトリックではないため、 vpツリーなどの別のメトリックインデックスを使用する必要があります

于 2012-05-26T12:05:53.607 に答える
1

Cleoを見てください。非常によく似たユースケースがあるようです。ブルームフィルターを使用してプレフィックスを検索し、転送インデックスを使用して誤検知を削除します。

于 2012-05-28T07:11:18.947 に答える