pygtrie

library2.5.0pypypi✓ verified 27d ago

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.

data serialization

pip install pygtrie

github ↗package ↗

INSTALL

IMPORT

SIG · PYGTRIE

pygtrie

datapythonv2.5.0

Install

1.6s avg

Import

10ms

Disk

16MB

Pass rate

10/ 10

Env Coverage10 / 10

glibc

3.9–3.13

musl

3.9–3.13

Install & Compatibility

Where this runs

tested against v2.5.0 · pip install

no network on importno background threads

Install × environment matrix

Each cell = how many times install + import succeeded across repeated harness runs. Partial = flaky.
glibc = Debian/Ubuntu slim · musl = Alpine Linux

musl

py 3.10–3.95 runs

installs and imports cleanly · install 0.0s · import 0.002s · 17.9MB

glibc

py 3.10–3.95 runs

installs and imports cleanly · install 1.6s · import 0.000s · 18MB

16MB installed

● package 16MB

Code

Verified usage

Verified import paths — ran on the pinned version, not inferred.

Trie

✓ from pygtrie import Trie

✗ from pytrie 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

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'))}")

Debug

Known issues

breakingThe 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`.

affects: <1.0

breakingPrior 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.

affects: >=2.0

deprecatedThe 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`).

affects: >=2.0

gotchaWhen 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.

affects: All versions

gotchaThe `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.

affects: All versions

Errors

Common errors & fixes

pygtrie.ShortKeyError: 'foo'

This error occurs when attempting to retrieve a value using `trie[key]` where the `key` exists as a prefix for other keys in the trie but does not have a value directly associated with itself. A `KeyError` would be raised if the key or prefix does not exist at all.

fix

To check if a key has an associated value, use `if key in trie:`. To retrieve a value safely, use `trie.get(key, default_value)` to provide a fallback, or ensure a value is set for the specific key before accessing it directly.

TypeError: separator is not a string

This error occurs when initializing a `pygtrie.StringTrie` and the `separator` argument provided is not a string, or `ValueError: separator can not be empty` is raised if an empty string is used.

fix

Ensure that the `separator` argument passed to `pygtrie.StringTrie` is a non-empty string, such as `pygtrie.StringTrie(separator='/')`.

AttributeError: 'tuple' object has no attribute 'join' (or other string methods)

Users often expect `pygtrie.Trie.keys()` or `iterkeys()` to return strings, but the base `Trie` class returns keys as tuples of their individual components (e.g., `('f', 'o', 'o')` instead of `'foo'`). Attempting to use string methods on these tuples will result in an `AttributeError`.

fix

If you intend to work with string keys and receive strings back, use `pygtrie.CharTrie` (for single-character components) or `pygtrie.StringTrie` (for keys split by a custom separator). For example, `t = pygtrie.CharTrie()` or `t = pygtrie.StringTrie()`.

RuntimeError: maximum recursion depth exceeded

This error can occur when performing recursive operations like `copy()` or `traverse()` on a `pygtrie.Trie` instance that has a very deep structure, as Python has a default recursion limit.

fix

For exceptionally deep tries, consider increasing Python's recursion limit temporarily using `sys.setrecursionlimit(new_limit)` (use with caution), or explore alternative (potentially iterative) methods for processing deep structures if available for your specific use case.

Upgrade

Version history

2.5.0latest on PyPI · released Sep 23, 2022

Audit

Dependencies

No dependency data recorded yet.

Agent activity

16 hits · last 30 days

node

Resources

githubhttps://github.com/mina86/pygtrie ↗

packagehttps://pypi.org/project/pygtrie/ ↗