pygtrie: Pure Python Trie Data Structure

2.5.0 · active · verified Mon Apr 06

pygtrie is a pure Python library implementing a trie data structure. It provides `Trie`, `CharTrie`, and `StringTrie` classes, each implementing a mutable mapping (dictionary-like) interface. Its strengths lie in prefix-based operations, such as iterating over or deleting subtries, prefix checking, and shortest/longest prefix look-ups. It also includes a `PrefixSet` for managing sets of prefixes. The current version is 2.5.0, with releases occurring periodically to introduce features and address compatibility.

Warnings

breaking The module name was changed from `trie` to `pygtrie` in the 1.0 release. Existing code using `from pytrie import trie` will break.
Fix: Update imports from `from pytrie import trie` to `import pygtrie as trie` or directly import classes like `from pygtrie import Trie`.
breaking Prior to version 2.0, child nodes were sorted by default during iteration and traversal. Since 2.0, this behavior is disabled for performance. Iteration order is no longer guaranteed unless explicitly enabled.
Fix: If sorted iteration is required, use `trie.enable_sorting()` after initialization or when needed.
deprecated The objects returned by `Trie.shortest_prefix()` and `Trie.longest_prefix()` could previously be treated directly as `(key, value)` tuples. This is deprecated.
Fix: Access the `key` and `value` properties directly from the returned `_Step` or `_NoneStep` object (e.g., `result.key`, `result.value`).
gotcha When using the generic `pygtrie.Trie` with string keys, `iterkeys()` and similar methods will return keys as tuples of characters (e.g., `('f', 'o', 'o')`) instead of strings. This can be unexpected.
Fix: For string keys, prefer using `pygtrie.CharTrie` or `pygtrie.StringTrie`, which are designed to handle string keys and return them as strings.
gotcha The `PrefixSet.add()` method has counter-intuitive behavior: adding a key that is a prefix of existing keys will remove those longer keys. Also, adding a key that already has a prefix in the set will have no effect.
Fix: Understand the semantics of `PrefixSet.add()`: it ensures that only the shortest unique prefixes are stored. Review existing entries before adding to avoid unintended deletions or no-ops.

Install

pip install pygtrie Install with pip

Imports

Trie
```
from pygtrie import Trie
```
The module was renamed from 'trie' to 'pygtrie' in version 1.0. Older versions used 'from pytrie import trie'.
CharTrie
```
from pygtrie import CharTrie
```
StringTrie
```
from pygtrie import StringTrie
```
PrefixSet
```
from pygtrie import PrefixSet
```

Quickstart

Demonstrates basic usage of `Trie` for key-value storage and `StringTrie` for path-like keys, including prefix-based retrieval.

from pygtrie import Trie, StringTrie

t = Trie()
t['foo'] = 1
t['bar'] = 2
t['baz'] = 3
t['foobar'] = 4

print(f"Trie contains 'foo': {t['foo']}")
print(f"All items with prefix 'foo': {list(t.items('foo'))}")

s_trie = StringTrie(separator='/')
s_trie['/home/user/docs/report.pdf'] = 'Report 2023'
s_trie['/home/user/photos/vacation.jpg'] = 'Vacation Pics'

print(f"StringTrie for '/home/user/docs': {list(s_trie.keys('/home/user/docs'))}")

view raw JSON →