Was browsing Peter Norvig home page the other day and found this interesting article about how to write a spelling corrector.

In his post he explains how to use statistical language processing to implement a small toy spelling corrector in python that achieves 80 or 90% accuracy at a processing speed of at least 10 words per second. It’s a good read and a good starting point if you are interested in language processing. While I was reading I hacked together a Boo version of the algorithm if someone is interested.

import System
import System.IO
import System.Collections.Generic
import System.Text.RegularExpressions
import Boo.Lang.Useful.Collections

def words(text as string):
    return m.Value for m as Match in  /[a-z]+/.Matches(text.ToLower())

def train(features):
    model = Dictionary[of string, int]()
    for f in features:
        if model.ContainsKey(f):
            model[f] += 1
        else:
            model[f] = 1
    return model

NWORDS = train(words(File.ReadAllText('big.txt')))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word as string):
    splits      = [(word[:i], word[i:]) for i in range(word.Length + 1)]
    deletes     = [a + b[1:] for a as string, b as string in splits if b]
    transposes  = [a + b[1] + b[0] + b[2:] for a as string, b as string in splits if b.Length > 1]
    replaces    = [a + c + b[1:]    for a as string, b as string in splits for c in alphabet if b]
    inserts     = [a + c + b        for a as string, b as string in splits for c in alphabet]
    return Set(deletes + transposes + replaces + inserts)

def known_edits2(word):
    return Set(e2 for e1 in edits1(word) for e2 in edits1(e1) if e2 in NWORDS)

def known(words):
    return Set(w for w in words if w in NWORDS)    

def correct(word):
    candidates = known([word]).Union(known(edits1(word))).Union(known_edits2(word)).Union(Set([word]))
    for candidate in candidates:
        if NWORDS.ContainsKey(candidate):
            yield (NWORDS[candidate], candidate)
        else:
            yield (1, candidate)

test = correct('ther')

for score, candidate in test:
    print "Score: " + score + " Candidate: " + candidate

print "Press any key to continue . . . "
Console.ReadKey(true)