hashtable - select by wilecard... is it doable?

Discussion in 'Java' started by tak, Sep 27, 2006.

  1. tak

    tak Guest

    Hi,

    What is a data structure out there, that you can select by wilecard,
    and also have fast retrievals?

    like, if i have 4 keys, JOHN, JONATHAN, JOAN, TOM., and I want to do a
    getKey by, "JO*", and that would return the values for the one that
    matches JO* as either array, set, collection..etc...

    thanks,
    T
    tak, Sep 27, 2006
    #1
    1. Advertising

  2. tak

    Dan Andrews Guest

    tak wrote:
    > Hi,
    >
    > What is a data structure out there, that you can select by wilecard,
    > and also have fast retrievals?
    >
    > like, if i have 4 keys, JOHN, JONATHAN, JOAN, TOM., and I want to do a
    > getKey by, "JO*", and that would return the values for the one that
    > matches JO* as either array, set, collection..etc...
    >
    > thanks,
    > T
    >


    If you are only concerned about matching the first few characters
    (starts with JO) then would a TreeSet<String> (that I refer to a treeSet
    below) work?

    SortedSet<String> tailSet = treeSet.tailSet("JO");
    TreeSet<String> matchingSet = new TreeSet<String>();
    for (String s : tailSet) {
    if (!s.startsWith("JO")) {
    break;
    }
    matchingSet.add(s);
    }
    return matchingSet;

    Just and idea and not sure if it is what you need.

    Cheers,

    Dan Andrews
    - - - - - - - - - - - - - - - - - - - - - - - - -
    Ansir Development Limited http://www.ansir.ca
    - - - - - - - - - - - - - - - - - - - - - - - - -
    Dan Andrews, Sep 28, 2006
    #2
    1. Advertising

  3. On 27 Sep 2006 15:01:47 -0700, tak wrote:
    > What is a data structure out there, that you can select by wilecard,
    > and also have fast retrievals?
    >
    > like, if i have 4 keys, JOHN, JONATHAN, JOAN, TOM., and I want to do a
    > getKey by, "JO*", and that would return the values for the one that
    > matches JO* as either array, set, collection..etc...


    If you only need to match key prefixes, then use a radix tree (or one
    of the many variants). In a radix tree, the key describes a path from
    the root of the tree to the corresponding object.

    When you follow the path described by a given prefix, you arrive at a
    node whose key matches the prefix exactly, and whose entire subtree
    consists of nodes whose keys start with that prefix.

    /gordon

    --
    [ don't email me support questions or followups ]
    g o r d o n + n e w s @ b a l d e r 1 3 . s e
    Gordon Beaton, Sep 28, 2006
    #3
  4. -----BEGIN PGP SIGNED MESSAGE-----
    Hash: SHA1

    Dan Andrews schreef:
    > tak wrote:
    >> Hi,
    >>
    >> What is a data structure out there, that you can select by wilecard,
    >> and also have fast retrievals?
    >>
    >> like, if i have 4 keys, JOHN, JONATHAN, JOAN, TOM., and I want to do a
    >> getKey by, "JO*", and that would return the values for the one that
    >> matches JO* as either array, set, collection..etc...
    >>
    >> thanks,
    >> T
    >>

    >
    > If you are only concerned about matching the first few characters
    > (starts with JO) then would a TreeSet<String> (that I refer to a treeSet
    > below) work?
    >
    > SortedSet<String> tailSet = treeSet.tailSet("JO");
    > TreeSet<String> matchingSet = new TreeSet<String>();
    > for (String s : tailSet) {
    > if (!s.startsWith("JO")) {
    > break;
    > }
    > matchingSet.add(s);
    > }
    > return matchingSet;
    >
    > Just and idea and not sure if it is what you need.


    He probably needs a TreeMap<String,Something>, but the principle remains
    the same.

    H.
    - --
    Hendrik Maryns
    http://tcl.sfs.uni-tuebingen.de/~hendrik/
    ==================
    http://aouw.org
    Ask smart questions, get good answers:
    http://www.catb.org/~esr/faqs/smart-questions.html
    -----BEGIN PGP SIGNATURE-----
    Version: GnuPG v1.4.2 (GNU/Linux)

    iD8DBQFFG4NZe+7xMGD3itQRAns3AJ0ba/FB9Wbis3hk8KkWJKSeaIXg5wCeKf0Z
    rWHF0ck07J84YLkd9hRSoy4=
    =xeVU
    -----END PGP SIGNATURE-----
    Hendrik Maryns, Sep 28, 2006
    #4
  5. Hendrik Maryns wrote:
    > -----BEGIN PGP SIGNED MESSAGE-----
    > Hash: SHA1
    >
    > Dan Andrews schreef:
    >> tak wrote:
    >>> Hi,
    >>>
    >>> What is a data structure out there, that you can select by wilecard,
    >>> and also have fast retrievals?
    >>>
    >>> like, if i have 4 keys, JOHN, JONATHAN, JOAN, TOM., and I want to do a
    >>> getKey by, "JO*", and that would return the values for the one that
    >>> matches JO* as either array, set, collection..etc...
    >>>
    >>> thanks,
    >>> T
    >>>

    >> If you are only concerned about matching the first few characters
    >> (starts with JO) then would a TreeSet<String> (that I refer to a treeSet
    >> below) work?
    >>
    >> SortedSet<String> tailSet = treeSet.tailSet("JO");
    >> TreeSet<String> matchingSet = new TreeSet<String>();
    >> for (String s : tailSet) {
    >> if (!s.startsWith("JO")) {
    >> break;
    >> }
    >> matchingSet.add(s);
    >> }
    >> return matchingSet;
    >>
    >> Just and idea and not sure if it is what you need.

    >
    > He probably needs a TreeMap<String,Something>, but the principle remains
    > the same.


    If it gets any more complicated than a TreeMap, it may be worth
    separating the find-the-key-set problem from the map.

    Patricia
    Patricia Shanahan, Sep 28, 2006
    #5
  6. tak

    Simon Brooke Guest

    in message <>, tak
    ('') wrote:

    > What is a data structure out there, that you can select by wilecard,
    > and also have fast retrievals?
    >
    > like, if i have 4 keys, JOHN, JONATHAN, JOAN, TOM., and I want to do a
    > getKey by, "JO*", and that would return the values for the one that
    > matches JO* as either array, set, collection..etc...


    It's doable, but it wouldn't be pretty or efficient:

    Vector result = new Vector();

    Enumeration foo = hash.keys();

    while ( foo.hasMoreElements())
    {
    String bar = foo.nextElement().toString();

    if ( bar.indexOf( pattern) > -1)
    {
    result.append( hash.het( bar);
    }
    }

    return result;

    If you want to go down this route you lose all the benefits you got from
    the hashtable in the first place. But if you do want to go down it I
    suggest it would be more flexible if you allowed regular expression rather
    than just substring matching.

    --
    (Simon Brooke) http://www.jasmine.org.uk/~simon/
    ;; We don't just borrow words; on occasion, English has pursued other
    ;; languages down alleyways to beat them unconscious and riffle their
    ;; pockets for new vocabulary -- James D. Nicoll
    Simon Brooke, Sep 29, 2006
    #6
  7. tak

    Wibble Guest

    Simon Brooke wrote:
    > in message <>, tak
    > ('') wrote:
    >
    >> What is a data structure out there, that you can select by wilecard,
    >> and also have fast retrievals?
    >>
    >> like, if i have 4 keys, JOHN, JONATHAN, JOAN, TOM., and I want to do a
    >> getKey by, "JO*", and that would return the values for the one that
    >> matches JO* as either array, set, collection..etc...

    >
    > It's doable, but it wouldn't be pretty or efficient:
    >
    > Vector result = new Vector();
    >
    > Enumeration foo = hash.keys();
    >
    > while ( foo.hasMoreElements())
    > {
    > String bar = foo.nextElement().toString();
    >
    > if ( bar.indexOf( pattern) > -1)
    > {
    > result.append( hash.het( bar);
    > }
    > }
    >
    > return result;
    >
    > If you want to go down this route you lose all the benefits you got from
    > the hashtable in the first place. But if you do want to go down it I
    > suggest it would be more flexible if you allowed regular expression rather
    > than just substring matching.
    >

    You could use a String Trie such as describe in links below. You'll
    probably have to write a walking pattern matcher but its not rocket science.

    http://www.limewire.org/nightly/javadocs/com/limegroup/gnutella/util/TrieSet.html

    http://en.wikipedia.org/wiki/Patricia_trie

    http://www.cs.duke.edu/~ola/courses/cps108/fall96/joggle/trie/Trie.java

    http://www.koders.com/java/fid0F06E53F2CFCC6E591C38752F355A7178F92FFE5.aspx

    http://www.stylusstudio.com/api/fop-0.20.5/org/apache/fop/layout/hyphenation/TernaryTree.htm
    etc...
    Wibble, Oct 1, 2006
    #7
    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. Rene Pijlman

    2.3 on Debian Woody: doable?

    Rene Pijlman, Oct 25, 2003, in forum: Python
    Replies:
    7
    Views:
    337
    Jan Dries
    Oct 26, 2003
  2. darrel
    Replies:
    5
    Views:
    352
    Plamen Ratchev
    Dec 29, 2006
  3. Replies:
    3
    Views:
    302
    Jim Langston
    Oct 31, 2007
  4. fkallgren

    Is this doable

    fkallgren, Mar 21, 2008, in forum: Python
    Replies:
    7
    Views:
    315
    Tobiah
    Mar 24, 2008
  5. s.eng.ashraf

    Is it doable,

    s.eng.ashraf, May 23, 2008, in forum: C++
    Replies:
    6
    Views:
    380
    Vincent Jacques
    May 24, 2008
Loading...

Share This Page