Quick filter list

Everyone is familiar with this functionality. If you open your Outlook address book and start typing a name, the list below the search box instantly filters only items that match your query. The .NET Reflector has a similar feature when you scan the types ... you start typing, and no matter how big the main assembly you scan is, it zooms in instantly.

I was always surprised that there was a secret sauce here. How is it so fast? I suppose there are other algorithms as well if the data is present in memory or if it needs to be retrieved from some external source (i.e. DB, look for a file, etc.).

I'm not sure if this would be relevant, but if there are resources, I am especially interested in how this can be done with WinForms ... but if you know the shared resources, I am interested in the same ones :-)

+1


source to share


2 answers


What is the most common use of the trie data structure?

A Trie is basically a tree structure for storing a large list of similar strings, which allows you to quickly look up strings (like a hash table) and allows you to iterate over them alphabetically.

Image from: http://en.wikipedia.org/wiki/Trie :
alt text



In this case, Trie saves the lines:
I'm
in the
hotel
for the image tea
ten

For any prefix you enter (like 't' or 'te'), you can easily find all the words that start with that prefix. More importantly, the search depends on the length of the string, not how many strings are stored in the Trie. Read the Wikipedia article I link to to find out more.

+2


source


The process is called full text indexing / searching.



If you want to play with algorithms and data structures for this, I would recommend you read Programming Collective Intelligence for a good introduction to the field, if you just need functionality, I would recommend lucene .

+1


source







All Articles