如何使用trie（或其他数据结构或算法）通过前缀有效地搜索多个单词？
例如：假设这是我的数据集：
trie数据结构允许我有效地检索以“Bo”开头的所有名称（因此不会迭代所有名称）。但我也希望通过前缀搜索姓氏，因此搜索“Wa”应该找到“Bobby Walker”。并且使事情变得复杂：当用户搜索“Bo Wa”时，这也应该找到相同的名称。我该如何实现呢？我应该为名称的每个部分使用单独的trie结构吗？ （以及如何结合结果）？
背景：我正在为大型地址簿（10000多个名字）编写搜索功能。我希望有一个非常快的自动完成功能，当人们输入名字和姓氏的前几个字母时显示结果。我已经有一个使用正则表达式的解决方案，但它需要迭代所有要减慢的名称。
您可以使用反向字符串和通配符搜索尝试第二个trie：http://phpir.com/tries-and-wildcards/
一个非常好的数据结构将是Burst Trie
我认为排序的数组也适合你的要求，一个包含Person对象的数组（它们有一个firstName和一个lastName字段）。假设您有一个prefix，并希望找到适合您的prefix的所有值。只需运行二分搜索，找到你的firstIndex出现在prefix上的第一个位置（比方说是firstName），另外一个找到最后一个位置（lastIndex）。现在，您可以在O(lastIndex - firstIndex)中检索您的值。当你想通过lastName找到它们时也是如此。当你有prefixFirstName和prefixLastName时，你可以搜索prefixFirstName值匹配的区间，然后在这个区间内，你可以检查与prefixLastName匹配的值。总而言之，当你有一个或两个前缀时，你运行4次二进制搜索（每次搜索大约17次迭代，100k名称），这足够快，你可以在线性时间内检索它们。即使它不是最快的解决方案，我也建议它，因为它易于理解且易于编码。