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

T

tak

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
 
D

Dan Andrews

tak said:
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
- - - - - - - - - - - - - - - - - - - - - - - - -
 
G

Gordon Beaton

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
 
H

Hendrik Maryns

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dan Andrews schreef:
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-----
 
P

Patricia Shanahan

Hendrik said:
-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Dan Andrews schreef:

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
 
S

Simon Brooke

tak said:
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.
 
W

Wibble

Simon said:
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...
 

Ask a Question

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

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,744
Messages
2,569,483
Members
44,903
Latest member
orderPeak8CBDGummies

Latest Threads

Top