pygtrie is a Python library implementing a trie data structure.
Trie data structure, also known
as radix or prefix tree, is a tree associating keys to values where
all the descendants of a node have a common prefix (associated with
The trie module contains Trie, CharTrie and StringTrie
classes each implementing a mutable mapping interface, i.e. dict
interface. As such, in most circumstances, Trie could be used as
a drop-in replacement for a dict, but the prefix nature of the
data structure is trie’s real strength.
The module also contains PrefixSet class which uses a trie to
store a set of prefixes such that a key is contained in the set if it
or its prefix is stored in the set.
- A full mutable mapping implementation.
- Supports iterating over as well as deleting a subtrie.
- Supports prefix checking as well as shortest and longest prefix
- Extensible for any kind of user-defined keys.
- A PrefixSet supports “all keys starting with given prefix” logic.
- Can store any value including None.
To install pygtrie, run:
pip install pygtrie
Or download the sources and save pygtrie.py file with your
Upgrading from 0.9.x
The 1.0 release introduced backwards incompatibility in naming. The
module has been renamed from trie to pygtrie. Fortunately,
updating scripts using pygtrie should boil down to replacing:
from pytrie import trie
import pygtrie as trie
- Fixes to setup.py breaking on Windows which prevents installation
among other things.
- The library is now Python 3 compatible.
- Value returend by shortest_prefix and longest_prefix evaluates
to false if no prefix was found. This is in addition to it being
a pair of Nones of course.
- Sorting of child nodes is disabled by default for better performance.
enable_sorting method can be used to bring back old behaviour.
- Tries of arbitrary depth can be pickled without reaching Python’s
recursion limits. (N.B. The pickle format is incompatible with one
from 1.2 release). _Node’s __getstate__ and __setstate__
method can be used to implement other serialisation methods such as
1.2: 2016/06/21 [pulled back from PyPi]
- Tries can now be pickled.
- Iterating no longer uses recursion so tries of arbitrary depth can be
iterated over. The traverse method, however, still uses recursion
thus cannot be used on big structures.
- Fixed PyPi installation issues; all should work now.
- The module has been renamed from trie to pygtrie. This
could break current users but see documentation for how to quickly
upgrade your scripts.
- Added traverse method which goes through the nodes of the trie
preserving structure of the tree. This is a depth-first traversal
which can be used to search for elements or translate a trie into
a different tree structure.
- Minor documentation fixes.
- Minor documentation fixes.
- Added Sphinx configuration and updated docstrings to work better
Download the file for your platform. If you're not sure which to choose, learn more about installing packages.