如何使用 trie(或其他数据结构或算法)通过前缀有效地搜索多个单词?
例如:假设这是我的数据集:
- 爱丽丝·琼斯
- 鲍勃·史密斯
- 鲍比·沃克
- 李四
- (共10000个名字)
trie 数据结构使我能够高效地检索所有以“Bo”开头的名称(因此无需遍历所有名称)。但我还想通过前缀搜索姓氏,因此搜索“Wa”应该会找到“Bobby Walker”。更复杂的是:当用户搜索“Bo Wa”时,也应该找到相同的名称。我该如何实现?我应该为名称的每个部分使用单独的 trie 结构吗? (以及如何组合结果)?
背景:我正在为一个大地址簿(10000 多个名字)编写搜索功能。我想要一个非常快速的自动完成功能,可以在人们输入名字和姓氏的前几个字母时显示结果。我已经有一个使用正则表达式的解决方案,但它需要遍历所有会变慢的名称。
最佳答案
一个非常好的数据结构应该是 Burst Trie
有一个 Scala implementation .
关于algorithm - 按前缀搜索多个单词(trie 数据结构),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/37533137/