SugarFuzzy
Fuzzy string matching with matched character indices plus the match score
Fuzzy string matching that returns matched character indices plus the match score. Two algorithms: Smith-Waterman (local alignment) and Sahilm (gum-style scoring with separator/camel-case bonuses). The matched indices enable filter-highlighting UIs that were impossible with score-only matchers. Extracted from sugar-forms; back-compat shims remain in sugar-forms and sugar-treelist for existing consumers, while new code depends on sugar-fuzzy directly.
Install
composer require sugarcraft/sugar-fuzzy
Quickstart
use SugarCraft\Fuzzy\Matcher\SmithWatermanMatcher;
use SugarCraft\Fuzzy\Highlighter;
$matcher = new SmithWatermanMatcher();
// Single match — returns null when no match
$result = $matcher->match('foo', 'foobar');
// $result->score === 19 (3 × matchScore + 2 × adjacentBonus = 19)
// $result->indices() === [0, 1, 2] (0-based character positions)
// $result->haystack === 'foobar'
// Match all candidates, sorted by score desc then candidate asc
$results = $matcher->matchAll('ab', ['apple', 'banana', 'cabbage']);
// cabbage (11, the adjacent "ab") before apple (3) and banana (3)
// Opt in to full-query mode for type-to-filter pickers: every query
// character must land, in order
$picker = SmithWatermanMatcher::new()->withRequireFullQuery();
$picker->match('bxz', 'abcdef'); // null — "x" and "z" never land
$picker->match('gst', 'git status')->indices(); // [0, 4, 5]
// Use Highlighter to mark matched runs with ANSI codes
$highlighter = new Highlighter();
echo $highlighter->highlight($result, fn($s) => "\e[1;31m{$s}\e[0m");
// Output: 'foobar' with positions [0,1,2] highlighted in bold red
// The highlighter is presentation-neutral: sanitize candidate text (strip
// \x1b/control bytes) before display — see Security below
FuzzyMatcher interface
<=>, so digit-only candidates order numerically); perfect ties keep input order (usort is stable as of PHP 8.0); limit: 0 yields none, a negative limit is unlimited. matchAllGenerator() yields the same ranked results — it drains and sorts the whole input before the first yield (ranking is global), a streaming API rather than per-candidate laziness.MatchResult
isMatched() is score > 0.indices() returns.Algorithms
ScoringProfile; ScoringProfile::canonical() (the default) is bit-equivalent to the original sugar-forms FuzzyMatcher for ASCII input (legacy deviations documented in the README), with strict() / lenient() presets. withRequireFullQuery() keeps only candidates that contain the whole query as an in-order subsequence, scoring the best alignment forced to cover every query character (floored at 1). Over-cap input is truncated, never handed to another algorithm: only the first maxQueryLength (128) query and maxCandidateLength (1000) candidate characters take part. Candidates truncate; under full-query mode an over-cap query is rejected — it never matches. SahilmMatcher is single-pass linear and intentionally uncapped — bound hostile-size candidates host-side.SahilmScoring; SahilmScoring::canonical() mirrors the bonus-constant shape of sahilm/fuzzy — the values are this port's historical constants, pinned by the characterization suites.Highlighter
Takes a MatchResult and a styler \Closure(string): string, returns the candidate string with matched runs passed through the styler. Non-matched runs are returned unchanged.
Highlighting is visual by default: pair color with bold/underline cues for color-blind users, and expose the matchedIndices + the deterministic matchAll() ranking for non-visual/screen-reader channels.
Security
The highlighter is presentation-neutral and forwards unmatched haystack segments verbatim. Callers must sanitize candidate text (strip \x1b/control bytes) before display — the styler callback receives raw matched substrings only and does not sanitize; sanitization belongs to the TUI render layer. Case folding maps malformed UTF-8 bytes to ?, so a literal ? in a query can forge a match against untrusted text — validate UTF-8 on either side when inputs are hostile.
Use it for
- Filter-as-you-type with highlighted matches — know exactly which characters triggered the match for underline/bold/color highlighting.
- Ranked autocomplete — matchAll sorts results by relevance score, not alphabetical order.
- File/path fuzzy finding — SahilmMatcher bonus for separators and camelCase makes it ideal for IDE-style file openers.
- Foundation for sugar-quickpick — the fuzzy finder overlay uses matched indices to paint the matched characters in each ranked row (match styling opt-in; selection is the formatter's
$isSelectedflag).
Source & demos
API
| Class | Method | Description |
|---|---|---|
| FuzzyMatcher | match(string $query, string $candidate): ?MatchResult | Single match or null |
| FuzzyMatcher | matchAll(string $query, iterable $candidates, ?int $limit = null, int $minScore = 1): list<MatchResult> | All matches sorted by score desc, then haystack asc (numeric-string aware); limit 0 yields none, negative limit is unlimited |
| FuzzyMatcher | matchAllGenerator(string $query, iterable $candidates, ?int $limit = null, int $minScore = 1): Generator | Ranked-order generator; drains and sorts before the first yield (same output as matchAll()) |
| MatchResult | $score / $needle / $haystack / $matchedIndices (readonly) | Match quality score (higher = better), the query and the candidate, and the matched code-point offsets |
| MatchResult | indices(): list<int> | 0-based matched code-point offsets into the original haystack |
| MatchResult | isMatched(): bool / isEmpty(): bool | score > 0 / no matched indices |
| SmithWatermanMatcher | new(?ScoringProfile $profile = null, int $maxQueryLength = 128, int $maxCandidateLength = 1000, bool $requireFullQuery = false) | Local sequence alignment; over-cap candidates truncate, and under full-query mode an over-cap query is rejected |
| SmithWatermanMatcher | score(string $query, string $candidate): int | Alignment score without building a full result (0 = no match) — SmithWatermanMatcher only, not part of the FuzzyMatcher contract |
| SmithWatermanMatcher | withRequireFullQuery(bool $require = true): self / requiresFullQuery(): bool | Full-query mode: every query character must land, in order |
| SmithWatermanMatcher | profile() / maxQueryLength() / maxCandidateLength() | Configured weights and length caps |
| ScoringProfile | canonical() / strict() / lenient() | Smith-Waterman weight presets |
| ScoringProfile | withMatchScore() / withMismatchPenalty() / withGapOpen() / withGapExtend() / withAdjacentBonus() | Immutable weight setters |
| SahilmMatcher | new(bool $caseSensitive = false, ?SahilmScoring $scoring = null) | Separator/camelCase bonus algorithm; scoring() / caseSensitive() accessors |
| SahilmScoring | canonical() / withMatchScore() / withConsecutiveBonus() / withSeparatorBonus() / withCamelBonus() / withFirstCharBonus() / withLowerCaseBonus() | Immutable Sahilm weights (canonical 1 / 5 / 10 / 10 / 15 / 1) |
| FuzzyMatcherFactory | named(string $type, ScoringProfile|SahilmScoring|null $scoring = null): FuzzyMatcher | 'smith-waterman' or 'sahilm'; a mismatched weight type or unknown name throws |
| Highlighter | highlight(MatchResult, \Closure(string): string): string | Apply styler to matched runs |
| CharFold | foldSplit(string): list<string> / fold(string): string | Per-codepoint case fold that stays 1:1 with the original string — keeps matched code-point indices truthful where whole-string lowercase would expand (U+0130, final sigma); malformed bytes fold to ? without desync |