Velocity Reviews - Computer Hardware Reviews

Velocity Reviews > Newsgroups > Programming > Python > iTunes Search Algorithm/Data Structure?

Reply
Thread Tools

iTunes Search Algorithm/Data Structure?

 
 
Bill Mill
Guest
Posts: n/a
 
      08-17-2006
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

 
Reply With Quote
 
 
 
 
Diez B. Roggisch
Guest
Posts: n/a
 
      08-17-2006
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
 
Reply With Quote
 
 
 
Reply

Thread Tools

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off
Trackbacks are On
Pingbacks are On
Refbacks are Off


Similar Threads
Thread Thread Starter Forum Replies Last Post
Apple Itunes - "Accessing Itunes Store" hangs Richard Fangnail Computer Support 2 12-08-2007 06:51 PM
Newbie: How to I search for a song on iTunes? eBayer Computer Support 5 08-28-2007 03:42 PM
DataGrid: iTunes-like incremental search Luis Ferrao ASP .Net 4 01-10-2005 04:18 PM
search within a search within a search - looking for better way...my script times out Abby Lee ASP General 5 08-02-2004 04:01 PM



Advertisments