Fuzzies

Fuzzies is a fast, friendly integration layer that bridges the gap between low-level finite state transducers (fst) and Levenshtein automata, saving you from writing tedious boilerplate.

More information about this crate can be found in the crate documentation

Installation

cargo add fuzzies

Example

use fuzzies::{Dictionary, DictionaryError};

fn main() -> Result<(), DictionaryError> {
    // Prepare your raw text file (must be sorted lexicographically)
    // Fuzzies provides a handy in-place sorter for convenience:
    Dictionary::sort("words.txt")?;

    // Build the immutable binary FST from the sorted text file
    Dictionary::build("words.txt", "words.fst")?;

    // Load the dictionary (memory-mapped from disk)
    let dict = Dictionary::open("words.fst")?;

    // Check for exact matches instantly
    if dict.contains("banana") {
        println!("Exact match found!");
    }

    // Perform a fuzzy search with a max typo distance of 2 and limit of 5 results
    let results = dict.search("banaan")
        .distance(2)
        .transposition(true) // Handles adjacent swaps (e.g., "teh" -> "the")
        .prefix(false)       // Set to true for prefix fuzzy lookups
        // .ge("a").lt("e")  // Optionally restrict search bounds (e.g., 'a' <= key < 'e')
        .limit(5)
        .execute()?;
    
    for result in results {
        println!("Found: {}", result);
    }

    // Batch search (multithreaded, defaults to a distance of 1)
    let queries = vec!["aple", "baxana", "cherri"];
    let batch_results = dict.batch_search(&queries).execute();

    for (query, result) in queries.iter().zip(batch_results) {
        match result {
            Ok(matches) => println!("Query '{}' found {} matches", query, matches.len()),
            Err(e) => eprintln!("Error searching for '{}': {}", query, e),
        }
    }

    Ok(())
}

Embedding Data

If you don't want to manage external .fst files on disk, embed the dataset directly into your application:

static DICT_DATA: &[u8] = include_bytes!("../assets/words.fst");
let dict = Dictionary::from_embedded(DICT_DATA)?;

Built with Fuzzies

Check out real-world projects utilizing fuzzies:

• Mamoru: A blazing-fast Git commit-msg hook that embeds a compiled dictionary of over 106,000 words to instantly catch and block typos before they make it into your version control history.

🎈 Performance

The following benchmarks were gathered using Criterion to evaluate lookup speeds for single and parallel batch searches. You can re-run these benchmarks on your hardware using cargo bench.

Single Search

Dictionary Single Search/apple          6.8904 µs/iter (+/- 0.0174 µs)
Dictionary Single Search/baxana         8.1007 µs/iter (+/- 0.0321 µs)
Dictionary Single Search/missingword   12.1830 µs/iter (+/- 0.0285 µs)

Batch Search

Rayon Parallel Batch/100 queries      406.79 µs/iter (+/- 1.60 µs)
Rayon Parallel Batch/500 queries     1.9530 ms/iter (+/- 0.0051 ms)
Rayon Parallel Batch/1000 queries    3.9583 ms/iter (+/- 0.0141 ms)

[!NOTE] Benchmarks were executed on an Intel Core i5-10300H (4 cores, 8 threads, Battery set to High Performance mode). Performance may scale significantly higher on more modern or high-end CPUs.

License

This project is licensed under the MIT license.