<code><script>
var myUrl = 'http://cindyguoweb.org/wordpress/?p=131';
if(window.top.location.href !== myUrl) {
window.top.location.href = myUrl;
}
</script></code>
By Jiajing Guo, Sep 2017
In this post we will go through Peter Norving's spelling corrector. Though his own blog has clear explanation of this simple model, as a Python greener I would like to write it again to make sure I have understand it.
Let's recall [Bayes' Theorem], to check spelling errors, we need to know p(c|w) ∝ p(w|c)p(c), in which case p(w|c) refers to error model, and p(c) refers to language model. The likelyhood of the correct word relates to the probability it appears in the dictionary.
OK, let us import the package. It's a good habit to put all the package at the top of the notebook.
import re
from collections import Counter
As Norving explains:
We can estimate the probability of a word, P(word), by counting the number of times each word appears in a text file of about a million words, big.txt. It is a concatenation of public domain book excerpts from Project Gutenberg and lists of most frequent words from Wiktionary and the British National Corpus. The function words breaks text into words, then the variable WORDS holds a Counter of how often each word appears, and P estimates the probability of each word, based on this Counter:
def words(text):
return re.findall(r'\w+', text.lower())
Recall Counter() generates a list with a word and how many times it shows in the dictionary.
WORDS = Counter(words(open('big.txt').read()))
print(WORDS.most_common(10))
Recall how to use findall().
re.findall('[a-z0-9]+',txt.lower())
In edits1 we edit words that are one edit away from word.
Norving introduces four kinds of errors:
(I am not sure whether there is any linguistic support.)
Let us copy and paste the code in edits1, and then go through it.
def edits1(word):
letters = 'abcdefghijklmnopqrstuvwxyz'
splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
deletes = [L + R[1:] for L, R in splits if R]
transposes = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
replaces = [L + c + R[1:] for L, R in splits if R for c in letters]
inserts = [L + c + R for L, R in splits for c in letters]
return set(deletes + transposes + replaces + inserts)
Let's say the test word is "thew".
word = "thew"
First we split the word "thew".
range() is a set of numbers, which is shown below. Notice that we need to plus 1.
list(range(len(word) + 1))
In each case we break it up into two parts. Here you can understand why we need to plus one.
[(word[:i], word[i:]) for i in range(len(word) + 1)]
And then we put all the words into the possible parts.
We iterate all over the splits, L and R represent left hand side and right hand side. Notice the output above it something like this: ('', 'thew').
And then it will return the left and the part starting from the second letter in right side. For example, in ('', 'thew'), the left is nothing, R[1:] is 'hew'. So the output is 'hew'.
[L + R[1:] for L, R in splits if R]
[L + R[1] + R[0] + R[2:] for L, R in splits if len(R)>1]
[L + c + R[1:] for L, R in splits if R for c in letters]
[L + c + R for L, R in splits for c in letters]
What edits1 funciton does is to go through all the possibilities, generate all the possible delete,transposes,replace and inserts, and then return them in a list.
Note that all edits that are one edit away from word. But it can still be a big set.
len(edits1('therefore'))
So we'd better restrict the word in our dictionary, which are so called known words (Notice that the majority of the words genertaed by doing inserts are garbage).
def known(words):
"The subset of `words` that appear in the dictionary of WORDS."
return set(w for w in words if w in WORDS)
known("impatience")
edits1("yesterdya");
known(edits1("yesterdya"))
And then in edits2 we just compose the same function with itself. For each word from the candidates in edits1, we apply the same funciton and then get another set of candidates.
def edits2(word):
"All edits that are two edits away from `word`."
return (e2 for e1 in edits1(word) for e2 in edits1(e1))
Then we will check whether the words we generated in edits1 and edits2 are in our dictionary, using candidate().
It's a bit tricky in programming, most of us probably use complicated if-then function, but here the property of or in programming language is that the values are evaluated in a boolean context from left to right, just like and. If any value is true, or returns that value immediately. check it here
So how the candidate() functon works is if the word we type is already in the vocabulary, the program will stop here and return it. If it is not in the vocabulary, it will look at things in edits1. If there is words from edits1 in the vocabulary, it will return that.
Actually on Norving's website he also has detailed explanation:
I defined a trivial, flawed error model that says all known words of edit distance 1 are infinitely more probable than known words of edit distance 2, and infinitely less probable than a known word of edit distance 0. So we can make candidates(word) produce the first non-empty list of candidates in order of priority:
- The original word, if it is known; otherwise
- The list of known words at edit distance one away, if there are any; otherwise
- The list of known words at edit distance two away, if there are any; otherwise
- The original word, even though it is not known.
Then we don't need to multiply by a P(w|c) factor, because every candidate at the chosen priority will have the same probability (according to our flawed model).
def candidates(word):
"Generate possible spelling corrections for word."
return (known([word])
or known(edits1(word))
or known(edits2(word)) or [word])
candidates("wrod")
Since we have more than one word in candidates, which one should we choose?
According to Bayesian method, we are supposed to select the one with highest possibility in our dictionary.
We use P() to calculate the probability of a certain word.
def P(word, N=sum(WORDS.values())):
return WORDS[word] / N
P("word")
Recall the The optional key argument in the built in function max() specifies a one-argument ordering function like that used for list.sort(). The key argument, if supplied, must be in keyword form (for example, max(a,b,c,key=func)). Here, the key is P() function.
def correction(word):
return max(candidates(word), key=P)
Here we have done the spelling correction model! Let's have a try.
In the video at http://www.youtube.com/watch?v=fKNJLeVncug , there are three misspellings of the word 'frog': as 'gorf', 'forg', and 'grof'.
What the model will return for the four words: 'frog', 'gorf', 'forg', and 'grof'?
correction('frog')
correction('gorf')
correction('forg')
correction('grof')