The ceiling the shortest pattern sets

Sixteen patterns of sixteen characters, over four symbols, in twenty thousand characters of text. The skipping matcher reads 11,684 distinct positions — 58% of the text — and examines 21,130 characters.

Now shorten one of the sixteen patterns to two characters. Nothing else changes: the same text, the same fifteen other patterns, the same algorithm, the same shift rules.

It reads every position, and examines 47,958 characters, which is two and a half times the length of the text.

The other fifteen patterns are unchanged and unmatched throughout. They are being searched for by an algorithm that has stopped skipping, because of a pattern that has nothing to do with them.

The ceiling, and why it is exactly the shortest pattern #

The shift rules derived in the previous essay both ask whether a pattern could still line up with the characters already read. Move the window forward by $d$ and the read segment sits at offsets $d$ and beyond, counted back from the new window end. Once $d$ reaches $|P|$, the segment lies entirely outside $P$ — every position of it is before where $P$ would start — and neither condition constrains anything at all.

So a shift is safe as soon as it is at least $|P|$ for some pattern, and the shift rule is a minimum over the set. The smallest such $|P|$ is $w_{\min}$.

$$\text{shift} \le w_{\min} \quad \text{always, for every node and every character}$$

That is not a bound on the average or a statement about ordinary text. It is a ceiling on the shift table itself, and it is asserted over every trie node against every character of the alphabet on every build rather than observed in a run — because a run is a sample and this is a claim about the algorithm.

And $w_{\min}$ is a property of the set, not of the pattern being matched. That is the whole essay. A user who adds one short pattern to a query has not made one search slower; they have made every search in the batch slower, by an amount that has nothing to do with the pattern they added.

The one-pass matcher has no such parameter #

The comparison is with a matcher whose cost is the same number for every input of a given length.

By characters examined, the skipping matcher is behind from eight patterns on. By positions ever read it is ahead everywhere, and still ahead at a hundred and twenty-eight — 96% of the text is less than 100%, though not by much that anyone would notice.

Neither count is the wrong one. They answer different questions and this collection has been separating them since it started: what an algorithm does and what the machine charges for it are two measurements, and they rank algorithms differently. A position re-read within a few instructions is free from anywhere but the register file; a position read at all, once, may be a page fault. The unit decides the answer, and the plate carries both rather than settling it on a reader’s behalf.

The phrase that goes wrong #

“Commentz-Walter is Boyer-Moore for many patterns” is true as a description of the construction and misleading as a description of the behaviour, and the reason is that the two algorithms have their parameters in different places.

Boyer-Moore is fast when the pattern is long and the alphabet is wide, and both of those are properties of the single thing being searched for. Commentz-Walter is fast when the shortest pattern is long and the alphabet is wide, and the first of those is a property of a set the user assembled — often automatically, often from a configuration file, often without anybody looking at the lengths.

The sweep where every pattern has the same length is the flattering one, and it is the one a benchmark produces. The sweep where one pattern is short is the one a deployment produces.

The alphabet moves it further than the set size does #

Everything above is over four symbols. The same sixteen patterns of eight characters, on the same length of text, over three alphabets:

The last column of that table is the point most easily missed. Over two symbols an eight-character pattern occurs by chance every 256 positions, so sixteen patterns produce 1,227 occurrences in twenty thousand characters. Every one of them must be read in full. A matcher whose whole value is not reading the text cannot be fast when the answer is a substantial fraction of the text, and whether it is is a property of the alphabet and the pattern lengths rather than of anything the algorithm decides.

That is a different mechanism from the ceiling and it acts in the same direction, which is why the binary row is the worst on every measure at once.

What the choice is actually between #

Strip away the shifts and the two algorithms are startlingly similar.

Both build a trie over the pattern set. Both hold the same number of nodes. Both attach something to each node: failure links and output links in one case, two shift values in the other. Both are correct for any set of patterns.

The differences that matter are three, and none of them is asymptotic:

The direction of the scan, which is what makes skipping possible at all and what makes the cost depend on the shortest pattern.

What preprocessing costs. The automaton’s failure links are built in one breadth-first pass over the trie — time linear in the total pattern length, and the number is not large. The exact shift rules used here are quadratic in the set, and at a hundred and twenty-eight patterns they cost 359,251 character comparisons against a scan of 49,072.

Whether the cost is predictable. The automaton’s is $n$ reads and one state transition each, always. The skipping matcher’s is somewhere between $n/w_{\min}$ and $nm$, decided by the text, the alphabet and the shortest pattern — none of which the algorithm knows in advance and two of which the caller does.

That last one is why the automaton is what gets deployed in the places where either would work. A system that scans network traffic against a signature set does not want a matcher whose throughput falls by a factor of five because somebody added a two-character rule.

The arithmetic of the ceiling, and where it puts the crossing #

The ceiling is easy to state and it is worth putting a number on what it implies, because the number explains the crossing without any measurement at all.

A window covers $w_{\min}$ positions and advances by at most $w_{\min}$, so in the best imaginable case the matcher performs $n / w_{\min}$ windows. Each window reads at least one character. So

$$\text{characters examined} \ \ge\ \frac{n}{w_{\min}}$$

and no shift rule, however clever, can get under it. On sixteen-character patterns that floor is $n/16$; on two-character patterns it is $n/2$, which is already half the work the one-pass matcher does before a single window has walked deeper than its first character.

The other end is the depth of the trie walk. A window that mismatches immediately costs one read and takes the longest shift available; a window that walks six levels in costs seven reads and takes the shortest. Over four symbols the expected depth of a walk into a trie of $k$ patterns rises with $k$ — there are more edges out of every node — so as the set grows, windows get more expensive and shift less, and the two effects multiply rather than adding.

That is what the crossing at eight patterns is. It is not a threshold in the algorithm and there is nothing at eight; it is where a product of two curves that are each degrading passes the flat line of a matcher that has neither problem.

And it is why the crossing moves so far with the alphabet. Over twenty-six symbols the expected trie depth barely rises with $k$, because most characters still have no edge out of most nodes, so only one of the two curves is degrading and the product crosses the line much later — past two hundred and fifty patterns on the sweep above.

The worst case is not exotic and it is not the point #

Both matchers have a worst case in which they do $\Theta(nm)$ work. For the skipping one it is the classic construction: a text of one repeated character and patterns of the same character with one difference, so every window walks to the bottom of the trie and shifts by one. This collection has that example already for the single-pattern case, and it transfers unchanged.

But the worst case is not the interesting failure here, because a worst case is an input somebody has to construct. The ceiling is a failure on ordinary input — no adversary, no repeated characters, no structure at all in the text — triggered by one entry in a list, and it degrades smoothly rather than falling off a cliff, which is why nobody notices where it started.

Between the two, the second is the one worth a measurement. The first has a proof.

There is a further asymmetry worth naming, because it is the reason the two failures feel different to somebody operating a system rather than analysing one. The adversarial worst case arrives as an input and leaves with it: the next query is fine. The ceiling arrives as a configuration, stays until somebody edits it, and applies to every query afterwards — and the query that suffers is never the one that caused it. A monitoring dashboard showing the throughput of a signature scanner would show a step down on the day the short rule was added and nothing at all about which rule it was.

Nor does the degradation announce itself as a bug. Every shift the matcher takes is still safe, every occurrence is still found, every assertion in the implementation still holds, and the only symptom is that a number nobody is looking at has doubled. That is the same shape as the defects this collection keeps finding in other places: an index counted at zero, a constant dropped by the notation, a floor nothing measures against. The class is unchanged, the correctness is unchanged, and the thing that moved is the only thing anybody cared about.

The repair is to split the set, and it changes the shape of the cost #

The last thing the essay measures is a defect with a known cause, a known trigger and a parameter the caller can see. It also has a repair that needs no new algorithm, and the repair is worth working out because its arithmetic is more interesting than the saving.

Partition the patterns by length. Send the short ones to a one-pass automaton and the long ones to the skipping matcher, and run both over the text. Nothing about either algorithm changes; what changes is that $w_{\min}$ for the skipping matcher is now the shortest of the long patterns rather than the shortest of everything.

On the run this essay opens with — fifteen patterns of sixteen characters and one of two — the numbers are:

A saving of about 14%, which is real and is not the point. The point is that the two arrangements have different shapes.

The combined matcher’s cost is the long patterns’ cost multiplied by a degradation factor that the short pattern sets. Add more long patterns, or make them longer, and the thing being multiplied grows while the factor stays; the damage scales with the whole set.

The split arrangement’s cost is the long patterns’ cost plus one pass over the text. That extra pass is $n$ reads however many long patterns there are and however long they get, so as the set grows the additive term becomes a smaller and smaller share.

Converting a multiplicative penalty into an additive one is almost always the better trade, and it is available here for the cost of running two matchers instead of one. On a set of a hundred long patterns and one short one the combined arrangement would be paying its degradation on all hundred, and the split would be paying one extra scan.

There is a limit and it is easy to state: the short group must be small enough that its own automaton is worth building, and the text must be scannable twice. A streaming deployment that sees each byte once cannot run two passes, and there the arrangement is two matchers driven in lockstep over one scan — which is what an intrusion-detection engine does, and which is why such engines carry several matchers rather than one.

A cost governed by a minimum is a cost one entry can destroy #

There is a general observation underneath all of this and it is worth separating from the algorithm, because it applies to a great many systems that have nothing to do with matching.

The skipping matcher’s performance is governed by $w_{\min}$ — a minimum over a user-supplied set. Minima have a property that means and sums do not: a single element can determine them completely, and no amount of goodness elsewhere compensates. Fifteen excellent patterns and one bad one give exactly the behaviour of sixteen bad ones.

That is a fragility with a shape, and once it is named it is easy to spot. A build system whose incremental time is set by its slowest-to-check dependency; a cache whose hit rate is set by its largest entry; a batch whose latency is set by its slowest member; a distributed query whose response time is the maximum over its shards — all of them are costs governed by an extremum over a set somebody else assembles, and all of them degrade the same way, invisibly and completely, when one entry changes.

The remedy is the same in every case and it is the one the section above describes: stop taking the extremum over the whole set. Partition, so that the bad entry governs only its own group; or bound the set at the point of entry, so that the extremum cannot move past a stated limit. What does not work is optimising the algorithm, because the algorithm was never the problem — the statistic was.

What is not measured here #

A clock. Everything above is characters examined, positions read, and character comparisons in precomputation. The backwards scan inside a window has a locality profile the forward one does not, and no number here reports it. The one thing that can be said is that the two counts diverge by a factor of two and a half at the right-hand end of the sweep, so any statement about running time depends on which of them the machine charges for.

Pattern sets with shared structure. Every set here is drawn at random and required to be distinct and non-nesting, which is the cleanest experiment and the least realistic one. A dictionary of English words shares prefixes heavily, which shrinks the automaton and shortens the shifts, and both effects are unmeasured.

The approximate shift functions. The published rules sit between “no shifting” and the exact rules measured here. Where they land is a third curve nothing above draws, and the direction of the difference is known — they under-estimate the safe shift, so they read more of the text and cost less to prepare — while its size is not.

Whether a caller could be warned. Nothing above is a defect that has to be lived with: $w_{\min}$ is known before the scan starts, the text length is known, and the crossing could be computed and the automaton chosen instead. That would be a matcher that picks its own algorithm from two numbers it already has, and no implementation this collection is aware of does it. Whether the choice can be made reliably enough to be worth making is a question about how well the crossing is predicted from $w_{\min}$, $\sigma$ and $k$ alone, and the sweeps above are three points of the surface that question is about rather than an answer to it.