zsift-matcher

Fast fuzzy matching library for Zig, inspired by nucleo (Rust). Built for editors, CLI tools, and anything that needs to rank search results by relevance.

Uses Smith-Waterman dynamic programming with affine gap penalties for optimal scoring, with a SIMD-accelerated batch path that processes 8 haystacks simultaneously on ARM NEON (16 on AVX2).

Naming: this library was previously called zmatch. It's the matcher half of a nucleo-style split: zsift-matcher (this repo) is the pure, thread-free SIMD matching layer, and zsift is the async, thread-pooled engine on top of it (item store + worker pool + query state). Use this crate directly when you want to score haystacks yourself; use zsift when you want a streaming, non-blocking match engine for a large/incremental list.

Features

• Optimal scoring -- Smith-Waterman DP with affine gaps, camelCase/boundary/consecutive bonuses
• SIMD batch matching -- 2-2.4x faster than scalar for bulk workloads (score-identical)
• Extended search syntax -- fzf-compatible pattern parsing with AND/OR, negation, prefix/suffix/exact/boundary modes
• Unicode support -- full case folding (~1484 entries), accent normalization (816 entries), smart case/normalization
• Top-K selection -- min-heap based O(N log K) without materializing all scores
• Zero allocations during matching -- all scratch memory pre-allocated
• Match indices -- get the positions of matched characters for highlighting
• Greedy fallback -- O(n) path for oversized haystacks
• Configurable -- custom delimiters, bonus weights, path matching presets, prefix preference

Search syntax

zsift-matcher supports fzf's extended search syntax via the Pattern type. Multiple terms are separated by spaces and combined with AND logic. A standalone | between terms creates OR groups.

A \ before a special character escapes it: \^foo matches ^foo literally, foo\ bar matches foo bar as one term.

OR groups: go$ | rb$ | py$ matches items ending with .go, .rb, or .py. Combined with AND: ^core go$ | rb$ | py$ matches items starting with core that end with any of the three.

constzsm=@import("zsift_matcher");varmatcher=tryzsm.Matcher.initDefault(allocator);defermatcher.deinit();constpattern=zsm.Pattern.parse("^src/ 'config !.bak$");if(pattern.match(&matcher,"src/config.zig"))|score|{// matches: starts with "src/", contains "config", doesn't end with ".bak"}

Usage

As a Zig package

// build.zig.zon dependencies:.zsift_matcher=.{.url="https://codeberg.org/sicher/zsift-matcher/archive/main.tar.gz",.hash="...",// zig build --fetch will fill this in},

// build.zigconstzsm_mod=b.dependency("zsift_matcher",.{}).module("zsift_matcher");exe.root_module.addImport("zsift_matcher",zsm_mod);

The module is imported as zsift_matcher; the examples below alias it to zsm for brevity.

Single match

constzsm=@import("zsift_matcher");varmatcher=tryzsm.Matcher.initDefault(allocator);defermatcher.deinit();// Score-only (returns ?u16 -- null means no match, higher is better)if(matcher.match("src/fuzzy_optimal.zig","fopt",.fuzzy))|score|{std.debug.print("score: {d}\n",.{score});}// With match positions (byte indices for highlighting)varindices:[128]u32=undefined;if(matcher.matchIndices("FooBarBaz","fbz",.fuzzy,&indices))|score|{// indices[0..3] = { 0, 3, 6 }std.debug.print("score: {d}, positions: {any}\n",.{score,indices[0..3]});}

Batch matching (SIMD)

constzsm=@import("zsift_matcher");varbatch=tryzsm.BatchMatcher.initDefault(allocator);deferbatch.deinit();consthaystacks=[_][]constu8{"foo","foobar","baz","football"};varresults:[haystacks.len]?u16=undefined;batch.matchAll(&haystacks,"foo",.fuzzy,&results);// results = { score, score, null, score }

BatchMatcher uses SIMD internally for throughput but produces identical scores to the scalar Matcher. Use it when scoring many haystacks against the same needle (e.g. filtering a file list as the user types). zsift_matcher.BatchMatcher is DefaultBatchMatcher -- the lane count is chosen for the host SIMD width.

Top-K selection

varbuf:[10]zsm.TopKResult=undefined;consttop=batch.matchTopK(&haystacks,"foo",.fuzzy,&buf);// top = sorted slice of best matches (score descending)for(top)|r|{std.debug.print("index={d} score={d}\n",.{r.index,r.score});}

Match modes

The MatchMode parameter controls how the needle is matched against haystacks:

Each mode has an inverse_ variant (e.g. .inverse_exact) that inverts the match -- returns a score when the haystack does not match.

You typically don't need to use match modes directly -- the Pattern parser (see Search syntax above) maps fzf syntax to the appropriate mode automatically.

Configuration

// Smart case (default): case-insensitive unless needle has uppercasevarmatcher=tryzsm.Matcher.init(allocator,.{.case_matching=.respect_case,// or .smart, .ignore_case.normalization=.never,// or .smart (default), .always.prefer_prefix=true,// bonus for matches near string start});// Path matching presetvarpath_matcher=tryzsm.Matcher.init(allocator,zsm.Config.pathMatchingUnix());

Limits

These limits are generous for interactive use (file pickers, command palettes, etc.). The greedy fallback produces reasonable scores for haystacks beyond 2048 bytes but without guaranteed optimal alignment.

Thread safety

Each Matcher and BatchMatcher instance owns pre-allocated scratch buffers and is not thread-safe. Create one instance per thread. Instances share no mutable state, so multiple threads can match independently without synchronization. (This is exactly how zsift drives a worker pool: one BatchMatcher per worker thread.)

Building

Requires Zig 0.16.0 or later.

zig build # build library + demo
zig build test # run all tests (369)
zig build run # run the demo

Benchmarks

zig build bench # run with hardcoded corpus (501 haystacks)
zig build bench-setup # download large corpus (~7400 markdown files)
zig build bench # re-run with both corpora (~1M haystacks)

Kubernetes corpus (Apple M-series, ~1M haystacks from markdown files)

The scalar path is 1.4-2.4x faster than nucleo; SIMD is 1.8-2.4x faster. SIMD produces bit-identical scores to scalar.

Linux kernel file paths (84,550 paths -- nucleo's benchmark)

Match sets and scores verified identical to nucleo on all needles.

Algorithm

The scoring algorithm follows nucleo's Smith-Waterman variant:

• Affine gap penalties: opening a gap costs more than extending one, so consecutive matches are preferred
• Character class bonuses: boundary transitions (e.g. /f, _b, cC) get bonus points, rewarding matches at word boundaries and camelCase humps
• Consecutive bonus: sustained runs of matches accumulate increasing bonuses
• Reduced-width matrix: only the feasible region is computed (width = h_len - n_len + 1)

The SIMD path interleaves L haystacks into a Structure-of-Arrays layout and runs the same DP using @Vector(L, u16) operations -- branch-free via @select, with LUT-based bonus precomputation.

License

MIT