Crate neo_frizbee 

Frizbee is a SIMD typo-resistant fuzzy string matcher written in Rust. 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, 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 match_list

use neo_frizbee::{match_list, match_list_parallel, Config};

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

let matches = match_list(needle, &haystacks, &Config::default());
// or in parallel (8 threads)
let matches = match_list_parallel(needle, &haystacks, &Config::default(), 8);

Example: using Matcher

Useful for when you want to match one needle against more than one haystack.

use neo_frizbee::{Matcher, Config};

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

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

Example: using FuzzyMatchExt

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

Structs

Config

Match

MatchIndices

Matcher

Scoring

Enums

CaseMatching

UnicodeMatching

Constants

SIMD_CHUNK_BYTES

Chunk width in bytes for the resolver-based matching APIs (crate::match_list_parallel_resolved). Haystacks are provided as lists of pointers to chunks of this size, with the last chunk zero-padded.

Functions

k_merge_matches

Merges multiple pre-sorted runs of Matches into a single sorted Vec.

match_list

Matches a list of haystacks, returning a list of Match values. This API provides the most performant path when matching on lists.

match_list_indices

Matches a list of haystacks, returning a list of MatchIndices which are equivalent to Match except they include the indices of the matched characters in the haystack.

match_list_parallel

Matches a list of haystacks in parallel on multiple real threads, returning a list of Match values. Threads work on 2048 item chunks, which are sorted and merged into a single sorted Vec at the end. The threads must be >0.

match_list_parallel_resolved

Matches items in parallel on multiple real threads, resolving each item’s haystack bytes through the resolve callback, returning a list of Match values. Threads work on 2048 item chunks, which are sorted and merged into a single sorted Vec at the end. The threads must be >0.

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.