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

问题描述：

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

我认为哈希表是最好的。我不确定你使用的语言或平台，所以通常哈希表是快速和动态的。 – c0d3Junk13 2012-02-27 20:33:36

好吧......首先我们需要知道你正在使用的平台。 Android的？ iOS版？视窗？ Linux呢？ OSX？网页或HTML？ – 2012-02-27 20:35:39

@ c0d3Junk13如何在散列表中搜索具有给定前缀的字符串？ – delnan 2012-02-27 20:37:17

答

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

答

你会发现这个线程有趣：

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

答

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

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

答

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