按前缀搜索多个单词（trie数据结构）

Question

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

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

• 艾丽丝·琼斯
• 鲍勃·史密斯
• 鲍比·沃克
• 约翰·多伊
• （共10000个名字）

trie 数据结构允许我有效地检索以“ Bo ”开头的所有名称（因此无需迭代所有名称）。但我还想按前缀搜索姓氏，因此搜索“ Wa ”应该找到“Bobby Walker”。让事情变得复杂的是：当用户搜索“ Bo Wa ”时，也应该找到相同的名字。我怎样才能实现这个？我应该为名称的每个部分使用单独的 trie 结构吗？（以及如何合并结果）？

背景：我正在为大型地址簿（10000 多个名称）编写搜索功能。我想要一个非常快速的自动完成功能，可以在人们输入名字和姓氏的前几个字母时显示结果。我已经有一个使用正则表达式的解决方案，但它需要迭代所有名称，这会很慢。

Answer 1

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

有一个Scala 实现。