The text that answers without reading it

An algorithm that reports every occurrence of a pattern in a text without examining most of the text sounds like a category error. If a character was never looked at, how can anything be known about it?

The answer is that it was ruled out rather than examined, and being ruled out is cheaper than being read. This is not a trick — it is one of the few genuinely surprising results in elementary algorithms, and it is a measurement rather than a slogan.

Reading the pattern backwards #

Everything follows from one decision: compare the pattern against its alignment right to left instead of left to right.

Line the pattern up. Compare its last character against the text character underneath. If they differ, the alignment is dead — and now the interesting question is how far the pattern may be moved before it could possibly match again.

That question has an answer that depends only on the text character the window’s last position landed on. Suppose the pattern is measured and the character sitting under its final d is a q. There is no q anywhere in measured, so no alignment that places any part of the pattern over that q can match. The pattern may be moved a full eight places, past the q entirely.

Seven characters of the text were never examined and never will be. Not skipped over optimistically — ruled out, by an argument about the pattern that is valid whatever those characters turn out to be.

The table is the algorithm #

The bad-character table maps each character to how far the pattern may jump when the window’s last position lands on it: for a character at position $i$ in the pattern, $m - 1 - i$; for a character absent from the pattern, $m$.

For measured that is m→7, e→1, a→5, s→4, u→3, r→2, everything else→8.

Two things about it are worth stating carefully.

The mean shift over a uniform alphabet is what decides the cost, and it is computable from the table alone. For measured over 26 letters it is $(20 \times 8 + 7 + 1 + 5 + 4 + 3 + 2)/26 = 7.000$. The measured mean step over an actual 20,000-character search is 6.96, and the agreement between a number computed from six table entries and a number measured over 2,874 alignments is what makes this a mechanism rather than an observation.

The table’s entry for a repeated character is the last occurrence’s, which is the smallest shift that character allows. measured has one e at index 1 and another at index 6; the table records 1, not 7, because a shift of 7 could step over a valid alignment. A safe shift must be the most pessimistic one, and every published implementation gets this right in the same way and for the same reason.

What sublinear means here, and what it does not #

At 26 symbols the search reads 2,985 characters of 20,000. That is 0.149 per character of text, or one character in 6.7.

The word for that is sublinear, and it needs qualifying in two directions before it means anything.

It is sublinear in the text, and only on average. The bound $O(n/m)$ that gets quoted is an expected cost over random text, not a guarantee. Horspool’s worst case is $\Theta(nm)$ and is reached by an input as boring as the naive scan’s: a text of one repeated character with a pattern of the same character reads 130,832 characters of an 8,192-character text, which is exactly what the naive scan reads and sixteen times what KMP reads.

It is also not free of the input’s structure, which is the harder half. Over a binary alphabet the same algorithm reads 24,083 characters of 20,000 — more than the text has. The shift table over two symbols has two entries, neither of which allows more than $m$, and both of which are usually small, so the pattern crawls.

The measurements across the alphabet sweep: 1.204 characters read per text character at two symbols, 0.565 at four, 0.149 at 26, 0.132 at 95. The whole result is a statement about the alphabet.

That is why every figure in this family prints the alphabet on its plate. A benchmark of string searches on English prose and a benchmark on DNA are measuring different algorithms as far as this effect is concerned, and quoting the first as though it settled the second is the field’s version of quoting a sorting result without saying what the input distribution was.

A longer pattern does not keep helping #

The obvious next thought is that if a longer pattern allows a longer jump, then longer patterns should keep getting cheaper. They do, and then they stop, and the place they stop is the most interesting number in the essay.

The mean shift across that sweep is 1.96, 3.76, 6.96, 11.95, 18.36, 24.29, 23.79. It grows with $m$ and then stalls at about 24 — and 24 is not close to 128, but it is close to 26.

The shift is bounded by the alphabet, not by the pattern length. A pattern of 128 characters over 26 symbols contains, almost certainly, every one of the 26. So no character in the text allows the full shift of 128; every one of them appears somewhere in the pattern and allows only the distance to its last occurrence, which is a few characters on average. The table has 26 entries however long the pattern is, and it cannot promise more than the entries it has.

Past the turning point a longer pattern buys nothing and costs something: each surviving alignment has more characters that might match before one fails.

The bound on how much the whole effect can be worth is therefore about $\sigma$, and it is measurable. Across four alphabets the ratio of the worst point to the best is 1.63 at two symbols, 2.57 at four, 5.07 at eight and 11.59 at 26 — each about half the alphabet, and none of them above it.

The half of Boyer–Moore that nothing ships #

What has been measured here is Horspool’s simplification, and the name it is usually given — Boyer–Moore — belongs to something larger. The original algorithm has two rules and takes the better shift of the two on every mismatch.

The bad-character rule is the table above. The good-suffix rule is the other half: when the pattern has matched its last $k$ characters before failing, those $k$ characters are known, and the pattern may be shifted to the next place where that suffix could recur — which is a fact about the pattern, computed in advance, exactly as KMP’s failure function is. Together the two rules give a worst-case bound of $O(n + m)$ comparisons rather than $\Theta(nm)$.

Almost nothing implements it. The reason is visible in the numbers already on this page: on ordinary text over a real alphabet the good-suffix rule almost never gives the larger shift, because the bad-character rule is already producing shifts near $m$ and the good-suffix rule cannot produce more. It buys a worst-case guarantee, on inputs nobody supplies, in exchange for a second preprocessing pass, a second table, and a second control flow to get wrong.

That trade is the one the depth limit that almost never fires describes for introsort and it is resolved the other way here, which is worth noticing. Introsort ships its guarantee because the fallback costs 0.14% and the attack it prevents is a denial of service; Horspool’s implementations mostly do not, because the guarantee costs more and the attack requires the attacker to supply both the text and the pattern. The same argument, the same shape, opposite conclusions, and the difference is entirely in who controls the input.

Ruling out is the general idea #

The move at the centre of this algorithm is not about strings.

An algorithm may establish something about data it has not read, if it can show that no value of that data could change the answer. Horspool’s version is that a character absent from the pattern rules out every alignment covering it, whatever that character is. It is the same move as a bound in branch and bound, the same move as a binary search discarding half an array on one comparison, and the same move as the adversary arguments this site uses to prove its floors — read backwards.

Seen that way, the floor moves when the question does is the general statement and this is a special case of it. Binary search is sublinear in the array for exactly this reason: it does not read the elements it skips, and it does not need to, because the sortedness rules them out. What is unusual about Horspool is only that the ruling-out is done by a table rather than by an invariant, and that it works on unsorted data.

The thing that makes it feel surprising is that no preprocessing of the text has happened. A binary search is sublinear because someone sorted the array first, and the index that is the text is sublinear because someone built an index. Horspool is handed the text cold and still does not read it all.

What the character counter cannot see here #

The count says Horspool reads one character in 6.7 and the naive scan reads all of them. It does not follow that Horspool is 6.7 times faster, and on short texts it is often not faster at all.

A skipping search has unpredictable branches. Every alignment ends in a data-dependent jump of a data-dependent distance, and the branch the machine guesses measures what that costs on this site’s own hardware model. The naive scan’s inner loop is a tight, highly predictable comparison; Horspool’s outer loop is a table lookup feeding an unpredictable increment. The counter charges both the same.

A skipping search has a worse access pattern. The naive scan sweeps memory in order, which is the case one access, eight kilobytes shows costs one transfer per block and nothing more. Horspool jumps, and while the jumps are short enough to stay inside a block most of the time, they defeat a hardware prefetcher’s stride detection.

And the table has to be built. For a 26-letter alphabet that is 26 entries and irrelevant; for a Unicode alphabet it is a hash map, and the lookup that used to be an array index becomes a hash — which is why implementations that must handle wide alphabets use a truncated table indexed by the low byte, and accept the shorter shifts that come with the collisions.

None of that is in any figure on this page. What is in the figures is the number of characters examined, which is exact, machine-independent, and only one of the things that decides which search to use.

The sweep, three ways #

The claim is about how the three matchers separate, and how they separate depends on the two parameters the sweep holds fixed.

The third is the control: nothing about the algorithms changes, only how much text they are given, and the axis is a rate.

The floor under all of it #

Every field on this site eventually asks what the bound is that no algorithm can beat, and this one has an unusually clean answer.

Any algorithm that finds all occurrences of a pattern of length $m$ in a text of length $n$ must examine at least $n/m$ characters. The argument is the adversary argument of the adversary who hides the edge, transplanted: if an algorithm reports its answer having left a gap of $m$ consecutive unexamined characters, an adversary is free to put the pattern in that gap, and the answer is wrong. So no gap may exceed $m - 1$, and there are at least $n/m$ examinations.

For the twenty-thousand-character text and the eight-character pattern that floor is 2,500. Horspool reads 2,985. It is 19% above a bound that no algorithm can go under, which is a closer approach to a floor than anything else this site has measured — closer than merge sort’s 16% above $\log_2(n!)$, and far closer than a Bloom filter’s 44% above the bits it needs.

At $m = 64$ the floor is 313 and the measured cost is 914, a factor of 2.9, and the gap has opened because the shift has saturated while the floor keeps falling. The floor is $n/m$; the achievable cost is about $n/\min(m, \sigma)$. Where $m$ exceeds $\sigma$, the two part company and the distance between them is the price of having only 26 letters to rule things out with.

The stronger result, which this site has not measured and states as a quotation, is Yao’s: the expected number of examinations for any algorithm is $\Theta(n \log_\sigma m / m)$. It has the alphabet in it, and it says the logarithmic factor above $n/m$ is unavoidable rather than a defect of this particular table.

The floor that actually binds #

Yao’s result is quoted above and left there, which is a shame, because the sweep on this page has enough points to evaluate it — and doing so changes what the 19% means.

Take $n\log_\sigma m / m$ with its constant fixed at one, which is the honest way to compare against a $\Theta$ and has to be said out loud: what follows is a ratio to that expression, not to Yao’s bound proper, whose constant nobody here knows. On twenty thousand characters over 26 symbols:

• $m = 2$ — expression 2,128, measured 10,600, a factor of 5.0
• $m = 8$ — expression 1,595, measured 2,985, a factor of 1.87
• $m = 64$ — expression 399, measured 914, a factor of 2.29
• $m = 128$ — expression 233, measured 1,000, a factor of 4.3

Against the same four points, the ratio to $n/m$ runs 1.06, 1.19, 2.9 and 6.4. So the two candidate floors behave completely differently across the sweep: $n/m$ is nearly attained at short patterns and abandoned by a factor of six at long ones, while the logarithmic expression stays inside a factor of five everywhere and is closest in the middle.

Which is what a floor doing its job looks like. The $n/m$ argument is correct and it is loose, because it says nothing about the alphabet — and the alphabet is, by this essay’s own account, the whole of the result. An adversary hiding a pattern in a gap does not care how many symbols exist; a real table cannot rule out more than it has entries for.

That reframes the headline number. Being 19% above $n/m$ at $m = 8$ is true and it is a distance to a bound no algorithm reaches at this alphabet, so it is not comparable to merge sort’s 16% above $\log_2(n!)$, which is a distance to a bound that is essentially achieved. Measured against the expression that has $\sigma$ in it, Horspool is a factor of about two off — respectable, and a different claim.

The more interesting thing the comparison finds is at the other end. Both expressions keep falling as $m$ grows: $n/m$ linearly, and $n\log_\sigma m/m$ nearly so, since the logarithm crawls. The measurement does not. It bottoms out around $m = 64$ and turns up, because the shift has saturated at the alphabet while the bounds have not.

So the gap to either floor widens without limit in $m$, and the mechanism is the one this essay already named: the table has $\sigma$ entries whatever the pattern length is. A bound that keeps improving with $m$ and an algorithm that stops improving with $m$ must diverge, and the sweep is where that divergence becomes a number rather than an argument.

None of which is a defect in Horspool. It is the difference between a bound on what some algorithm could do and a measurement of what this one does, and the floor moves when the question does is the general form: two floors for one problem, differing in what they are allowed to know, and the tighter one is the one that knows about the alphabet. The same distinction is why a floor on the bits reports a filter as 44% above its floor rather than above a weaker one that would have flattered it.

Which one to use, which is not the question the counters answer #

Three algorithms have now been measured on the same job, and each is best on some input and worst on another.

On random text over 26 symbols: Horspool 2,985 characters, KMP 20,833, naive 20,862. Horspool by a factor of seven.

On the naive scan’s constructed worst case — a text of one repeated character searched for a near-match — naive 520,256, KMP 16,321, Horspool 8,129. Horspool again, and by half KMP’s count, because every alignment dies on its first comparison and the shift table is not needed for anything more than moving one place along.

On Horspool’s own worst case — the same repeated text searched for a pattern that does match — naive 130,832, Horspool 130,832, KMP 8,192. Now KMP by a factor of sixteen, and Horspool has lost its advantage entirely.

Each algorithm’s worst case is another’s ordinary input, and there is no ordering of these three that survives all three tables. That is not an unsatisfying conclusion — it is the same conclusion the frontier between time and space reaches about sorting, and it is the honest one whenever a single number is being asked to summarise a family of inputs.

What standard libraries actually do is take the bet: almost all of them ship a Boyer–Moore variant, because ordinary text over a real alphabet is what substring search is overwhelmingly called on, and a factor of seven on the common case is worth a factor of sixteen on a case that requires a pathological pattern. Where an adversary picks the input, the bet is off, and that is precisely the argument the next essay’s algorithm makes for itself and then loses.