python-rust-fst
Python bindings for burntsushi's fst crate (rustdocs) for FST-backed sets and maps.
For reasons why you might want to consider using it, see BurntSushi's great article on "Index[ing] 1,600,000,000 Keys with Automata and Rust".
tl;dr:
- Work with larger-than-memory sets
- Perform fuzzy search using Levenshtein automata
Installation
- You will need:
- Python >= 3.3, Python or PyPy >= 2.7 with development headers installed
- Rust nightly (install via rustup)
- Clone the repository. Installation with
pip install git+...
does not work currently - Run
rustup override add nightly
to add an override for rustup to use the nightly channel for the repository - Run
python setup.py bdist_wheel
to generate a wheel - Install the wheel with
pip install dist/rust_fst-0.1-py3-none-any.whl
Status
The package exposes almost all functionality of the fst
crate, except for:
- Combining the results of slicing,
search
andsearch_re
with set operations - Using raw transducers
Examples
from rust_fst import Map, Set
# Building a set in memory
keys = ["fa", "fo", "fob", "focus", "foo", "food", "foul"]
s = Set.from_iter(keys)
# Fuzzy searches on the set
matches = list(s.search(term="foo", max_dist=1))
assert matches == ["fo", "fob", "foo", "food"]
# Searching with a regular expression
matches = list(s.search_re(r'f\w{2}'))
assert matches == ["fob", "foo"]
# Store map on disk, requiring only constant memory for querying
items = [("bruce", 1), ("clarence", 2), ("stevie", 3)]
m = Map.from_iter(items, path="/tmp/map.fst")
# Find all items whose key is greater or equal (in lexicographical sense) to
# 'clarence'
matches = dict(m['clarence':])
assert matches == {'clarence': 2, 'stevie': 3}
Documentation
Head over to readthedocs.org for the API documentation.
If you want to know more about performance characteristics, memory usage and about the implementation details, please head over to the documentation for the Rust crate