pygtrie 2.6.2

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.

For example usage, see scripts in examples directory.

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.6.2: 2026/09/14

• Optimise code and type annotations to reduce overhead introduced by the type hints in version 2.6.0. Changes brought noticeable improvements compared to version 2.5.0:

  • Lookup of a non-existent key is 20–40% faster. Prefer the Trie.get method to the subscription operator (i.e. trie[key] syntax) as it’s consistently faster.

  • Lookup of an existing key in a StringTrie is about 20% faster.

  • Equality comparison between two tries of the same type, done either via the == operator or the Trie.strictly_equals method, is over 30% faster.

  • Trie.prefixes, Trie.shortest_prefix and Trie.longest_prefix methods are 30–40% faster. On the flip side, Trie.walk_towards is about 5–15% slower.

  • Copying and merging tries is up to 10% faster.

  Unfortunately, some decrease in performance compared to v2.5.0 is still present. Many operations are up to 5% slower. Operations with larger change include:

  • CharTrie creation is about 20% slower.

  • Lookup of an existing key in a CharTrie via subscription operator (i.e. trie[key] syntax) is about 10% slower. (Prefer Trie.get to avoid that slowdown).

  • Key deletion (i.e. del trie[key] operation) is up to 25% slower. Trie.popitem is up to 10% slower.

  • Pickling and unpickling a trie is about 20–30% slower. (As a side note, you should not be using pickle).

  Note that benchmarks used to arrive at those numbers aren’t particularly robust, and trie performance depends greatly on its structure. Results may vary greatly depending on application.

  [Thanks to Dan Homola for reporting]

• Slices are no longer reported as existing in the trie. Previously slice(some_key, None) in trie would always return true. This was an unintended behaviour. Now, such checks throw an exception.

• Trie.merge no longer throws TypeError when trying to merge a StringTrie into a Trie.

  Merging can lead to inconsistent state; the check tried to prevent it. However, it caught only one specific case. Considering that the trie types can be subclassed, it’s not possible to predict all possible failures.

  Because of that, the explicit check was removed, and corner cases and possible failures were better documented.

• Add missing py.typed marker file which is required for type checkers to notice that the package contains type annotations. [Thanks to Avasam for reporting]

2.6.1: 2026/09/01

• Add python_requires metadata to indicate Python 3.11 requirement. [Thanks to skshetry for reporting]

2.6: 2026/09/01 [pulled back from PyPI]

• Python 3.11 is now required. Users still on 3.10 need to hold off on upgrading till they switch to newer Python versions (3.10 is reaching end-of-life in a couple months) or temporarily vendor the module and replace all instances of _t.Self in pygtrie.py with _t.Any.

• Add type annotations to the codebase. This enables better static type analysis in codebases using pygtrie.

  There are a few corner cases where the type annotations aren’t entirely sound. Most notably, the Trie class always returns keys as tuple[S, ...] regardless of declared type. The documentation points out ways to deal with it.

  [Thanks to Dave Tapley and Avasam for requesting and discussing the feature]

• Deprecate and warn about some methods of _NoneStep returned by Trie.shortest_prefix and Trie.longest_prefix when no prefix is found.

  Historically, prefixes were returned as (key, value) pairs and to maintain compatibility, lack of a prefix was signalled by a (None, None) pair. However, treating lack of prefix as a tuple has long been deprecated:

  >>> result = CharTrie(foo=42).longest_prefix('bar')
  >>> key, value = result # Currently, (None, None);
  >>>                     # in the future, will raise TypeError.
  >>> key = result.key  # Currently None;
  >>>                   # in the future will raise AttributeError.
  >>> val = result.value  # Currently None;
  >>>                     # in the future will raise AttributeError.
  

  Truth value testing can be used to see whether a prefix exists, and the _NoneStep.get method can be used to safely get the value of a prefix with a fallback if no prefix is found:

  >>> result = CharTrie(foo=42).longest_prefix('bar')
  >>> if result:
  ...     key = result.key
  ... else:
  ...     key = None
  >>> value = result.get(None)
  

  Behaviour when a prefix exists remains unchanged:

  >>> result = CharTrie(foo=42).longest_prefix('foobar')
  >>> key, value = result
  >>> assert (key, value) == ('foo', 42)
  >>> key, value = result.key, result.value
  >>> assert (key, value) == ('foo', 42)
  

• Add a deprecation warning to the _Step.set method. _Step is returned by methods such as Trie.shortest_prefix and Trie.prefixes and represents a valid prefix of a key. The method has been deprecated since version 2.3.3; it’ll now issue a warning when used. The proper way to set the value of a prefix is via the value property, e.g.:

  >>> prefix = CharTrie(foo=0, foobar=0).longest_prefix('foobarbaz')
  >>> prefix.value += 1
  

• Fix _Step string conversion raising an exception if a step represents a node without a value. In previous versions the following would raise KeyError:

  >>> list(map(repr, CharTrie(a=42).walk_towards('a')))
  ["('': <no value>)", "('a': 42)"]
  

• Remove obsolete license classifiers from the package metadata. [Thanks to Benjamin T. Schwertfeger for reporting]

2.5: 2022/07/16

• Add Trie.merge method which merges structures of two tries.

• Add Trie.strictly_equals method which compares two tries with stricter rules than the regular equality operator. It’s not sufficient that keys and values are the same but the structure of the tries must be the same as well. For example:

  >>> t0 = StringTrie({'foo/bar.baz': 42}, separator='/')
  >>> t1 = StringTrie({'foo/bar.baz': 42}, separator='.')
  >>> t0 == t1
  True
  >>> t0.strictly_equals(t1)
  False
  

• Fix Trie.__eq__ implementation such that key values are taken into consideration rather than just looking at trie structure. To see what this means it’s best to look at a few examples. Firstly:

  >>> t0 = StringTrie({'foo/bar': 42}, separator='/')
  >>> t1 = StringTrie({'foo.bar': 42}, separator='.')
  >>> t0 == t1
  False
  

  This used to be true since the two tries have the same node structure. However, as far as Mapping interface is concerned, they use different keys, i.e. set(t0) != set(t1). Secondly:

  >>> t0 = StringTrie({'foo/bar.baz': 42}, separator='/')
  >>> t1 = StringTrie({'foo/bar.baz': 42}, separator='.')
  >>> t0 == t1
  True
  

  This used to be false since the two tries have different node structures (the first one splits the key into ('foo', 'bar.baz') while the second splits it into ('foo/bar', 'baz')). However, their keys are the same, i.e. set(t0) == set(t1). And lastly:

  >>> t0 = Trie({'foo': 42})
  >>> t1 = CharTrie({'foo': 42})
  >>> t0 == t1
  False
  

  This used to be true since the two tries have the same node structure. However, the two classes return key as different types: Trie returns keys as tuples while CharTrie returns them as strings.

2.4.2: 2021/01/03

• Remove use of super in setup.py to fix compatibility with Python 2.7. This changes build code only; no changes to the library itself.

2.4.1: 2020/11/20

• Remove dependency on packaging module from setup.py to fix installation on systems without that package. This changes build code only; no changes to the library itself. [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 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 ‘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 Trie.walk_towards et al. This deprecates the set method.

• The module now exposes 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 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 a member of the set, foobar is as well). [Thanks to Tal Maimon for reporting]

• Fix the Trie.copy method not preserving the enable-sorting flag and, in the case of StringTrie, the separator property.

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

• Leaves 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 PrefixSet.

• Improvements to the string representation of objects, which now includes the type and, for a StringTrie object, the value of the separator property.