通过前缀搜索多个单词（使用Trie数据结构）

Question

我该如何使用trie（或其他数据结构或算法）来有效地通过前缀搜索多个词语？

例如：假设这是我的数据集：

• Alice Jones
• Bob Smith
• Bobby Walker
• John Doe
• （总共10000个名字）

trie数据结构使我能够有效地检索所有以"Bo"开头的名称（因此不需要遍历所有名称）。但我还想按前缀搜索姓氏，因此在搜索"Wa"时，应找到"Bobby Walker"。并且为了让事情更复杂：当用户搜索"Bo Wa"时，这也应该找到相同的名称。 我该如何实现这一点？我应该为姓名的每个部分使用单独的trie结构吗？ （如何组合结果）？

背景：我正在为一个大型地址簿（10000+个名称）编写搜索功能。 我想拥有一个真正快速的自动完成函数，可以在人们输入名字的前几个字母时显示结果。我已经有一个使用正则表达式的解决方案，但它需要遍历所有名称，速度太慢。

- compie

Answer 1

一种非常好的数据结构是 Burst Trie

这里有一个Scala实现。

- Oren Yosifon

Answer 2

您可以尝试使用反转字符串和通配符搜索的第二个trie树： http://phpir.com/tries-and-wildcards/。

- Micromega

Answer 3

我认为一个排序的数组也适合您的要求，该数组包含Person对象（它们有一个firstName和lastName字段）。假设您有一个prefix并想找到所有符合您的prefix的值。只需运行二分查找以找到第一个位置（假设是firstIndex），其中您的prefix出现在firstName上，并再找到一个位置来找到最后一个位置（lastIndex）。现在，您可以在O(lastIndex - firstIndex)中检索您的值。当您想通过lastName找到它们时，情况也是如此。当您有一个prefixFirstName和一个prefixLastName时，您可以搜索匹配prefixFirstName的区间，然后在该区间上检查匹配prefixLastName的值。总之，当您有一个或两个前缀时，您运行4次二分查找（每个搜索大约17次迭代，对于100k个名称）足够快，您可以在线性时间内检索它们。即使它不是最快的解决方案，我建议使用它，因为易于理解和编码。

- Iulian Popescu