The filter that feeds the table

Two structures, built in this collection, that cannot talk to each other.

The index. A compressed self-index answers how many times does this exact string occur in about two rank operations per pattern character, without comparing a single character and without keeping the text. It answers nothing else. Ask it for a string with one letter wrong and it returns zero, correctly.

The table. A semi-global dynamic programme finds every position where a pattern occurs within $k$ errors, by filling a rectangle as wide as the text. A pattern of 24 characters against 20,000 of text is 480,000 cells, and the cost does not depend on whether the answer is seven positions or none.

The thing that joins them is a counting argument two sentences long.

The pigeonhole #

Cut the pattern into $k+1$ pieces. An occurrence with at most $k$ errors cannot have an error in every piece — there are $k+1$ pieces and only $k$ errors to go round — so at least one piece occurs exactly.

That is the whole of it, and it converts a question the index cannot answer into $k+1$ questions it can.

A hit for the piece beginning at pattern offset $q$, found at text position $p$, places the occurrence’s start near $p - q$. How near is decided by the errors: an occurrence with $k$ edits can have its start displaced by at most $k$, so each hit widens into $2k+1$ candidate starting positions.

Twenty-three hits, widened and deduplicated into 140 candidate starts, of which 7 survive verification.

How the pieces are cut, and where the spare characters go #

Twenty-four characters into four pieces is six each and there is nothing to decide. Twenty-five is not, and the choice matters more than it looks.

The pieces here are $\lfloor m/(k+1)\rfloor$ characters each, with the last piece taking the remainder. So a pattern of 26 cut into four gives pieces of 6, 6, 6 and 8, and the longest piece is at the end.

The alternative — spreading the remainder over the first pieces — gives 7, 7, 6, 6, and it is worse for a reason worth naming: the filter’s candidate count is dominated by the shortest seed, because a seed of length $s$ is expected to occur $n/\sigma^s$ times and that number is exponential in $s$. Cutting 6, 6, 6, 8 leaves three seeds of six; cutting 7, 7, 6, 6 leaves two of six. Two shortest seeds are better than three, so the second cut is in fact the better one — and neither is what the arithmetic actually wants, which is pieces as equal as possible.

The version here takes the simpler rule and states it, because on the lengths measured the remainder is zero and nothing depends on it. What the rule cannot be is unequal by design: a filter that cut a pattern into one long piece and $k$ short ones would still be correct by the pigeonhole and would propose candidates by the thousand, and its correctness would be no defence at all.

Verification is the table, made small #

Each candidate is checked by the same recurrence the whole-text table uses, on a window of $m + k$ characters instead of on the text. And it is banded: a cell whose row and column differ by more than $k$ cannot lie on a path of cost $k$ or less, so it is never computed.

$$\text{cells per candidate} \le m \cdot (2k+3)$$

At $m = 24$ and $k = 3$ that is about 216 cells, against 480,000 for the rectangle.

The saving is not the ratio of the answer to the text. It is the ratio of the candidates to the text, and the whole design lives in the gap between those two numbers.

What the filter costs on its own side #

The index queries are not free either, and it would be a poor accounting that charged the table and not the structure that replaced it.

Locating the twenty-three seed occurrences performed 1,749 rank operations on bit vectors. Reading the 140 candidate windows touched 660 distinct text positions — 3.3% of the text — which is what the verification stage costs in the unit the matching field charges a scan in.

The two stages are counted separately and never summed, because they are different acts on different structures: a rank on a bit vector is a directory read and a mask, a table cell is three additions and a minimum, and a number adding them would belong to no level of anything. What can be said is that both are small, and that the second is the one the whole-table alternative pays 480,000 of.

The stages are checked against each other #

An approximate matcher is easy to make fast by making it wrong, and there are two ways to do it here. Both are checked on every build.

Missing an occurrence. The filter’s answers are compared against the whole table’s, at every $k$ in the sweep, on the same text. Every end position the table reports must be covered by some start the filter reports.

The reconciliation is not trivial and is worth a sentence, because the two stages answer different questions. The table reads its answers off its last row, so it reports end positions. The filter proposes start positions and verifies windows. An occurrence starting at $s$ with at most $k$ errors ends somewhere in $[s+m-k,\ s+m+k]$, so the check expands each start into its possible ends and requires the table’s set to be contained. At $k=7$ the filter reports 75 starts against the table’s 48 ends, and neither number is wrong: several starts share an end when the alignment can absorb the difference in a gap.

Reporting a candidate as an answer. This is the interesting one, because a filter that skips verification returns the right answers whenever its candidates happen to be right, and is enormously faster.

The text is handed to the verification stage through an object with a single accessor, which records every read at the position it happened. Afterwards, one condition:

Every character of every occurrence reported must have been read.

A genuine verification passes it, because verifying a window means reading the window. A filter that reports its candidates directly reads only the seed — six characters of twenty-four — and is stopped at the first occurrence whose seventh character nobody looked at. The check is the same device this field uses to stop an index quietly reading the text it claims to have replaced, applied to a stage that is allowed to read the text and must be shown to have done so.

Where the widening comes from, and why it is 2k+1 #

The step between “the seed occurs here” and “an occurrence might start here” is the one place the construction can be quietly wrong, and it is worth doing the arithmetic rather than asserting the constant.

A piece beginning at pattern offset $q$ is found at text position $p$. If the occurrence were exact, its start would be $p - q$ exactly. It is not exact: there are up to $k$ edits, and any of them lying before the piece shifts the piece’s position relative to the pattern’s start. An insertion moves it right by one, a deletion moves it left by one, and a substitution does not move it at all.

So the start lies in $[p - q - k,\ p - q + k]$ — $2k+1$ positions — and no fewer, because $k$ insertions before the seed is a real occurrence and so is $k$ deletions.

Two consequences follow, and both are measurable.

The candidate count is the number of seed hits times $2k+1$, minus whatever collides. At a real occurrence all $k+1$ pieces point at the same start, so a genuine occurrence contributes exactly $2k+1$ candidates however finely the pattern was cut. At a chance hit only one piece fires, so it also contributes $2k+1$. The two are indistinguishable at this stage — which is the point of a filter, and the reason the next stage exists.

And the window verified is $m + k$ characters, not $m$. An occurrence with $k$ deletions in the pattern is $m + k$ characters of text. Verifying $m$ would find the shorter alignments and miss the longer ones, and would find every occurrence in a test whose edits happened to be substitutions — which is exactly the shape of test somebody writes first.

The selectivity is the only number that matters #

A filter is worth having exactly when the candidates it proposes are few. That ratio has a name here and it goes on every plate in this family.

At zero errors the filter is the index answering the question directly and the table is not needed at all, which is a saving of three orders of magnitude. At four errors, running the filter and then verifying its candidates costs more than filling the whole rectangle would have.

That collapse has an essay of its own, because the mechanism is arithmetic rather than luck and there are two thresholds in it, both computable before anything is measured.

Why this is what every practical matcher does #

Nothing above is a trick. It is the shape of every approximate matcher that runs on data large enough to care about, and the shape is forced by three facts that have all been measured in this collection.

The exact question is cheap and the approximate one is not. Counting occurrences of an exact string is two ranks per character and independent of the text length. Approximate matching is $nm$ cells, and under a standard conjecture that cannot be improved to $n^{2-\epsilon}$ in the worst case.

The bound is about the worst case and about exactness, so it forbids a general algorithm and forbids nothing about a filter. A filter does not compute edit distance faster; it computes it in fewer places, which the bound says nothing about.

And the index is already there. A search system that supports exact queries has built the structure; the filter is a loop over $k+1$ backward searches on top of it. The marginal cost of approximate matching, given an index, is the verification — and the verification is what the selectivity decides.

The pigeonhole is checked, not quoted #

An argument this short is easy to state and easy to state slightly wrong — with $k$ pieces instead of $k+1$, or with the pieces overlapping, or with the last piece taking the remainder in a way that leaves it shorter than the others.

So it is performed. Eight hundred strings within $k$ substitutions of a pattern are constructed at $k = 1, 2, 3, 4$, and each is required to contain at least one of its pattern’s $k+1$ pieces exactly. None fails.

The construction is deliberately the easy case — substitutions only — and the check that covers insertions and deletions is the one above, which compares against the table’s own answers on text containing genuine occurrences of both kinds. Two checks, because the short one proves the counting argument and the long one proves the implementation of it.

More pieces than errors, and the filter gets sharper #

The pigeonhole gives a floor on the number of pieces and no rule, which the section above records as an open choice. It is worth working out, because the arithmetic points somewhere the simple version does not go.

Cut the pattern into $p$ pieces rather than $k+1$. Each error spoils at most one piece, so at least $p - k$ pieces occur exactly. With $p = k+1$ that is one, which is the version built here. With $p = k+2$ it is two, and with $p = k+j$ it is $j$.

That changes what a candidate has to look like. At $p = k+1$ a single seed hit is enough to propose a start. At $p = k+2$ a start is only worth proposing if two different pieces both point at it, and requiring agreement between two independent chance events is a much stronger filter than requiring one.

The two effects pull against each other and both are computable. Shorter pieces occur more often by chance — the expected hits for a piece of length $m/p$ are $n/\sigma^{m/p}$, exponential in the piece length, so raising $p$ raises the hit count sharply. But the probability that two chance hits from different pieces land on the same start is the product of two small numbers rather than one, and a product falls faster than the individual terms rise.

Where the balance lands depends on $m$, $k$, $\sigma$ and $n$ — the same four parameters that decide everything else in this family. The important point is structural: going from one required seed to two converts the candidate count from something linear in the chance-hit rate to something quadratic in it, and quadratic in a small number is the direction worth going.

It also costs nothing new to implement. The seeds are already located; what changes is the bookkeeping that turns hits into candidates — count how many distinct pieces vote for each start, and propose only the starts with at least $p - k$ votes. That is a tally over the same hits rather than an extra index query.

Nothing above is measured here, and the reason is worth stating rather than skipping. The version in this collection is the $p = k+1$ one because its correctness argument is a single sentence, and adding a second parameter to a filter whose selectivity already has an essay’s worth of behaviour would mean measuring a surface rather than a curve. What is offered here is the arithmetic that says which direction the surface slopes.

Why the floor is a floor and not a target #

One thing follows from the same counting that is worth stating explicitly, because it is the reason the dial is one-sided.

Cutting into fewer than $k+1$ pieces is not a worse filter; it is not a filter at all. With $p \le k$ the errors can spoil every piece, no piece is guaranteed to occur exactly, and an occurrence can be missed with no indication. The algorithm would still run, still verify whatever candidates it found, and still report answers — just not all of them.

That is the same class of failure the verification check in this essay exists to catch, arriving from the other end: a filter that reports fewer answers than there are looks exactly like a query that had fewer answers. The pigeonhole is not a heuristic that gets better with more pieces; it is a correctness condition with a hard floor and a free parameter above it, and the two halves of that sentence want completely different treatment.

What is not measured here #

A clock, and the two stages are not comparable without one. The plate reports rank operations on one side and table cells on the other, and which of them a processor charges more for is a question a count cannot answer.

Other filters. The pigeonhole partition is the simplest correct filter and not the only one. Counting filters, $q$-gram filters and the backtracking search that walks the index itself with an error budget are each used in practice, and none of them is built here. What is built is the one whose correctness argument fits in a sentence.

The optimal number of pieces. Cutting into more than $k+1$ pieces is always allowed and always shortens them, so there is a choice here and nothing above makes it. The pigeonhole gives a floor on the piece count, not a rule.

Weighted models. Everything above is unit cost — every substitution and every gap character costs one — and the pigeonhole argument depends on it: an occurrence “within $k$” has to mean at most $k$ discrete edits for the counting to work. Under a cost model with real-valued entries there is no such argument, and the filters that exist for that case are a different subject.