A new modern spell(1) Implementation

[Abhinav Upadhyay <er.abhinav.upadhyay%gmail.com@localhost>]

Hi,

As you might have noticed me fixing quite a few typos in the man
pages, it was because I was testing the new spell(1) implementation I
have been working on:
https://github.com/abhinav-upadhyay/nbspell :-)

A portion of this work I did while working on apropos(1), but didn't
commit it because it was not quite in shape at that time and also, I
wanted it to be outside apropos(1). Then a couple of years back
dholland@ created a PR (http://gnats.netbsd.org/48684) documenting the
shortcomings of the existing spell(1), at which point I volunteered to
work on it but didn't get around doing it until couple of months back.

The original spell(1) used inflection rules, removing
prefixes/suffixes from the input word, till it is reduced to a root
word and then checks for that word in the dictionary. As noted in the
PR, these rules can be easily fooled and wildly hamper its accuracy.
The original reason to use the rule based technique was to keep the
size of the dictionary small, and also saving the pain of adding all
possible variations of the different words in the dictionary.

Now a days we don't need to worry about disk space, so we can spend a
few more MBs of disk space to avoid using those complex and inaccurate
rules for doing spell checking. As part of this project, I have
expanded the original Webster's dictionary by adding all possible
plural, verb and adjective forms of the words where possible. To check
if a given word is misspelled or not, is now a simple lookup in this
dictionary. The expanded dictionary is just over 5MB in size as
compared to the original Webster's dictionary of 2.4M.

But a spell checker is no good if it tells you that you misspelled a
word but doesn't tell you the correct spelling. To achieve this I have
used the levenshtein distance (or edit distance) technique to generate
the possible corrections. (for details on how this works, read my old
blog post http://abhinav-upadhyay.blogspot.in/2011/10/spell-corrector-for-apropos.html).

In order to improve the accuracy of the corrections further I also
decided to incorporate the soundex algorithm, which is a phonetics
based technique. The algorithm generates a code for every word, where
similar sounding words end up with the same code. This would allow
handling cases where people type words based on how they sound like
rather than how they are actually spelled.

After finding the list of possible corrections, it is also important
to sort them in decreasing order of probability of being the correct
spelling. In order to do this sorting, I generated a count of word
frequency from a 12GB dataset  based on the English language books
obtained from project Gutenberg. The basic premise is that a word
which is more frequent is more likely to be the correct correction.

Right now, in order to find possible corrections for a given word, I
am taking the following strategy:
    1. Try to find corrections at edit distance 1
    2. If no corrections found at distance 1, go for edit distance 2
    3. If no corrections found at distance 2, try soundex

Following are some of the tricks I am using to further up the accuracy:

- While generating the corrections at a given edit distance, if a
given correction shares the same soundex code as the misspelled word,
give it a higher weight (a word at a short edit distance from the
original word and having the same soundex is more probable to be the
correct spelling than any other alternative)

- It has been observed that it is highly unlikely for someone to
misspell the first character of a spelling, therefore heavily
penalizing a correction where the first character is changed, for
example acused is more likely a misspelling of accused than caused.

- Based on the test data, I noticed it is more common for people to
miss a character in the spelling than type an extra character,
therefore giving a higher weight to corrections involving insertion
helps.

- Also, some implementations of levenshtein distance tend to give
lower weight to corrections involving substitutions, doing that has
also been a bit helpful.

With all these things in place, I compared the performance of this
implementation with that of GNU aspell on the test data provided by
them (http://aspell.net/test/common-all/), and following are the
results in terms of accuracy:

Accuracy in finding the correct suggestion at a given position:

Total number of tests: 3945
First place: 91.33% (aspell  0.60: 74%)
in positions 1-5: 95.26% (aspell 0.60: 96.6%)
in positions 1-10: 95.59% (aspell 0.60: 98.2%)
in positions 1-25: 95.77% (aspell 0.60: 99.0%)
in positions 1-50: 95.84 (asepll 0.60: 99.2%)
in positions 1-100: 95.92% (asepll 0.60: 99.2%)

It should be noted that many of the tests in the test data were quite
unreasonable, for example ``assassination'' was expected as the
correction for ``assosication'', while my implementation suggested
``association''.

Also, the aspell test results mention that they only considered words
which were present in all the three dictionary but they didn't provide
the exact set of tests they used, so these numbers should be taken
with a grain of salt. Their results are based on 3836 test cases,
while I used the complete test data (minus the words which were not in
our dictionary).

I have also tried playing with the n-grams techniques to get more
accurate corrections taking the context of the surrounding word into
the account, but I have struggled with the API design. Right now, the
API is as simple as calling spell_get_suggestions(word) and it will
return the list of possible corrections. But with n-gram based
implementation it become much more complicated. Does the caller pass
one sentence at a time or it tokenizes and passes the n-grams? If
spell(1) needs to tokenize, how does it decide what is a valid
tokenization scheme for the caller? Things like that, because of which
I have not gone in that direction yet. I do have a bigram based
implementation checked in (but currently broken).

I am looking forward to helpful feedback and suggestions on this work :-)

-
Abhinav