Alex Rivera | Logout

Optimal data structure for a special dictionary

Asked 2011-09-23T11:14:37.463
10

Which data structure is best in terms of computational complexity to implement a dictionary of (key,val) items, which must support only following commands:

  1. Insert(key) - appends an item (key,val) with val=1
  2. Increment(key) - increments val of existed (key,val)
  3. Find(key) - returns a val of (key,val)
  4. Select(part_of_key) - returns a list of all items (key,val) if strstr(key,part_of_key)!=NULL in the form of a new dictionary of the same type (without allocating new memory if possible); for example if dictionary is {(red,3), (blue,4), (green,1)}, then Select(re)={(red,3), (green,1)}
  5. Max(i) - returns an item which has the i-th maximal value among all items; for example if dictionary is {(red,3), (blue,4), (green,1)}, then Max(1)=blue, Max(2)=red, Max(3)=green

The keys are strings and the values are positive integers. The number of items in the dictionary is expected to be very large.

I think it must be a synthesis of two different data structures. But should it be a hash table + a binary tree or a trie + sorted array or something else?

algorithm data-structures hash complexity-theory trie
Edit
Report

3 Answers

6

A combination of balanced tree (such as red-black tree) and suffix tree (or suffix array).

  • Balanced tree: operation 1, 2 (implemented as remove + insert), 3 and 5.
  • Suffix tree: operation 4.

NOTE: Hash table will not be able to support operation 5 efficiently.

I think you'll have a hard time implementing the suffix tree. You could possibly use Mark Nelson's C++ implementation of Ukkonen's algorithm, but it has memory leaks and is essentially a singleton, so you'll need to clean it up before being ready for production use. Even after you fix it, you'll need to adjust it so it works with your "other" data structure (which is balanced tree in my proposal) instead of one big plain string.

If you do operation 1 more frequently than operation 4 and/or you can live with linear operation 4, I recommend you skip the whole complication with the suffix tree and just traverse your data structure linearly.

answered 2011-09-23T12:22:35.537
4

For first three operation, hash table might be good idea.

For 4th operation (select part of key), you may have to write hash function differently. Yes, hash function which was used to find/calculate hash value from given key. As you want to support partial match and your key is string, you may want to use Suffix-tree or trie.

For 5th operation (ith max element), you may want to maintain heap or sorted Linked-list (or skip-list) which interacts with hash-table.

You will also have to see various use-cases and find which operation should be optimized. For exa: If you have lots of query on part_of_key operation, you should use Suffix-tree/LC-trie kind of structure and that will give good results. However, your Find operation may not be fast as it will take O(logN) instead of constant look-up.

To summarize, you need to integrate hash-table, heap and suffix tree to achieve all operations.

answered 2011-09-23T11:23:21.287
1

I think an efficient data base will be a modified trie, with bi-directional links [can go from leaves to the root and reconstruct the word], and each terminating node will have additional 'value' field.
You will also need a multimap [i.e. a map, in which each value is a set of addresses].
The keys will be arranged in a tree like, and the set of values will be hash based. [in jave, it should be something like TreeMap<Integer,HashSet<Node>>]

Pseudo-code: [well, very pseudo... it just shows the general ideas for each op].

Insert(key):
1. Insert a word into the trie
2. add the value `1` to the terminating node.
3. add the terminating field to the multimap [i.e. map.add(1,terminating_node_address)]
Increment(key):
1. read the word in the trie, and store the value from the terminating node as temp.
2. delete the entree (temp,terminating_node_address) from the multimap.
3. insert the entree (temp+1,terminating_node_address) to the multimap.
4. increase the value of the terminating node's address by 1.
Find(key):
1. find the terminating node for the key in the trie, return its value.
Select(part_of_key):
1. go to the last node you can reach with part_of_key.
2. from this node: do BFS and retrieve all possible words [store them in an empty set you will later return].
Max(i):
1. find the i'th biggest element key in the multimap.
2. choose an arbitrary address, and return get the relevant terminating word node.
3. build the string by following the uplinks to the root, and return it.

complexities:
let n be the number of strings, k be the maximum value, and S a string's length.
Insert: O(S) [trie insertion is O(S)]. The smallest element (1) in the map can be cached, and thus can be access at O(1).
Increment: O(S+logk): find the string in a

answered 2011-09-26T13:40:56.843

Your Answer