How to implement a spell checker in 21 lines of Python code

Introduction

When you use Google or Baidu search, when entering search content, Google can always provide a very good spelling check. For example, if you enter speling, Google will return immediately. spelling.
The following is a simple but fully functional spelling checker implemented with 21 lines of python code.

Code

import re, collections

def words(text): return re.findall('[a-z]+', text.lower()) 

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model

NWORDS = train(words(file('big.txt').read()))

alphabet = 'abcdefghijklmnopqrstuvwxyz'

def edits1(word):
   splits     = [(word[:i], word[i:]) for i in range(len(word) + 1)]
   deletes    = [a + b[1:] for a, b in splits if b]
   transposes = [a + b[1] + b[0] + b[2:] for a, b in splits if len(b)>1]
   replaces   = [a + c + b[1:] for a, b in splits for c in alphabet if b]
   inserts    = [a + c + b     for a, b 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]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get)

The correct function is the entry point of the program, and incorrectly spelled words passed in will be returned correctly. Such as:

>>> correct("cpoy")
'copy'
>>> correct("engilsh")
'english'
>>> correct("sruprise")
'surprise'

In addition to this code, as part of machine learning, there should definitely be a large amount of sample data, and big.txt is prepared as our sample data.

Principle behind

The above code is implemented based on Bayesian. In fact, the spelling check implemented by Google Baidu is also implemented through Bayesian, but it is definitely more complicated than this.
First of all, let’s briefly introduce the principle behind it. If the reader has understood it before, you can skip this paragraph.
Given a word, we try to select the most likely correct spelling suggestion (the suggestion may also be the entered word). Sometimes it is unclear (for example, should lates be corrected to late or latest?), and we use probability to decide which one to use as a suggestion. We find the most likely spelling suggestion c from all possible correct spellings related to the original word w:

argmaxc  P(c|w)

Through Bayes’ theorem, the above formula can be transformed into

argmaxc P(w|c) P(c) / P(w)

below Let me introduce the meaning of the above formula:

1. P(c|w) represents the probability that you originally wanted to input word c when you input word w.

2. P(w|c) represents the probability that the user wants to enter word c but enters w. This can be considered as given.

3. P(c) represents the probability that word c appears in the sample data

4. P(w) represents the occurrence of word w in the sample number The probability of
   can be determined that P(w) has the same probability for all possible words c, so the above formula can be converted into

argmaxc P(w|c) P(c)

All our codes are based on this The formula comes from the following analysis of the specific code implementation

Code analysis

Use the words() function to extract words in big.txt

def words(text): return re.findall('[a-z]+', text.lower())

re.findall('[a-z] +' uses the python regular expression module to extract all words that meet the condition of '[a-z]+', that is, words composed of letters (regular expressions will not be introduced in detail here, interested students can see regular expressions. Introduction. text.lower() converts text into lowercase letters, that is, "the" and "The" are both defined as the same word.

Use the train() function to calculate the number of occurrences of each word. Train a suitable model

def train(features):
    model = collections.defaultdict(lambda: 1)
    for f in features:
        model[f] += 1
    return model
NWORDS = train(words(file('big.txt').read()))

so that NWORDS[w] represents the number of times word w appears in the sample. What should we do if a word does not appear in our sample? The number of times is set to 1 by default, which is implemented here through the collections module and lambda expression. collections.defaultdict() creates a default dictionary, and lambda: 1 sets each value in this dictionary to 1 by default (lambda expression. You can see the introduction to lambda

Now that we have finished processing P(c) in the formulaargmaxc P(w|c) P(c), we will next process P(w|c). The probability of entering word c but incorrectly entering word w is measured by the "edit distance" - the number of edits required to change one word into another. An edit may be a deletion, a swap (two adjacent words letters), one insertion, one modification. The following function returns a set of all possible words w that can be obtained by editing c once:

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

Related papers show that 80-95% of spelling errors are related to the intended spelling. The words have only one edit distance. If you feel that one edit is not enough, let’s do it again

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

At the same time, there may also be words with an edit distance of 0 times that are spelled correctly:

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

We assume that the probability of 1 edit distance is much greater than 2 times, and 0 times is much greater than 1 edit distance. Next, use the correct function to first select the word with the smallest edit distance, and its corresponding P(w|c) will be larger, as Candidate words, and then select the word with the largest P(c) as the spelling suggestion

def correct(word):
    candidates = known([word]) or known(edits1(word)) or known_edits2(word) or [word]
    return max(candidates, key=NWORDS.get

The above is the detailed content of How to implement a spell checker in 21 lines of Python code. For more information, please follow other related articles on the PHP Chinese website!