• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

Indexing strings for fast lookups

 
Ranch Hand
Posts: 782
Python Chrome Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Hi,

Imagine I have a list of Strings.

On the UI side, I want to provide an autocompletion feature such that when

the user enters the first few characters, I want to display a list of possible matches.

Since I am using JDK1.1 (j2me) which does not have the Collections data structures,

I will have to build all the relevant parts to achieve quick retrieval from either

a sorted Vector of sorted Hashtable.

Could you point me to some relevant theoretical resources on how to index strings ?

I am currently looking inside the source of Lucene to glean some ideas.

Thanks.

Regards,

P





 
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Have a look at huffman codes. While they are typically used for compression, you can also use them to build a tree, where you enter the first part of the tree and the contents of the sub-tree are all of the available completions.
 
Pho Tek
Ranch Hand
Posts: 782
Python Chrome Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Thanks David. I vaguely remember learning Huffman codes in university days. Well ... back to the books.
 
David O'Meara
Rancher
Posts: 13459
Android Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
oop, maybe just an n-ary tree.
imagine a tree where each node has (up to) 26 branches. so following branches a-n-t will show the word 'ant', but will also contain the tree showing all words starting with 'ant'
 
Author and all-around good cowpoke
Posts: 13078
6
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Huffman codes are for compact representation, not fast lookups.

I have done this sort of thing before - the technology you want is used in spell checking toolkits. Try a google search for "java spell check".

Bill

 
Ranch Hand
Posts: 98
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
Since in you are more interested in quick retrieval, you can give a look at Trie, which in cases might be better than a sorted hashtable.
 
reply
    Bookmark Topic Watch Topic
  • New Topic