什么是文本自动完成的最佳数据结构？

Question

我有一长串单词，我想显示以用户输入的文字开头的单词。当用户输入一个字符时，应用程序应该更新显示给用户的列表。它应该像Android上的AutoCompleteTextView。我只是很好奇存储单词的最佳数据结构，因此搜索速度非常快。

Answer 1

可以使用trie。 http://en.wikipedia.org/wiki/Triehttps://stackoverflow.com/search?q=trie

一个很好的文章 - http://www.sarathlakshman.com/2011/03/03/implementing-autocomplete-with-trie-data-structure/

PS：如果你有一些子序列，即“不分支”，那么你可以通过使用基数线索，这是一个索引树的实现，使一些节省空间在节点的字符可能的情况下 - http://en.wikipedia.org/wiki/Radix_tree

Answer 2

你会发现这个线程有趣：

• String similarity algorithms?

这不完全是你想要的，而是它的一个稍微扩展的问题。

Answer 3

为了实现自动完成功能，三元搜索树（TST）也可用于：

http://igoro.com/archive/efficient-auto-complete-with-a-ternary-search-tree/

但是，如果你想找到一个字符串中的任何随机字符串，尝试广义后缀树。

http://en.wikipedia.org/wiki/Generalised_suffix_tree

Answer 4

尝试次数（及其各种变种）是有用的在这里。关于这个主题的更详细的处理是在这个paper。也许你可以实现Android的完成trie？