## fuzzy-matcher

Fuzzy Matching Library

### 9 releases

✓ Uses Rust 2018 edition

 new 0.3.5 Jul 5, 2020 Feb 23, 2020 Dec 10, 2019 Dec 1, 2019 Mar 2, 2019

#26 in Text processing

Used in 27 crates (11 directly)

62KB
1.5K SLoC # Fuzzy Matcher

Fuzzy matching algorithm(s) in Rust!

## Usage

``````[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 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.

### 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.

### 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.

~44KB