ngrammatic 0.5.0

This crate provides fuzzy search/string matching using N-grams.

This implementation is character-based, rather than word based, matching solely based on string similarity.

Licensed under the MIT license.

Documentation

https://docs.rs/ngrammatic/latest/ngrammatic/

Installation

This crate is published on crates.io.

To use it, add this to your Cargo.toml:

[dependencies]
ngrammatic = "0.5"

Or, for a possible improvement search speeds, enable the "rayon" feature:

[dependencies]
ngrammatic = { version = "0.5", features = ["rayon"] }

Benchmark results show 0-80% performance improvement in search, but a 0-3% performance decline for corpus creation. With such a wide variation in performance impact, it was decided not to enable it by default. When enabled, it is possible to use any combination of serialized or parallelized methods depending on which shows better performance for your use cases.

Usage

To do fuzzy matching, build up your corpus of valid symbols like this:

use ngrammatic::{CorpusBuilder, Pad};

let mut corpus = CorpusBuilder::new()
    .arity(2)
    .pad_full(Pad::Auto)
    .finish();

// Build up the list of known words
corpus.add_text("pie");
corpus.add_text("animal");
corpus.add_text("tomato");
corpus.add_text("seven");
corpus.add_text("carbon");

// Now we can try an unknown/misspelled word, and find a similar match
// in the corpus
let word = String::from("tomacco");
if let Some(top_result) = corpus.search(word, 0.25).first() {
    if top_result.similarity > 0.99 {
        println!("✔ {}", top_result.text);
    } else {
        println!("❓{} (did you mean {}? [{:.0}% match])",
                 word,
                 top_result.text,
                 top_result.similarity * 100.0);
    }
} else {
    println!("🗙 {}", word);
}

Benchmarking

Some benchmarks exist to compare the performance of various scenarios.

In order to run them, rayon must be enabled, e.g.:

cargo bench --features rayon

The benchmarks of the top-domains.txt file can take quite a long time to complete, as they're working against a very large dataset.

Here's a sample of data collected from the 0.5 version on my development machine:

Do note that those search times against the top domain names corpus were taking several seconds to complete in the case where a perfect match exists. It's unclear at the moment why search results with perfect matches always take significantly longer.

Areas for future improvement

Adding string interning to the corpus was a really big performance and memory win. Unfortunately, updating Ngram with interning is quite a bit more complicated, and I'm open to proposals for how to accomplish it.

Interning the grams themselves (HashMap<String, usize>) might be less of a win, though. The default symbol for StringInterner is a u32, while the string itself is the same size or small for arity <= 4. Because we don't actually care about the 'stringness' of the grams, something like a tinyvec pre-sized to arity could be a win.