The counts only short words carry

A checker that stops at two edits gave a spelling checker a cap. It searches a trie of 2,424 vocabulary words for the words nearest a misspelt query, and it declines to answer once the nearest word is more than two edits away. Every misspelling in its test streams is one or two edits from its source, so the cap keeps every correction the checker could make. It does not stop false suggestions: on short words, two edits is most of the word, and a typo of a word the vocabulary lacks lands within two edits of something on the list as easily as a typo of a word it has. The triples a typo writes then tried the query’s letters as a second test and found they mostly count the typing. One edit writes about one unseen letter-triple into any word, familiar or not, and the test gave up twenty-two corrections for every false suggestion it removed.

That page’s closing section named the one piece of evidence about a writer’s intention a checker already holds: how often each vocabulary word is used. A two-edit typo of the is far more likely than a two-edit typo of theorem, and a query whose nearest words are all rare is more likely to be a word the vocabulary lacks than a slip on one of those rare words. It proposed scoring an answer by its nearest words’ combined frequency, weighed against the chance of the edits needed to reach them, and predicted the test would do on short words what the triples could not, removing most false suggestions to unfamiliar words of three and four letters while keeping most corrections.

The prediction turned out to depend on a property of the streams that none of the earlier pages had needed to state. The counts are only evidence if the typos follow them.

A score from the corpus the words came from #

The vocabulary is every word of three letters or more in a frozen corpus of English prose about algorithms, 19,279 uses of 2,424 distinct words. Each word’s count in that corpus is the frequency the test reads. A query the cap of two answers has a list of nearest words, all at one distance $d$, and its score is

$$s = \Big(\sum_{w \in \text{nearest}} c(w)\Big)\,\varepsilon^{\,d},$$

where $c(w)$ is the word’s count and $\varepsilon$ is the weight of one edit, a tenth unless stated. This is the shape of the noisy-channel reasoning behind every practical spelling corrector: the chance that a writer meant $w$ and typed the query is the chance of meaning $w$, which is its frequency, times the chance of the typing, which falls by some factor for each edit. The checker declines when $s$ is under a threshold $\tau$. A threshold of nought is the cap alone, and each larger threshold can only remove answers, never add one. The trie, whose shared prefixes the columns the candidates share turned into shared work, the walks at one edit then two, each abandoned as the bound the search finds for itself abandons a table, and the verdicts are the earlier pages’: a misspelt vocabulary word is corrected when its source is among the nearest words, and an answer to an unfamiliar word is false unless it shares the word’s stem and differs only in an ending.

Half the vocabulary is used once or twice #

41% of the vocabulary’s words occur once in the corpus, and the hundred commonest take 51% of all uses. The counts are as skewed as word counts always are. The occurs 2,072 times, and 828, table 96; theorem five times and hop three. The skew runs along word length. Words of three or four letters are 15% of the list and 47% of the uses, with a median count of five. Words of nine letters or more are a quarter of the list, a tenth of the uses, and their median count is one.

That shape decides what a frequency can say about each kind of word before any test is run. A count of one is the floor, since every listed word occurs at least once, and it carries no information: half of the long words sit there, so a score built from counts cannot rank them against one another. A count of 2,072 against a count of three does carry information, and those differences live almost entirely among short words. The test was proposed for short words, and short words are the only place the counts have anything in them.

On the checker’s own streams the false suggestions are the common ones #

On the streams every earlier page measured, the median false suggestion scores 0.31 and the median correction 0.10. The false suggestions go to commoner words. The test was built on the opposite assumption, and there is nothing wrong with the test. The streams are the reason.

Those streams were made by drawing a source word uniformly from a list and applying one or two random edits: 2,000 misspellings of vocabulary words and 600 of words from another technical text, about instrumenting programs, that the vocabulary does not contain. Uniform drawing means theorem is mistyped exactly as often as the. Since 41% of the vocabulary is used once, a typical correction’s source is a word used once or twice, alone at its distance, and its score is one or two occurrences times a tenth or a hundredth. Only 4% of the sources are among the hundred commonest words.

A false suggestion has no source on the list. What it has is a query that happens to lie close to the list, and the close part of the list is the short common words. Pos, mistyped as phs, is two edits from sixteen vocabulary words including the, has, this and was. Their counts add up to a score of 26. The nearest-word list for a false suggestion has five words on average against two for a correction, and every one of them contributes its count. A score that sums the evidence for every nearest word rewards exactly the ambiguity a false suggestion is made of.

Run as a test on these streams, frequency is worse than the triples were at first sight and about as bad on the exchange. A threshold of 0.5 keeps 25% of the corrections, from 94%, and still gives 14.5% of unfamiliar words a false suggestion, from 31.7%. On a stream one fifth unfamiliar, it gives up sixteen corrections for each false suggestion it removes.

A stream that mistypes words as often as it uses them #

A writer does not choose which word to mistype uniformly from a dictionary. The words most often mistyped are the words most often written, so a stream of real misspellings draws its sources in proportion to use. That is a second pair of streams, made with the same edit process and the same verdicts. The 2,000 vocabulary misspellings draw their sources by their prose counts. The 600 unfamiliar ones draw theirs by their counts in the instrumentation text, where const occurs dozens of times and klass, opts and push recur.

Drawn by use, a correction’s nearest words score a median of 2.19 and a false suggestion’s 0.73, and a threshold of 0.5 keeps 67% of the corrections while taking the false suggestions from 45% of unfamiliar words to 25%. The order of the two populations has turned over. Half of the vocabulary misspellings are now of the hundred commonest words, their mean length is 5.3 letters against 7.1, and 45% of the queries are four letters or fewer against 16%. A correction is now usually a short common word, and the test that rewards common words keeps it.

The new stream also makes the problem harder, which the curve’s starting point shows. The cap alone gives 45% of unfamiliar words a false suggestion here against 32% on the even stream, because the unfamiliar words people actually write in that text are short: const, opts, alg, pos. Each of those has a vocabulary word within two edits. Const typed as cont lands one edit from cost, count and cent, and the checker confidently offers all three. The vocabulary misspellings, being shorter too, are slightly harder to correct: 91% have their source among the nearest words, against 94%.

On the exchange that a stream one fifth unfamiliar sets, the test at 0.5 now gives up 4.9 corrections for each false suggestion removed, and between 3.0 and 6.4 across every threshold tried. The prediction’s direction was right. Its size was not, and its location was not either, which the next plate shows.

Where the counts are large enough to mean something #

At three or four letters a threshold of one loses 6% of the corrections and takes false suggestions from 88% of unfamiliar words to 58%; at seven or eight it loses 72% of the corrections to remove false suggestions from 13% of them. The test works where the prediction said it would and nowhere else, and the reason is the counts plate. A misspelt short word’s source is usually common, and its score clears any threshold here. A misspelt long word’s source has a median count of one or two, and the score of one occurrence two edits away is a hundredth. No threshold that removes a false suggestion can keep it.

The long words are also where the test has nothing to do. The cap declines unfamiliar long words by itself, because such words lie far from everything, and on queries of eleven letters or more it gave none of them a false suggestion. Every correction the frequency test declines there is pure loss. A test applied to every query is mostly a test on the words it cannot judge.

That suggests the obvious restriction: apply the counts only where they mean something. Declining under 0.5 only on queries of four letters or fewer keeps 90.1% of the corrections, from 91.1%, and takes false suggestions from 44.5% of unfamiliar words to 39.3%. It gives up 0.74 corrections for each false suggestion removed. Raising the threshold there to one gives up 1.46; extending the rule to words of six letters at a threshold of one gives up 2.65.

The weight of an edit #

The weight given to an edit decides what kind of test this is. Weighted one, an edit costs nothing and the score is the nearest words’ combined count. Since every vocabulary word is used at least once, no threshold of one or less declines anything, and the curve does not leave its starting point until the threshold reaches the counts of moderately common words. Weighted a hundredth, a word one edit away needs a count of two to survive a threshold of 0.02, and a word two edits away needs two hundred. That is a cap of one edit with an exception for very common words, and it sits right beside a plain cap of one edit, which corrects 57% of misspelt vocabulary words and gives 12% of unfamiliar words a false suggestion.

The plain cap of one is the comparison the frequency test has to beat, and on the stream drawn by use it trades at 4.2 corrections for each false suggestion removed. The tenth-weighted test at 0.5 trades at 4.9. Applied to every query, the counts do slightly worse than the cheapest test there is, which reads no counts at all.

The weight was set at a tenth by assumption. The streams themselves cannot set it, because they split their misspellings evenly between one edit and two, so the share of two-edit typos is a property of the stream’s construction rather than of typing. A real error model would fit the weight from a corpus of real misspellings, and it would fit a different weight for each kind of edit, which is the subject of a cost built from two properties carried over from alignment to typing. Unequal weights have a price of their own: a distance that is not a distance found that a stated substitution matrix can break the triangle inequality, and with it every structure that prunes candidates by distance.

Every test at one price #

Of the seven policies on the plate, one removes more false suggestions than it costs corrections: frequency, applied only to words of four letters or fewer. It is also the smallest intervention. Of the 267 false suggestions the cap left on the stream drawn by use it removes 31, about a ninth, and of the 1,822 corrections it gives up 19, one in ninety-six. Every other policy pays more than one correction for each false suggestion, and the triples on the even stream pay twenty-two.

Two things moved those numbers, and only one of them was the test. The triples at two pay 10.4 on the stream drawn by use, half what they paid on the even one. Nothing about the triples changed. The stream did, and the false suggestions it makes are to short unfamiliar words, where any test that declines short queries removes a larger share of false suggestions for each correction lost. A change of stream halved the price of a test that reads no frequencies at all. That puts every rate on the earlier spelling pages in a particular light. Each was measured on misspellings drawn evenly from the list, a stream that over-represents long rare words and under-represents the short common ones that real misspellings are mostly of. A collection is a construction made that point about benchmarks of compressed indexes: the same characters arranged two ways give different answers about which structure to build, and which arrangement was used is usually not recorded. The streams here were recorded, and the arrangement turned out to decide the answer.

The second thing was the restriction to short words, and that is the test’s own contribution. A frequency is evidence where it varies, and it varies among short words. Asked of a long word it says rare almost every time, which tells the checker nothing it could act on.

What the prediction got right, and what it needed #

The closing section of the triples page predicted the frequency test would remove most false suggestions to unfamiliar words of three and four letters while keeping most corrections. On the stream drawn by use, a threshold of one on short words keeps 92% of their corrections and removes a third of their false suggestions, from 88% to 58%. A threshold of five removes two thirds and keeps 65%. “Most” was not reached at any threshold that kept most corrections. The direction was right and the size was half the claim.

What the prediction did not say, and could not have, was that it depended on the stream. On the streams every earlier spelling page used, the test runs backwards: the false suggestions are the common words, because uniform sources are rare and an unfamiliar short query lies near many common words at once. The section reasoned as a writer does — the is mistyped more often than theorem — and the streams had not been built by that reasoning. A second try before any feature and a trie fitted to its queries both learned from these same streams, the first a starting bound and the second which prefixes queries visit. A stream drawn by use would move both: its queries are shorter, so their walks are cheaper, and they cluster on the prefixes of common words, which is the part of the trie a fitted structure would keep. Neither was re-measured here.

The section’s last question was whether a vocabulary’s own word counts are enough to tell a slip from a word the writer meant. They are enough on short words, barely, and only if the slips follow the counts. On long words the counts are all one and the question is not answered by frequency at all. There the cap already does the job, because a long unfamiliar word is far from everything, and the honest checker for long words is the cap alone.

Three assumptions the counts rest on #

A corpus of 19,279 words. The counts come from the same text the vocabulary was taken from, so every word occurs at least once and 41% occur exactly once. A corpus a hundred times larger would separate the long words — some would occur five hundred times and some twice — and the test might then have something to say about them. It would also make the vocabulary larger, which puts more words within two edits of every unfamiliar query. Neither effect was measured.

Sums over ties. The score adds the counts of every nearest word, which is the right noisy-channel quantity for the question “did the writer mean any vocabulary word?” and the reason false suggestions with sixteen tied neighbours score well. A score from the single commonest nearest word, or the mean, would answer a different question. Only the sum was run.

Typing as random edits. Both pairs of streams apply insertions, deletions and substitutions at random positions with random letters. Real errors favour adjacent keys, transpositions and doubled letters, and they are rarer in short words than random edits make them, since a short word is typed quickly and checked at a glance. The stream drawn by use corrects which words are mistyped; it does not correct how.

Still open: one suggestion, chosen by use #

Every verdict in the spelling essays so far counts a correction when the source is anywhere among the nearest words. For a long word that is usually one word. For a short one it is often a dozen: cont is one edit from cost, count and cent, and a typo of the two edits away can be tied with forty words. A checker that lists forty candidates has not corrected anything, and the counts that only modestly help decide whether to answer may help much more in deciding which single word to offer.

The measurement that follows ranks each answer’s nearest words by their counts, offers the commonest, and counts a correction only when that one word is the source. It does so on both pairs of streams and by length, and compares a first choice by count with a first choice made at random among the ties and with a list of the top three. The prediction is that on the stream drawn by use a first choice by count recovers about nine in ten of the corrections the full list makes on short words, since a short source is usually the commonest of its ties. On the even stream it should recover far fewer, because a uniformly drawn short source is as likely to be a rare word tied with common ones. The question is whether frequency’s real job in a checker is the ranking rather than the refusal, and whether a checker that offers one word can be measured on the evenly drawn streams the earlier spelling essays used at all.