java - 在联系人数据库中快速搜索子串的算法

Question

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

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

我希望在内存中获取整个索引(我有大约 4GB 的 RAM 用于此目的)。

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

Answer 1

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

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