A checker that stops at two edits

A second try before any feature searched a trie of 2,424 vocabulary words for the word nearest a misspelt query. It measured the cost in cells of the edit-distance table and charged every attempt. The best fixed schedule was a walk that gives up past one edit, then one that gives up past two, then the discovering walk, which finds the nearest word however far away it is. On a stream where a fifth of the queries were misspellings of words the vocabulary lacks, that schedule cost 10,327 cells a query, well under the discovering walk alone. (It costs 10,398 below, where all 600 unfamiliar queries are weighted into the fifth rather than the first 500 interleaved.)

Its closing section pointed at where the rest of the price goes. The queries still unfound after the walk at two were 11% of the stream and paid 52,737 cells each to discover. For those queries the answer found is almost never the one wanted. Every misspelt vocabulary word in the stream is one or two edits from its source, so a query that fails the walk at two is a query whose intended word is not in the vocabulary. The nearest vocabulary word to instrumnted is not what its writer meant, however carefully it is found.

So the section proposed a checker that declines: after the walk at two, report “no suggestion within two edits” and stop, or pay for one walk at a larger cap and stop there. It predicted that a cap at two would keep every useful suggestion and cost about a third of discovering, and that the false suggestions of the uncapped search would be almost all at three edits or more. It named one way the prediction could fail. A large share of unfamiliar words might have a vocabulary word within two edits that is a plausible suggestion — a plural, a tense.

Scoring a suggestion against the word that was meant #

Measuring what a suggestion is worth needs something the earlier pages never kept: the word each query was made from. The streams are 2,000 misspellings of vocabulary words and 600 of words from a second corpus that the vocabulary lacks, each word given one or two random insertions, deletions or substitutions from a seeded generator. Replaying the generator’s own arithmetic with the same seed gives each query’s source beside it. Every one of the 2,600 replayed queries is checked against the stream’s own, so the sources belong to exactly these queries.

A checker returns every vocabulary word at the nearest distance, since ties are what a list of suggestions would show; a misspelt vocabulary word gets 1.9 on average. For a misspelt vocabulary word, a suggestion list is a hit if it contains the source. For a word the vocabulary lacks, the right answer is none. A suggestion list is scored a variant if it contains a vocabulary word that differs from the writer’s word only in its ending: time for timed, adjacent for adjacency, continues for continue. The rule is stated once — a shared prefix of at least three letters and, after it, an ending from a list of thirty English ones on each side — and it refuses floor for flow and the for theory. Anything else is a false suggestion.

A cap $C$ runs the earlier page’s schedule and stops: a walk at one, a walk at two, and if $C$ is larger, one walk at $C$. Every walk is charged. A query whose nearest word is further than $C$ gets no suggestion.

With a fifth of the queries unfamiliar, a cap of two costs 4,368 cells a query against 10,398 with no cap — 42% of the price. The prediction said about a third, and it is a little more. The misspelt vocabulary words cost 3,726 cells whatever the cap, because every one of them is answered by the walk at one or the walk at two. So the whole saving comes from the other fifth. Each unfamiliar query costs 6,938 cells at a cap of two against 37,086 uncapped. Of the 600, 336 have no vocabulary word within two edits, and discovering theirs cost 53,835 cells each. Those 336 queries are 85% of everything the uncapped search spends on unfamiliar words, because the discovering walk’s bound starts at infinity. The bound the search finds for itself found that a search’s price is set by how soon it finds a good bound, and a query with no near word finds one late. The columns the candidates share priced the trie walk that gives one column to each prefix. A walk bounded at two abandons a prefix as soon as every cell of its column exceeds two, and for a query unlike any vocabulary word that happens within a few letters of the root, down every branch.

What the uncapped search finds for those queries is what the proposal expected. The median declined query’s nearest word is four edits away. For pprimitives, a misspelling of primitives, it offers pyrimidine, positives and priorities. For receatable it offers reachable, predictable and recomputable, and for a misspelt growthtradeoff, ten edits away, trades. A few of the far suggestions are close relatives — substantially for substantfal at three edits, condition for conditinal — which is why the cap declines some variants as well.

A cap of one would save far more, 1,085 cells a query, but the walk at one answers only 59% of misspelt vocabulary words. The other 41% have been given two edits and need the walk at two. So two is the smallest cap that keeps the misspelt vocabulary words, and it keeps all of them. From a cap of two upwards, 93.9% of their suggestion lists contain the word that was meant, the same share as with no cap at all. The other 6.1% are misspellings that landed nearer to some other word — ecent from descent is one edit from event — and no cap, large or small, gets those right.

What the checker says to a word it lacks #

The price is half the case. The other half is the part the cap was meant to change: what the checker says to a word it does not have.

Uncapped, every unfamiliar word gets a suggestion and 77% get only false ones. A cap of two declines 56% of them — and still gives a false suggestion to 32%. The prediction that the false suggestions would be almost all at three edits or more fails. Of the 600 unfamiliar queries, 264 have a vocabulary word within two edits, and 190 of those are offered only words that are not a form of what was meant: has for bzs, a misspelling of bfs; deploy for destoy, a misspelling of destroy; spell for sohell, a misspelling of shell.

The failure mode the section named is real but small. Variants of the writer’s word — the plural or tense that makes a false suggestion almost useful — are 12.3% of unfamiliar queries at a cap of two and 22.7% uncapped. The cap removes some of them along with the false suggestions, and it removes them in about the proportion they occur. Of the 336 queries it declines, 18% would have been offered a variant and 82% only false suggestions. Among what a cap of two still says to an unfamiliar word, 72% is false. Uncapped it was 77%. The cap makes the checker say less without making what it says much better.

The distribution says why. An unfamiliar query is its source plus one or two edits, so its nearest vocabulary word is roughly as far away as the source’s nearest, give or take what the edits did. The vocabulary is full of short common words, and a short source is close to many of them. The variants concentrate at two and three edits, the distances of a suffix plus a typo. Past four edits there are almost none, because a source that far from every vocabulary word has no form in the vocabulary at all. The prediction pictured false suggestions as far-away words and variants as near ones. In fact both are spread over the same few edits, and the cap cuts through the middle of both.

Two edits is most of a short word #

One property of the query decides, far more than any other, whether a cap of two declines it: the length of the word that was meant.

A cap of two declines 95% of unfamiliar words of eleven letters or more and 1% of those of three or four, and gives a false suggestion to 87% of the short ones. Two edits is a different distance for different words. For an eleven-letter word it is a fifth of the word, and for most such words nothing in the vocabulary is that close. For a three-letter word it is two thirds of the word. bfs with one substitution becomes bzs, which is two edits from sixteen vocabulary words, has, was and best among them. A short unfamiliar query has a median of eleven vocabulary words within two edits of it, and as many as 46. The cap is a fixed number of edits, and a fixed number of edits is a lenient cap on short words and a strict one on long ones.

The filter that feeds the table refused candidates before they reached a table, on a cheap exact test: cut the pattern into pieces, and a match within $k$ edits must contain one piece exactly. Its refusal was sound, since no match it refused could have been within the bound. The cap’s decline is sound in the same sense for misspelt vocabulary words at every length, since all of them are within two edits. As a test of whether a word is in the vocabulary at all, though, it has no such guarantee. It works on long words and hardly at all on short ones.

The misspelt vocabulary words show what any repair would cost. Their sources have the same short words in them, and their misspellings are also two edits away. A cap tightened to one edit for words of four letters or fewer is the obvious repair, and the streams already contain its whole account. Of the 87 short unfamiliar queries, 59 are exactly two edits from their nearest vocabulary word, and the tightened cap would stop answering them. Of the 2,000 misspelt vocabulary words, 298 come from words of four letters or fewer, and 92 of those are two edits from the nearest vocabulary word. Every one of the 92 gets its source among the suggestions at a cap of two. The tightened cap would refuse 92 right answers to silence 59 wrong ones. On short words, distance cannot tell the two kinds of query apart, because a short word two edits from the vocabulary is exactly what a two-edit typo of a short vocabulary word looks like.

A saving that grows with the unfamiliar share #

The saving is linear in the share of unfamiliar queries, and at half the stream the uncapped search costs 3.8 times a cap of two. With no unfamiliar queries the caps are identical, since every query is answered at two. Each unfamiliar query costs 6,938 cells at a cap of two, 17,718 at a cap of three and 37,086 uncapped, against 3,726 for a misspelt vocabulary word. A checker facing technical writing, where a larger share of words are identifiers and jargon the vocabulary lacks, gains more from the cap. That is the same stream on which the cap’s suggestions are least useful. A trie fitted to its queries found the unfamiliar queries to be the expensive ones for every policy it tried, and the cap is the first policy here that makes them cheap. It does so by not answering them.

A cap of three is the obvious compromise, and the measurements put a price on it. It costs 2,156 more cells a query than a cap of two at a fifth unfamiliar. It raises the unfamiliar queries offered a variant from 12.3% to 20.3%, and those offered only false suggestions from 31.7% to 48.2%. Two variants are bought for every four false suggestions added. Whether that is worth it depends on what a false suggestion costs the person reading it, which no cell count can say. The cost is the number of subproblems first counted this table’s work in cells, and a count of cells has no second axis to weigh against. This page has one, and the two axes do not share a unit.

Where these measurements come from #

One vocabulary, one second corpus, one typo model. The vocabulary is the prose corpus’s 2,424 distinct words, and the unfamiliar words are those of a corpus of program text that the prose lacks. Many of them are identifiers — bfs, cmp, nan — shorter than typical English words, which weights the unfamiliar stream towards the short words the cap handles worst. Typos are uniform insertions, deletions and substitutions. Real typing errors favour adjacent keys and transposed letters, and would move some misspellings closer to their sources and some into other words.

The variant rule is a rule, not a reader. It counts note for not and proved for proven as variants. It refuses instance for instanceof and every suggestion that shares a stem but changes the middle of a word. Its verdicts were read against the queries they scored, and on the ones read it agrees with what a person would call the same word in another form more often than not. It is not a judgement of usefulness, only of whether a suggestion is plausibly the word that was meant.

Ties are listed, not ranked. A suggestion list holds every word at the nearest distance, 1.9 on average. A checker that ranked ties by word frequency, as real ones do, would show one word. It would be right more often on misspelt vocabulary words and would give the same number of false suggestions to unfamiliar ones, since none of those can be right.

Cells are the cost. Every walk is charged in cells of the table. Cells are not the cost found tables whose cells each hide many transitions. An edit-distance cell reads three neighbours and nothing more, so here a cell is a fair unit, and a cap that stops early also saves the stack of trie nodes the skipped walks would have held.

Still open: a decline that reads the query’s letters #

The cap failed as a test of whether a word is in the vocabulary because distance is the only thing it looks at, and on short words distance does not separate the two kinds of query. A two-edit typo of hop and a one-edit typo of bfs look the same to any rule about edits. Something else about the query has to do the separating.

The candidate is the query’s letters. A second try before any feature found that the number of letter-triples in a query that no vocabulary word contains predicts how far its answer is. That is a property of the query’s spelling, not of its distance, and a typo of a vocabulary word breaks at most a few of its triples, while a word from another corpus may have triples the vocabulary has never seen. The measurement that follows declines a query when its unseen triples pass a threshold, before any walk, and combines that with the cap of two. It counts the same things: cells a query, hits kept, variants and false suggestions given. The prediction is that on long words the triples add nothing the cap has not already done, and on short words they do what distance cannot. A three-letter query has only one triple, so the test there is a single yes or no — whether bzs is a string the vocabulary could contain. The question is whether one triple is enough evidence to decline a word, or whether short words are simply where a checker has to answer and be wrong.