Table — the series
-
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.
-
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 cells are not the cost
This field opened by pricing a dynamic program in subproblems — 29,737 calls became 56 cells and the class changed. That is right when a cell is cheap. A table over intervals has 8,385 cells and considers 349,504 transitions to fill them, and the cubic in its bound is inside the cell rather than in the table.
-
The argmin that cannot go backwards
The same triangular table, the same ninety-one cells, the same tree at the end of it — and 364 transitions one way against 156 the other. At 256 keys the ratio is 38. What removes the factor is not a property of the recurrence but a property of the numbers it is given, and the recurrence does not mention them.
-
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.
-
The 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.
-
A triangle stored in a square
An interval table has a cell for every range of keys and nothing below its diagonal, and it can be stored as a square array, as packed rows, or as packed diagonals — the last matching the order it is filled in. On sixty-four keys, with every read replayed through a small cache, the square misses 39.7% of its reads, packed rows 38.8%, and packed diagonals 78.4%. Storing a table in the order it is written is storing it in the order it is not read.
-
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 split scan cut into blocks
Every way of filling an interval table one cell at a time stops at about one cache miss per split point considered once the table outgrows the cache — 1.01 at 128 keys, whether the cells go by length, by rows, or in a recursive tiling. Cut each cell's scan into blocks instead, and apply a block of split points to a block of cells whose inputs are all in hand, recursively at every scale, and the same 357,760 split points cost 0.094 misses each. The fill is told nothing about the cache, blocks of one and of four do equally well, and it needs no extra memory, where storing the table twice gets to 0.151 by doubling it.
-
The bound a block can and cannot have
Knuth's condition turns an interval table's cubic fill into a quadratic one by bounding each cell's best split between its two neighbours'. A blocked fill cannot use it a cell at a time, and the two cells that bound a block lie outside the block — one to its left, one below it. The schedule has finished both for ten per cent of the blocks, the bound then removes eleven per cent of the splits, and it removes half a per cent of the cache misses, because the splits it skips are the ones already in the cache.
-
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.
-
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 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.