3

我有一个包含大约 100 万个姓名和地址的数据库。该数据库应公开用于在网页上进行类似“Google Suggest”的即时搜索。我正在寻找一种有效的算法/数据结构来帮助我实现这一目标。

使这比仅使用Trie或Generalized Suffix Tree更困难的是，它必须支持省略某些名称的查询。例如，当用户键入“Elvis Pr”时，应建议“Elvis Aaron Presley”。

我希望在内存中获得整个索引（我有大约 4GB 的 RAM 可用于此）。

该应用程序是用 Java 编写的，因此指向基于 Java 的库的链接被认为是非常有用的。我一直在研究Lucene和MG4J，但我还没有弄清楚我可以使用哪种类型的索引来解决我的问题。

4

4 回答 4

2

也许您真正想要的是一个搜索，其中用户输入的每个单词都必须作为联系人中某个单词的前缀出现。这比一般的子字符串搜索更容易和更快。

  1. 构建属于任何联系人的所有单词的单个排序数组，并在每个单词旁边存储一个“联系人 ID”字段（例如 [Aaron/1, Aleksander/2, Blomskøld/2, Elvis/1, Presley/1]）。
  2. 对于用户键入的每个单词，分别使用二分搜索来查找以该单词开头的名称范围（这必然是数组中连续的索引范围）。由于用户通常每次击键只调整一个单词，因此您只需要在每次击键时重新计算其中一个范围 - 事实上，即使是这个重新计算步骤也可以在输入额外字母的常见情况下更有效地完成，因为这只能缩小匹配词的范围。
  3. 最后，将联系人 ID 集合相交以生成可能性列表。为了显示可能性，您将需要第二个数组，按联系人 ID 索引并包含全名。
于 2012-05-26T15:41:32.623 回答
1

您可以尝试使用带有字符串距离度量的bk-tree，例如levenshtein ，另请参阅http://blog.notdot.net/2007/4/Damn-Cool-Algorithms-Part-1-BK-Trees。

编辑： 发明距离度量很困难，但我碰巧知道一个可以使用的称为结构熵距离的度量，它基于信息差异。它的工作原理如下：

取两个字符串 x = "Elvis Pr" 和 y = "Elvis Aaron Presley"

为每个计算出一元和二元的多重集：

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-tree

于 2012-05-26T12:05:53.607 回答
1

Solr 提供了全功能的自动建议功能 OOTB。此链接提供了一些从流行查询生成的背景。但是您可以轻松地对其进行调整以构建一些先验知识，例如您描述的场景。

于 2012-05-26T15:55:24.550 回答
1

看看Cleo，它看起来你有一个非常相似的用例。他们使用 Bloom 过滤器来搜索前缀，并使用 Forward 索引来去除误报。

于 2012-05-28T07:11:18.947 回答