怎样写一个拼写检查器一

取自 自然语言处理百科

上个星期, 我的两个朋友 Dean 和 Bill 分别告诉我说他们对 Google 的快速高质量的拼写检查工具感到惊奇. 比如说在搜索的时候键入 [speling], 在不到 0.1 秒的时间内, Google 会返回: 你要找的是不是 [spelling]. (Yahoo! 和微软也有类似的功能). 让我感到有点奇怪的是我原想 Dean 和 Bill 这两个很牛的工程师和数学家应该对于使用统计语言模型构建拼写检查器有职业的敏感. 但是他们似乎没有这个想法. 我后来想了想, 他们的确没什么理由很熟悉统计语言模型. 不是他们的知识有问题, 而是我预想的本来就是不对的.

我觉得, 如果对这方面的工作做个解释, 他们和其他人肯定会受益. 然而像Google 的那样工业强度的拼写检查器的全部细节只会让人感到迷惑而不是受到启迪. 前几天我乘飞机回家的时候, 顺便写了几十行程序, 作为一个玩具性质的拼写检查器. 这个拼写检查器大约1秒能处理10多个单词, 并且达到 80% -90% 的准确率. 下面就是我的代码, 用Python 2.5 写成, 一共21 行, 是一个功能完备的拼写检查器.

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):
   n = len(word)
   return set([word[0:i]+word[i+1:] for i in range(n)] +                     # deletion
              [word[0:i]+word[i+1]+word[i]+word[i+2:] for i in range(n-1)] + # transposition
              [word[0:i]+c+word[i+1:] for i in range(n) for c in alphabet] + # alteration
              [word[0:i]+c+word[i:] for i in range(n+1) for c in alphabet])  # insertion
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=lambda w: NWORDS[w])

这段代码定义了一个函数叫 correct, 它以一个单词作为输入参数, 返回最可能的拼写建议结果. 比如说:

>>> correct('speling')
'spelling'
>>> correct('korrecter')
'corrector'

转自Eric You XU翻译：http://blog.youxu.info/spell-correct.html

原文作者Peter Norvig，原始链接：http://norvig.com/spell-correct.html