The data that is not a number
The comparison that is not one comparison
What happens to a comparison count when the elements are strings — why the element count cannot move while the character count grows seventeenfold, and why a radix sort that never compares anything is the honest comparison.
The shift the pattern already knows
KMP's failure function, the exact 2n bound on characters examined, why the bound is worth almost nothing on the inputs it is usually quoted for, and what a worst-case guarantee actually buys.
The text that answers without reading it
Why a string search can be sublinear, what the bad-character table actually measures, why the advantage saturates at the alphabet size rather than growing with the pattern, and where the floor under all of it sits.
The model is the compressor
Conditional entropy as a measured quantity, why every model gives a different and correct floor, what an adaptive coder pays for not being told the model in advance, and where the estimate stops being an estimate.
The shift a set of patterns allows
Commentz-Walter, the multi-pattern matcher that skips — the two shift conditions computed exactly, the bad-character rule doing almost nothing, and what the tables cost to build.
The transform that emits nothing
How a permutation lowers a floor it cannot change — sorted rotations, the clustering that follows, move-to-front, and why the inverse is the only proof the transform is real.
A distance that is a path through a grid
Edit distance as a shortest path, why it is a metric and which of the four conditions is doing work, and what changes when a substitution is priced at two.
The filter that feeds the table
Seed-and-extend over a compressed self-index — the pigeonhole that makes it correct, the funnel from twenty thousand positions to seven, and the two numbers that decide whether the filter paid.
One pass for every pattern at once
Aho–Corasick as KMP's failure function applied to a trie, what the output links are for, and the measured gap between one pass and one pass per pattern.
The entropy that cannot see a copy
Why Hₖ is blind to repetition at a distance, what r and z measure instead, and the three orderings five texts get from three measures of compressibility.
The row that starts at zero
Approximate search as the edit-distance table with its top row zeroed — why the global distance says nothing about occurrence, what the last row is, and what the threshold does and does not change.
The phrases a text copies from itself
What the greedy self-referential parse counts, how its phrase count compares with the run count on the same texts, and why neither is an entropy.
The occurrences that cross a boundary
Why an index built on a parse only has to search for the occurrences that straddle a phrase boundary, and what producing the rest costs.
The q-grams an error cannot destroy
The counting filter, the pigeonhole argument behind its threshold, and why its saving is in a different currency from the seed filter's.
The shift somebody published
What Commentz-Walter's published shift functions actually compute, why they are cheap, and how they are checked against the exact rules they approximate.
A parse that will not follow a long chain
How a depth-bounded Lempel-Ziv parse is constructed, why the bound has to be checked over the whole source region rather than at its start, and what the dial does at each end.
The errors the rest of the pattern needs
How a one-pass lower bound on the errors in each pattern prefix is computed, why it is safe, and how close it comes to the true minimum.
The table the links already knew
How the exact Commentz-Walter shift rule splits into a case the failure links already compute and a case they do not, and what the second case is.
The search that starts in the middle
Search schemes over a bidirectional index, why beginning at a piece that must match exactly cuts the tree by a factor of nearly three, and how the saving grows with the budget.
The parse in one pass of the text
The greedy Lempel-Ziv parse driven by a suffix automaton, the one ordering that makes it reproduce the quadratic construction exactly, and what it costs per character.
A corpus that was not generated
The frozen real corpus, its three parts and why they repeat for three different reasons, and the first measurements of a collection nobody in this collection made.
A million characters of the same thing
The second frozen corpus at a million characters, both measures of repetition swept across two orders of magnitude, and the control that says how much of the movement is the collection.
The shape of a real history's depth
The depth profile of two real version histories and two collections that are not histories at all, measured position by position, against the generated collection every earlier number was taken on.
The cell nobody filled
The four cells of repetition against document count, measured on one text arranged four ways, and why the empty corner had to be built rather than predicted.
What repetition is worth once the logarithm is gone
The size sweep drawn on a repetitive collection with its own shuffled control, and the difference between a text that repeats and one that is merely predictable.
The array is the length distribution
How far a document array compresses, decided in advance by how a collection apportions its characters, with the null case measured rather than mentioned.