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 on an Intel Core i5-10300H (4 cores / 8 threads). You can re-run these on your hardware with cargo bench.

[!NOTE] Running cargo bench on the published crate executes against a small, dynamically generated dataset. The 106,000-word benchmarks shown below were gathered independently using a local dictionary.

License

This project is licensed under the MIT license.