Baike.dev
All toolsOnline toolsAI codingTrendingOpen sourceNewsSubmit
Log in
< Back to tools
F

frizbee

> 编程语言
Open source

Fast typo-resistant fuzzy matching via SIMD smith waterman, similar algorithm to FZF

570 stars0 likes0 views
WebsiteGitHub

About

Fast typo-resistant fuzzy matching via SIMD smith waterman, similar algorithm to FZF

Frizbee

Frizbee is a SIMD typo-resistant fuzzy string matcher written in Rust, with bindings for C, C++, Python and JS (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.

Usage

See the docs for more usage examples.

…

or use the slightly slower fuzzy_match iterator API

rust
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);

Bindings (C, C++, Python, JS (WASM))

The bindings directory contains bindings for C, C++, Python and JS (WASM).

  • frizbee-c (C ABI, C++ header): Native performance, pre-built binaries available on GitHub Releases
  • frizbee-py (Python 3.10+): Native performance after one-time copy of strings to Rust (42ms copy on Chromium, 24ms for matching)
  • frizbee-wasm (SIMD128 WASM): 60% slower (40.5ms on Chromium) than AVX-512 with one-time copy of strings to Rust (130ms) with maxItems = 1000. Sending Match objects to JS has significant overhead so maxItems is essential for performance critical use cases. The WASM binary is 50KBs (Brotli)

If you're integrating this crate into your own WASM bundle, include RUSTFLAGS='-C target-feature=+simd128' while building your project, otherwise the scalar path will be taken. See this repo's .cargo/config.toml.

Benchmarks

See BENCHMARKS.md

Algorithm

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)

Prefiltering

Nucleo and FZF use a prefiltering step that removes any haystacks that do not include all of the characters in the needle. Frizbee does this by default but supports alternative algorithms to allow for typos. You may control the maximum number of typos with the max_typos property.

Nucleo uses memchr to ensure that the needle is wholly contained in the haystack, in the correct order. For case insensitive matching, it checks the lowercase and uppercase needle chars separately. For each character, it loads the haystack from the previously matched position and performs a sequential search via SIMD. This results in many unnecessary loads (for a needle of 6 chars with a haystack of length 32 with 16 byte wide SIMD, this would lead to 6 + 2 - 1 = 7 loads).

Frizbee improves upon this by loading the haystack chunk by chunk and masking out the already-matched prefix for each needle char. This results in a haystack of length 32 with 16 byte wide SIMD only performing 2 loads. Frizbee also uses prefiltering to find the prefix/suffix of the haystack of characters that are impossible to match (not in the needle), similar to FZF.

…

Smith Waterman

The matrix receives a row per needle UTF-8 codepoint, rather than per needle byte. This significantly reduces the size of the matrix versus the naive path (i.e. 5 chars of 3 bytes/char would be 15 rows vs 5 rows). The match mask uses a similar approach to the prefilter with the offset loads. The tricky part was applying the gap propagation, since we only want to apply a gap penalty once per multi-byte haystack char. The solution was to keep track of the number of lead/continuation bytes we've crossed, see the docs on the implementation.

Limitations

Frizbee will not perform any unicode normalization before matching. You should apply this yourself if you need it.

With the default UnicodeMatching::Smart, an ASCII needle matching against a haystack with multi-byte UTF-8 codepoints will have a slightly lower score than a pure ASCII haystack. For example, hw matched against hw will receive a penalty to the score of gap_open_penalty + gap_extend_penalty * 4 due to the emoji taking up 4 bytes. If the haystack was instead hew, the penalty would be gap_open_penalty + gap_extend_penalty. Typically, this shouldn't be an issue, but you can force the slower unicode path with UnicodeMatching::Always on ASCII needles if necessary.

For case-insensitive matching, the case flipped version will be skipped if it's a different byte length (İ -> i in Turkish) or has multiple codepoints (such as the German ß -> SS). These cases are typically very rare (<0.01% of text, depending on language). This could be solved by running match_list twice when one of these is detected in the needle, PRs welcome!

Unlike FZF/Nucleo, Frizbee will not match a against á.

no_std

Frizbee supports no_std (requires alloc) by disabling the default std feature, in which case Matcher::match_list_parallel is unavailable.

toml
frizbee = { version = "...", default-features = false }

Safety

On stable Rust, it's only possible to use SIMD via intrinsics (portable-simd is nightly-only). Many excellent safe SIMD wrappers exist (fearless_simd or wide + cargo-multivers) but using raw intrinsics has slightly better performance and compatibility, at the cost of testing overhead. The codebase isolates the vast majority of the unsafe code to SIMD "Backend"s (prefilter and smith waterman) which contain many unit/property tests, checked through Miri. For those interested in writing SIMD themselves, it's actually possible to write safe SIMD with only one unsafe block and a macro, check out Sergey Davidoff's blog post on the topic.

Without the safe_read feature, Frizbee will over-read haystacks when safe to do so (within page-boundary) which will trigger the AddressSanitizer. Without AVX512, performance regresses by ~40% with safe_read enabled. Over-reads are automatically disabled when running inside of miri (cfg!(miri)).

Issues· 0 open

View all issuesOpen on GitHub

No open issues yet, or sync has not completed.

> Tags

Rust

No comments yet. Be the first to share.

> Details

PublishedAug 1, 2026
UpdatedSep 17, 2026
Category编程语言
PricingOpen source

> Related tools

T
TypeScript
JavaScript 的超集,为前端与全栈提供静态类型
P
Python
通用编程语言,广泛用于 Web、数据与 AI
G
Go
Google 推出的简洁高效系统语言