11 releases
0.3.7 | Oct 4, 2020 |
---|---|
0.3.6 | Oct 3, 2020 |
0.3.5 | Jul 5, 2020 |
0.3.4 | Feb 23, 2020 |
0.1.0 | Mar 2, 2019 |
#115 in Text processing
85,847 downloads per month
Used in 178 crates
(59 directly)
67KB
1.5K
SLoC
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::FuzzyMatcher;
use fuzzy_matcher::skim::SkimMatcherV2;
let matcher = SkimMatcherV2::default();
assert_eq!(None, matcher.fuzzy_match("abc", "abx"));
assert!(matcher.fuzzy_match("axbycz", "abc").is_some());
assert!(matcher.fuzzy_match("axbycz", "xyz").is_some());
let (score, indices) = matcher.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.
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.
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)
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.
Dependencies
~87KB