The q-grams an error cannot destroy

A pattern of $m$ characters holds $m - q + 1$ overlapping substrings of length $q$. One error — a substitution, an insertion, a deletion — sits inside at most $q$ of them, because a changed character belongs to $q$ windows of that length.

So an occurrence with at most $k$ errors still shares at least

$$t = (m - q + 1) - kq = m + 1 - q(k+1)$$

of them with the pattern. That is the whole of the filter: slide a window along the text, count the shared $q$-grams, and verify only the windows that reach $t$.

The other filter, and why this is not it #

This collection already has an approximate-matching filter. The filter that feeds the table cuts the pattern into $k+1$ pieces and looks each up exactly, on the pigeonhole grounds that $k$ errors cannot damage all $k+1$ of them.

Both filters rest on a pigeonhole argument and they are otherwise opposites.

The seed filter asks an index an exact question and gets back a set of positions. It never reads the text except to verify, and it skips: on the sweep below it touches four per cent of the characters.

The counting filter asks nothing. It reads every character exactly once, maintains a count as a window slides, and decides each window on a number. It cannot skip and it has no index behind it.

That difference is not an implementation choice. A filter that decides on a count has to have counted, and counting a window’s contents means reading them.

What it costs, in the currency it saves #

The expensive stage in approximate matching is the dynamic-programming table: $n \times m$ cells to find every place a pattern occurs with at most $k$ errors, which a distance that is a path through a grid built, the row that starts at zero turned into a search, and a band as wide as the answer narrowed to a band of width $2k+1$.

A filter’s job is to avoid filling it. On four thousand characters with a twenty-four-character pattern and six planted occurrences, the whole table is 96,000 cells; the counting filter at $q = 4$ computes 420 of them at zero errors, 5,336 at one, 16,744 at two, 27,675 at three and 105,122 at four.

The last of those is larger than the table, which is the same shape the filter that proposes everything measured for the other filter. That is not a rounding error — it is the collapse, and it has its own essay in the threshold that reaches zero.

The window is $m+k$ and not $m$ #

One detail decides whether the filter is correct, and the natural choice is the wrong one.

An occurrence of an $m$-character pattern with $k$ errors is between $m-k$ and $m+k$ characters long, because insertions lengthen it and deletions shorten it. A window of exactly $m$ characters may therefore hold only part of one, and the lemma bounds the shared $q$-grams between the pattern and the whole occurrence.

So the window here is $m+k$ characters starting at each position. Any occurrence beginning at that position is inside it, and a superset can only share more $q$-grams, so the bound still holds.

This is the kind of argument that is easy to make and easy to make wrongly, so it is checked rather than trusted: at four error counts, every window the table reports an occurrence in must be a window the filter kept. On 2,500 characters with five planted occurrences, it is.

Multiplicity matters, and it is easy to drop #

The count is over $q$-grams with multiplicity: if the pattern holds three copies of the then a window holding five of them shares three, not one and not five.

Dropping the multiplicity is the natural simplification — a set is easier than a multiset and the code is shorter — and it breaks the lemma in the unsafe direction. The bound counts occurrences: a pattern of twenty-four characters holds twenty-one four-grams whether or not they are distinct, and each error destroys at most $q$ of them.

The gate’s check for this is a small one: on abababab with $q = 2$ the profile must hold seven $q$-grams over two distinct values. A set-based profile holds two, which is smaller than any threshold the arithmetic produces and would make the filter propose nothing at all.

The count is maintained rather than recomputed #

The filter as described sounds quadratic — count the shared $q$-grams in every window — and it is not, which is worth a paragraph because the cost model in every plate depends on it.

The windows overlap by all but one position, so the count is maintained incrementally: as the window slides, one $q$-gram leaves and one enters, and each of them raises or lowers the shared count by at most one. The bookkeeping is a table of how many copies of each $q$-gram the window currently holds, compared against how many the pattern holds.

That is one hash-table operation per position rather than $m$ of them, and it is why the filter’s read count is $n$ plus $q$ rather than $n$ times $w$. The characters are read once each and the counting is a constant per position.

The subtlety is the multiset arithmetic: a $q$-gram entering raises the shared count only if the window now holds no more copies than the pattern does. Getting that condition backwards produces a count that drifts upward, a filter that proposes more than it should, and a completely correct answer set — the failure this collection’s gates exist to catch, since an over-proposing filter is safe and merely expensive.

Choosing $q$, which is a trade rather than a maximum #

The threshold falls by $q$ for every error allowed and rises by one for every character of $q$ taken away, so a larger $q$ gives a smaller threshold and a rarer $q$-gram. Both effects matter and they point opposite ways.

At $k = 2$ on this text: $q = 3$ proposes 92 windows, $q = 4$ proposes 104, $q = 5$ proposes 121. The larger $q$ is worse here, because the threshold has fallen faster than the $q$-grams have got rarer.

At $k = 0$: $q = 3$ proposes 8 and $q = 4$ and $q = 5$ propose 6, which is the planted count. The larger $q$ is better, because with no errors the threshold is nearly $m$ and any $q$ is rare enough.

So there is no best $q$, and the arithmetic that decides it is available before any text is read: the threshold is exact, and the chance of sharing a $q$-gram is about $(m-q+1)/\sigma^q$. What is not available in advance is which of the two dominates on a real corpus, which is why the sweep exists.

The prediction, and what it is a prediction of #

A window holds $w = m + k - q + 1$ $q$-grams, and a random one is in the pattern’s profile with probability at most $d/\sigma^q$ where $d$ is the number of distinct $q$-grams the pattern holds. Treating them as independent gives a binomial, and the share of windows proposed is its upper tail at $t$.

Compared against the measurement on a text with occurrences planted in it, that prediction is wrong by twenty orders of magnitude — and it is not the prediction’s fault. At $q = 4$, $k = 0$ the filter proposes exactly six windows and six occurrences were planted: the candidates are entirely the planted ones, and a prediction of chance candidates has nothing to be compared against.

This is the same correction the filter that feeds the table had to make in the other direction, where the term everybody drops is the planted one. A filter’s candidate count is a sum of two terms with different causes, and comparing a prediction of one against a measurement of both is how a working filter comes to look broken or a broken one correct.

On an empty text the prediction is right within a factor of five #

Run the same sweep with no occurrences planted and the two quantities become comparable. Where the filter is still a filter and chance produces anything at all, the ratios are: at $q = 3, k = 3$ the prediction is 4.89 times the measurement; at $q = 3, k = 4$ it is 3.64 times; at $q = 4, k = 4$ it is 0.80 times.

Over by a factor of five at the short $q$ and under by a fifth at the longer one. The direction is explicable — overlapping $q$-grams are strongly dependent, which clusters the shared counts and makes the tail heavier than a binomial in some regimes and lighter in others — and the important thing is that the error runs both ways.

A tolerance fitted at $q = 3$ would have been wrong at $q = 4$ and the other way round, which is why the check requires the prediction to be within an order of magnitude and requires both an over-estimate and an under-estimate in the sweep. A one-sided check here would have been a fitted constant wearing a gate’s clothes.

Why a larger $q$ proposes more: the candidates are clusters #

“The threshold has fallen faster than the $q$-grams have got rarer” is offered above as the reason $q = 5$ proposes 121 windows where $q = 3$ proposes 92. The arithmetic says something else, and it says it exactly.

Six occurrences were planted. A window that starts $\delta$ positions away from a true occurrence still contains nearly all of it: it loses about $\delta$ of the pattern’s $q$-grams off one end and gains $\delta$ unmatched ones at the other, so it shares roughly $(m + 1 - q) - \delta$. That window passes while

$$(m+1-q) - \delta \;\ge\; m + 1 - q(k+1),$$

which is $\delta \le qk$. Each true occurrence therefore proposes a cluster of about $2qk + 1$ windows, and the cluster’s width is proportional to $q$.

Put the numbers in at $k = 2$ with six occurrences: $q = 3$ gives clusters thirteen wide and 78 candidates; $q = 4$ gives seventeen and 102; $q = 5$ gives twenty-one and 126. Measured: 92, 104 and 121. The whole candidate count is the planted occurrences smeared, and the smear grows linearly in $q$.

The check at the other end confirms it. At $k = 0$ the cluster width is one, so the prediction is six candidates — and $q = 4$ and $q = 5$ propose exactly six. The $q = 3$ row proposes eight, the two extra being the chance term finally becoming visible at a $q$ short enough for a four-symbol alphabet to repeat.

So the rarity argument is not what decides this sweep; it is almost entirely absent from it. On a four-symbol alphabet with $m = 24$, a random window shares about 8.3 four-grams by chance against a threshold of 13, and about 0.4 five-grams against a threshold of 10 — nowhere near passing in either case. The chance term is negligible at every $q$ measured, and the candidate count is a property of the tolerance band the threshold draws around each real occurrence.

That reframes the choice of $q$ in a way the sweep alone does not. Two regimes exist and they want opposite things. Where chance dominates — a short $q$, a small alphabet, a long window — raising $q$ helps, sharply, because the chance term falls exponentially. Where the planted term dominates, raising $q$ hurts, linearly, because it widens every cluster. The optimum is the $q$ at which the two terms are comparable, which on this text is just below three.

And it says what a candidate count is actually measuring. A filter proposing 104 windows for six occurrences has a selectivity of 17 windows per answer, and 17 is $2qk + 1$ rather than anything about the text — so quoting the ratio as a filter’s quality is quoting a number set by the threshold’s slack. The threshold that reaches zero is the same parameter at its other end, where the slack has swallowed the whole text; here it is swallowing a band around every answer, and the filter that proposes everything is what the far end of that looks like.

What the filter reads, and why it cannot do otherwise #

Every plate in this strand reports the characters read as well as the cells computed, and for the counting filter the first number is always $n$ plus a few.

That is not a defect and it is not an accident of this implementation. The filter’s decision is a function of the window’s contents; a window that has not been read has no contents; and the windows overlap, so an incremental count reads each character once and then reuses it. There is no version of this algorithm that skips.

The comparison with the seed filter is therefore not “which is cheaper” but “which resource is scarce”. On the sweep at $k = 2$: the counting filter reads 18,692 characters and computes 16,744 cells; the seed filter reads 780 characters, performs 879 index ranks, and computes 4,830 cells.

Different columns, no ordering, and the machine decides. Three savings in three currencies is where that is put on one page with a third method beside them.

What the two filters have in common #

Both filters in this collection now rest on a pigeonhole argument, and the arguments are close enough that the difference between them is instructive.

The filter that feeds the table partitions the pattern into $k+1$ disjoint pieces and observes that $k$ errors cannot touch all of them. The counting filter takes $m-q+1$ overlapping pieces and observes that $k$ errors cannot touch more than $kq$ of them.

Disjointness gives a stronger conclusion — one piece survives intact, so it can be looked up exactly — at the cost of a small stock of pieces. Overlap gives a weaker conclusion — many pieces survive but which ones is unknown — from a large stock, so the conclusion has to be a count rather than an exact query.

That difference is what puts one filter behind an index and the other in front of a scan, and it is the mechanism behind their different currencies. An exact query needs a structure; a count needs a pass.

The check that must reject #

The filter’s threshold is the one parameter that can be wrong without any symptom, so it gets the rejection test.

Raise $t$ by one and rerun. The windows kept are a subset of the correct ones, every occurrence found inside them is real, and the answer set is missing an occurrence — measured, one of twelve on a 2,500-character text at $k = 2$.

Everything about that run looks healthy. The candidates are fewer, the cells are fewer, the saving is larger, and every reported occurrence verifies. The only way to see it is to compare against the whole table, which is what the gate does.

The complementary check is that lowering $t$ is safe but useless: at $t \le 0$ every window is proposed, the answers are all correct, and the filter has cost more than not filtering. Both directions are failures and only one of them is visible in the answers.

Where the lemma is tight #

The rejection above says something about the lemma as well as about the code: raising the threshold by one loses an occurrence, so the bound is reached on this text rather than merely holding.

That is expected and it is worth confirming. The bound is tight when the $k$ errors are spread far enough apart to destroy $q$ distinct $q$-grams each, which on a twenty-four-character pattern with two errors needs them about eight characters apart — a common arrangement rather than a contrived one.

When the errors are adjacent they destroy fewer, the occurrence shares more $q$-grams than the bound requires, and a filter with a raised threshold would find it anyway. So the tightness is a property of where the errors fall, and a filter that was tuned on adversarially clustered errors would be unsafe on ordinary ones.

The honest limit #

The texts here are drawn from a four-symbol alphabet with occurrences planted by substituting $k$ characters at random positions in a copy of the pattern. Real approximate matching is against corpora whose near-occurrences arrive from a process — sequencing error, typing, versioning — and the arrangement of errors within an occurrence is exactly what the tightness above depends on.

The sweeps run to $k = 4$ or $k = 5$ because past the collapse there is nothing to measure, and to four thousand characters because the baseline is a full table and the full table is quadratic. Nothing here establishes how the filter behaves at the lengths a real application uses; what it establishes is the shape, and the shape has an $n$ in neither the threshold nor the candidate fraction.

The one number that would change with scale is the crossing between filtering and not filtering, which depends on the ratio between a verification and a table row and therefore on $n$. It is measured at one length here and is a line on a plate rather than a formula.