The commonest word at the distance

The counts only short words carry asked whether a spelling checker should answer at all. The checker searches a trie of 2,424 vocabulary words for the words nearest a misspelt query and, since a checker that stops at two edits, declines once the nearest word is more than two edits away. That essay scored each answer by how often its nearest words are used in the corpus the vocabulary came from, and declined answers that scored low. The test earned its keep only on words of four letters or fewer, and only on a stream of misspellings drawn as a writer makes them, in proportion to use.

Every verdict in that essay and the three before it shared an assumption that was never priced. A misspelt vocabulary word counted as corrected when its source was anywhere among the nearest words. On a long query that list is nearly always one word, so the assumption costs nothing. On a short query it can be a dozen words, all at the same distance, and a checker that hands a writer twelve candidates has not corrected anything. The closing section of that essay proposed using the counts for a different job: not to decide whether to answer, but to decide which single word to offer. It predicted that on the stream drawn by use, offering the commonest nearest word would keep about nine in ten of the full list’s corrections on short words, and that on the even stream it would keep far fewer.

The first half of the prediction was too generous and the second half was too mild. The interesting part is a third result the prediction did not ask about: over all query lengths together, the two streams give almost the same answer, and that average is exactly the number that would have been reported.

Four ways to offer from one list #

The checker, the streams and the verdicts are those of the earlier essays. Two pairs of streams are measured. The even pair takes 2,000 misspellings of vocabulary words and 600 of words from a technical text about instrumenting programs, which the vocabulary lacks, each source drawn uniformly from its list and given one or two random edits. The pair drawn by use takes its sources in proportion to their counts in their own corpora, with the same edits. The cap of two answers every misspelt vocabulary word, since none is more than two edits from its source, and the question here is only what the answer contains.

Four ways to fill it are compared. The whole list is every nearest word, which is the earlier verdict. The three commonest are the top three of that list by count in the 19,279-word prose corpus. The commonest is the single top word. The last choice offers one word from the list without reading the counts at all, and it is the baseline that says whether the counts are doing anything. Ties are not broken by drawing. When the source shares the top count with two other words, offering the commonest earns a third of a correction, which is what a random tie-break earns on average. A choice that ignores the counts earns one over the list’s length. Every number below is an expectation over tie-breaks, so no seed for the tie-break can flatter it.

How many words tie at the nearest distance #

Drawn by use, 59% of answered misspellings of three or four letters have more than one nearest word, 16% have six or more, and the list averages 3.5 words. At seven or eight letters 86% have exactly one, and from nine letters up the share passes 95%. The problem the earlier verdict ignored is a short-word problem and nothing else.

The reason is the arithmetic of a small space. Four letters allow 456,976 strings and the vocabulary holds about 360 words of three or four letters. One edit from the already holds four vocabulary words, them, they, then and tie, and two edits from it hold thirty more, among them that, one, this, are and two. The trie that the columns the candidates share turned into shared work finds all of them in a single walk, and the walk cannot say which one the writer meant, because at equal distance distance is no longer evidence. A long word is different. Its neighbourhood within two edits is mostly strings no one has ever written, so a typo of recurrence has one plausible source and the list has nothing to choose between.

The even stream has the longer lists at three or four letters, 4.2 words against 3.5, and the reason matters later. Its short sources are drawn evenly from the vocabulary’s short words, so they are mostly the rarely used ones, such as hood, cuts, tens and met, and a random edit to one of them lands among the common short words as easily as an edit to the does.

Drawn by use, the commonest keeps three quarters #

On the stream drawn by use, offering only the commonest nearest word corrects 63.8% of misspelt words of three or four letters, against 83.0% for the whole list: it keeps 77% of the list’s corrections, not the nine in ten the prediction named. At five or six letters it keeps 88%, and from seven letters up it keeps 96% or more. The counts are certainly doing work. A choice that ignores them corrects 46.3% of the short words, so ranking by use recovers more than half of what blind choice gives up.

The three commonest are the surprise of the plate. They correct 79.7% of short misspellings, 96% of what the whole list corrects, and in practice three words is a list a writer can read at a glance. Most of the list’s value on short words lies in its top three by count, and most of the rest of the list is padding: words such as tie, used once, which sits one edit from the and is almost never meant.

The prediction reasoned that a short source is usually the commonest of its ties. That is true more often than chance and much less often than usually. The prediction’s error lay in imagining the ties as a common word surrounded by rare ones. Among short words the competitors are often common too. A typo of was written wah is one edit from was and from way, used 34 and 33 times, and the count settles that contest by a single occurrence.

Drawn evenly, the counts point the wrong way #

On the even stream the commonest nearest word corrects 37.5% of misspelt words of three or four letters, 48% of what the whole list corrects, and less than the 40.8% a choice that ignores the counts corrects. The same holds at five or six letters, 70.0% against 72.4%, and at every other length the two are within half a point. On the streams every earlier spelling essay measured, ranking by frequency is not merely weak. It is worse than not ranking.

The three commonest suffer the same way: 60.2% of short words against the list’s 78.7%, so a three-word list gives up nearly a quarter of the list’s short corrections where on the other stream it gave up 4%. The prediction expected “far fewer”. What it did not expect was that the counts would be anti-correlated with the right answer, and the next plate shows why.

Where the source stands among its ties #

Among misspellings of three to six letters with more than one nearest word, the source is the commonest of them 63.6% of the time on the stream drawn by use, against 32.6% for a guess, and 26.1% of the time on the even stream, against 32.9%. Ranking by count is close to twice as good as chance on one stream and a fifth worse than chance on the other, on lists of the same length.

The medians explain it. On the even stream the median source among these queries is used three times, and the commonest of its competitors is used eighteen times. Drawing sources uniformly from a vocabulary in which 41% of words occur once means the typical source is rare, and the neighbourhood of any short string is dominated by common short words, because common words are short. So the commonest word near the query is, by construction, more common than the source, and ranking by count pushes the source down. A quarter of the even stream’s sources rank fourth or lower. On the stream drawn by use the median source is used 47 times. It is still outranked by a median competitor used 83 times, which is why the commonest choice keeps three quarters of corrections and not nine tenths, but it is common enough to win most of its contests.

The plate makes the mechanism concrete: a ranking by frequency measures how well the stream’s sources follow frequency, and nothing else. A collection is a construction found the same of compressed indexes: the same characters, arranged two ways, rank structures in opposite orders, and the arrangement is usually not reported. Here both arrangements were built on purpose, and they reverse the ranking’s sign.

Two streams, one average #

The aggregate rows of the two policy plates are the reason this matters beyond spelling. Over all lengths, the commonest nearest word corrects 78.8% of misspellings drawn by use and 78.1% of those drawn evenly, and the whole list 91.1% and 93.9%. Reported as a single number, a one-word checker performs identically on the two streams, and anyone measuring it on the even stream would conclude the counts were a sound tie-break.

The averages agree for opposite reasons. The even stream is mostly long words, since long words outnumber short ones in a vocabulary, and on long words the list is one word and every policy agrees. Its short words, where the counts mislead, are 14% of its queries. The stream drawn by use is 35% short words, because short words are written most, and there the counts help. Each stream’s average is its long words’ easy 95% blended with its short words’ hard case, in proportions set by how the stream was drawn. The two blends happen to land within a point of each other.

That is a property of the measurement, not of spelling. A second try before any feature and a trie fitted to its queries both reported averages over the even stream, the first a learned starting bound and the second a trie pruned to the prefixes queries visit. An average over a stream is a statement about that stream’s mix of easy and hard queries. When the mix moves, the average can stay still while the hard part reverses.

How the first choice fails #

On the stream drawn by use, when the list holds the source, the commonest-word choice loses it to a commoner neighbour 7.7% of the time even when the source is used a hundred times or more, and ties at the top count cost at most 1.4% in any band. Ties are not the problem. Counts in a 19,279-word corpus are distinct enough among the words that matter that a random tie-break almost never decides anything, and the 1.4% in the band of words used once comes from lists of several rare words that all sit at a count of one.

What does the damage is being outranked, and it happens at every level of use. A source used two to four times loses a fifth of its contests, which is the band where a short rare word, such as hop, used three times, sits beside common neighbours. A source used a hundred times still loses one in thirteen. Those losses are pairs of common words that sit one or two edits apart, and one pair dominates them: of the 39 lost corrections of words used a hundred times or more, 15 are typos of that that the checker turns into the. Others include than lost to the or to that, not lost to and, and what lost to that. A frequency prior cannot separate them, since both are common, and only context could. A checker that sees the word before and after has evidence that a checker reading one word in isolation does not, and every essay in this series has read one word in isolation.

The band of words used once is the oddity: 85.1% kept, better than the bands above it. That is selection, not skill. On this stream a word used once is rarely mistyped at all, and the 104 queries in that band are mostly long ones: their mean length is 8.3 letters, and 87 of them have the source alone at its distance, where there is nothing to lose it to.

Reaching past the nearest words #

The first choice only ranks words at the nearest distance. A checker built on the noisy-channel model does something else: it offers the word within reach that maximises the word’s count times the chance of the edits needed to reach it, and that can be a common word two edits away instead of a rare word one edit away. On paper this is strictly more general. It can recover a correction the nearest-word list never held, and nothing in the earlier verdicts could credit that. The transposition teh is two edits from the by this distance and one edit from ten, used nine times, so the nearest-word list offers ten alone, while the channel weighs the’s 2,072 uses at two edits against ten’s nine at one.

At a tenth an edit, the weight the counts only short words carry assumed, the noisy-channel choice corrects 75.2% of the stream drawn by use against the first choice’s 78.8%: it finds 1.9% beyond the nearest words and loses 5.6% the first choice had. Each recovered two-edit typo of a common word is paid for by several one-edit typos of moderately rare words, now displaced by a common word one edit further on. At a hundredth an edit the gains and losses nearly cancel, and the channel choice corrects 79.0%, a fifth of a point above the first choice. Below that it is the first choice, because a weight that small never lets a farther word win.

The weight that works can be read off the streams’ own construction, which is a reason to trust it rather than a fit to the curve. A random edit to a word of four letters produces one of about 234 strings: 130 insertions, four deletions and 100 substitutions. So the chance that a given one-edit typo of the is exactly the query is about one in two hundred, and a second edit divides by roughly two hundred again. The tenth assumed in the earlier essay overstated the chance of reaching any particular string by an edit by a factor of twenty or more. An edit is cheap in the sense that it happens often, but expensive in the sense the channel needs, because the probability of any one outcome of an edit is tiny. At the weight the edit process implies, the noisy channel ranks the nearest words by count and almost never looks further. Real typing would set the weight differently for each kind of edit, which is what a cost built from two properties did for alignment, and a distance that is not a distance is the warning about what unequal weights do to any structure that prunes by distance.

On the even stream the channel finds almost nothing beyond the nearest words at any weight, at most 0.4%, because an evenly drawn source is rarely common enough to win from farther away. Its losses are the same as on the other stream. Reaching further for common words is a bet on the stream following use, the same bet the first choice makes, placed with more money.

What a writer is shown #

On a stream drawn by use and one fifth unfamiliar, a checker that offers one word shows the writer the word they meant for 63.1% of queries, and 69% of the words it offers are right: 51% on queries of three or four letters, 89% at seven or eight, and 95% or more beyond. This is the plate the earlier essays could not draw, because a list that contains the right word does not say what a reader sees. A single word does.

On short words the checker is a coin toss. Of every hundred short queries, 51 are shown the right word, 29 are shown a different vocabulary word, often a common neighbour of the source, and 20 are unfamiliar words given a suggestion they did not need. The cap declines almost none of the short unfamiliar ones, as a checker that stops at two edits found. On long words the same checker is reliable: unfamiliar long words are declined by the cap, and misspelt long words have one nearest word, which is the source.

Two numbers from the earlier essays now look different. The cap’s 91% of corrected vocabulary misspellings, drawn by use, becomes 79% once the checker has to commit to one word. And the frequency decline that removed a ninth of the short false suggestions for one correction in ninety-six acts on the 20% band of this plate, while the 29% band of wrong vocabulary words is untouched by any decision about whether to answer. On short words the larger error was never answering an unfamiliar word. It was answering a familiar one with the wrong word, and that error is invisible to every verdict that counts the source anywhere in a list.

The even stream, run through the same plate, is worse on short words than the coin toss: 30% of short offers are right. Its aggregate is 70%, a point above the stream drawn by use. That is the average of the previous section again, agreeing for opposite reasons.

What the prediction got right, and what it missed #

The closing section of the earlier essay predicted that on the stream drawn by use a first choice by count would recover about nine in ten of the list’s corrections on short words. It recovers 77% on words of three or four letters and 88% at five or six, so the nine in ten holds only once the words reach five letters. The prediction imagined a common source surrounded by rare ties, and short words are surrounded by other common words.

It predicted far fewer on the even stream. The truth is starker: ranking by count is worse there than ignoring the counts, because a uniform source is typically rarer than its commonest neighbour. And it asked whether a one-word checker can be measured on the even streams at all. The answer is that it can be measured, and the measurement is wrong in the most dangerous way. Short words reverse sign while the aggregate stays within a point of the honest stream, so nothing in the headline number warns that the ranking has stopped working.

Three things the measurement assumes #

Isolated words. Every choice here reads one query with no context. The 7.7% of very common sources lost to a commoner neighbour are pairs such as that and the, which no frequency can split and a single word of context nearly always would. Whether a bigram count fixes most of those losses was not measured.

A corpus as the prior. The counts are from the prose the vocabulary came from, so they describe what this corpus writes, not what any writer mistypes. A writer’s own history would be a different prior and a sharper one, and it is the prior a real editor holds.

Expected tie-breaks. Ties are scored by expectation, never drawn. This is fair to every policy and removes the luck of a seed, but it means no single run of a real checker would show these exact shares, only a spread around them. The spread is small where lists are short and wide where the list holds eleven words.

Still open: a list as long as the doubt #

A one-word checker is right 51% of the time on short words, and a three-word list catches 96% of what the whole list catches. Between them sits the obvious checker. It offers one word when the commonest nearest word dominates its competitors and more when it does not, so the list grows only where the counts are close. The ratio of the top count to the second is the natural signal: the against them is twenty-six to one and needs no second word, while was against way is thirty-four to thirty-three and needs both.

The measurement that follows offers the commonest word alone when its count exceeds the next by a factor r, and the top two or three otherwise, and charts corrections against mean list length as r runs from one to a thousand, by length and on both streams. The prediction is that on the stream drawn by use, a list averaging about 1.3 words on short queries recovers nine tenths of what the three commonest recover. On the even stream the ratio should mislead as the ranking did, since a dominant count there more often belongs to the wrong word. The question is whether the right length of a suggestion list is itself a measurement of how much the counts know, and whether a checker can tell from the counts alone when the counts are not enough.