The distance is large and the match is good

Suppose the query is sridx and the candidate is src/search/index.ts. The query's characters appear in order:

src/search/index.ts
^^  ^      ^   ^
s r        i   d x

Turning the query into the candidate by insertions has a large edit cost. Yet an interactive file picker should rank it highly. The user did not claim that the two strings were misspellings of one another. They supplied an ordered set of landmarks.

Define $q\preceq c$ when query $q$ is a subsequence of candidate $c$: there are positions

$$1\leq p_1<p_2<\cdots<p_{|q|}\leq |c|$$

such that $q_i=c_{p_i}$ under the declared character comparison. Existence is Boolean. Ranking asks which valid position sequence best explains intent.

Positions carry evidence

A useful file or command matcher commonly rewards:

• a match at the beginning of the candidate;
• a word start after space, dash, or underscore;
• a path component after a separator;
• an uppercase transition in camelCase or PascalCase;
• consecutive matched characters; and
• a compact span with fewer or shorter gaps.

It may penalize unmatched prefixes, interior gaps, or long candidates. These are not facts about strings in general. They are a policy for a corpus and a task. A path matcher may value the final component; command history may value recency; an API-symbol picker may value camel-case starts.

Write the score for a position sequence $p$ as

$$S(p)=\sum_i b(i,p_i)+\sum_{i>1} t(p_{i-1},p_i)+e(p_1,p_{|q|},|c|),$$

where $b$ is a position bonus, $t$ rewards adjacency or charges a gap, and $e$ accounts for unmatched edges. The best match is

$$\max_{p:q_i=c_{p_i}} S(p).$$

This is a constrained alignment problem, not a minimum edit path.

Leftmost is feasible, not optimal

A linear scan that takes the first possible occurrence of every query character correctly decides subsequence existence. It does not necessarily find the best positions.

For query ab and candidate axb/ab, greedy leftmost matching chooses the first a and the first following b. The later ab begins at a path boundary and is consecutive. Any policy whose boundary and run bonuses exceed the cost of its later start prefers the later alignment.

Thus “find a match, then score those positions” is not equivalent to “find the highest-scoring match.” The positions are part of the optimization.

The score has optimal substructure

Let $D[i,j]$ be the best score for matching query prefix $q_{1..i}$ with $q_i$ placed exactly at candidate position $j$. Let $M[i,j]$ be the best score for matching that query prefix anywhere through candidate position $j$.

For a simple policy with position bonus $b(i,j)$, consecutive reward $r$, and nonconsecutive-gap charge $g$:

$$D[i,j]=\begin{cases} -\infty, & q_i\ne c_j,\\ b(i,j), & i=1\text{ and }q_i=c_j,\\ b(i,j)+\max(D[i-1,j-1]+r,\;M[i-1,j-2]-g), & \text{otherwise}, \end{cases}$$

and

$$M[i,j]=\max(M[i,j-1],D[i,j]).$$

Out-of-range terms are $-\infty$. The exact boundary conditions and gap function are policy, but the structure is stable: the last query symbol lands at $j$, and the previous optimal alignment either ends at $j-1$ or earlier.

The same replacement argument used for edit distance proves optimal substructure. If the chosen predecessor were not optimal for its state, a better predecessor would improve the whole alignment. Filling the two tables takes $O(|q||c|)$ time and $O(|c|)$ score storage with rolling rows. Recovering highlighted positions again requires predecessors or a traceback strategy.

If gap opening and extension differ, add explicit states as in the previous chapter. If a bonus depends on more history—say, the number of path components crossed—that history must either become finite state or destroy this recurrence.

SUBSEQUENCE-SCORE(QUERY, CANDIDATE, POLICY)
Input:  QUERY, CANDIDATE, and positional scoring POLICY
Output: maximum legal subsequence score or negative infinity

previousBest ← array filled with negative infinity
previousEnd ← array filled with negative infinity
for i ← 1 to length(QUERY)
    currentBest ← array filled with negative infinity
    currentEnd ← array filled with negative infinity
    for j ← 1 to length(CANDIDATE)
        if QUERY[i] = CANDIDATE[j]
            adjacent ← previousEnd[j - 1] + POLICY.consecutiveReward
            separated ← previousBest[j - 2] - POLICY.gapCharge
            currentEnd[j] ← POLICY.POSITION-BONUS(i, j) + max(adjacent, separated)
        currentBest[j] ← max(currentBest[j - 1], currentEnd[j])
    previousBest ← currentBest
    previousEnd ← currentEnd
return previousBest[length(CANDIDATE)]

Reject before optimizing

Most candidates do not match a typed query. Run cheap necessary conditions before the dynamic program:

1. Length: if $|q|>|c|$, no subsequence exists.
2. Presence: if the candidate lacks enough copies of any query symbol, reject.
3. Endpoints: if a required first or last symbol cannot occur in admissible order, reject.
4. Ordered feasibility: greedily advance through candidate positions, or use a precomputed next-occurrence table or word-parallel state, and reject if the full query cannot be consumed.

Each filter is safe because it checks a necessary condition. A character bag admits anagrams whose order is wrong; ordered feasibility rejects them. Neither assigns the rich score.

This repairs an apparent contradiction from the previous chapter. Position bonuses may disqualify the unit-cost bit-vector representation from scoring. They do not affect whether the ordered characters exist. A word-parallel feasibility test can therefore remain valid as a rejector. Technique eligibility is attached to the observation it computes, not to an entire pipeline.

State the survivor law:

prefilter rejects candidate c  =>  no legal position sequence for c exists

Test it differentially against the simplest greedy subsequence oracle across generated strings. A false positive costs time; a false negative changes the answer.

Matching, scoring, and selection remain separate

An interactive matcher has at least four outputs:

The distinction matters for explanations. Highlighting greedy positions while ranking by optimal positions displays a reason the ranker did not use. Sorting by a score but recovering positions through a different entry point can make the same error.

Tie-breaking carries more perceived quality than its mathematical status suggests. Declare, in order, such choices as earlier start, shorter span, shorter candidate, lexical order under a pinned comparison, or stable corpus ordinal. Never inherit container iteration order accidentally.

Published names are claims about exact behavior

Tools such as fzf, fzy, skim, and uFuzzy expose different match relations, schemes, entry points, and carriers. “Fuzzy matcher” is not a behavioral specification. A fair comparison needs a receipt for each entrant:

• exact upstream revision or release;
• exact callable entry point and options;
• character normalization and comparison policy;
• score-only or score-plus-position output;
• candidate carrier and preprocessing;
• per-candidate allocation and retained scratch;
• score direction, range, tie-break, and no-match representation; and
• executable fixtures recorded from the upstream implementation.

Take oracle outputs from the running upstream, not only from prose. Documentation often omits boundary details and tie behavior. A reimplementation tested against its own paraphrase proves agreement with the paraphrase.

Equalize carriers before comparing time. If one matcher receives normalized bytes with reusable scratch while another receives newly allocated strings, the experiment ranks adapters together with algorithms. Both are real costs, but they belong on separate ledger rows.

There is no context-free winner

A scorer optimized for paths values separators and final components. A symbol matcher values camel-case boundaries. A command-history matcher may preserve chronology. A title search may prefer contiguous words and reject arbitrarily wide gaps. One universal winner would require one universal intent distribution.

Measure by strata:

• file paths, symbols, command names, prose titles, and mixed labels;
• query length and candidate length;
• exact, prefix, contiguous substring, boundary subsequence, and loose subsequence cases;
• survivor count before scoring;
• score-only versus highlighted-range requests; and
• warm scratch reuse versus cold allocation.

If different policies dominate different strata, the conclusion is a dispatcher. Its thresholds are algorithmic decisions: measure them, test boundary minus one, boundary, and boundary plus one, and record the selected branch in the query receipt.

A simple floor is valuable. Exact substring, then greedy ordered-subsequence feasibility, then a coarse stable score may outperform a sophisticated DP for small lists or broad early keystrokes. The floor is not embarrassed by its simplicity; it identifies what added machinery actually buys.

Negative results preserve the design space

Keep these failures in the workbench. A counterexample is more durable than a claim that one current implementation wins.

Lessons

• Spelling correction minimizes edits; interactive navigation rewards ordered landmarks.
• Subsequence feasibility is Boolean; positional ranking optimizes among many valid alignments.
• Greedy leftmost matching decides existence but is not optimal under bonuses.
• Dynamic programming makes boundary, run, and gap policy explicit.
• Necessary-condition prefilters improve constants without changing recall.
• A representation rejected for rich scoring may still be valid for exact feasibility.
• Score positions and highlighted positions must describe the same alignment.
• Published matcher comparisons pin revisions, entry points, carriers, and upstream fixtures.
• Corpus strata can justify a measured dispatcher, not a universal winner.

Practice

1. Enumerate every ab alignment in axb/ab. Choose bonuses that make the greedy alignment lose and compute both scores.
2. Prove the greedy two-pointer scan decides subsequence existence correctly.
3. Give a candidate that passes length and character-bag filters but fails ordered feasibility.
4. Extend the recurrence with a distinct gap-extension charge. Name the extra state it requires.
5. Design a stable tie-break for equal-scoring file paths and explain why runtime iteration order is not sufficient.
6. Write the receipt for one upstream matcher experiment, including revision, entry point, normalization, carrier, output, and five adversarial fixtures.

References

1. John Hawthorn. “fzy Algorithm.” Upstream design note, accessed August, 2026.
2. Junegunn Choi. “fzf.” Upstream source and documentation, especially scoring schemes and algorithm entry points.
3. skim contributors. “skim.” Upstream source and matcher documentation.
4. Leon Sorokin. “uFuzzy.” Upstream source and documentation, especially the filter, information, and sort phases.
5. Temple F. Smith and Michael S. Waterman. “Identification of Common Molecular Subsequences.” Journal of Molecular Biology 147(1), 1981.