Trie 字典查找

Question

刚看完http://ejohn.org/blog/javascript-trie-performance-analysis/

我有用户名和姓氏字典

Alex Woha
Mike Ivanov 
Donald Duck
Alex Wolf
John Wolf

等等。假设用户输入了单词

Wolf

我要给他推荐下一个

Alex Wolf
John Wolf

如果他输入

Wolf Al or Alex Wol

我只能建议

Alex Wolf

词典很大，所以我更愿意使用trie 或dawg。我该如何解决这个问题？

Answer 1

您正在寻找的是基于前缀的特里树。并非所有的 trie 实现都这样做（john resig 的实现就是其中之一）。幸运的是，node natural 的 trie 实现可以。来自文档：

Tries are a very efficient data structure used for prefix-based searches. Natural comes packaged with a basic Trie implementation which can support match collection along a path, existence search and prefix search.

在这里查看 https://github.com/NaturalNode/natural#tries

Answer 2

所以，我通过使用 ngram 索引解决了这个问题（这是我的 implementation）

Trie 字典查找

Trie dictionary lookups

javascript

dictionary

trie