API Reference¶
ctrie¶
This module provides a compact trie (CTrie
) implementation for Python.
-
class
ctrie.
CTrie
(terminal=False)[source]¶ 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:
terminal
(bool
, default:False
): specifies if the trie contains the empty string. This is the same as:>>> ct = CTrie() >>> ct.add('') # empty string
-
add
(*words)[source]¶ Add one or more words in the trie. The function returns
True
if all words were successfully added. It’ll returnFalse
if 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
-
height
()[source]¶ 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.
-
is_empty
()[source]¶ Return
True
if the trie is empty.>>> ct = CTrie() >>> ct.is_empty() True >>> ct.add('') True >>> ct.is_empty() False
-
remove
(*words)[source]¶ Remove one or more words from the trie. The function returns
True
if all the words were successfully removed (i.e. they were in the trie before) orFalse
if 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