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

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

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.