Frizbee scores fuzzy matches with Smith-Waterman instead of counting them

Why Smith-Waterman rather than a character filter

Frizbee is a SIMD typo-resistant fuzzy string matcher written in Rust, and its distinguishing choice is the algorithm. The core uses Smith-Waterman with affine gaps, and the README says the same family of approach underlies other popular fuzzy matching algorithms such as FZF and Nucleo. The properties the README lists are what make it work for this problem. Smith-Waterman always finds the best alignment. It supports insertion, an unmatched character in the haystack, which is the basis of fuzzy matching. It supports deletion, an unmatched character in the needle, which is the basis of typo resistance. And it supports substitution, a mismatch between haystack and needle characters, also the basis of typo resistance. So a typo in the query is not a special case bolted onto a matcher, it is an alignment operation the algorithm already knows how to score. The result is a ranked list where the ordering reflects alignment quality rather than a count of matched characters.

The prefilter loads the haystack twice instead of seven times

The prefilter is the part where the SIMD work is visible, and the README walks through it in detail. Nucleo and FZF both use a prefiltering step that removes any haystack that does not include all of the characters in the needle. Frizbee does this by default but supports alternative algorithms so that typos are allowed, and the maximum number of typos is controlled by the `max_typos` property. The difference in implementation is in how the haystack is loaded. Nucleo uses `memchr` to ensure the needle is wholly contained in the haystack in the correct order, and for case insensitive matching it checks the lowercase and uppercase needle characters separately. For each character it loads the haystack from the previously matched position and performs a sequential search via SIMD, which the README says results in many unnecessary loads, giving the worked example of a needle of 6 characters against a haystack of length 32 with 16 byte wide SIMD leading to 6 plus 2 minus 1, or 7 loads. Frizbee instead loads the haystack chunk by chunk and masks out the already-matched prefix for each needle character, so the same case gives 2 loads. It also uses prefiltering to find the prefix and suffix of characters in the haystack that cannot match, in a similar way to FZF.

Matching a list, in parallel, with a query language

The API is Rust-first, and there are three ways to use it. The basic form builds a matcher from a needle and a config and runs it over a list of haystacks.

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

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

The multi-pattern query form takes a whitespace separated query string instead.

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

A `Matcher` is built from a needle and a `Config`, and `match_list` runs it over a list of haystacks. `match_list_parallel` does the same with a thread count, where 8 threads can be requested or 0 can be passed to auto-detect. And `Matcher::from_query` takes a whitespace separated multi-pattern query with syntax for controlling the matching mode. The documented modes are fuzzy, substring, prefix, suffix, exact and negated, and the latter combines with the others, with the examples showing `foo` for a plain fuzzy match, `^foo` for prefix, `foo$` for suffix, `^foo$` for exact and `!foo` for negated. Per-pattern configuration is possible as well, where `Pattern::parse_query` produces patterns you can adjust before handing them to `Matcher::from_patterns`, and the example computes a maximum typo count from the needle length. There is also a slightly slower iterator API built on the `fuzzy_match` extension trait, with `radix_sort_matches` for ordering the results.

Four language bindings with very different performance profiles

The bindings directory holds four ways in, and the README is candid that they are not equivalent. The C binding, `frizbee-c`, exposes a C ABI with a C++ header and has pre-built binaries on the GitHub releases page, and it gives native performance. The Python binding, `frizbee-py`, targets Python 3.10 and later and gives native performance after a one-time copy of the strings into Rust, which the README measures as 42ms for the copy on Chromium and 24ms for the matching. The WebAssembly binding, `frizbee-wasm`, is a SIMD128 build and is described as 60 percent slower, at 40.5ms on Chromium, than AVX-512, with the one-time copy of strings into Rust costing 130ms when `maxItems` is 1000. The README also warns that sending `Match` objects to JavaScript carries significant overhead, so `maxItems` is essential for performance-critical use cases, and that the WASM binary is 50KBs compressed with Brotli. If you bundle the crate into your own WASM build, you need `RUSTFLAGS='-C target-feature=+simd128'` or the scalar path is taken.

Benchmark claims and the projects already using it

The performance claim is stated precisely, and it is worth reading the qualifiers rather than the headline. In the included benchmark, with typo resistance disabled, Frizbee outperforms Nucleo by roughly 4x and FZF by roughly 5x, and it supports multithreading. When matching against unicode, it outperforms Nucleo and FZF by 20x. The details are in BENCHMARKS.md, and the benchmark harness is criterion, with a `lib` bench and a `sort` bench configured in the manifest, and the dev dependencies pull in nucleo 0.5.0 and rand and rand_distr for the property tests. The adoption list is more telling than the numbers. Frizbee is used by blink.cmp, atuin, television, skim and fff, which are all fuzzy-finder or shell-adjacent tools, and the README thanks two contributors by name. Note that all of these figures come from the project's own benchmark, so the sensible move is to run it on your own data.

A Rust workspace with three binding crates

The repository is a Cargo workspace, and the manifest shows how the pieces fit together. The root package is `frizbee` at version 0.13.0, with the licence MIT, edition 2024, and a minimum supported Rust version of 1.89.0. The workspace members are the three binding crates, `bindings/frizbee-c`, `bindings/frizbee-py` and `bindings/frizbee-wasm`. The release profile enables link time optimisation, and the feature flags are small and worth knowing about. `std` is on by default and is required for `Matcher::match_list_parallel`, `serde` is optional and enables serialisation, `match_end_col` and `safe_read` are off by default, and the `safe_read` flag exists because the hot loops read unaligned memory. The crate also ships a `justfile` that drives the whole matrix, with a test target that runs the Rust tests, the C tests, the Python tests and the WASM tests, and separate build and bench targets for each. The C test target regenerates the header with cbindgen and fails if the checked-in header differs, which is a cheap guard against a stale public API.

Where Frizbee is the wrong choice

There is a clear case against it, and it is about maturity and about the shape of the API rather than about speed. The version is 0.13.0, which in Cargo semantics means the API is still allowed to change, and the project is one maintainer's work with a single published release line. If you are choosing a fuzzy matcher for a tool other people depend on, the alternatives named in the README itself, FZF and Nucleo, are the ones with wider use, and Nucleo is already a dev dependency here for comparison. Second, the iterator API is documented as slightly slower, and if your use case is a small interactive list you are paying for a design built for large haystacks. Third, the WASM path has the `maxItems` caveat and the SIMD128 build requirement, so a browser integration that ignores those two details will be slower than the README suggests. And fourth, the typo tolerance is opt-in in the sense that the default prefilter removes haystacks lacking the needle's characters, so a query with a typo will find nothing until you configure `max_typos` and the alternative prefilter algorithms.

Editorial conclusion

Adopt Frizbee when you need ranked fuzzy matches with typo tolerance in a Rust codebase, or when you need the same algorithm available from C, Python or WebAssembly with consistent results. Skip it if you need a proven, battle-tested matcher and would rather not read the source of a young crate, since the version is 0.13.0 and the published benchmark is the author's own. Before you commit, run the bundled benchmarks yourself on your own haystacks, and if you build the WebAssembly binding into your own bundle, set the simd128 target feature as the README requires.

Frequently asked questions

Official sources

1. License: MIT
2. Project website
3. README
4. Releases
5. saghen/frizbee on GitHub