Implements a trie data-structure (see http://en.wikipedia.org/wiki/Trie)
Typical use:
For tries without data:
t = Trie(['ab', 'ac', 'abc'])
try:
value = t.search('ac')
except KeyError, e:
print 'not found'
For tries with data:
t = Trie({'ab':'data1', 'ac':'data2', 'abc':'data3'})
data = t.search('ac')
t.assign('ac', 'data4') # changes the data associated to 'ac'
t.assign('acd', 'data5') # adds 'acd' to t and associates 'data5' to it.
Trees with data can also be constructed with lists of tuples, or generator expressions:
t = Trie([('ab',data1), ('ac', data2), ('abc', data3)])
or
t = Trie((k, data) for k in ['ab','ac',abc'])
There is a mapping type syntax for these methods:
t['ac']
is equivalent to
t.search('ac')
and
t['ac'] = 'data6'
is equivalent to
t.assign('ac', 'data6')
A trie is a tree data-structure that is used to implement associative arrays or maps from sequences to some data. Typically the keys are strings, but they can be any sequence of hashable objects.
The data is stored in the tree’s nodes, and the branches are labelled with the objects in the key sequence. Thus, searching for an item with a key k = (k_1,k_2, .., k_n) is done by following the path k from the root, and at each node i choosing the branch labelled with `k_i’.
Nodes in the tree are tuples of the form
(id, arrows, data)
where id is a unique identifier within the trie (a natural number,) arrows is a dictionary with keys being the objects labelling the arrows from the node, and values being the target nodes, i.e. a pair (key, value) in this dictionary is really a pair (obj, target-node), so there is an arrow from this node to the target node labelled obj; and data is any additional data associated with this node.
The constructor creates a new trie with the given dictionary indexed by sequences. The keys are expected to be the sequences of hashable objects and the values are the data to be stored at the end node for the corresponding sequence.
Parameters: | sequences ((sequence, ‘a) dict, where sequence is either a tuple, a list or any other sequence object, and ‘a is any type.) – A dictionary mapping sequences to values to put in the trie. |
---|
Adds the (key,value) association to the trie.
Parameters: |
|
---|
Looks for the key in the trie. It returns the data associated with the key, or raises a KeyError exception if the key is not in the trie.
Parameters: | key (hashable seq, a sequence (tuple, list, etc.) of hashable objects) – A key to search. |
---|---|
Returns: | the value object associated to the key if it is in the trie. |
Raises : | KeyError if the key is not in the trie. |