This module provides a compact trie (
CTrie) implementation for Python.
A compact trie. A trie, or prefix tree, is a data structure to efficiently store a set of strings with a lot of shared prefixes, like URLs.
Compact tries are recursively defined, a trie has zero or more other child tries. A trie is said to be terminal if it contains the empty string. Each child is labelled with a prefix for its own children. For example, one compact trie that contains words “foo”, “bar” and “foo42” has two children, one labelled “foo” and the other labelled “bar”. The last one is terminal because once we read “bar” we can end our walk in the trie. The first one is terminal for the same reason, but have one terminal child labelled “42”. In the following symbolic representation, a terminated child is represented with a dot at the end of its label:
<empty> | +-- bar. | +-- foo. | +-- 42.
Each possible walk in the trie, starting from the root and ending on a terminal node is a contained word. In the previous example, the empty string is not present in the trie because the root node is not terminal.
A non-compact trie contains only one char per node.
>>> from ctrie import CTrie >>> ct = CTrie() >>> c.add("foo", "bar", "qux") >>> "foo" in c True >>> "Bar" in c False >>> c.remove("foo") >>> "foo" in c False >>> len(c) 2
- Keyword arguments:
False): specifies if the trie contains the empty string. This is the same as:
>>> ct = CTrie() >>> ct.add('') # empty string
Add one or more words in the trie. The function returns
Trueif all words were successfully added. It’ll return
Falseif one or more words were already present in the trie.
>>> ct = CTrie() >>> ct.add('foo', 'bar') True >>> 'foo' in ct True >>> ct.add('bar') False >>> ct.add('qux') True
Take a dictionary in the format returned by
to_dictand build a new instance.
Compute the height of the trie. An empty trie has a zero height, and the maximum height of a compacted trie is the length of its longuest word.
>>> ct = CTrie() >>> ct.height() 0 >>> ct.add(''); ct.height() 0 >>> ct.add('foo'); ct.height() 1 >>> ct.add('bar'); ct.height() 1 >>> ct.add('boo'); ct.height() 2
New in version 0.1.0.
Trueif the trie is empty.
>>> ct = CTrie() >>> ct.is_empty() True >>> ct.add('') True >>> ct.is_empty() False
Return a pretty-printed version of the internal state of the tree. It helps understand how words are split to fit in a tree.
Remove one or more words from the trie. The function returns
Trueif all the words were successfully removed (i.e. they were in the trie before) or
Falseif one or more words couldn’t be found in the trie.
>>> ct = CTrie() >>> ct.add('foo', 'qux') True >>> 'foo' in ct True >>> ct.remove('foo', 'bar') False >>> 'foo' in ct False >>> ct.remove('qux') >>> True
Return a subtree that’s equivalent to the current one with all values stripped from the given prefix. Values that don’t start with this prefix are not included. An empty trie is returned if the prefix doesn’t match any value.
Note that the returned subtree may share its nodes with the current one.
>>> ct = CTrie() >>> ct.add('foo', 'bar', 'foobar', 'fooo', 'qux') True >>> foo = ct.subtree('foo') >>> list(foo) # actual order may vary ['', 'bar', 'o'] >>> ct.subtree('nope').is_empty() True
Recursively convert the tree to a dictionary.
Yield all values from this trie in arbitrary order. The order in which they’re yielded doesn’t depend on the order in which they’re inserted.
>>> ct = CTrie() >>> ct.add('foo', 'bar', 'qux') True >>> for x in ct.values(): print x ... qux foo bar
New in version 0.1.0.
pretty_stringthat uses the given writer’s