The thread: The definition is not the algorithm
The zero that moves the answer out of the corner
One extra term in the recurrence — a floor at zero — and the answer stops being in the last cell. It becomes a maximum over all 1,040 of them, the traceback's starting point is a search, and the whole mode is meaningless unless a randomly matched pair of characters scores negative on average. That last condition is on the scoring scheme, not on the sequences.
When the algorithm is a tableThe edit that reaches back two rows
Swapping two adjacent characters is one keystroke and costs two edits. Adding it as a fourth transition is four lines, it is what nearly everything ships, and the function those four lines compute is not the one they are named after. Over 1,600 pairs of short strings the two definitions differ on twelve, and the shipped one breaks the triangle inequality on twelve triples where the other breaks it on none.
When the algorithm is a tableThe cells that were never worth having
Two three-hundred-character strings over twenty-six letters give a table of 90,601 cells, and 3,421 of them are pairs of positions whose characters agree. Only those can lengthen anything. A method that enumerates exactly those computes a twenty-sixth of the table — and on a two-letter alphabet it computes half of it and is worse than the table it replaced.
When the algorithm is a tableThe parameter plane has few answers
Sweep the cost of opening a gap against the cost of extending one over five hundred and seventy-six settings, and the optimal alignment of intention against execution takes four values — one of them at 571 of the settings. Under a linear model the plane divides into three wedges through the origin, because doubling every cost changes nothing and only the ratio is a parameter. Tuning an aligner is choosing a region, and most of the plane is one.
Two parametersAn estimate is a reweighting
Reprice every arc by the estimate's drop across it and run plain Dijkstra, and it expands the same 325 cells A* does, in the same order, because the two are one algorithm. Replace the estimate with one that is still never too high but drops too fast between neighbours, and 215 arcs go below zero — and on a stated grid the search that refuses to reopen a finished cell returns a path of 178 where the shortest is 169.
Two parametersWhere two searches should stop
Search from both ends of a shortest-path query at once and the two frontiers meet somewhere in the middle, having expanded about two thirds of what one search would. Stop at the first vertex both searches have finished, and on five of forty weighted grids the path returned is longer than the shortest. The rule that is always right stops on a different condition, and on one of those grids it also stops sooner.
When the algorithm is a tableThe bound the search finds for itself
A spelling checker that computes the full edit-distance table against every word in a 2,424-word vocabulary fills 156,714 cells for each misspelt query. Bound each table by the best distance found so far, and abandon it the moment a whole row exceeds that bound, and the same search fills 40,273 and finds the same words. Meet the candidates nearest in length first and it fills 26,203, starting a table for exactly the words a search that knew the answer in advance would start. The last factor of 1.7 is the price of not knowing, and it is largest when the misspelling is smallest.
What the libraries doWhere the exact rules pay now
With a construction as cheap as the published one, the exact shift rules pay for themselves past eight thousand characters of text at two patterns, four thousand at four, and never at thirty-two — because by thirty-two patterns the two rules make identical decisions.
When the algorithm is a tableThe columns the candidates share
Three thousand tables against one query, and most of them begin the same way. Stored as a trie, the 2,424-word vocabulary has 7,710 distinct prefixes holding 17,239 letters, and a search that computes one column per prefix reads 61,449 cells against 156,714 — before it applies any bound at all. Apply the bound at a prefix instead of at a word and it reads 16,958, beating a list search that was told the answer in advance.
What a bound isThe case a failure link does not cover
Compute the exact good-suffix rule from the failure links alone and eighteen of twenty-two entries come out too large. The matcher then steps past sixty-six of two thousand and twenty-five occurrences, and every match it does report is a match.
The data that is not a numberThe table the links already knew
The exact good-suffix rule costs 757,058 character comparisons to build from its definition at 128 patterns, and 3,824 from the trie's failure links. Same table, checked at every node — a factor of 198, and the definition was never the algorithm.
What a bound isThe cap an automaton cannot see
A state of a suffix automaton stands for a set of occurrences and hands back one of them. So a capped parse driven by it can ask whether the earliest occurrence is shallow enough and cannot ask whether any occurrence is — which costs up to 9.8% of the phrases, and only at the caps that bind.
The data that is not a numberThe parse in one pass of the text
The same parse, phrase for phrase, from 1,324,336 character comparisons or from 25,420 transitions and suffix-link steps. One of those numbers grows with the text and the other grows with its square, and the difference is why every measurement about a depth cap here was taken on a few thousand characters.
The other axisTwo bits a value, and what undoes them
The parentheses of a range minimum over 65,536 values are 131,072 bits. Everything that makes them answerable is 651,800 more — five times the payload — and one encoding choice nobody quotes accounts for a sixth of it on its own.
StructuresThe shape a range question is about
A range minimum is a question about a tree, and the tree is determined by the array. Twelve values, eleven parent links, and the answer to every one of the seventy-eight ranges is a lowest common ancestor — with the values themselves no longer needed.
What is taught wronglyThe deepest text is punctuation
Eight source files reach depth 78 in a parse, on a collection with no version history in it at all. The positions between depth 20 and depth 72 are the same 48 characters at every level, and every one of them is a dash in a comment separator.
The index that replaces the textThe half that is never asked where
A bidirectional index is two indexes and one interval. One of them is asked for ranks several hundred times a search and for a position never — and the parts that answer "where" are two of the five it is made of.
What is taught wronglyThe ratio that was an implementation
This collection published a factor of forty-two between two shift rules' preprocessing. Sixty-nine per cent of the denominator was a table the published rule never reads, and the numerator was a definition rather than a construction. The corrected ratio is 1.6.
What is taught wronglyWhat a quadratic construction was setting
A depth cap of one costs 90% of an 8,192-character text in phrases, and 86% of a 65,536-character one. The ladder's conclusions hold at thirty-two times the size — and the number the ladder could not reach, the deepest chain a real collection produces, turns out to be fourteen.
The index that replaces the textThe array the walk never reads
Document listing compares a chain entry against the start of a range. The comparison is true exactly when the document has not been reported yet — which the walk already knows, because it just wrote it down.
StructuresA document already in the answer
The same walk, with the chain's test replaced by a lookup in the answer so far. It reports the same documents at the same cost, and two exchanged lines make it lose nine of seventeen without failing.
StructuresThe price of a boundary is what precedes it
A separator sorts before everything, so its rows sit at the top of the suffix array and hold the documents' last characters. What a document boundary costs the transform is the entropy of the character in front of it, and nothing else.
The index that replaces the textThe tree answers the question
The distinct documents in a range of rows are the distinct symbols of the document array in that range. A wavelet tree enumerates those in one descent, so the range minimum, the chain, the bitmap and the recursion all go at once.
The index that replaces the textAsking about symbols that are not there
A search extends an interval by every character of the alphabet, and on a deep branch almost all of them produce an empty interval. That is a full rank walk whose entire result is the discovery that nothing was there.
What is taught wronglyOne set, three orders
The symbols an interval holds do not depend on the tree's shape. The order they come out in does, and a search that accumulates a running count as it reads them computes a plausible number that is wrong on eighty per cent of queries.
StructuresEvery copy points right
A greedy self-referential parse chooses each phrase's source from text already produced, so an occurrence copied from another lies strictly to its right. That one fact removes a visited set from a propagation, exactly as a left-first walk removed an array one strand ago.
StructuresTwo states per operator
Thompson's construction adds a bounded number of states per rule and no rule copies a sub-machine, so the machine is linear in the expression and is built in linear time. Every exponential in this field is somewhere else.
What is taught wronglyThe folklore is about a matcher
Four million steps against three hundred and twenty-nine, on a twenty-character expression matched against twenty characters. One of the two machines doubles with every character of the input and the other does not, and only one of them is what a regular expression is.