Fast typo-resistant fuzzy matching via SIMD smith waterman, similar algorithm to FZF
Fast typo-resistant fuzzy matching via SIMD smith waterman, similar algorithm to FZF
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.
See the docs for more usage examples.
…or use the slightly slower fuzzy_match iterator API
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);The bindings directory contains bindings for C, C++, Python and JS (WASM).
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.
See BENCHMARKS.md
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:
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.
…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.
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_stdFrizbee supports no_std (requires alloc) by disabling the default std feature, in which case Matcher::match_list_parallel is unavailable.
frizbee = { version = "...", default-features = false }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)).
No open issues yet, or sync has not completed.