sift-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 is the matcher half of a nucleo-style split: sift-matcher (this repo) is the pure, thread-free SIMD matching layer, and sift 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 sift 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

sift-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.

Token	Match type	Description
sbtrkt	fuzzy-match	Items that fuzzy-match sbtrkt
'wild	exact-match	Items that include wild
'wild'	boundary-exact-match	Items that include wild at word boundaries
^music	prefix-exact-match	Items that start with music
.mp3$	suffix-exact-match	Items that end with .mp3
!fire	inverse-exact-match	Items that do not include fire
!^music	inverse-prefix-exact-match	Items that do not start with music
!.mp3$	inverse-suffix-exact-match	Items that do not end with .mp3

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.

const sm = @import("sift_matcher");

var matcher = try sm.Matcher.initDefault(allocator);
defer matcher.deinit();

const pattern = sm.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:
.sift_matcher = .{
    .url = "https://git.urverk.org/urverk/sift-matcher/archive/main.tar.gz",
    .hash = "...", // zig build --fetch will fill this in
},

// build.zig
const sm_mod = b.dependency("sift_matcher", .{}).module("sift_matcher");
exe.root_module.addImport("sift_matcher", sm_mod);

The module is imported as sift_matcher; the examples below alias it to sm for brevity.

Single match

const sm = @import("sift_matcher");

var matcher = try sm.Matcher.initDefault(allocator);
defer matcher.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)
var indices: [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)

const sm = @import("sift_matcher");

var batch = try sm.BatchMatcher.initDefault(allocator);
defer batch.deinit();

const haystacks = [_][]const u8{ "foo", "foobar", "baz", "football" };
var results: [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). sift_matcher.BatchMatcher is DefaultBatchMatcher -- the lane count is chosen for the host SIMD width.

Top-K selection

var buf: [10]sm.TopKResult = undefined;
const top = 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:

Mode	Description
.fuzzy	Subsequence match with Smith-Waterman scoring (default for interactive search)
.exact	Substring match (case-aware)
.prefix	Haystack must start with needle
.suffix	Haystack must end with needle
.equal	Full string equality (case-aware)
.boundary_exact	Substring at word boundaries (non-alphanumeric or string edge)

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 uppercase
var matcher = try sm.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 preset
var path_matcher = try sm.Matcher.init(allocator, sm.Config.pathMatchingUnix());

Limits

Limit	Value	Behavior when exceeded
Max haystack length	2048 bytes	Returns null (no match) for optimal DP; greedy fallback handles longer strings
Max needle length	128 bytes	Returns null (no match)
Max pattern atoms	16	Excess terms silently ignored

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

Needle	scalar	SIMD	nucleo	fzf
"sift"	2.9M/s	4.0M/s	2.0M/s	1.6M/s
"webpack"	5.2M/s	5.5M/s	2.5M/s	2.5M/s
"config"	3.4M/s	4.2M/s	2.2M/s	2.0M/s
"install"	2.7M/s	3.7M/s	1.9M/s	1.9M/s
"the"	2.5M/s	3.5M/s	1.8M/s	1.5M/s
"st"	2.2M/s	3.0M/s	1.7M/s	1.3M/s

The scalar path is 1.3-2.1x faster than nucleo; SIMD is 1.8-2.2x faster. SIMD produces bit-identical scores to scalar.

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

Needle	sift-matcher	nucleo	Ratio
"never_matches"	40.0M/s	37.0M/s	1.08x
"copying"	35.7M/s	34.5M/s	1.04x
"/doc/kernel"	31.3M/s	30.3M/s	1.03x
"//.h"	8.9M/s	11.1M/s	0.80x

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