Fuzzy Matcher
Fuzzy matching algorithm(s) in Rust!
Usage
In your Cargo.toml add the following:
[]
= "*"
Here are some code example:
use FuzzyMatcher;
use SkimMatcherV2;
let matcher = default;
assert_eq!;
assert!;
assert!;
let = matcher.fuzzy_indices.unwrap;
assert_eq!;
fuzzy_match
only return scores whilefuzzy_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)
wherem, n
are the length of the pattern and input line. - Space complexity is
O(mn)
forfuzzy_indices
andO(2n)
forfuzzy_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.
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)
wherem, n
are the length of the pattern and input line. - Space complexity is
O(mn)
forfuzzy_indices
andO(2n)
forfuzzy_match
which will compress the table for dynamic programming.