7

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.

ipman
  • 1,212
  • 2
  • 21
  • 29
  • I think a hash table would be best. I'm not sure about the language or platform you're using, so in general hash tables are fast and dynamic. – C0D3 Feb 27 '12 at 20:33
  • well... first we need to know the platform you're working with. Android? iOS? Windows? Linux? OSX? Web or HTML? – Chase Florell Feb 27 '12 at 20:35
  • 2
    @c0d3Junk13 How would you search for strings with a given prefix in a hashtable? –  Feb 27 '12 at 20:37
  • i am not interested in how to achieve this in a specific platform. i am just curious about adata structures. – ipman Feb 27 '12 at 20:44
  • @delnan I offered hash tables as a generic data structure. Not as a solution to his problem of searching an autocomplete list. That is why it's a comment and not an answer. To answer your question, I don't think it's effective to "search" a hash table with prefixes, a DB is probably better for his case... However depending on your hash function, this is doable. http://en.wikipedia.org/wiki/Hash_table – C0D3 Mar 01 '12 at 18:21
  • 1
    @c0d3Junk13 I asked because the question is pretty clear on what's required, and since a hash table seems to have nothing in common with these requirements, I think it's completely pointless to suggest it. –  Mar 01 '12 at 18:38
  • @delnan No, hash tables are relevant and it is a valid and perfectly fine suggestion whether you like it or not. It's up to coderdem to implement or not. Ask any programmer the best way to store text data in memory that is easy and fast to access, you'll hear hash tables. Sorry that you have nothing else to do but pick on my suggestion/comment... – C0D3 Mar 01 '12 at 18:49
  • 2
    @c0d3Junk13 You don't need to tell me hash tables have plenty of good uses. But the use case of *this question* is not among them. Besides, I sure hope most programmers are aware that "the best way" to store data depends on what you need to do with it. And as we seem to agree, hash tables are not practical for searching by prefix (i.e. doing autocompletition). Oh, as for *why* I "pick on" your comment: I originally hoped your suggestion *was* useful and I merely missed it point, but you seem to confirm that isn't really the case. –  Mar 01 '12 at 19:19

4 Answers4

12

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

A nice article - http://www.sarathlakshman.com/2011/03/03/implementing-autocomplete-with-trie-data-structure/

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

Community
  • 1
  • 1
andrew cooke
  • 45,717
  • 10
  • 93
  • 143
  • Auto complete should not 100% assume your prefix is correct. Good software is more complicated. Like doing a Levenshtein on the prefix – Lothar May 17 '23 at 03:53
1

For implementation of autocomplete feature, ternary search trees(TST) are also used:

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

However, if you want to find any random substring within a string, try a Generalised suffix tree.

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

Rndm
  • 6,710
  • 7
  • 39
  • 58
1

You may find this thread interesting:

It's not exactly what you want, instead it's a slightly extended version of your problem.

Community
  • 1
  • 1
nodakai
  • 7,773
  • 3
  • 30
  • 60
0

Tries (and their various varieties) are useful here. A more detailed treatment on this topic is in this paper. Maybe you can implement a completion trie for Android?

Kedar Mhaswade
  • 4,535
  • 2
  • 25
  • 34