Three savings in three currencies

Four methods, one question: where does this pattern occur with at most two errors? Every one of them is required to find what the whole table finds, checked against it rather than against each other.

The table computes 60,000 cells and reads 60,000 characters. The counting filter computes 6,251 cells and reads 13,022. The seed filter computes 3,325 cells, reads 550 characters and performs 554 index ranks. The index walk computes no cell, reads no character, and performs 18,645 ranks.

Why there is no total #

The three columns are three resources and this collection does not add them up.

A table cell is three additions and a minimum, over data that is in a row of an array. A character read is a memory access into a text, which may or may not be resident. An index rank is a directory lookup and a popcount over a bit vector, and on a wavelet tree it is several of them.

Which of the three is scarce is a property of a machine and of a deployment: a corpus too large to hold makes the reads the binding constraint, a cache-resident text makes the cells cheap, and an index in memory makes the ranks nearly free. No ranking of these methods survives changing that.

That is this collection’s standing position, established for two counters and now needed for three. The count somebody chose is the general argument and one run, two counts is the first case; the third currency arrives here because the index walk spends something the other three do not.

The four methods in one paragraph each #

The table. Fill an $n \times m$ dynamic-programming rectangle with a zero row at the top, and read off the columns whose final entry is at most $k$. It is the baseline every other method is checked against, and it is the only one whose cost is completely independent of the budget: 60,000 cells whether $k$ is zero or three, because $k$ only decides which of the filled cells count as answers.

The counting filter. Slide a window of $m + k$ characters, count how many $q$-grams it shares with the pattern, and verify the windows reaching $m + 1 - q(k+1)$. It reads every character exactly once — 13,022 of them at $k = 2$, which is the text plus the window bookkeeping — and computes a banded table per candidate.

The seed filter. Cut the pattern into $k+1$ pieces, look each up exactly in a self-index, and verify a window around each hit. It reads almost nothing — 550 characters at $k = 2$, four per cent of the text — because the index answers the exact queries and only the verification touches the text.

The index walk. Walk the backward search as a tree, spending budget on each mismatching step. It reads nothing at all and spends ranks.

The fourth column nobody spends #

There is a resource none of the four columns names and it belongs in the comparison, because it is the one that decides whether three of the methods are available at all.

Two of them need a structure built in advance. The seed filter and the walk both query a self-index, which costs a suffix array to build and a few bits a character to keep — 8,426 bits over a collection of sixteen thousand characters for the run-length structure this phase measures, or 36,169 for an entropy-bounded one over eight thousand characters of English.

The other two need nothing but the text. The table and the counting filter can answer a query on a corpus that arrived a moment ago, and neither has a build step.

That is not a small distinction. A one-off query against a text nobody has indexed makes the two structure-free methods the only candidates whatever the plates say, and a corpus queried a million times makes the index’s build cost irrelevant. The four-way plate is drawn under the assumption that the index exists, which is stated here rather than left as an assumption.

An index larger than what it indexes is where this collection weighed that structure, and the index that is smaller than the text is where it became small enough to be a reasonable prerequisite.

Where each one wins, by budget #

At $k = 0$ the seed filter is a single exact query: 232 cells, 80 characters, 304 ranks. The walk is 20 interval extensions and 304 ranks. Both are three orders of magnitude under the table and there is nothing to choose between them.

At $k = 1$ the seed filter computes 1,152 cells against the counting filter’s 1,248, and the walk performs 1,700 ranks. All three are far under the table.

At $k = 2$ the seed filter is ahead on cells (3,325 against 6,251) and far ahead on reads (550 against 13,022), and the walk’s ranks have grown elevenfold to 18,645.

At $k = 3$ the seed filter computes 17,745 cells and reads 2,415 characters; the counting filter computes 24,843 and reads 15,369; the walk performs 177,046 ranks. Every method is within an order of magnitude of the table and the walk’s growth has become the dominant term in its own column.

What each method is a function of #

The reason the ordering moves is that the four costs depend on different things, and a plate at one budget on one text cannot show that.

The table is $nm$: the text length times the pattern length, and nothing else.

The counting filter is $n$ reads plus a verification per candidate, and the candidate count depends on the threshold and on how often a random window shares that many $q$-grams — so it depends on the alphabet, and it collapses when the threshold reaches zero.

The seed filter is a handful of index queries plus a verification per candidate, and its candidate count depends on how often a seed of length $m/(k+1)$ occurs by chance — so it depends on the alphabet and the text length, and it degrades as the seeds shorten.

The walk is a tree whose size depends on the budget, the alphabet and how quickly intervals empty — so it depends on the text length only weakly, and it grows by about an order of magnitude per error.

Four different functions of four different subsets of the same parameters. That is why the four-way plate is drawn at several budgets and several lengths rather than once.

The one thing they have in common #

Every one of the four returns the same occurrences, and that is checked rather than assumed at every point of every sweep.

The check is not “the counts agree”. The table reports the positions where an occurrence ends and the three other methods report where one begins, so the comparison converts starts into the windows of ends they could produce and requires every end the table found to be covered.

That conversion is generous in one direction — a method reporting spurious starts still covers every real end — so it is paired with the exact check at $k = 0$, where the answer sets must be equal. Together they are tight enough that a method returning too much or too little fails one of them.

Getting this wrong is easy and this collection has recorded doing so: the filter that feeds the table notes that starts and ends are different questions, which is the index field’s own note about count and locate one level up.

Three limits arriving at the same error rate #

The most striking thing in the sweep is not any single column; it is that all three fast methods run out at about the same place.

The counting filter’s threshold reaches zero at $q(k+1) = m+1$, which for a twenty-four-character pattern at $q = 5$ is $k = 4$. The seed filter’s seeds fall below $\log_\sigma n$ at about the same budget: on the four-thousand-character sweep with a twenty-four-character pattern it proposes 649 candidates at $k = 4$ and computes 160,446 cells against the table’s 96,000 — 1.7 times worse than not filtering. The walk crosses the table’s cost between $k = 3$ and $k = 4$.

Three mechanisms, three completely different arguments, one error rate: about a fifth of the pattern’s length.

That is not a coincidence and it is not a deep theorem either. At $k/m \approx 0.2$ a pattern stops constraining a window: enough of it can be changed that the surviving structure — a shared $q$-gram, an intact seed, a prefix that still occurs — no longer separates an occurrence from a random stretch of text. Every method here exploits some such structure and they all lose it at once.

What a reader should do with four methods #

The decision procedure is short and it is not “benchmark them”.

Compute the error rate. If $k/m$ is above about a fifth, none of the three fast methods will help and the table is the answer. That is arithmetic and costs nothing.

Ask which resource is scarce. If the text is not resident, the walk is the only method that never touches it. If the index is not built, the counting filter is the only method that does not need one. If both are available, the seed filter is cheapest on this instance in both of the columns it spends.

Then measure the candidate fraction, once, on a sample. That is the only number in this essay that cannot be computed in advance, and it decides the size of the verification, which is the dominant term for both filters.

What happens if the pattern gets longer #

Every number above is at one pattern length, and lengthening the pattern moves all four methods in the same direction for different reasons — which is the cleanest demonstration that the columns are not measuring one thing.

The table grows linearly: $nm$ cells, so a pattern half again as long costs half again as much.

The counting filter improves: the threshold $m + 1 - q(k+1)$ rises with $m$ at fixed $k$, so the same budget is a smaller error rate and fewer windows pass. At $m = 32$ and $q = 5$ the threshold at $k = 4$ is 8 rather than 0, and the filter is alive where it had collapsed.

The seed filter improves too: the seeds are $m/(k+1)$ characters, so a longer pattern gives longer seeds, which occur by chance less often.

The walk improves: a longer pattern empties its intervals sooner, so the tree is smaller — 39,957 extensions at $m = 16$ against fewer at $m = 20$ for the same budget.

Three methods get better and the baseline gets worse, so every ratio in this essay understates the fast methods on long patterns. The error rate, again, is the variable that matters rather than the budget.

The three limits are functions of different variables #

“Three mechanisms, one error rate” is the striking observation, and it dissolves under arithmetic in a way worth following, because the dissolution is what stops a fifth of the pattern from becoming a rule of thumb.

Write the two filter limits out. The counting filter’s threshold reaches zero at $q(k+1) = m+1$, so it dies at

$$\frac{k}{m} \;\approx\; \frac{1}{q}.$$

The seed filter dies when its seeds stop being selective, which is when the seed length $m/(k+1)$ falls below $\log_\sigma n$ — the length at which a string starts occurring by chance in a text of $n$ symbols. So it dies at

$$\frac{k}{m} \;\approx\; \frac{1}{\log_\sigma n}.$$

One of those contains no $n$ and the other is governed by it. They agree here because $q$ was chosen to be four or five and $\log_4 4{,}000$ is 5.98 — and $q$ is chosen that way on purpose, since a $q$-gram shorter than $\log_\sigma n$ occurs everywhere and one much longer is destroyed by every error. The two thresholds coincide on this sweep because the same design rule set both of them, not because the two mechanisms are secretly one mechanism.

That matters as soon as the text is a realistic size. On a four-symbol corpus of a billion symbols, $\log_\sigma n$ is fifteen, so a well-chosen $q$ is fifteen and both limits fall to

$$\frac{k}{m} \;\approx\; \frac{1}{15} \;\approx\; 0.067,$$

which is a third of the rate measured here. A twenty-four-character pattern that tolerates four errors on four thousand symbols tolerates one on a billion, and every one of the fast methods is back at the table’s cost by two.

So the number to carry out of the sweep is not a fifth. It is $1/\log_\sigma n$, and the fifth is what that expression evaluates to on a text small enough for a full dynamic-programming table to serve as the baseline — which is the constraint the honest limit at the end of this essay already names, arriving as a bound on the conclusion rather than on the measurement. A limit is not a prediction is normally about extrapolating a class past its measured range; this is the same move with a constant, and the constant is the one a reader would most want to reuse.

It also says which of the three limits is the robust one. The walk’s cost grows by roughly an order of magnitude per error whatever the text is, so its crossing with the table moves only with the table’s own $nm$ — slowly, and in its favour as the text grows. The two filters’ limits both tighten with $n$. On a large corpus the walk outlives the filters, which reverses the ordering this sweep reports at its highest budget, and is the sort of reversal the filter that proposes everything is about: a filter that stops filtering does not fail, it quietly becomes the thing it was placed in front of.

The comparison this essay does not make #

There is no wall-clock number anywhere in this collection and there is none here, which is worth restating at the point where a reader most wants one.

A rank, a cell and a character read have different costs on a real machine and the ratios depend on the cache, on the representation, on the branch predictor and on the size of the index. This collection has a counter for cache misses and one for branch mispredictions, and neither has been pointed at any of these four methods.

What the counts do give is invariance. The four columns above are the same on any machine, for the same inputs, and they will be the same in five years. A timing would not be, and counting instead of timing is the founding decision that makes every plate here reproducible.

The honest form of the recommendation is therefore conditional: given a machine’s ratios between the three currencies, the plates decide. Producing those ratios is somebody else’s measurement and this collection does not have it.

Why this is in the wrong-answers field #

The statement this essay is against is the reasonable-sounding one: that among methods for the same problem, one is fastest and benchmarking finds it.

For this problem, at this budget, on this text, the four methods spend 60,000 cells, 6,251 cells and 13,022 reads, 3,325 cells and 550 reads, and 18,645 ranks. There is no number that ranks those, and constructing one requires choosing exchange rates that belong to a machine rather than to an algorithm.

The mistake it produces in practice is not choosing wrongly; it is choosing without knowing that a choice was being made. A benchmark on a machine with the text in cache reports the counting filter as competitive; the same benchmark on a corpus that does not fit reports it as hopeless; and neither run mentions that the difference is the exchange rate rather than the algorithms.

The block that is not a block is the same complaint about a model parameter, and two searches, one comparison count is the case where two algorithms agree in one currency and differ in another.

The honest limit #

Every measurement is on a four-symbol alphabet with occurrences planted by substitution, three thousand to four thousand characters, patterns of sixteen to twenty-four. That is the regime where a full table is affordable as a baseline, which is what makes the correctness checks possible and what limits the lengths.

The seed filter’s index is sampled at one value in thirty-two and the walk’s is the same index, so both carry a locate cost that is not in these columns. The counting filter and the table carry none, because their answers are positions already.

And the walk has no lower-bound pruning, so its rank column is an upper bound. That does not change the shape — the growth per error is what makes it lose at $k = 4$ — but a careful implementation would move the crossing by some amount this collection has not measured.