我该如何使用trie(或其他数据结构或算法)来有效地通过前缀搜索多个词语?
例如:假设这是我的数据集:
- Alice Jones
- Bob Smith
- Bobby Walker
- John Doe
- (总共10000个名字)
trie数据结构使我能够有效地检索所有以"Bo"开头的名称(因此不需要遍历所有名称)。但我还想按前缀搜索姓氏,因此在搜索"Wa"时,应找到"Bobby Walker"。并且为了让事情更复杂:当用户搜索"Bo Wa"时,这也应该找到相同的名称。 我该如何实现这一点?我应该为姓名的每个部分使用单独的trie结构吗? (如何组合结果)?
背景:我正在为一个大型地址簿(10000+个名称)编写搜索功能。 我想拥有一个真正快速的自动完成函数,可以在人们输入名字的前几个字母时显示结果。我已经有一个使用正则表达式的解决方案,但它需要遍历所有名称,速度太慢。