iTunes Search Algorithm/Data Structure?

[Diez B. Roggisch]

Bill Mill schrieb:
> Hello all,
> 
> What data structure would you use to implement something analogous to
> the iTunes search? I imagine that it must be a tree of some sort, but I
> can't figure out an easy structure for it.
> 
> Requirements (in case you haven't used it):
> 
> You are given 4 rows in a list view:
> [["alpha, "beta"], ["delta", "gamma"], ["foo", "bar"], ["etc", "etc"]]
> 
> and a search text box.
> 
> Typing "a" in the list box leaves rows 0, 1 and 2 in the list box,
> because some element in each of those rows has an "a" in it. Typing
> "am" leaves only row 1, since "gamma" has the substring "am" in it.
> 
> The key here is that this works instantaneously as you type, even with
> very large lists with many elements per row. I'd like the employee list
> in my current application to be similarly filtered, but I don't quite
> see how.
> 
> Thoughts?


Use an index. You can create one for each character, tuples of 
characters and so on that are contained in a word. That makes finding 
the entries a dict lookup + throwing the results together, filtering 
doubles.

I guess you can stop using indices at 3 or 4 characters, and then 
linearily search through the rest of the possibilities linearily.

Diez