pygtrie 2.3.2

Trie data structure implementation.

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 that node).

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.

Features

• A full mutable mapping implementation.

• Supports iterating over as well as deleting a subtrie.

• Supports prefix checking as well as shortest and longest prefix look-up.

• Extensible for any kind of user-defined keys.

• A PrefixSet supports “all keys starting with given prefix” logic.

• Can store any value including None.

Installation

To install pygtrie, run:

pip install pygtrie

Or download the sources and save pygtrie.py file with your project.

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

with:

import pygtrie as trie

Version History

2.3.2: 2019/07/18

• Trivial metadata fix

2.3.1: 2019/07/18 [pulled back from PyPi]

• Fix to pygtrie.PrefixSet initialisation incorrectly storing elements even if their prefixes are also added to the set.

  For example, PrefixSet(('foo', 'foobar')) incorrectly resulted in a two-element set even though the interface dictates that only foo is kept (recall that if foo is member of the set, foobar is as well). [Thanks to Tal Maimon for reporting]

• Fix to pygtrie.Trie.copy method not preserving enable-sorting flag and, in case of pygtrie.StringTrie, separator property. Related to this, add support for the copy module so copy.copy can now be used with the objects.

• Leafs and nodes with just one child use more mummery-optimised representation which reduces overall memory usage of a trie structure.

• Minor performance improvement for adding new elements to a pygtrie.PrefixSet.

• Improvements to string representation of objects which now include type and, for pygtrie.StringTrie object, value of separator property.

2.3: 2018/08/10

• New walk_towards method allows walking a path towards given a node with given key accessing each step of the path. Compared to prefixes method, steps for nodes without assigned values are

• Fix to pygtrie.PrefixSet.copy not preserving type of backing trie.

• pygtrie.StringTrie now checks and explicitly rejects empty separators. Previously empty separator would be accepted but lead to confusing errors later on. [Thanks to Waren Long].

• Various documentation improvements, Python 2/3 compatibility and test coverage (python-coverage reports 100%).

2.2: 2017/06/03

• Fixes to setup.py breaking on Windows which prevents installation among other things.

2.1: 2017/03/23

• The library is now Python 3 compatible.

• Value returend by pygtrie.Trie.shortest_prefix and pygtrie.Trie.longest_prefix evaluates to false if no prefix was found. This is in addition to it being a pair of Nones of course.

2.0: 2016/07/06

• Sorting of child nodes is disabled by default for better performance. pygtrie.Trie.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 JSON.

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 pygtrie.Trie.traverse method, however, still uses recursion thus cannot be used on big structures.

1.1: 2016/01/18

• Fixed PyPi installation issues; all should work now.

1.0: 2015/12/16

• 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 pygtrie.Trie.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.

0.9.3: 2015/05/28

• Minor documentation fixes.

0.9.2: 2015/05/28

• Added Sphinx configuration and updated docstrings to work better with Sphinx.

0.9.1: 2014/02/03

• New name.

0.9: 2014/02/03

• Initial release.