iTunes Search Algorithm/Data Structure?

Discussion in 'Python' started by Bill Mill, Aug 17, 2006.

  1. Bill  Mill

    Bill Mill Guest

    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
    Bill Mill, Aug 17, 2006
    #1
    1. Advertising

  2. 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
    Diez B. Roggisch, Aug 17, 2006
    #2
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Luis Ferrao

    DataGrid: iTunes-like incremental search

    Luis Ferrao, Jan 10, 2005, in forum: ASP .Net
    Replies:
    4
    Views:
    947
    Luis Ferrao
    Jan 10, 2005
  2. Replies:
    1
    Views:
    909
    Hywel Jenkins
    Apr 17, 2006
  3. Richard Rudie

    iTunes and XSLT

    Richard Rudie, Jan 15, 2005, in forum: XML
    Replies:
    4
    Views:
    598
    Andy Dingley
    Jan 16, 2005
  4. Jane Austine
    Replies:
    14
    Views:
    784
    Dennis Lee Bieber
    Oct 9, 2004
  5. Jane Austine
    Replies:
    2
    Views:
    454
    Changjune Kim
    Oct 5, 2004
Loading...

Share This Page