rust-fst 0.1.2

Python bindings for the Rust `fst` crate, providing sets and maps backed by finite state transducers.

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 and search_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