pygtrie

pygtrie is a pure Python implementation of a trie, also known as a radix or prefix tree, that associates keys with values based on shared prefixes. Its Trie, CharTrie, and StringTrie classes each implement Python’s MutableMapping interface, so a Trie works as a drop-in replacement for a dict while adding prefix-aware operations like shortest/longest-prefix lookup, subtrie iteration, and subtrie deletion that a plain dict cannot do without scanning every key.

Beyond the core Trie classes, pygtrie ships PrefixSet, a set variant where membership means “this key or one of its prefixes is present,” useful for compactly representing directory, URL, or permission hierarchies. The library has no runtime dependencies, ships type stubs (py.typed), and is fully typed for mypy strict mode, making it straightforward to drop into a codebase that already tracks types tightly.

What You Get

• Trie: a dict-like MutableMapping keyed on iterables of hashable steps
• CharTrie and StringTrie: string-keyed variants that return str keys/paths instead of tuples, with StringTrie splitting on a configurable separator
• PrefixSet: a MutableSet where a key is considered a member if it or any of its prefixes was added
• ShortKeyError plus shortest_prefix/longest_prefix lookup helpers that return a cursor-like Step object
• Subtrie iteration and deletion so an entire prefix branch can be read or removed in one call

Common Use Cases

• Autocomplete and prefix search over large string keysets
• Routing tables that dispatch on the longest matching URL or filesystem-path prefix
• IP address / CIDR-style prefix matching
• Building permission or namespace hierarchies with PrefixSet

Under The Hood

Architecture pygtrie is a single-module implementation layered internally: _NoChildren/_OneChild/_Children node classes implement a size-optimized children-storage strategy chosen dynamically depending on how many children a node has, _Step wraps traversal-cursor state returned from prefix lookups, and the public Trie/CharTrie/StringTrie/PrefixSet classes sit on top implementing MutableMapping/MutableSet. Trie delegates key-to-path conversion to overridable _path_from_key/_key_from_path hooks, which is how CharTrie and StringTrie customize key representation without touching node or traversal internals — a clean separation for what is fundamentally one data structure with several front-ends.

Tech Stack Pure Python with zero runtime dependencies, targeting Python 3.11+, using only the standard library (copy, collections.abc, warnings, types, typing). It ships py.typed for type-checker consumption and is packaged as a single py_modules entry rather than a package directory, via a custom setup.py that stamps version numbers into the source and drives Sphinx documentation builds; docs are hosted on Read the Docs.

Code Quality The test suite is a large unittest-based file that exercises all three Trie flavors through a parameterized factory pattern covering multiple construction styles (dict, kwargs, tuples, update, sorted) against each subtype — a strong technique for cross-cutting coverage relative to the size of the implementation. A .pylintrc and a strict mypy.ini (disallow_untyped_defs, warn_unreachable, and related strict flags) enforce linting and static typing, and the module itself is fully annotated with generics and protocols. No GitHub Actions workflow was found in the repository, so it is unclear whether tests and lint run automatically on every push.

What Makes It Unique Implementing a trie as a genuine MutableMapping/MutableSet subclass isn’t a new idea, but the lookup API is thoughtfully designed: shortest_prefix/longest_prefix return a cursor object that participates in truth-value testing and exposes its own .get()/.value() methods, avoiding the awkward sentinel-based prefix APIs common in other trie libraries. The subclassing hook pattern for key conversion lets consumers plug in custom key types, such as pathlib.Path, without touching internals, as shown directly in the class documentation.