什麼是文本自動完成的最佳數據結構？

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？