The shift a set of patterns allows

Eight patterns of ten characters each. Twenty thousand characters of text. Find every occurrence of every pattern.

The automaton does it in one pass: a trie of the patterns with failure links, one character read, one state transition, no backtracking. Twenty thousand reads, and the number does not move if the pattern set grows to a thousand.

The other way round is to read the text backwards inside a window, and to move the window forward by more than one position wherever the patterns allow it. On these eight patterns that matcher looks at 12,314 distinct positions out of twenty thousand.

Thirty-eight per cent of the text is never examined. That is Commentz-Walter, and the interesting part of it is not that it skips but what decides how far.

The scan runs backwards through a trie of the patterns reversed #

The window ends at text position $i$ and covers the $w_{\min}$ positions ending there, where $w_{\min}$ is the length of the shortest pattern. Read $\text{text}[i]$, then $\text{text}[i-1]$, then $\text{text}[i-2]$, walking a trie whose paths spell the patterns backwards.

A pattern ending at $i$ is a path in that trie, so the walk finds it. A walk that runs out of edges has established something about the text segment it read, and the shift is what that something buys.

The structure is not the difference between the two algorithms. It is the same trie, node for node.

The two conditions, written down #

Suppose the walk has read $\text{text}[i-j+1..i]$ — call that segment $w$, spelled from the window end backwards — and stopped because there is no trie edge for $c = \text{text}[i-j]$. Move the window end to $i + d$. For a pattern $P$ to end at $i+d$, two things must hold.

The good-suffix condition. The characters already read sit at offsets $d$ through $d+j-1$ counted back from the new window end, so $P$ reversed must carry $w$ at position $d$:

$$P^R[t] = w[t-d] \quad \text{for } d \le t \le \min(d+j-1,\ |P|-1)$$

The bad-character condition. The mismatching character sits at offset $d+j$, so $P^R[d+j] = c$ — unless $d+j$ is past the end of $P$ altogether, in which case the condition says nothing.

Both are necessary. So the smallest $d$ that could carry an occurrence is at least the larger of the two smallest, and the safe shift is the maximum of the two, not the minimum of anything.

Both are computable exactly, by walking every pattern at every offset for every node of the trie. That is what is done here, and the reason it is worth saying out loud is that the shift functions in the literature are not these: they are approximations chosen so that they can be built in time linear in the total pattern length. The exact rules are available, and the cost of computing them is the subject of the last section below.

The rule everybody implements does almost nothing #

Split the shift into its two halves and run all three variants over the same text: no shifting at all, the bad-character rule alone, and both conditions.

The bad-character rule takes the coverage from 100% to 99.5%. It is, on eight patterns over four symbols, worth almost exactly nothing.

That is not what a reader of the single-pattern literature expects. Horspool’s matcher — the one that ships, the one in every string library that skips — is the bad-character rule alone, and on a wide alphabet it is genuinely sublinear. The reason it collapses here is mechanical and is worth stating precisely.

A shift must be safe for every pattern, so the shift table is a minimum over the set. For one pattern, “where does character $c$ appear, counted from the right end” is often “nowhere”, and the shift is the whole pattern length. For eight patterns of ten characters over four symbols there are eighty positions in which each of four characters might appear, and the chance that none of them holds $c$ near the right-hand end is small. The minimum over eight patterns is nearly always one or two.

The good-suffix condition does not degrade the same way, because it is a condition on a segment rather than on a single character, and the number of places a segment of several characters can sit inside a pattern set stays small as the set grows.

The shifts are a distribution with a hard ceiling #

The mean shift of 2.06 is a summary of something lumpy.

The largest shift here is nine and the shortest pattern is ten. That is not a coincidence: no shift can ever exceed the shortest pattern in the set, because once $d$ reaches $|P|$ the characters already read fall entirely outside $P$ and neither condition constrains anything. The ceiling is asserted over the whole shift table on every build rather than observed in a run, because a run is a sample and the claim is about the algorithm.

That ceiling turns out to be the whole story of when this matcher is worth having, and it has an essay of its own.

Two counts of one run, and they cross in different places #

A window of ten characters that shifts by two overlaps the next window by eight, so the matcher can read the same position several times. It has two costs and they are not the same number.

By one count the skipping matcher stops paying at eight patterns. By the other it never stops paying — it reads 96% of the text at a hundred and twenty-eight patterns and that is still less than 100%.

Both counts are honest and they answer different questions. Characters examined is the right unit when a comparison is the cost, which it is in memory. Positions ever read is the right unit when the text is somewhere it costs something to reach — a disk, a network, a memory-mapped file larger than the cache — because a position read twice in quick succession is read once from anywhere but the register file. This collection has made that distinction before with blocks, and this is the same distinction with a matcher rather than a sort on the end of it.

A plate showing either count alone would have settled the question. That is why both are on the figure.

Both matchers return identical occurrence sets at every point, checked against exhaustion on every build. That check is not decorative: a shift is a claim about text nobody looked at, and the only way to know the claim is true is to have looked.

Every match reported was read #

There is a second check, and it catches something the occurrence sets cannot.

The text is handed to the matcher through an object with a single accessor. There is no string to index, no indexOf, no slice; every read is recorded at the position it happened. Afterwards:

Every character of every occurrence the matcher reports must have been read by the matcher.

A skipping matcher passes this by construction, because a skip is only ever over a stretch that contains no occurrence. What it rules out is a matcher that reports a match it did not verify — which is not a hypothetical defect and is exactly what a filter feeding a table does when the verification stage is dropped. The check is the one thing that can tell a genuine skip from a claimed one, because a matcher that reads more than it says still returns the right answers.

The rejection carried beside it is a shift table inflated by one — the smallest possible overstatement, and the one an off-by-one produces. On a text with a dozen planted occurrences it finds nine of fifteen.

What a mean shift of two actually buys #

It is worth converting the shift distribution into the quantity a reader cares about, because the conversion is not the obvious one.

A mean shift of $s$ over a window of $w_{\min}$ characters does not mean the matcher reads $1/s$ of the text. Each window reads as many characters as the trie walk goes deep, which is one more than the depth reached — usually one or two, occasionally ten. So the characters examined per window and the positions advanced per window are two independent quantities, and the coverage is the ratio between the positions touched and the positions passed.

On these eight patterns the walk goes an average of 0.28 characters deep past its first read, so a window costs 1.28 examinations and advances 2.06 positions. That is 12,428 trie steps against 9,726 windows and 22,153 reads, and it is why the coverage lands at 62% rather than at the 49% a naive reading of the mean shift would predict: the windows overlap, and an overlapping window re-reads the position it starts on.

The deeper the walk goes, the longer the shift and the more characters it cost to earn it. Those two effects pull in opposite directions and the balance between them is the whole behaviour of the algorithm. It is also why the mean shift is nearly useless as a summary: the windows that shift by nine are the ones that mismatched immediately, having read one character, and the windows that shift by one are the ones that walked six levels into the trie before running out of edges. The cheap windows are the productive ones.

The tables are not free #

The exact rules are computed by walking every pattern at every offset for every trie node. That is quadratic in the pattern set where the scan is linear in the text, so there is a text length below which building the tables is the entire cost — and it moves.

At a hundred and twenty-eight patterns, preparing to skip costs seven times as much as reading the text would have, and the scan itself already reads more than the text.

This is why the published shift functions are approximations. Commentz-Walter’s char, d1 and d2 are each computable in time linear in the total pattern length, and each is a safe under-estimate of the exact shift derived above. They skip less and they cost nothing to build, and on any set large enough for the difference to matter the second consideration wins.

Which is a measurement about the algorithm rather than about the implementation, and it is the kind that does not appear in an asymptotic statement: both the exact and the approximate rule give a matcher whose worst case is $O(nm)$ and whose behaviour on ordinary text is sublinear, and the choice between them is decided by a constant that is a function of how many patterns there are.

The two formulas above make the next table predictable rather than surprising, which is the point of having derived them: the alphabet enters the first rule linearly and the second one exponentially, so widening it helps the condition that was already doing the work far more than the one that had stopped.

What the alphabet does to all of it #

Everything above is on four symbols. The alphabet moves every number in the table, and it moves them a long way.

Over two symbols a pattern of eight characters occurs 1,227 times in twenty thousand — the answer set is large, every occurrence must be read in full, and there is nothing left to skip. That is not a failure of the shift rules; it is the problem being different. A matcher that skips is fast when the answer is small, and the answer’s size is a property of the text and the alphabet rather than of the algorithm.

The bad-character rule dies like σ over k #

The collapse of the bad-character rule is measured above and it is worth deriving, because the derivation gives a formula that predicts where it happens and the measurement then becomes a check on it rather than an isolated fact.

For a single pattern over $\sigma$ symbols, the shift a character $c$ permits is the distance from the right-hand end to the nearest occurrence of $c$. On a random pattern that distance is geometric with mean about $\sigma$ — one has to look back about $\sigma$ positions before finding any particular character.

For $k$ patterns the table is a minimum over the set, and the minimum of $k$ independent geometric variables is geometric with $k$ times the rate. So the mean bad-character shift is about

$$\frac{\sigma}{k}$$

and it is floored at one, because a window must always advance.

Check it against the measurements. Eight patterns over four symbols gives $4/8 = 0.5$, which floors to one — and the measured mean shift under the bad-character rule alone is 1.04. Sixteen patterns over twenty-six symbols gives $26/16 = 1.6$, which is small but not yet degenerate, and the coverage over that alphabet is the only one in the sweeps above where the matcher still skips substantially.

So the rule that ships is useful while $\sigma > k$ and useless once the pattern count passes the alphabet size. That is a very low bar: eight patterns over the twenty-six letters is fine, and eight patterns over four nucleotides is not, and neither fact is visible in any description of the algorithm. It also explains why Horspool’s matcher is excellent at $k = 1$ and why nothing survives the generalisation: the single-pattern case is the one where the minimum is over one thing.

And the good-suffix condition survives for the same reason a seed does #

The other condition does not degrade that way, and the reason is the same arithmetic run over segments rather than over characters.

A walk that has read $j$ characters has a segment of $j$ characters in hand. The number of places such a segment can sit inside a set of $k$ patterns of length $m$ is about $km/\sigma^{\,j}$ — there are $km$ positions and each matches a given segment with probability $\sigma^{-j}$. So the condition becomes selective as soon as

$$\sigma^{\,j} \;>\; km \qquad\text{that is,}\qquad j \;>\; \log_\sigma(km)$$

On eight patterns of ten characters over four symbols that is $j > \log_4 80 = 3.16$, so a walk of four characters is already expected to have no continuation anywhere in the set — and the shift is then bounded only by the ceiling.

That is exactly the arithmetic a seed-and-extend filter runs, with the pattern set in place of the text: a segment is selective once the alphabet raised to its length exceeds the number of places it could hide. The two algorithms are unrelated and the threshold is the same expression, because in both cases the question is how long a string has to be before it stops occurring by chance in a corpus of a stated size.

And it says why the two conditions behave so differently as the set grows. The bad-character rule’s selectivity is $\sigma$ against $k$ — linear in the set. The good-suffix condition’s is $\sigma^{\,j}$ against $km$ — exponential in the depth of the walk. Doubling the pattern count costs the first rule half its shift and costs the second one extra character of walking.

What is not measured here #

The approximate shift functions themselves. The comparison above is between the exact rules and no rules; the published $d_1$/$d_2$ pair sits between them and is not built here. What is measured is that the exact rules are computable and that computing them costs more than they save past a set size that a figure can show.

A real clock. Every number here is a character examined or a character comparison performed in precomputation. Which of them a processor charges for, and at what rate, is a different measurement — and the backwards scan inside a window has a locality profile the forward one does not, which nothing here reports.

Sets with structure. The patterns here are drawn at random and required to be distinct and non-nesting. A real dictionary — English words, virus signatures, URL prefixes — shares prefixes and suffixes heavily, which makes the trie smaller and the shifts shorter, and neither effect is quantified by anything above.