pygtrie¶

Pure Python implementation of 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 any of its prefixes, is stored in the set.

Features¶

A full mutable mapping implementation.
Supports iterating over as well as deleting a branch of a trie (i.e. 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.

Trie classes¶

class Trie(other: SupportsKeysAndGetItem[K, V], /)[source]¶

class Trie(other: Iterable[tuple[K, V]] = (), /)

class Trie(other: SupportsKeysAndGetItem[K, V], /, **kwargs: V)

class Trie(other: Iterable[tuple[K, V]] = (), /, **kwargs: V)

A trie implementation with dict interface plus some extensions.

Typing: The class has three generic arguments: K, V and S. K and V are the types of keys and values respectively. Keys must be iterables of hashable objects, called steps. In other words, for a given key, dict.fromkeys(key) must be valid expression. S is type of those steps, i.e. an item returned when iterated over the key. For example, if K is tuple[int, ...] then S needs to be int.

Due to limited expressiveness of Python’s type system, the S type has to be specified explicitly and it’s possible to declare incompatible generic argument combinations. For example, Trie[tuple[int, ...], V, str] makes no sense.

Furthermore, methods which return keys (e.g. keys or popitem) always return them as tuple[S, ...] (regardless of K). As a result, some combination of generic arguments may lead to unsound type inference. For example:

>>> import typing
>>> import pygtrie

>>> trie: pygtrie.Trie[str, bool, str] = pygtrie.Trie(foo=True)
>>> key: str = trie.keys()[0]
>>> # ‘keys` method’s declare return type is `list[K]` hence why type of
>>> # `trie.keys()[0]` expression is `K` which is `str` in the example.
>>> # However, in reality
>>> isinstance(key, str)
False
>>> key
('f', 'o', 'o')

The problem can be solved in a few ways. First, use tuple[S, ...], typing.Sequence[S] or typing.Iterable[S] as the K generic argument. This is robust because all type inference remains sound. For example:

>>> t: pygtrie.Trie[typing.Sequence[str], bool, str] = pygtrie.Trie()
>>> t['foo'] = True
>>> t[('b', 'a', 'r')] = True
>>> keys: list[typing.Sequence[str]] = t.keys()
>>> print([type(key).__name__ for key in keys])
['tuple', 'tuple']
>>> print(keys)
[('f', 'o', 'o'), ('b', 'a', 'r')]

Second, use an existing subclass such as CharTrie and StringTrie. This is best if the key is a string as the classes properly convert a sequence of string steps into a single string:

>>> t: pygtrie.CharTrie[bool] = pygtrie.CharTrie(foo=True)
>>> key: str = t.keys()[0]
>>> isinstance(key, str)
True
>>> key
'foo'

Third, define your own subclass which does desired conversion key-steps conversion. See below for an example.

Fourth, upon getting a key from the trie, convert it to desired type. This is fragile as type inference cannot detect issues and it’s easy to forget about the conversion.

Subclassing: Subclasses can modify the way keys are iterated over by overriding _path_from_key and _key_from_path. For example, consider a trie whose keys are paths:

class PathTrie(pygtrie.Trie[pathlib.Path, V, str]):
    def _path_from_key(self, key: pathlib.Path) -> tuple[str, ...]:
        return key.parts()

    def _key_from_path(self,
                       path: typing.Iterable[str]) -> pathlib.Path:
        return pathlib.Path(*path)

Note on terminology: keys are converted into paths which are sequences of steps. Steps correspond to labels on the trie vertices and path defines how to get from root node to a particular node.

__init__(other: SupportsKeysAndGetItem[K, V], /) → None[source]¶

__init__(other: Iterable[tuple[K, V]] = (), /) → None

__init__(other: SupportsKeysAndGetItem[K, V], /, **kwargs: V) → None

__init__(other: Iterable[tuple[K, V]] = (), /, **kwargs: V) → None

Initialises the trie.

Arguments are interpreted the same way update interprets them.

update(other: SupportsKeysAndGetItem[K, V], /) → None[source]¶

update(other: Iterable[tuple[K, V]] = (), /) → None

update(other: SupportsKeysAndGetItem[K, V], /, **kwargs: V) → None

update(other: Iterable[tuple[K, V]] = (), /, **kwargs: V) → None

Updates stored values. Works like dict.update.

Parameters:

other – Mapping or iterable of (key, value) pairs to update the trie with.
**kwargs – Mapping from strings (names of keyword arguments) to values. May be specified if the trie’s keys accept strings only.

enable_sorting(enable: bool = True) → None[source]¶

Enables sorting the child nodes when iterating and traversing.

Normally, child nodes are not sorted when iterating or traversing over the trie (just like dict elements are not sorted). This method allows sorting to be enabled (which was the behaviour prior to pygtrie 2.0 release).

For Trie class, enabling sorting the child nodes is identical to sorting the list of items since Trie returns keys as tuples. However, in subclasses such as StringTrie, the two may behave differently. For example, sorting items might produce:

root/foo-bar
root/foo/baz

even though foo comes before foo-bar.

Parameters:: enable – Whether to enable sorting the child nodes.

clear() → None[source]¶: Removes all the values from the trie.

merge(other: Trie[K, V, S], overwrite: bool = False) → None[source]¶

Moves nodes from other trie into this one.

The merging happens at trie structure level and as such is different than iterating over items of one trie and setting them in the other trie.

The merging may happen between different types of tries resulting in different (key, value) pairs in the destination trie compared to the source. For example, merging two StringTrie objects each using different separators will work as if the other trie had separator of this trie. Similarly, a CharTrie may be merged into a StringTrie but when keys are read those will be joined by the separator. For example:

>>> import pygtrie
>>> st = pygtrie.StringTrie(separator='.')
>>> st.merge(pygtrie.StringTrie({'foo/bar': 42}))
>>> list(st.items())
[('foo.bar', 42)]
>>> st.merge(pygtrie.CharTrie({'baz': 24}))
>>> sorted(st.items())
[('b.a.z', 24), ('foo.bar', 42)]

Not all tries can be merged into other tries. For example, a StringTrie may not be merged into a CharTrie because the latter imposes a requirement for each component in the key to be exactly one character while in the former components may be of arbitrary length.

Note that the other trie is cleared and any references or iterators over it are invalidated. To preserve other’s value it needs to be copied first.

Parameters:

other – Other trie to move nodes from.
overwrite – Whether to overwrite existing values in this trie.

copy() → Self[source]¶: Returns a shallow copy of the object.

classmethod fromkeys(keys: Iterable[K]) → Trie[K, V | None, S][source]¶

classmethod fromkeys(keys: Iterable[K], value: V) → Trie[K, V, S]

Returns a new trie with given keys set to provided value.

This is equivalent to calling the constructor with a (key, value) for key in keys generator.

Typing: Calling the method without value argument specified is valid only if the trie can store None values (i.e. when the trie’s V generic argument accepts None).

Parameters:

keys – An iterable of keys that should be set in the new trie.
value – Value to associate with given keys. The value is not copied; all keys reference the same object.

iteritems(prefix: K = ..., shallow: bool = False) → Iterator[tuple[K, V]][source]¶

Yields all nodes with associated values with given prefix.

Only nodes with values are output. For example:

>>> import pygtrie
>>> t = pygtrie.StringTrie()
>>> t['foo'] = 'Foo'
>>> t['foo/bar/baz'] = 'Baz'
>>> t['qux'] = 'Qux'
>>> sorted(t.items())
[('foo', 'Foo'), ('foo/bar/baz', 'Baz'), ('qux', 'Qux')]

Items are output in topological order (i.e. parents before children) but the order of siblings is unspecified. At the expense of efficiency, enable_sorting can make ordering of siblings deterministic.

With prefix argument, only items with specified prefix are generated (i.e. only given subtrie is traversed) as demonstrated by:

>>> t.items(prefix='foo')
[('foo', 'Foo'), ('foo/bar/baz', 'Baz')]

With shallow argument, if a node has a value associated with it, its children are not traversed even if they exist which can be seen in:

>>> sorted(t.items(shallow=True))
[('foo', 'Foo'), ('qux', 'Qux')]

Parameters:

prefix – If given, prefix to limit iteration to.
shallow – Perform a shallow traversal, i.e. do not yield items if their prefix has been yielded.

Yields:

(key, value) tuples.

Raises:

KeyError – If prefix does not match any node.

iterkeys(prefix: K = ..., shallow: bool = False) → Iterator[K][source]¶

Yields all keys having associated values with given prefix.

This is equivalent to taking first element of tuples generated by iteritems.

Parameters:

prefix – If given, prefix to limit iteration to.
shallow – Perform a shallow traversal, i.e. do not yield keys if their prefix has been yielded.

Yields:

All the keys (with given prefix) with associated values in the trie.

Raises:

KeyError – If prefix does not match any node.

itervalues(prefix: K = ..., shallow: bool = False) → Iterator[V][source]¶

Yields all values associated with keys with given prefix.

This is equivalent to taking second element of tuples generated by iteritems.

Parameters:

prefix – If given, prefix to limit iteration to.
shallow – Perform a shallow traversal, i.e. do not yield values if their prefix has been yielded.

Yields:

All the values associated with keys (with given prefix) in the trie.

Raises:

KeyError – If prefix does not match any node.

items(prefix: K = ..., shallow: bool = False) → list[tuple[K, V]][source]¶

Returns a list of (key, value) pairs in given subtrie.

This is equivalent to constructing a list from generator returned by iteritems.

keys(prefix: K = ..., shallow: bool = False) → list[K][source]¶

Returns a list of all the keys, with given prefix, in the trie.

This is equivalent to constructing a list from generator returned by iterkeys.

values(prefix: K = ..., shallow: bool = False) → list[V][source]¶

Returns a list of values in given subtrie.

This is equivalent to constructing a list from generator returned by itervalues.

__len__() → int[source]¶

Returns the number of values in the trie.

This method is expensive to run as it iterates over the whole trie.

HAS_VALUE = 1¶: Bit returned by has_node to indicate that the node has value assigned to it.

HAS_SUBTRIE = 2¶: Bit returned by has_node to indicate that the node has child nodes.

has_node(key: K) → int[source]¶

Returns whether given node is in the trie.

Return value is a bitwise OR of HAS_VALUE and HAS_SUBTRIE constants indicating node has a value associated with it and that it is a prefix of another existing key respectively. Both of those are independent of each other and all of the four combinations are possible. For example:

>>> import pygtrie
>>> t = pygtrie.StringTrie()
>>> t['foo/bar'] = 'Bar'
>>> t['foo/bar/baz'] = 'Baz'
>>> t.has_node('qux') == 0
True
>>> t.has_node('foo/bar/baz') == pygtrie.Trie.HAS_VALUE
True
>>> t.has_node('foo') == pygtrie.Trie.HAS_SUBTRIE
True
>>> t.has_node('foo/bar') == (pygtrie.Trie.HAS_VALUE |
...                           pygtrie.Trie.HAS_SUBTRIE)
True

There are two higher level methods built on top of this one which give easier interface for the information. has_key returns whether node has a value associated with it and has_subtrie checks whether node is a prefix. Continuing previous example:

>>> t.has_key('qux'), t.has_subtrie('qux')
(False, False)
>>> t.has_key('foo/bar/baz'), t.has_subtrie('foo/bar/baz')
(True, False)
>>> t.has_key('foo'), t.has_subtrie('foo')
(False, True)
>>> t.has_key('foo/bar'), t.has_subtrie('foo/bar')
(True, True)

Parameters:: key – A key to look for.
Returns:: Non-zero if node exists and if it does a bit-field denoting whether it has a value associated with it and whether it has a subtrie.

has_key(key: K) → bool[source]¶: Indicates whether given key has value associated with it. Cf. has_node.

has_subtrie(key: K) → bool[source]¶: Returns whether given key is a prefix of another key in the trie. Cf. has_node.

__getitem__(key_or_slice: K) → V[source]¶

__getitem__(key_or_slice: slice) → Iterator[V]

Returns value associated with given key or raises KeyError.

When argument is a single key, value for that key is returned (or KeyError exception is thrown if the node does not exist or has no value associated with it).

When argument is a slice, it must be one with only start set in which case the access is identical to itervalues invocation with prefix argument.

Example

>>> import pygtrie
>>> t = pygtrie.StringTrie()
>>> t['foo/bar'] = 'Bar'
>>> t['foo/baz'] = 'Baz'
>>> t['qux'] = 'Qux'
>>> t['foo/bar']
'Bar'
>>> sorted(t['foo':])
['Bar', 'Baz']
>>> t['foo']
Traceback (most recent call last):
    ...
ShortKeyError: 'foo'

Parameters:

key_or_slice – A key or a slice to look for.

Returns:

If a single key is passed, a value associated with given key. If a slice is passed, a generator of values in specified subtrie.

Raises:

ShortKeyError – If the key has no value associated with it but is a prefix of some key with a value. Note ShortKeyError is a subclass of KeyError.
KeyError – If key has no value associated with it nor is a prefix of an existing key.
TypeError – If key_or_slice is a slice but its stop or step are not None.

__setitem__(key_or_slice: K | slice, value: V) → None[source]¶

Sets value associated with given key.

If key_or_slice is a key, associates it with given value. If it is a slice (which must have start set only), in addition clears any subtrie that might have been attached to particular key. For example:

>>> import pygtrie
>>> t = pygtrie.StringTrie()
>>> t['foo/bar'] = 'Bar'
>>> t['foo/baz'] = 'Baz'
>>> sorted(t.keys())
['foo/bar', 'foo/baz']
>>> t['foo':] = 'Foo'
>>> t.keys()
['foo']

Parameters:

key_or_slice – A key to look for or a slice. If it is a slice, the whole subtrie (if present) will be replaced by a single node with given value set.
value – Value to set.

Raises:

TypeError – If key is a slice whose stop or step are not None.

setdefault(key: K) → V | None[source]¶

setdefault(key: K, default: V) → V

Sets value of a given node if not set already. Also returns it.

In contrast to __setitem__, this method does not accept slice as a key.

Typing: Calling the method without default argument specified is valid only if the trie can store None values (i.e. when the trie’s V generic argument accepts None).

pop(key: K, default: T = ...) → V | T[source]¶

Deletes value associated with given key and returns it.

Parameters:

key – A key to look for.
default – If specified, value that will be returned if given key has no value associated with it. If not specified, method will throw KeyError in such cases.

Returns:

Removed value, if key had value associated with it, or default (if given).

Raises:

ShortKeyError – If default has not been specified and the key has no value associated with it but is a prefix of some key with a value. Note ShortKeyError is a subclass of KeyError.
KeyError – If default has not been specified and key has no value associated with it nor is a prefix of an existing key.

popitem() → tuple[K, V][source]¶

Deletes an arbitrary value from the trie and returns it.

There is no guarantee as to which item is deleted and returned, whether in terms of lexicographical or topological order.

Returns:: (key, value) tuple indicating deleted key.
Raises:: KeyError – If the trie is empty.

__delitem__(key_or_slice: K | slice) → None[source]¶

Deletes value associated with given key or raises KeyError.

If argument is a key, value associated with it is deleted. If the key is also a prefix, its descendants are not affected. On the other hand, if the argument is a slice (in which case it must have only start set), the whole subtrie is removed. For example:

>>> import pygtrie
>>> t = pygtrie.StringTrie()
>>> t['foo'] = 'Foo'
>>> t['foo/bar'] = 'Bar'
>>> t['foo/bar/baz'] = 'Baz'
>>> del t['foo/bar']
>>> t.keys()
['foo', 'foo/bar/baz']
>>> del t['foo':]
>>> t.keys()
[]

Parameters:

key_or_slice – A key to look for or a slice. If key is a slice, the whole subtrie will be removed.

Raises:

ShortKeyError – If the key has no value associated with it but is a prefix of some key with a value. This is not thrown if key_or_slice is a slice – in such cases, the whole subtrie is removed. Note ShortKeyError is a subclass of KeyError.
KeyError – If key has no value associated with it nor is a prefix of an existing key.
TypeError – If key is a slice whose stop or step are not None.

walk_towards(key: K) → Iterator[_Step[K, V, S]][source]¶

Yields nodes on the path to given node.

Parameters:

key – Key of the node to look for.

Yields:

_Step objects which can be used to extract or set node’s value as well as get node’s key.

When representing nodes with assigned values, the objects can be treated as (k, value) pairs denoting keys with associated values encountered on the way towards the specified key. This is deprecated, prefer using key and value properties or get method of the object.

Raises:

KeyError – If node with given key does not exist. it’s all right if the value is not assigned to the node provided it has a child node. Because the method is a generator, the exception is raised only once a missing node is encountered.

prefixes(key: K) → Iterator[_Step[K, V, S]][source]¶

Walks towards the node specified by key and yields all found items.

Example

>>> import pygtrie
>>> t = pygtrie.StringTrie()
>>> t['foo'] = 'Foo'
>>> t['foo/bar/baz'] = 'Baz'
>>> list(t.prefixes('foo/bar/baz/qux'))
[('foo': 'Foo'), ('foo/bar/baz': 'Baz')]
>>> list(t.prefixes('does/not/exist'))
[]

Parameters:

key – Key to look for.

Yields:

_Step objects which can be used to extract or set node’s value and get its key.

The objects can be treated as (k, value) pairs denoting keys with associated values encountered on the way towards the specified key. This is deprecated, prefer using key and value properties of the object.

shortest_prefix(key: K) → _NoneStep | _Step[K, V, S][source]¶

Finds the shortest prefix of a key with a value.

This is equivalent to taking the first item yielded by the prefixes method with additional handling of situations when no prefixes are found.

Example

>>> import pygtrie
>>> t = pygtrie.StringTrie()
>>> t['foo'] = 'Foo'
>>> t['foo/bar/baz'] = 'Baz'
>>> t.shortest_prefix('foo/bar/baz/qux')
('foo': 'Foo')
>>> t.shortest_prefix('foo/bar/baz/qux').key
'foo'
>>> t.shortest_prefix('foo/bar/baz/qux').value
'Foo'
>>> t.shortest_prefix('does/not/exist')
(None Step)
>>> bool(t.shortest_prefix('does/not/exist'))
False

Parameters:: key – Key to look for.
Returns:: _Step object (which can be used to extract or set node’s value and get its key), or a _NoneStep object (which is falsy value) if no prefix is found.

longest_prefix(key: K) → _NoneStep | _Step[K, V, S][source]¶

Finds the longest prefix of a key with a value.

This is equivalent to taking the last item yielded by the prefixes method with additional handling of situations when no prefixes are found.

Example

>>> import pygtrie
>>> t = pygtrie.StringTrie()
>>> t['foo'] = 'Foo'
>>> t['foo/bar/baz'] = 'Baz'
>>> t.longest_prefix('foo/bar/baz/qux')
('foo/bar/baz': 'Baz')
>>> t.longest_prefix('foo/bar/baz/qux').key
'foo/bar/baz'
>>> t.longest_prefix('foo/bar/baz/qux').value
'Baz'
>>> t.longest_prefix('does/not/exist')
(None Step)
>>> bool(t.longest_prefix('does/not/exist'))
False

Parameters:: key – Key to look for.
Returns:: _Step object (which can be used to extract or set node’s value as well as get node’s key), or a _NoneStep object (which is a falsy value).

strictly_equals(other: Trie[K, V, S]) → bool[source]¶

Returns whether tries are equal with the same structure.

This is stricter comparison than the one performed by equality operator. It not only requires keys and values to be equal but also the two tries to be of the same type and have the same structure.

For example, two StringTrie objects to compare strictly equal if they have the same structure as well as the same separator.

Example

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

Parameters:: other – Other trie to compare to.

__eq__(other: object) → bool[source]¶

Compares this trie’s mapping with another mapping.

Note that this method doesn’t take trie’s structure into consideration. What matters is whether keys and values in both mappings are the same. This may lead to unexpected results, for example:

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

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

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

This behaviour is required to maintain consistency with Mapping interface and its __eq__ method. For example, this implementation maintains transitivity of the comparison:

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

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

Parameters:: other – Other object to compare to.
Returns:: NotImplemented if this method does not know how to perform the comparison or a bool denoting whether the two objects are equal or not.

_path_from_key(key: K) → Sequence[S][source]¶

Converts a user visible key object to internal path representation.

The default implementation returns the key. Subclasses may override this method (together with _key_from_path) to support keys of other types, e.g. splitting a string key into path components.

Parameters:: key – User supplied key.
Returns:: A path, which is an iterable of steps. Each step must be hashable.
Raises:: TypeError – If key is of invalid type.

_key_from_path(path: Iterable[S]) → K[source]¶

Converts an internal path into a user visible key object.

The default implementation creates a tuple from the path. Subclasses may override this method (together with _path_from_key) to support keys of other types, e.g. splitting a string key into path components.

Parameters:: path – Internal path representation.
Returns:: A user visible key object.

traverse(node_factory: NodeFactory[K, V, S, T], prefix: K = ...) → T[source]¶

Traverses the tree using node_factory object.

node_factory is a callable which accepts (key_from_path, path, children, value=...) arguments, where key_from_path converts paths to corresponding keys, path is the path to this node, children is an iterable of child nodes constructed by node_factory, optional value is the value associated with the path.

node_factory’s children argument is a lazy iterable which has a few consequences:

To traverse into node’s children, the object must be iterated over. This can be accomplished by children = list(children) statement.
Ignoring the argument allows node_factory to stop the traversal from going into the descendants of the node. In this way, whole subtries can be removed from traversal.
If children is stored as is (i.e. as a iterator), once it is iterated over later on, it may see an outdated state of the trie.

To allow constant-time determination whether the node has children, the children iterator implements meaningful truth value testing, such that has_children = bool(children) can be used. (Note that, if the node has children, children value remains truthy even after the iterator has been exhausted).

traverse has two advantages over iteritems and similar methods:

it allows subtries to be skipped completely when going through the list of nodes based on the property of the parent node; and
it represents structure of the trie directly making it easy to convert structure into a different representation.

For example, the below snippet prints all files in current directory counting how many HTML files were found, but ignores hidden files and directories:

import os
import typing

import pygtrie

trie: pygtrie.StringTrie[bool] = pygtrie.StringTrie(
    separator=os.sep)

# Construct a trie with all files in current directory and all of
# its sub-directories.  Files get set a True value.  Directories are
# represented implicitly by being prefixes of files.
for root, _, files in os.walk('.'):
    for name in files:
        trie[os.path.join(root, name)] = True

def traverse_callback(
        key_from_path: typing.Callable[[typing.Iterable[str]], str],
        path: typing.Sequence[str],
        children: typing.Iterable[int],
        is_file: bool=False) -> int:
    if path and path[-1] != '.' and path[-1][0] == '.':
        # Ignore hidden directory (but accept root node and '.')
        return 0
    elif is_file:
        print(key_from_path(path))
        return int(path[-1].endswith('.html'))
    else:
        # Otherwise, it’s a directory.  Traverse into children.
        return sum(children)

print(trie.traverse(traverse_callback))

Ignoring the children argument causes subtrie to be omitted and not walked into.

In the next example, the trie is converted to a tree representation where child nodes include a pointer to their parent. As before, hidden files and directories are ignored:

import os
import typing

import pygtrie

trie: pygtrie.StringTrie[bool] = pygtrie.StringTrie(
    separator=os.sep)
for root, _, files in os.walk('.'):
    for name in files:
        trie[os.path.join(root, name)] = True

class File:
    name: str
    parent: typing.Optional['File']

    def __init__(self, name: str) -> None:
        self.name = name
        self.parent = None

class Directory(File):
    children: list[File]

    def __init__(self,
                 name: str,
                 children: list[File]) -> None:
        super().__init__(name)
        self.children = children
        for child in children:
            child.parent = self

def traverse_callback(
        key_from_path: typing.Callable[[typing.Iterable[str]], str],
        path: typing.Sequence[str],
        children: typing.Iterable[File | None],
        is_regular_file: bool=False) -> File | None:
    if path and path[-1] != '.' and path[-1][0] == '.':
        return None
    if is_regular_file:
        return File(path[-1])
    return Directory(path[-1] if path else '',
                     list(filter(None, children)))

root_dir: Directory = typing.cast(
    Directory, trie.traverse(traverse_callback, prefix='.'))

Note: Unlike iterators (e.g. returned by iteritems), using traverse may raise an exception when used on a deep trie. This may happen when Python’s maximum recursion depth is reached. To address this, children iteration may be done non-recursively outside of the node_factory. For example, the below code converts a trie into an undirected graph using adjacency list representation:

import collections
import os
import typing

import pygtrie

K = typing.TypeVar('K')
V = typing.TypeVar('V')
S = typing.TypeVar('S')

Node = collections.namedtuple('Node', 'path neighbours')

def undirected_graph_from_trie(
        trie: pygtrie.Trie[K, V, S]
) -> list[Node]:
    '''Converts trie into a graph and returns its nodes.'''

    class Builder:
        node: Node
        children: typing.Iterable[typing.Self]
        parent: Node | None

        def __init__(
                self,
                key_from_path: typing.Callable[
                    [typing.Iterable[S]], K],
                path: typing.Sequence[S],
                children: typing.Iterable[typing.Self],
                _: typing.Any=None) -> None:
            self.node = Node(key_from_path(path), [])
            self.children = children
            self.parent = None

        def build(self, queue: list[Node | Builder]) -> Node:
            for builder in self.children:
                builder.parent = self.node
                queue.append(builder)
            if self.parent:
                self.parent.neighbours.append(self.node)
                self.node.neighbours.append(self.parent)
            return self.node

    nodes: list[Node | Builder] = [trie.traverse(Builder)]
    i = 0
    while i < len(nodes):
        nodes[i] = typing.cast(Builder, nodes[i]).build(nodes)
        i += 1
    return typing.cast(list[Node], nodes)

Parameters:

node_factory – Makes opaque objects from the keys and values of the trie.
prefix – Prefix for node to start traversal, by default starts at the root.

Returns:

Node object constructed by node_factory corresponding to the root node.

class CharTrie(other: SupportsKeysAndGetItem[K, V], /)[source]¶

class CharTrie(other: Iterable[tuple[K, V]] = (), /)

class CharTrie(other: SupportsKeysAndGetItem[K, V], /, **kwargs: V)

class CharTrie(other: Iterable[tuple[K, V]] = (), /, **kwargs: V)

Trie which accepts and returns strings as keys.

The only difference between CharTrie and Trie is that CharTrie returns keys (for instance when Trie.keys method is called) as strings, whereas Trie returns keys as tuples. For example, compare:

>>> import pygtrie
>>> trie = pygtrie.Trie()
>>> trie['foo'] = True
>>> trie['bar'] = True
>>> trie.keys()
[('f', 'o', 'o'), ('b', 'a', 'r')]

>>> trie = pygtrie.CharTrie()
>>> trie['foo'] = True
>>> trie['bar'] = True
>>> trie.keys()
['foo', 'bar']

Typing: The class takes one generic argument V. It specifies the type of values stored in the trie. The key type is str.

class StringTrie(other: SupportsKeysAndGetItem[str, V] | Iterable[tuple[str, V]] = (), /, separator: str = '/', **kwargs: V)[source]¶

Trie which accepts strings with a separator as keys.

This trie accepts strings as keys which are split into components (or steps) using a separator specified during initialisation (forward slash by default).

A common example where this class can be used is when keys are paths. For example, it could map from a path to a request handler:

import pygtrie

def handle_root(): pass
def handle_admin(): pass
def handle_admin_images(): pass

handlers = pygtrie.StringTrie()
handlers[''] = handle_root
handlers['/admin'] = handle_admin
handlers['/admin/images'] = handle_admin_images

request_path = '/admin/images/foo'

handler = handlers.longest_prefix(request_path)

Typing: The class takes one generic argument V. It specifies the type of values stored in the trie. The key type is str.

__init__(other: SupportsKeysAndGetItem[str, V] | Iterable[tuple[str, V]] = (), /, separator: str = '/', **kwargs: V) → None[source]¶

Initialises the trie.

Except for a separator named argument, all other arguments are interpreted the same way Trie.update interprets them.

Parameters:

other – Passed to super class initialiser.
separator – A separator to use when splitting keys into paths used by the trie.
**kwargs – Passed to super class initialiser.

Raises:

TypeError – If separator is not a string.
ValueError – If separator is empty.

classmethod fromkeys(keys: Iterable[str], *, separator: str = '/') → StringTrie[V | None][source]¶

classmethod fromkeys(keys: Iterable[str], value: V, separator: str = '/') → StringTrie[V]

Returns a new trie with given keys set to provided value.

This is equivalent to calling the constructor with a (key, value) for key in keys generator.

Typing: Calling the method without value argument specified is valid only if the trie can store None values (i.e. when the trie’s V generic argument accepts None).

Parameters:

keys – An iterable of keys that should be set in the new trie.
value – Value to associate with given keys. The value is not copied; all keys reference the same object.
separator – A separator to use when splitting keys into paths used by the trie.

class _Step[source]¶

Representation of a single step on a path towards particular node.

Note: Reading value property of this class may raise KeyError if the node at the step does not have a value. Writing the property always succeeds. _Step.get returns value or default and always succeeds.

The class is private because it should not be constructed by external code. Objects of this type are returned by Trie methods such as Trie.prefixes and Trie.walk_towards.

__bool__() → Literal[True][source]¶: Returns whether the object is a valid step, which for _Step is always true.

property key: K¶: Node’s key.

property value: V¶

Node’s value; on read, raises KeyError if node has no value.

To safely get value of a step without raising an exception, use _Step.get method instead.

property is_set: bool¶: Whether the node has value assigned to it.

property has_subtrie: bool¶: Whether the node has any children.

get() → V | None[source]¶
get(default: T) → V | T: Returns node’s value or the default if value is not assigned.

set(value: V) → None[source]¶: Deprecated. Use step.value = value instead.

setdefault(value: V) → V[source]¶: Assigns value to the node if one is not set then returns it.

__getitem__(index: Literal[0]) → K[source]¶

__getitem__(index: Literal[1]) → V

Makes object appear like a (key, value) tuple.

Cf. _Step.key, _Step.value and _Step.get.

Parameters:

index – Element index to return.

Returns:

self.key if index is 0, self.value if index is 1.

Raises:

IndexError – If index is not 0 or 1.
KeyError – If index is 1 and the node has no value.

class _NoneStep[source]¶

Representation of a non-existent step towards a non-existent node.

The class is private because it should not be constructed by external code. Objects of this type are returned by Trie methods Trie.shortest_prefix and Trie.longest_prefix.

__bool__() → Literal[False][source]¶: Returns whether the object is a valid step, which for _NoneStep is always false.

property key: None¶: Deprecated. Currently None. In the future accessing it will raise AttributeError (cf. _Step.key).

property value: None¶

Deprecated. Currently None. In the future accessing it will raise AttributeError (cf. _Step.value).

To safely get value of a step without raising an exception, use _NoneStep.get method instead.

property is_set: Literal[False]¶: Whether the node has value assigned to it. Since _NoneStep represents no node, this is always false.

property has_subtrie: Literal[False]¶: Whether the node has any children. Since _NoneStep represents no node, this is always false.

get() → None[source]¶
get(default: T) → T: Returns node’s value or the default if value is not assigned. Since _NoneStep represents no node, returns the default.

__getitem__(index: int) → None[source]¶

Deprecated. Makes object appear like a (key, value) tuple.

Prefer bool(self) to detect whether this is a _Step or _NoneStep; and _Step.get to get value of the node.

Parameters:: index – Element index to return.
Returns:: None if index is 0 or 1.
Raises:: IndexError – If index is not 0 or 1.

PrefixSet class¶

class PrefixSet(iterable: Iterable[K] = (), factory: Callable[[...], Trie[K, Literal[True], S]] = Trie, **kwargs: Any)[source]¶

A set of prefixes.

PrefixSet works similarly to a regular set except it contain a key if the key or its prefix is stored in the set. For instance, if “foo” is added to the set, the set contains “foo” as well as “foobar”.

The set supports addition of elements but does not support removal of elements. This is because there’s no obvious consistent and intuitive behaviour for element deletion.

Typing: The class has two generic arguments: K and S. They have the same meaning and caveats as the corresponding generic arguments of the Trie class (q.v.). To change the type of the trie backing the prefix set, use factory argument of the __init__ method.

__init__(iterable: Iterable[K] = (), factory: Callable[[...], Trie[K, Literal[True], S]] = Trie, **kwargs: Any)[source]¶

Initialises the prefix set.

Parameters:

iterable – A sequence of keys to add to the set.
factory – Callback which creates the trie backing the prefix set.
kwargs – Additional keyword arguments passed to the factory function. Notably necessary when using StringTrie as the trie backing the prefix set.

copy() → Self[source]¶: Returns a shallow copy of the object.

clear() → None[source]¶: Removes all keys from the set.

__contains__(key: K) → bool[source]¶: Checks whether set contains key or its prefix.

__iter__() → Iterator[K][source]¶: Return iterator over all prefixes in the set. Cf. PrefixSet.iter.

iter(prefix: K = ...) → Iterator[K][source]¶

Iterates over all keys in the set optionally starting with a prefix.

Since a key does not have to be explicitly added to the set to be an element of the set, this method does not iterate over all possible keys that the set contains, but only over the shortest set of prefixes of all the keys the set contains.

For example, if “foo” has been added to the set, the set contains also “foobar”, but this method will not iterate over “foobar”.

If prefix argument is given, method will iterate over keys with given prefix only. The keys yielded from the function if prefix is given do not have to be a subset (in the mathematical sense) of the keys yielded when there is no prefix. This happens, if the set contains a prefix of the given prefix.

For example, if only “foo” has been added to the set, iter method called with no arguments will yield “foo” only. However, when called with “foobar” argument, it will yield “foobar” only.

__len__() → int[source]¶

Returns number of keys stored in the set.

Since a key does not have to be explicitly added to the set to be an element of the set, this method does not count over all possible keys that the set contains (since that would be infinity), but only over the shortest set of prefixes of all the keys the set contains.

For example, if “foo” has been added to the set, the set contains also “foobar”, but this method will not count “foobar”.

add(value: K) → None[source]¶

Adds given value to the set.

If the set already contains prefix of the value being added, this operation has no effect. If the value being added is a prefix of some existing values in the set, those values are deleted and replaced by a single entry for the value being added.

For example, if the set contains value “foo” adding a value “foobar” does not change anything. On the other hand, if the set contains values “foobar” and “foobaz”, adding a value “foo” will replace those two values with a single value “foo”.

This makes a difference when iterating over the values or counting number of values. Counterintuitively, adding a value can decrease size of the set.

Parameters:: value – Value to add.

discard(value: K) → Never[source]¶: Raises NotImplementedError.

remove(value: K) → Never[source]¶: Raises NotImplementedError.

pop() → Never[source]¶: Raises NotImplementedError.

Custom exceptions¶

class ShortKeyError[source]¶: Raised when given key is a prefix of an existing longer key but does not have a value associated with itself.

Typing classes¶

class NodeFactory(*args, **kwargs)[source]¶

A node factory used when traversing a trie. For more details, see Trie.traverse.

__call__(key_from_path: Callable[[Iterable[S]], K], path: Sequence[S], children: Iterable[T], /) → T[source]¶

__call__(key_from_path: Callable[[Iterable[S]], K], path: Sequence[S], children: Iterable[T], value: V, /) → T

Processes and transforms a node of a trie. For more details, see Trie.traverse.

Parameters:

key_from_path – A function converting path to a key as used in the trie.
path – Path to the node being processed.
children – A lazy iterator over children of the node. The iterator is falsy if the node has no children; it’s truthy otherwise. The items of the iterator are values returned by calls to the node factory on corresponding child.
value – If provided, a value assigned to the node.

Returns:

A value which is passed to parents through children iterator and eventually returned by the Trie.traverse method.

Version History¶

2.6.1: 2026/09/01

Added 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 till they upgrade their Python version (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 annotation to the code base. This enables better static type analysis on the code bases using pygtrie.

There are a few corner cases where the type annotations aren’t entirely sound. Most notably, the pygtrie.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 discussion the feature]

Deprecated and warn about some methods of pygtrie._NoneStep returned by pygtrie.Trie.shortest_prefix and pygtrie.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 (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 prefix exist, and pygtrie._NoneStep.get method can be used to safely get value of a prefix with a fallback if prefix isn’t valid:

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

Behaviour when 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 deprecation warning to pygtrie._Step.set method. pygtrie._Step is returned methods such as pygtrie.Trie.shortest_prefix and pygtrie.Trie.prefixes and represent a valid prefix of a key. The method has been deprecated since version 2.3.3; it’ll now issue a warning when used. Proper way to set value of a prefix is via value property, e.g.:
```
>>> prefix = CharTrie(foo=0, foobar=0).longest_prefix('foobarbaz')
>>> prefix.value += 1
```
Fixed pygtrie._Step string conversion raising an exception if step represents node without 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 pygtrie.Trie.merge method which merges structures of two tries.
Add pygtrie.Trie.strictly_equals method which compares two tries with stricter rules than 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 pygtrie.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 key into ('foo', 'bar.baz') while the second 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 values. pygtrie.Trie returns keys as tuples while pygtrie.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 pygtrie.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.

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.

pygtrie¶

Features¶

Installation¶

Trie classes¶

PrefixSet class¶

Custom exceptions¶

Typing classes¶

Version History¶

Table of Contents

This Page