pygtrie 2.4.1

A pure Python trie data structure implementation.

pygtrie is a pure Python implementation of a trie data structure compatible with Python 2.x and Python 3.x.

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, simply run:

pip install pygtrie

or by adding line such as:

pygtrie == 2.*

to project’s requirements file. Alternatively, if installation from source is desired, it can be achieved by executing:

python setup.py install

Version History

2.4.1: 2020/11/20

• Remove dependency on packaging module from setup.py to fix installation on systems without that package. [Thanks to Eric McLachlan for reporting]

2.4.0: 2020/11/19 [pulled back from PyPi]

• Change children argument of the node_factory passed to Trie.traverse from a generator to an iterator with a custom bool conversion. This allows checking whether node has children without having to iterate over them (bool(children))

  To test whether this feature is available, one can check whether Trie.traverse.uses_bool_convertible_children property is true, e.g.: getattr(pygtrie.Trie.traverse, 'uses_bool_convertible_children', False).

  [Thanks to Pallab Pain for suggesting the feature]

2.3.3: 2020/04/04

• Fix to ‘AttributeError: _NoChildren object has no attribute sorted_items’ failure when iterating over a trie with sorting enabled. [Thanks to Pallab Pain for reporting]

• Add value property setter to step objects returned by pygtrie.Trie.walk_towards et al. This deprecates the set method.

• The module now exports pygtrie.__version__ making it possible to determine version of the library at run-time.

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.

• Add support for the copy module so copy.copy can now be used with trie objects.

• Leafs and nodes with just one child use more memory-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 includes type and, for pygtrie.StringTrie object, value of separator property.

2.3: 2018/08/10

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

• 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 returned 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.