The triples a typo writes

A checker that stops at two edits put a cap on a spelling checker. It searches a trie of 2,424 vocabulary words for the words nearest a misspelt query, and it stops and declines to answer once the nearest word is more than two edits away. Every misspelling in the test streams is one or two edits from its source, so a cap of two keeps every correction the checker could make, at 42% of the uncapped price. What it does not do is stop false suggestions. Of the misspelt words the vocabulary lacks, the cap still answers 44%, and 72% of those answers are words the writer did not mean. It declines 95% of unfamiliar words of eleven letters or more and 1% of three or four.

The essay’s closing section named the reason and proposed a second test. Distance cannot tell hop mistyped twice from bfs mistyped once, since both land a couple of edits from something. The query’s letters might. A second try before any feature had found that the count of a query’s letter-triples that no vocabulary word contains predicts how far the query’s answer is. The proposal: decline a query when that count passes a threshold, before any walk, and combine it with the cap. It predicted the triples would add nothing on long words, where the cap already declines, and would do what distance cannot on short ones. A three-letter query has a single triple, so its test is one yes or no. The question was whether one triple is enough evidence to decline a word.

A test on the letters, before any walk #

The vocabulary’s letter-triples are a fixed set: every run of three consecutive letters in any of its 2,424 words, 2,102 distinct triples of the 17,576 that three letters can make. A query’s unseen triples are those of its own triples not in the set, counted in a single pass over its letters. The checker here declines a query outright when it carries at least $\theta$ unseen triples, for $\theta$ from one to four, and costs nothing for it. Every other query is answered as the earlier page answered it: a walk that gives up past one edit, then one that gives up past two, and no answer beyond that. The streams, the walks and the verdicts are the earlier page’s. A misspelt vocabulary word is corrected when its source is among the suggestions. A suggestion for an unfamiliar word is a variant when it shares the word’s stem and differs only in an ending, and false otherwise.

Two kinds of query, one distribution #

71% of misspelt vocabulary words carry at least one unseen triple, and 79% of misspelt words the vocabulary lacks. The two distributions are almost the same shape. The unfamiliar words have a slightly longer tail, 14% with four or more against 6%, and that is all the triples can see. Among queries of three or four letters, where the test was meant to do its work, the difference vanishes: 50% of misspelt vocabulary words have an unseen triple and 51% of unfamiliar ones. A short query’s letters say nothing about which kind it is.

The prediction assumed the triples measure unfamiliarity. They measure something else, and the next plate shows what.

The typo writes the triples #

A single edit writes about one unseen triple into any word; a word the vocabulary lacks brings 0.59 of its own. One insertion, deletion or substitution changes the triples that span the edited position — up to three of them — and on average 1.62 of a mistyped word’s triples are new. The vocabulary’s triples are 12% of the triples three letters can make, so a new triple is more likely unseen than seen, and 0.99 of the 1.62 are. The edit’s contribution is the same whether the word it lands on is familiar or not. Two edits write 1.77 unseen triples into a vocabulary word and add 1.64 to an unfamiliar one.

The unfamiliar words’ own contribution is small because they are ordinary English. The second stream is words from another technical text, about instrumenting programs — instrumented, snapshots, counters, with a few run-together identifiers such as alloctotal — and two thirds of them are made entirely of triples the vocabulary already has. A word the vocabulary lacks is rarely a strange string. It is usually a familiar arrangement of familiar pieces that happens not to be on the list. So the triples carry about one unit of evidence about typing errors for every half unit about vocabulary. A test built on them mostly counts edits, which is what the cap already counts, and more precisely.

The q-grams an error cannot destroy used the same arithmetic in the other direction. An error destroys at most $q$ of a string’s $q$-grams, so a pattern of 21 four-grams keeps thirteen through two errors, and a filter demanding thirteen shared ones loses no true occurrence. That filter asks what an error cannot destroy. The decline asks what an error writes, and an error writes new triples as readily into a known word as into an unknown one.

What the test buys #

Declining at two unseen triples removes a quarter of the false suggestions, from 32% of unfamiliar words to 24%, and costs 41% of the corrections, from 94% of misspelt vocabulary words to 53%. Every threshold makes a trade of the same shape. At four the test removes no false suggestion and costs 6% of the corrections. At one it removes more than half the false suggestions and three quarters of the corrections. On a stream where a fifth of the queries are unfamiliar, a threshold of two gives up twenty-two corrections for each false suggestion it prevents. The curve never bends toward the corner where both would be good, because the test is not looking at the property that separates the two kinds.

The variants go the same way as the false suggestions. The cap alone gives 12.3% of unfamiliar words a variant of their own word — timed for time, adjacent for adjacency — a suggestion a writer might accept. At two unseen triples 8.2% get one. The triples decline plausible answers and false ones in about the same proportion, which is what a test blind to the difference between them would do.

Rarity instead of absence #

A triple is unseen or it is not, and the test throws away everything in between. A triple that occurs in one vocabulary word is weaker evidence of familiarity than one that occurs in two hundred, and an unfamiliar word built from familiar pieces may still use pieces the vocabulary uses rarely. So a finer version of the test was run beside the plates: score each query by the mean surprise of its triples, $-\log_2$ of the share of vocabulary words containing each, and decline above a threshold.

It does better than counting unseen triples, and not by enough. Declining when the mean surprise is 11 bits or more keeps 82% of the corrections and leaves 23.5% of unfamiliar words with a false suggestion; at 10 bits, 66% and 19.5%. The unseen-triple test at three keeps 75% and leaves 30.5%. On a stream one fifth unfamiliar, the surprise test at 11 bits gives up about six corrections for each false suggestion it prevents, against twenty-two for unseen triples at two. On words of three and four letters it moves false suggestions from 91% to 63% at 12 bits, and corrections from 79% to 56%. That is closer to an even trade, still a loss, since a correction is what the checker exists to make.

The improvement is in the same direction as everything else on this page. Rarity carries a little of the vocabulary’s own statistics into the test, and the vocabulary’s statistics are the only part of the evidence that is about the source rather than the typing. The filter that feeds the table found a cheap test in front of an expensive one worth having exactly when it rejected what the expensive one would reject. Neither letter test does that here; both reject what the cap would have answered correctly.

Where the triples cost most #

On words of eleven letters or more, declining at two unseen triples loses 64% of the corrections the cap would make and removes false suggestions from 1% of unfamiliar long words to none. The prediction said the triples would add nothing on long words. They add a large loss. A long word has more triples for a typo to break, and nothing about a long vocabulary word protects the triples its typo writes from being unseen. The cap had already made long words safe: it declines almost every unfamiliar long word because such words are far from anything. The triples then decline the misspelt long vocabulary words as well.

On words of three or four letters, the triples take false suggestions from 91% of unfamiliar short words to 79%, and lose 15% of the corrections. That is where the test does the most of what it was meant to do, and it is not much. A four-letter word has two triples. A typo in it breaks one or two of them, and a word the vocabulary lacks has as good a chance of containing only familiar pieces as a long one. With a single triple the decision is exactly the section’s question — is this string one the vocabulary could contain? — and at these lengths the answer is yes for most strings of either kind.

The work, which is the one thing the triples save #

A declined query walks nothing, so every threshold saves work. The cost is the number of subproblems is why the work is counted in table cells: each cell is one subproblem of the edit-distance recurrence, and a declined query solves none. The saving runs from 4,368 cells a query with the cap alone to 1,814 at two unseen triples and 723 at one. The saving is almost entirely in the corrections given up. Cells are not the cost made the point that a count of table cells prices the work and says nothing of the answer’s value. The prices here fall with the corrections, and a checker that saved work this way would be cheaper and would stop doing its job.

At four unseen triples the trade is closest to free: 13% of the work saved and 6% of the corrections lost, with no false suggestion prevented. That is a cost cut, not a quality repair, and it is the only threshold a checker could defend. It declines the queries so damaged that their nearest word, if any, is a guess.

What was wrong with the evidence #

The evidence the proposal leaned on was real. The earlier page found unseen triples predicting a query’s distance to its nearest word, and they do: a query with four or more unseen triples lies far from the vocabulary whichever stream it came from. But distance was never the problem. The cap already measures distance exactly, and the queries it answers wrongly are the ones that are close. For a close query the triples mostly count the typos that made it close, since those write the same unseen triples into a familiar word as into an unfamiliar one.

What would separate the two kinds is evidence about the source rather than the query. A misspelt vocabulary word is one or two edits from a word on the list, and an unfamiliar word is one or two edits from a word that is not. The checker cannot see the second word. It can only see that the nearest listed word is close, and that is equally true of both. The bound the search finds for itself showed a search can learn a great deal from its own walk about where the answer lies. What a walk cannot learn is whether a writer meant a word it has no record of.

So the section’s own question has a short answer. One triple is not enough evidence to decline a word, and neither are two. A three-letter query’s single triple is unseen for half the misspelt vocabulary words of that length, because the typo that made the query wrote it. The unfamiliar words are no more likely to have one. On these streams the answer to is this a string the vocabulary could contain? is the same for both kinds of short query, and for the same reason: the vocabulary could contain almost any three letters that a slip of the fingers could produce. A test that asks it can only decline at random with respect to the thing the checker cares about. That is what the plate of corrections against false suggestions shows, every threshold on it trading corrections for false suggestions at a loss.

What was not measured #

One vocabulary and one other corpus. The unfamiliar words come from one technical text about instrumenting programs, and their triples overlap the vocabulary’s because both are English written about computing. A second stream from another language or from identifiers in code would bring many more unseen triples of its own, and there the test might separate the kinds. Only this pair was measured.

Triples, counted and weighted. Unseen triples are on the plates, and the mean surprise of a query’s triples is reported in the text without a plate of its own. Pairs of letters, or longer grams, were not tried. A vocabulary ten times larger would see more of the 17,576 possible triples, so a typo would write fewer unseen ones; it would also leave fewer in the unfamiliar words, and whether the gap between the two kinds widens or narrows with the vocabulary’s size was not measured.

Uniform edits. The streams apply insertions, deletions and substitutions at uniformly random positions with uniformly random letters. Real typing errors favour adjacent keys and transpositions, which write triples that look more like English, and a real typo might carry fewer unseen triples than these. That would make the test decline fewer vocabulary words, and it would also tell the two kinds apart no better, since unfamiliar words would be mistyped the same way.

Still open: a decline that asks whether the nearest word is common #

Distance and letters both fail on short words for the same reason: the question they answer is about the query, and the question that matters is about the writer’s intention. There is one source of evidence about intention the checker already holds, which is how often each vocabulary word is used. A two-edit typo of the is far more likely than a two-edit typo of theorem at the same distance, and a query whose nearest words are all rare is more likely to be a word the vocabulary lacks than a typo of one of them. A trie fitted to its queries put a trie’s structure where its queries went; a checker could weigh its answers the same way.

The measurement that follows gives each vocabulary word its frequency in the corpus it was taken from, and declines a capped answer when the nearest words’ combined frequency, weighed against the chance of the edits needed to reach them, falls below a threshold. It counts corrections kept and false suggestions removed, by length. The prediction is that the frequency test does what the triples could not on short words, removing most false suggestions to unfamiliar words of three and four letters while keeping most corrections. Common short words are both the most often mistyped and the most often suggested. The question is whether a vocabulary’s own word counts are enough to tell a slip from a word the writer meant, or whether the one thing a spelling checker cannot know is the thing it most needs.