文本自动完成的最佳数据结构是什么? [英] What is the best data structure for text auto completion?

问题描述

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

I have a long list of words and I want to show words starting with the text entered by the user. As user enters a character, application should update the list showed to user. It should be like AutoCompleteTextView on Android. I am just curious about the best data structure to store the words so that the search is very fast.

推荐答案

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

A trie could be used . http://en.wikipedia.org/wiki/Trie https://stackoverflow.com/search?q=trie

一篇不错的文章- http://www.sarathlakshman.com/2011/03/03/implementing-autocomplete-with-trie-data-structure/

PS:如果您有一些不分支"的子序列，则可以使用基数trie来节省空间，该基数trie是一种Trie实现，在可能的情况下在节点中放置多个字符-

PS : If you have some sub-sequences that "don't branch" then you may save space by using a radix trie, which is a trie implementation that puts several characters in node when possible - http://en.wikipedia.org/wiki/Radix_tree

这篇关于文本自动完成的最佳数据结构是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！