Fuzzy Matcher
Fuzzy matching algorithm(s) in Rust!
Usage
In your Cargo.toml add the following:
[dependencies]
fuzzy-matcher = "*"
Here are some code example:
use fuzzy_matcher::skim::{fuzzy_match, fuzzy_indices};
assert_eq!(None, fuzzy_match("abc", "abx"));
assert!(fuzzy_match("axbycz", "abc").is_some());
assert!(fuzzy_match("axbycz", "xyz").is_some());
let (score, indices) = fuzzy_indices("axbycz", "abc").unwrap();
assert_eq!(indices, [0, 2, 4]);
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.
Clangd
- The algorithm is based on clangd's FuzzyMatch.cpp.
- Also checkout lewang/flx#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.