MARISA Trie for Python

1.4.1 · active · verified Thu Apr 09

marisa-trie provides static, memory-efficient, and fast Trie-like data structures for Python, wrapping the C++ MARISA library. It's ideal for use cases like autocomplete, spell checkers, and storing large sets of strings or byte sequences for fast prefix matching and lookup. The library is actively maintained with regular updates to support new Python versions and minor feature enhancements.

Warnings

breaking Python 3.7 and 3.8 support was dropped. Users on these versions must upgrade Python or stick to older marisa-trie versions.
Fix: Upgrade to Python 3.9 or newer. For Python 3.7/3.8, use marisa-trie<1.3.0.
gotcha MARISA tries are immutable after creation. You cannot add or remove keys once the trie is built. To modify, you must build a new trie.
Fix: Plan your data set in advance. If dynamic updates are needed, MARISA Trie might not be the right choice, or you'll need to re-build the trie periodically.
gotcha The default `Trie` and `BytesTrie` classes expect `bytes` objects, not `str`. Operations like `trie.keys(b'prefix')` or `b'word' in trie` require byte strings.
Fix: Encode strings to bytes (e.g., `s.encode('utf-8')`) before passing them to `BytesTrie` methods. Alternatively, use `StringTrie` (available since v1.4.0) if you primarily work with `str` type keys and values.

Install

pip install marisa-trie Install stable version

Imports

Trie
```
from marisa_trie import Trie
```
Trie is an alias for BytesTrie and expects byte strings.
BytesTrie
```
from marisa_trie import BytesTrie
```
The primary Trie implementation for byte strings.
RecordTrie
```
from marisa_trie import RecordTrie
```
For storing structured data (records) associated with keys.
StringTrie
```
from marisa_trie import StringTrie
```
Introduced in v1.4.0, specifically for string-to-string mappings without manual encoding.

Quickstart

Demonstrates creating a BytesTrie (the default Trie) and a StringTrie, then performing basic lookups and prefix searches. Note that BytesTrie expects byte strings for all operations.

from marisa_trie import BytesTrie, StringTrie

# Example with BytesTrie (most common, requires bytes)
words_bytes = [b'apple', b'apricot', b'banana', b'bandana', b'cherry']
b_trie = BytesTrie(words_bytes)

print(f"'apple' in BytesTrie: {b'apple' in b_trie}")
print(f"Words starting with 'ap': {list(b_trie.keys(b'ap'))}")

# Example with StringTrie (requires strings, new in 1.4.0)
words_str = ['hello', 'world', 'helium', 'wonder']
s_trie = StringTrie(words_str)

print(f"'hello' in StringTrie: {'hello' in s_trie}")
print(f"Words starting with 'h': {list(s_trie.keys('h'))}")

view raw JSON →