Crate frizbee 

Frizbee is a SIMD typo-resistant fuzzy string matcher written in Rust, with bindings for C, C++, Python and WASM. The core of the algorithm uses Smith-Waterman with affine gaps, similar to FZF. In the included benchmark, with typo resistance disabled, it outperforms Nucleo by ~4x and FZF by ~5x and supports multithreading, see benchmarks. When matching against unicode, it outperforms Nucleo and FZF by 20x.

Used by blink.cmp, atuin, television, skim, and fff. Special thank you to stefanboca and ii14!

For commercial support, please contact me. I’d be happy to work with you directly! Also, please consider sponsoring me.

The core of the algorithm is Smith-Waterman with affine gaps and row-wise parallelism via SIMD. Besides the parallelism, this is the basis of other popular fuzzy matching algorithms like FZF and Nucleo. The main properties of Smith-Waterman are:

• Always finds the best alignment
• Supports insertion (unmatched char in haystack, basis of fuzzy matching)
• Supports deletion (unmatched char in needle, basis of typo-resistance)
• Supports substitution (haystack and needle char mismatch, basis of typo-resistance)

Example: using Matcher

Matcher compiles the pattern once, allocates memory for the Smith Waterman matrix, and reuses the selected SIMD backend.

Ideally, only construct these at most once per list. They’re cheap to construct, but end up being expensive if you construct them for each item in your list.

use frizbee::{Config, Matcher};

let needle = "fBr";
let haystacks = ["fooBar", "foo_bar", "barfoo", "prelude", "println!"];

let mut matcher = Matcher::new(needle, &Config::default());
let matches = matcher.match_list(&haystacks);
// or in parallel (8 threads, set to 0 to auto-detect)
let matches = matcher.match_list_parallel(&haystacks, 8);

Example: using multi-pattern queries

Matcher::from_query parses whitespace-separated atoms. Atom syntax can control the matching mode:

fuzzy  substring  prefix    suffix    exact    negated (combines with others)
foo    'foo       ^foo      foo$      ^foo$    !foo

use frizbee::{Config, Matcher};

let haystacks = ["foo", "barfoo", "foobar", "bar/foo"];
let mut matcher = Matcher::from_query("foo !^bar", &Config::default());
let matches = matcher.match_list(&haystacks);

Pattern::parse_query returns the parsed patterns, so per-pattern config can be applied before building the matcher. For example, setting the max typos based on needle length:

use frizbee::{Config, Matcher, Pattern};

let haystacks = ["foo", "barfoo", "foobar", "bar/foo"];
let patterns = Pattern::parse_query("foo !^bar")
    .into_iter()
    .map(|pattern| {
        let max_typos = (pattern.needle.len() / 4) as u16;
        pattern.max_typos(Some(max_typos))
    })
    .collect::<Vec<_>>();
let mut matcher = Matcher::from_patterns(&patterns, &Config::default());
let matches = matcher.match_list(&haystacks);

Example: using explicit Patterns

If query syntax is not a good fit, build patterns directly and pass them to Matcher::from_patterns or Matcher::new (if you only have one pattern).

use frizbee::{Config, Matcher, Matching, Pattern, PatternConfig};

let patterns = [
    Pattern::new("foo", PatternConfig::default()),
    Pattern::new("bar", PatternConfig::default().matching(Some(Matching::Prefix))).negated(true),
];
let haystacks = ["foo", "barfoo", "foobar"];

let mut matcher = Matcher::from_patterns(&patterns, &Config::default());
let matches = matcher.match_list(&haystacks);

Example: using FuzzyMatchExt

The iterator API is convenient when chaining with other iterator adapters, but it is slower than matching a full list with Matcher::match_list.

use frizbee::{iter::FuzzyMatchExt, Config, radix_sort_matches};

let haystacks = ["fooBar", "foo_bar", "prelude", "println!"];
let mut matches: Vec<_> = haystacks
    .iter()
    .fuzzy_match("fBr", &Config::default())
    .collect();
radix_sort_matches(&mut matches);

Modules

iter

Iterator extension for fuzzy matching

k_merge

Merges multiple pre-sorted runs of crate::Matches into a single sorted Vec using the k-way merge algorithm specialized for crate::Matches.

Structs

Config

Match

Result of a fuzzy match, containing the score and index in the haystack

MatchIndices

Like Match but includes the indices of the chars in the haystack that matched the needle in reverse order

Matcher

Primary entrypoint for fuzzy matching

Pattern

A single pattern to match, parsed from syntax like !^foo

PatternConfig

Per-pattern overrides for the matcher’s Config. Every field is optional and falls back to the matcher’s Config when left as None (see PatternConfig::resolve)

Scoring

Controls the scoring used by the smith waterman algorithm. Pay close attention to the documentation for each property, as small changes can lead to poor matching.

Enums

CaseMatching

Matching

Selects the matching algorithm

SortStrategy

UnicodeMatching

Functions

radix_sort_matches

Sorts a slice of Match values in-place by descending score using a stable radix sort. This assumes that the matches are already sorted by index.