Fuzzy Matcher

Fuzzy matching algorithm(s) in Rust!

Usage

In your Cargo.toml add the following:

toml [dependencies] fuzzy-matcher = "*"

Here are some code example:

```rust use fuzzymatcher::FuzzyMatcher; use fuzzymatcher::skim::SkimMatcherV2;

let matcher = SkimMatcherV2::default(); asserteq!(None, matcher.fuzzymatch("abc", "abx")); assert!(matcher.fuzzymatch("axbycz", "abc").issome()); assert!(matcher.fuzzymatch("axbycz", "xyz").issome());

let (score, indices) = matcher.fuzzyindices("axbycz", "abc").unwrap(); asserteq!(indices, [0, 2, 4]); ```

• fuzzy_match only return scores while fuzzy_indices returns the matching indices as well.
• Both function return None if the pattern won't match.
• The score is the higher the better.

More example

echo "axbycz" | cargo run --example fz "abc" and check what happens.

About the Algorithm

Skim

The skim is currently used by skim, a fuzzy finder.

Skim V2

• Just like fzf v2, the algorithm is based on Smith-Waterman algorithm which is normally used in DNA sequence alignment
• Also checkout https://www.cs.cmu.edu/~ckingsf/bioinfo-lectures/gaps.pdf for more details
• The time complexity is O(mn) where m, n are the length of the pattern and input line.
• Space complexity is O(mn) for fuzzy_indices and O(2n) for fuzzy_match which will compress the table for dynamic programming.
• V2 matcher has an option to set the max element of the score matrix, if m*n exceeded the limit, it will fallback to a linear search.

Skim V1

• It's based on Smith's post Reverse Engineering Sublime Text’s Fuzzy Match
• The implementation here actually has some flaws that don't perform well in certain cases.
• It's recommended to checkout original implementation in C++ and JavaScript

Clangd

• The algorithm is based on clangd's FuzzyMatch.cpp.
• Also checkout https://github.com/lewang/flx/issues/98 for some variants.
• The algorithm is O(mn) where m, n are the length of the pattern and input line.
• Space complexity is O(mn) for fuzzy_indices and O(2n) for fuzzy_match which will compress the table for dynamic programming.