data structure to support lookup based on full key or part of key

Question

I need to be able to lookup based on the full key or part of the key..

e.g. I might store keys like 10,20,30,40 11,12,30,40, 12,20,30,40

I want to be able to search for 10,20,30,40 or 20,30,40

What is the best data structure for achieving this..best for time.

our programming language is Java..any pointers for open source projects will be appreciated..

Thanks in advance..

Answer 1

If those were the actual numbers I'd be working with, I'd use an array where a given index contains an array of all records that contain the index. If the actual numbers were larger, I'd use a hash table employed the same way.

So the structure would look like (empty indexes elided, in the case of the array implementation):

10 => ((10,20,30,40)),
11 => ((11,12,30,40)),
12 => ((11,12,30,40), (12,20,30,40)),
20 => ((10,20,30,40), (12,20,30,40)),
30 => ((10,20,30,40), (11,12,30,40), (12,20,30,40)),
40 => ((10,20,30,40), (11,12,30,40), (12,20,30,40)),

It's not clear to me whether your searches are inclusive (OR-based) or exclusive (AND-based), but either way you look up the record groups for each element of the search set; for the inclusive search you find their union, and for the exclusive search you find their intersection.

Answer 2

Since you seen to care about retrieval time over other concerns (such as space), I suggest you use a hashtable and you enter your items several times, once per subkey. So you'd put("10,20,30,40",mydata), then put("20,30,40",mydata) and so on (of course this would be a method, you're not going to manually call put so many times).

Answer 3

Use a tree structure. Here is an open source project that might help ... written in Java :-)
http://suggesttree.sourceforge.net/