9 releases

✓ Uses Rust 2018 edition

new 0.3.5 Jul 5, 2020
0.3.4 Feb 23, 2020
0.3.1 Dec 10, 2019
0.2.2 Dec 1, 2019
0.1.0 Mar 2, 2019

#26 in Text processing

Download history 844/week @ 2020-03-16 1234/week @ 2020-03-23 1442/week @ 2020-03-30 824/week @ 2020-04-06 686/week @ 2020-04-13 490/week @ 2020-04-20 672/week @ 2020-04-27 479/week @ 2020-05-04 506/week @ 2020-05-11 414/week @ 2020-05-18 626/week @ 2020-05-25 659/week @ 2020-06-01 693/week @ 2020-06-08 1158/week @ 2020-06-15 884/week @ 2020-06-22 672/week @ 2020-06-29

2,836 downloads per month
Used in 27 crates (11 directly)

MIT license

62KB
1.5K SLoC

Crates.io

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

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.

Dependencies

~44KB