### 19 releases

new 0.3.26 | Aug 5, 2024 |
---|---|

0.3.25 | Aug 5, 2024 |

0.3.23 | Mar 9, 2024 |

0.3.13 | Feb 28, 2024 |

0.3.10 | May 23, 2023 |

#**165** in Algorithms

**947** downloads per month

Used in **3** crates
(via two_percent)

**MIT**license

79KB

2K
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``]``)``;`

only return scores while`fuzzy_match`

returns the matching indices as well.`fuzzy_indices`- Both function return None if the pattern won't match.
- The score is the higher the better.

## More example

and check what happens.`echo "axbycz" | cargo run --example fz "abc"`

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

where`O``(`mn`)`

are the length of the pattern and input line.`m``,`n - Space complexity is

for`O``(`mn`)`

and`fuzzy_indices`

for`O``(`2n`)`

which will compress the table for dynamic programming.`fuzzy_match` - V2 matcher has an option to set the max element of the score matrix, if

exceeded the limit, it will fallback to a linear search.`m``*`n

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

where`O``(`mn`)`

are the length of the pattern and input line.`m``,`n - Space complexity is

for`O``(`mn`)`

and`fuzzy_indices`

for`O``(`2n`)`

which will compress the table for dynamic programming.`fuzzy_match`

#### Dependencies

~86KB