iTunes Search Algorithm/Data Structure?

[Bill Mill]

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?

-Bill Mill
bill.mill at gmail.com
billmill.org

[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