Substring/Bitap-style fuzzy matching for short-string list search

[micheleriva]

Summary

zbsearch's typo tolerance is per-token bounded Levenshtein against indexed terms. It cannot fuzzy-match an arbitrary substring anywhere within an untokenized string the way Fuse.js does:

• Fuse.js — a modified Bitap algorithm does approximate substring matching over whole field values, tuned by threshold, distance, and location.

Motivation

For short-string / list-picker use cases (command palettes, file/symbol pickers, tag lists) Bitap-style matching over full strings often feels better than tokenized BM25 + Levenshtein, because it tolerates typos across token boundaries and rewards contiguous matches near a location.

Proposed direction

• Evaluate an optional matching mode that scores whole-field approximate matches (Bitap or similar), selectable per search or per field.
• This is a different paradigm from the inverted-index core, so likely an opt-in mode/plugin rather than a change to default ranking.
• Lower priority — captured for completeness from the competitive review.

Notes / trade-offs

• Bitap is ~O(n·m) per field and usually caps pattern length (~32 chars); best for small/medium datasets and short queries.

Related

Part of a competitive feature-gap review vs Fuse.js, MiniSearch, FlexSearch, Lunr.