468,253 Members | 1,306 Online
Bytes | Developer Community
New Post

Home Posts Topics Members FAQ

Post your question to a community of 468,253 developers. It's quick & easy.

iTunes Search Algorithm/Data Structure?

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

Aug 17 '06 #1
1 1876
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
Aug 17 '06 #2

This discussion thread is closed

Replies have been disabled for this discussion.

By using this site, you agree to our Privacy Policy and Terms of Use.