Edit distance — where it appears
Named by 39 essays across 8 fields — each of them below, with the objects they name alongside it.
The cost is the number of subproblems
The edit-distance recurrence, written down literally, makes 29,737 calls on a six-letter word and a seven-letter word. Written down with a table beside it, it makes 56. Nothing about the arithmetic changed, and the class did.
The same table, filled two ways
Top-down and bottom-up compute identical cells and return identical answers. One of them asks the table half a million questions and recurses four hundred frames deep; the other asks none and recurses none — and on a knapsack it fills twenty-two times as many cells as anything can reach.
A band as wide as the answer
If two strings are close, the optimal route stays near the diagonal and nine cells in ten cannot be on it. A band of three finds the right answer on a pair 300 characters long — and a band of thirty-two is needed before anything can prove it.
A cost that is not one
The same eighty-one cells, filled by the same recurrence, return 6, 10, 10 and 15 — in edits, in cost, in bits and in bits again. Only the first is a count of anything, two of them are equal by arithmetic coincidence, and the alignment each one chooses is different.
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.
The table nobody has to keep
A million-cell table, computed cell for cell in the same order, holding two thousand cells at its peak instead of a million. The saving is exactly (n+1)/2, it costs nothing on any operation counter, and what it buys is paid for with the one thing the table was for.
The order that has a depth
One hundred cells, filled in three orders, producing one table. Row order takes ninety-one steps and anti-diagonal order takes nineteen. Nineteen is not a property of the order — it is the longest chain of cells in the recurrence itself, no schedule can get under it, and every count taken until now was a total that could not see it.
A distance divided by a length is not a rate
Two substitutions turn "ab" into "ba", a distance of two over an alignment of two columns — a rate of 1.00. Deleting, matching and inserting also costs two, over three columns, for 0.67. Both are alignments of the same pair, the second has the better rate, and the optimal alignment is not the one that achieves it. Over every pair of strings up to three characters on three letters, 21% disagree.
The 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.
A distance that is a path through a grid
How far apart two strings are is a shortest-path problem on a grid whose every edge is drawn by the recurrence — and finding a string in a text costs 4,988 character comparisons where measuring how far it is from one costs 96,000.
The alignment that fits in one line
Compute the table twice and hold three rows of it. The factor of two is a geometric series and is predicted exactly; measured, it comes down from 2.269 to 2.052 as the strings grow, and the peak is 3(m+1) cells on the nose.
The filter that feeds the table
A self-index answers exact queries and nothing else. Approximate matching needs a table with twenty thousand columns in it. The pigeonhole joins them — cut the pattern into k+1 pieces and at least one occurs exactly, and the index that cannot answer the question decides where to ask it.
A column computed in machine words
Adjacent cells of a distance table differ by at most one, so a whole column is two bits per cell — and thirty-two of them fit in one register. Fifteen word operations per character replace three cell evaluations per cell, and below a pattern of fifteen characters the trade is a loss.
The matrix a corpus wrote
A substitution matrix is not a property of an alphabet. Fit one to four hundred pairs of sequences that rarely change and the dearest substitution costs five; fit the same model to four hundred pairs that often change and it costs two. Two hundred test pairs aligned under each matrix give different alignments in 115 cases — and a matrix fitted to eight pairs of the first kind moves 79 of them, from sampling alone.
The row that starts at zero
The same 1,413 cells, filled by the same recurrence in the same order, answer 148 and 0. One line of initialisation decides which question the table was asked, and only one of the two answers is about whether the pattern is there.
The 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.
A floor that holds if something else does
The four lower bounds written before it are proofs. This one is a chain of implications with a conjecture at the top, and neither end of it is proved. The link that can be performed is performed here — checked over 55,754 formulas, 918 of them unsatisfiable — and the link that cannot is quoted and marked as quoted.
The branches an error opens
The tree multiplies by 19.6 for the first error, 12.3 for the second, 10.3 for the third and 8.8 for the fourth. A branching factor of four on a sixteen-character pattern would predict sixty-four, and the gap between sixty-four and eight is the intervals emptying.
The q-grams an error cannot destroy
A pattern of twenty-four characters holds twenty-one four-grams. Two errors can destroy at most eight of them, so any occurrence with two errors still shares thirteen — and a filter that keeps only the windows sharing thirteen proposes 104 of 3,977 and computes 16,744 table cells instead of 96,000.
The search that spends a budget
A backward search narrows one interval per pattern character. Give it a budget of three errors and it narrows 39,943 of them instead, finds every occurrence the whole table finds, and reads not one character of the text — 177,046 index ranks against 60,000 table cells and zero characters examined.
The 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.
The 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.
The filter that proposes everything
Seed-and-extend saves two thousand times the work at zero errors and costs more than doing nothing at four. Between them the selectivity falls through the floor, and where it falls is set by two numbers that can be computed before the filter is run — one of which does not contain the length of the text at all.
A trie fitted to its queries
A nearest-word search over a trie of 2,424 words gives a column to about 30% of the prefixes each query, and it was proposed that a stream of queries would pick out a part of the trie worth keeping and a part worth collapsing. A hundred queries have visited 93% of it; two thousand, 99.5%. A stream does not choose a part of the trie. It chooses a distance: misspelt vocabulary words all lie within two edits, and a search that starts at the median past answer does a fifth of the work of one that discovers its bound. Misspellings of words the vocabulary lacks break that, unless the search tries the learned bound once and then gives it up.
A distance that is not a distance
Under unit cost the edit distance obeys the triangle inequality and this site asserts that it does. Under a stated substitution matrix it need not, and on 42,840 enumerated triples it fails 2,832 times — taking with it every structure that prunes by distance, at a measured 13.22% of the bounds they rely on.
The errors the rest of the pattern needs
Read the pattern left to right in an index of the reversed text and count the points where the interval empties. That count is a lower bound on the errors any alignment of the prefix must contain, it costs 72 rank operations, and it removes 70% of a search tree.
A second try before any feature
A nearest-word search that learned one starting bound for a whole stream was proposed a bound for each query instead, read off features the search can compute before it walks. The proposed feature separates nothing: 58% of misspelt vocabulary words and 53% of words the vocabulary lacks begin with a real three-letter prefix. Length and unseen letter-triples do predict distance, and still buy about 1%, because the best start is two for almost every class. What closes half the gap to an oracle is a second cheap walk: one, then two, then discover.
A checker that stops at two edits
A nearest-word search that must always answer pays most of its price on the queries whose answer is useless: misspellings of words the vocabulary does not have, whose nearest vocabulary word can be twenty edits away. Capping the answer at two edits keeps every suggestion a misspelt vocabulary word could get and costs 42% of the uncapped search. What it does not do is stop the false suggestions. It declines 95% of unfamiliar words of eleven letters or more and 1% of those of three or four, because two edits is most of a short word, and 72% of what it still says to an unfamiliar word is wrong — against 77% with no cap at all.
The triples a typo writes
A spelling checker capped at two edits keeps every correction it could make and still gives a false suggestion to 72% of the unfamiliar words it answers, because on short words distance cannot tell a typo of a vocabulary word from a word the vocabulary lacks. The query's letters were proposed as the second test: decline a query whose letter-triples the vocabulary has never seen. They cannot separate the two either. One edit writes about one unseen triple into any word, familiar or not, while an unfamiliar word brings 0.59 of its own, and two thirds bring none. Declining at two unseen triples removes a quarter of the false suggestions and costs half the corrections — twenty-two corrections for every false suggestion removed.
The counts only short words carry
A spelling checker capped at two edits still gives a false suggestion to many words its vocabulary lacks, and the one evidence about a writer's intention it already holds is how often each vocabulary word is used. Scored by its nearest words' counts, weighed a tenth for each edit, an answer was predicted to separate a slip from an unfamiliar word on short queries. On the streams the checker was built against, whose typos are of words drawn evenly from the list, the false suggestions go to commoner words than the corrections do, and the test gives up sixteen corrections for each false suggestion it removes. Drawn as a writer mistypes, in proportion to use, the counts separate the two at last — and still trade worse than a plain cap of one edit, except on words of four letters or fewer, where a threshold removes a ninth of the false suggestions for one correction in ninety-six.
The commonest word at the distance
A spelling checker that lists every nearest word counts a correction whenever the intended word is somewhere in the list, and on a short query that list averages three or four words. Offering only the commonest of them was predicted to keep nine in ten of the list's corrections on short words when misspellings follow use, and far fewer when they are drawn evenly from the word list. It keeps 77% on words of three or four letters, and on the even stream it keeps 48% — less than a choice that ignores the counts. Across all lengths the two streams look the same, which is how the difference stays hidden.
A list as long as the doubt
A spelling checker that offers one word is right 64% of the time on short misspellings, and one that offers three is right 80% of the time. Between them sits the obvious design: one word when the commonest nearest word's count dominates the next, more when the counts are close. The counts do know when the commonest word is right, from 36% of the time at a ratio under two to 91% over a hundred. Yet a list sized by that ratio beats a blind mix of one word and three by at most two and a half points, a plain list of two does as well, and on misspellings drawn evenly from the word list the ratio is worse than not reading it.
A second word judged by its own share
A spelling checker that offered its commonest nearest word alone when that word's count was many times the next, and two or three words otherwise, beat a coin's mix of one-word and three-word lists by at most two and a half points, and a plain list of two did better. The ratio measures how dominant the first word is, not how likely the second is. Judged instead by its own share of everything within two edits of the misspelling, the second word is shown only when that share is at least 0.15: on short words drawn by use the checker then sits 4.5 points over the coin's line at 1.32 words a query, nearly twice the ratio's lift and above the list of two, and the weight given a two-edit word moves the result by a tenth of a point. A second word with a share under 0.01 is never the source. On misspellings drawn evenly the share is no guide at all, and the list of two wins.
The threshold that reaches zero
At q = 5 and four errors on a twenty-four-character pattern the filter demands zero shared q-grams, proposes all 2,977 windows, and computes 986,266 table cells where filling the whole table would have cost 96,000. The failure is arithmetic and is knowable before a character is read.
Three savings in three currencies
The same six occurrences, found four ways. The table computes 60,000 cells and reads 60,000 characters. The counting filter computes 6,251 cells and reads 13,022 characters. The seed filter computes 3,325 and reads 550. The index walk computes none, reads none, and performs 18,645 ranks.
The dial that has no setting
The generator has one parameter. The real version history's run count asks it for 2.3% and its phrase count asks for 3.2% — and the reason is not that the dial is badly calibrated. Real edits average 7.3 characters a block and generated ones average 1.04.
The order with the best depth
An edit-distance table can be filled row by row, column by column, or one anti-diagonal at a time, and the anti-diagonal order is the one that needs the fewest rounds — 513 against 65,793 on two strings of 256 characters, because every cell on an anti-diagonal is independent of the others. Stored the usual way, row by row, it also misses the cache on 31.1% of its reads, where row order misses 6.3%. The order that is best for parallel work is worst for the memory it runs on.
The table stored the way it is filled
Store an edit-distance table by anti-diagonals instead of by rows, and the anti-diagonal fill keeps its 513 rounds while its cache misses fall from 31.1% of reads to 8.7%. It does not fall to row order's 6.3%, and the gap is not noise — on caches of four and eight lines the two rates are 9.4% and 6.3%, exactly three to two, because a cell reads from two earlier diagonals and only one earlier row. The same layout turns row order into the order that strides, at 28.3%. How a table is stored and the order it is filled in are one decision, and its price is the number of earlier fronts the recurrence reads.
Eight cells at once
The anti-diagonal fill order exists because its cells do not depend on one another, and every table filled here has been walked one cell at a time anyway. Computed eight at a time, a step touches 5.71 cache lines on the layout that stores the table by diagonals and 10.87 on the one that stores it by rows — and per cell the first keeps falling to 0.42 while the second stops at 1.27. The prediction that a diagonal step would touch three or four lines was wrong, and line-aligning each diagonal only takes it to 4.94.
Named alongside it
The objects these essays reach for when they reach for this one.
Dynamic programmingMeasured countCost modelMeasurementSubproblemPruningAlignmentApproximate matchingTrade offCorpusHonest limitThreshold