{"library":"pygtrie","title":"pygtrie: Pure Python Trie Data Structure","description":"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.","status":"active","version":"2.5.0","language":"en","source_language":"en","source_url":"https://github.com/google/pygtrie","tags":["trie","data structure","prefix tree","dictionary","mapping"],"install":[{"cmd":"pip install pygtrie","lang":"bash","label":"Install with pip"}],"dependencies":[],"imports":[{"note":"The module was renamed from 'trie' to 'pygtrie' in version 1.0. Older versions used 'from pytrie import trie'.","wrong":"from pytrie import trie","symbol":"Trie","correct":"from pygtrie import Trie"},{"symbol":"CharTrie","correct":"from pygtrie import CharTrie"},{"symbol":"StringTrie","correct":"from pygtrie import StringTrie"},{"symbol":"PrefixSet","correct":"from pygtrie import PrefixSet"}],"quickstart":{"code":"from pygtrie import Trie, StringTrie\n\nt = Trie()\nt['foo'] = 1\nt['bar'] = 2\nt['baz'] = 3\nt['foobar'] = 4\n\nprint(f\"Trie contains 'foo': {t['foo']}\")\nprint(f\"All items with prefix 'foo': {list(t.items('foo'))}\")\n\ns_trie = StringTrie(separator='/')\ns_trie['/home/user/docs/report.pdf'] = 'Report 2023'\ns_trie['/home/user/photos/vacation.jpg'] = 'Vacation Pics'\n\nprint(f\"StringTrie for '/home/user/docs': {list(s_trie.keys('/home/user/docs'))}\")\n","lang":"python","description":"Demonstrates basic usage of `Trie` for key-value storage and `StringTrie` for path-like keys, including prefix-based retrieval."},"warnings":[{"fix":"Update imports from `from pytrie import trie` to `import pygtrie as trie` or directly import classes like `from pygtrie import Trie`.","message":"The module name was changed from `trie` to `pygtrie` in the 1.0 release. Existing code using `from pytrie import trie` will break.","severity":"breaking","affected_versions":"<1.0"},{"fix":"If sorted iteration is required, use `trie.enable_sorting()` after initialization or when needed.","message":"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.","severity":"breaking","affected_versions":">=2.0"},{"fix":"Access the `key` and `value` properties directly from the returned `_Step` or `_NoneStep` object (e.g., `result.key`, `result.value`).","message":"The objects returned by `Trie.shortest_prefix()` and `Trie.longest_prefix()` could previously be treated directly as `(key, value)` tuples. This is deprecated.","severity":"deprecated","affected_versions":">=2.0"},{"fix":"For string keys, prefer using `pygtrie.CharTrie` or `pygtrie.StringTrie`, which are designed to handle string keys and return them as strings.","message":"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.","severity":"gotcha","affected_versions":"All versions"},{"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.","message":"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.","severity":"gotcha","affected_versions":"All versions"}],"env_vars":null,"last_verified":"2026-04-06T00:00:00.000Z","next_check":"2026-07-05T00:00:00.000Z"}