fuzzy-search

fuzzy-search provides collections for fuzzy search, allowing you to efficiently find strings that approximately match a pattern. It leverages algorithms and data structures such as BK Trees, Levenshtein Automaton, and SymSpell to enable fast and accurate fuzzy searching.

Motivation

The motivation behind the BK Trees, Levenshtein Automaton, and SymSpell algorithms lies in their ability to optimize the fuzzy search process specifically for scenarios where you want to find strings with an edit distance of N or less within choices. They achieve this optimization by reducing the need to perform actual edit distance calculations. These algorithms excel in the efficiency they bring to the search process by employing a technique known as "pruning". This technique prunes away choices that are guaranteed to be outside the desired edit distance, thereby significantly reducing the computational overhead.

For instance, consider the following code, which straightforwardly calculates the Levenshtein distance and returns strings within a maximum edit distance (max_edits):

pub fn fuzzy_search<E>(
    query: &str,
    choices: &[String],
    max_edits: usize,
) -> Vec<String>
where
    E: Fn(&str, &str) -> usize + Sync,
{
    choices
        .iter()
        .filter(|choice| levenshtein(query, choice) <= max_edits)
        .cloned()
        .collect()
}

While this approach works, it can be computationally expensive, especially for large datasets. BK Trees, Levenshtein Automaton, and SymSpell address this issue by employing various pruning strategies that eliminate candidate strings early in the search process. This optimization significantly reduces the number of edit distance calculations, making fuzzy searching more efficient, particularly for cases where the edit distance is relatively large or where the dataset is extensive.

Features

• BK-Tree
• Levenshtein Automaton
  • See this article for the actual implementations.
• SymSpell

Installation

Add the following line to your Cargo.toml file to include this library in your project:

[dependencies]
fuzzy-search = "0.1"

Example

BK-Tree

extern crate fuzzy_search;

use fuzzy_search::bk::BkTree;

fn main() {
    let choices = // put strings for fuzzy search

    let mut bk = BkTree::new(levenshtein, 2);
    for c in choices {
        bk.insert(c);
    }
    println!("{:?}", bk.fuzzy_search("food").len());
}

Levenshtein Automaton

extern crate fuzzy_search;

use fuzzy_search::automata::LevenshteinAutomata;

fn main() {
    let choices = // put strings for fuzzy search

    let automata = LevenshteinAutomata::new("food", 2);
    println!("{:?}", automata.fuzzy_search(&choices).len());
}

SymSpell

extern crate fuzzy_search;

use fuzzy_search::symspell::SymSpell;

fn main() {
    let choices = // put strings for fuzzy search

    let mut sym = SymSpell::new(levenshtein, 2);
    for c in choices {
        sym.insert(c);
    }
    println!("{:?}", sym.fuzzy_search("food").len());
}

License

This project is licensed under the MIT License. See the LICENSE file for details.