转载自AI Studio 项目链接：https://aistudio.baidu.com/aistudio/projectdetail/3747520?channelType=0&channel=0
📖 0 项目背景
拼写纠错是指在进行单词输入时，计算机自动识别并纠正错误的技术。

在谷歌网页中，成熟的纠错技术可以在用户输入单词speling时，Google会自动返回spelling的搜索结果。在百度搜索中，类似的纠错技术也得到了成功的应用。

这一技术背后是计算机对大量数据的统计，对可能存在的错误拼写，按概率自动给出正确的词汇列表，供用户进行修正。

工业级拼写校正器的全部细节非常复杂，但我们可以通过一个简单纠错模型的实现，来对纠错过程的学习和理解。

本项目将从零基础为大家讲解一个简单的贝叶斯纠错模型，该模型能以每秒至少 10 个单词的处理速度达到 80% 或 90% 的接错准确率。

🥦 1 项目功能
如果有以下需求，该项目可能对您有用：

零基础但希望了解一个纠错模型的工作原理

希望使用python语言学习并完成简单的纠错模型

希望能学习贝叶斯概率及其应用的相关知识

💡 2 数据集介绍
本项目测试数据来自：

Birkbeck拼写错误语料库.
birkbeck文件包含 6,136 个单词的 36,133 个拼写错误 。它是从伯克贝克拼写错误语料库的母语部分（英国或美国作家）中提取的错误的合并，该语料库是从各种来源收集的拼写错误文件的集合，可作为单独的文件以及牛津文本档案中的详细文档提供. 它包括拼写测试的结果和自由写作的错误，主要来自学童、大学生或成人识字学生。其中大部分最初是手写的。

每个正确的单词前面都有一个美元符号，后面是它的拼写错误，每个都在一行，没有重复。（一个拼写错误可能在语料库中出现不止一次，但仅作为不同单词的拼写错误。）如果拼写或拼写错误包含空格，则替换为下划线（a_lot，Christ_mas）。虽然大多数拼写错误都是非单词，但也有一些真实单词错误，例如“admitted”的“省略”。

这个语料库的用户应该记住，它包括幼儿和极差的拼写者的错误，他们接受了超出他们能力范围的拼写测试，因此一些拼写错误与他们的目标有很大的不同；例如，单个字母“o”作为单词“accordingly”的拼写错误出现。

维基百科
维基百科文件包含 1,922 个单词的 2,455 个拼写错误。另外，我将“rigeur”作为正确的拼写改为“de_rigeur”，将“orignal”作为正确的拼写改为“Orignal”（安大略省的一个地方），并删除了“vigeur”作为正确的拼写。

请注意，单个拼写错误可能会出现多个正确单词的拼写错误；例如，“buring”会出现“burin”、“burning”、“burying”和“during”的拼写错误。

本项目训练数据(big.txt)来自：

Project Gutenberg的公共领域书籍摘录以及来自维基词典和英国国家语料库的最常用词列表的拼接.
本项目对国内外相关文章资料进行整理，对其中的错误进行修改，并加入个人的理解。

[1]. https://blog.csdn.net/suixinsuiyuan33/article/details/69215082
[2]. https://norvig.com/spell-correct.html
⚙️ 3 纠错实例
函数correction(word) 返回一个可能的拼写更正：
In [ ]
import re
from collections import Counter

def words(text): return re.findall(r’\w+', text.lower())

WORDS = Counter(words(open(‘work/big.txt’).read()))

def P(word, N=sum(WORDS.values())):
“Probability of word.”
return WORDS[word] / N

def correction(word):
“Most probable spelling correction for word.”
return max(candidates(word), key=P)

def candidates(word):
“Generate possible spelling corrections for word.”
return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])

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)

def edits1(word):
“All edits that are one edit away from 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®>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)

def edits2(word):
“All edits that are two edits away from word.”
return (e2 for e1 in edits1(word) for e2 in edits1(e1))
In [ ]
correction(‘speling’)
‘spelling’
In [ ]
correction(‘korrectud’)
‘corrected’
📦 4 贝叶斯概论模型介绍
4.1 贝叶斯概率简介
贝叶斯概率（Bayesian Probability）是由贝叶斯理论所提供的一种对概率的解释，它采用将概率定义为某人对一个命题信任的程度的概念。

其数学定义如下：

P(A∣B)=P(B∣A)×P(A)P(B)P(A|B)=\frac{P(B|A) \times P(A)}{P(B)}P(A∣B)=
P(B)
P(B∣A)×P(A)
​

其中AAA,BBB为研究的两个事件，并且P(B)P(B)P(B)的值不等于0

注意：

P(A∣B)P(A|B)P(A∣B)是条件概率：鉴于发生事件BBB的情况下，事件AAA的发生概率。也称为给定BBB的后验概率AAA。

P(B∣A)P(B|A)P(B∣A)也是条件概率：在发生事件AAA后事件BBB的发生概率。

P(A)P(A)P(A)和P(B)P(B)P(B)是观察到事件AAA和事件BBB的发生概率。被称为边际概率或先验概率。

事件AAA和事件BBB是不同的事件

进一步证明可参考：Bayes_theorem

4.2 贝叶斯概率和纠错问题
下面来讨论下如何使用概率来进行纠错。

当输入一个单词时，我们希望选择和它拼写最相似的单词. (如果这个单词本身拼写就是正确的, 那么最相近的就是它自己)。

但在遇到多个相似单词时，困难是：如何进行选择？

比如输入的单词lates，调用编写完成的correction函数可以将其更正为late，latest，lattes…

我们将使用基于概率论的方法对其进行选择，即在给定原始单词WWW的情况下，从所有可能的候选矫正中找到正确单词CCC，以最大化CCC在给定原始单词WWW下的条件概率：

argmaxc∈candidatesP(C∣W)argmax_{c\in candidates}P(C|W)argmax
c∈candidates
​
P(C∣W)

由贝叶斯公式，改式可化为

argmaxc∈candidatesP(W∣C)×P©P(W)argmax_{c\in candidates} \frac{P(W|C)\times P©}{P(W)}argmax
c∈candidates
​

P(W)
P(W∣C)×P©
​

由于输入的原始单词的概率P(W)P(W)P(W)对所有的候选矫正来说概率是相同的，因此在比较概率时，我们可以将其忽略，即：

argmaxc∈candidatesP(W∣C)×P©argmax_{c\in candidates} {P(W|C)\times P©}argmax
c∈candidates
​
P(W∣C)×P©

该表达式从左到右有四个部分：

选择机制：argmaxargmaxargmax

我们选择概率最高的候选矫正

候选模型：c∈candidatesc\in candidatesc∈candidates

告诉我们要考虑哪些候选修正

语言模型：P©P©P©

CCC为英文单词出现的概率。例如，the的出现约占英文文本的7%，所以我们应该有P(the)P(the)P(the)= 0.07。

错误模型：P(W∣C)P(W|C)P(W∣C)

当待修改单词为CCC时，WWW被作为纠正单词的概率。

例如，P(teh∣the)P(teh|the)P(teh∣the)相对较高，但P(theeexyz∣the)P(theeexyz|the)P(theeexyz∣the)会非常低

为什么要使用像P(C∣W)P(C|W)P(C∣W)这样的简单表达式，并将其替换为涉及两个模型而不是一个模型的复杂表达式？

实际上P(C∣W)P(C|W)P(C∣W)已经将两个因素混为一谈，将两者分开并明确处理它们会更容易。

考虑拼写错误的单词W=thewW=thewW=thew 和两个候选更正C=theC=theC=the 和C=thawC=thawC=thaw。哪个具有更高的P(C∣W)P(C|W)P(C∣W)?

thaw似乎很好，因为唯一的变化是a到e，这是一个很小的变化。另一方面，the也很好，因为the是一个非常常见的词，而添加w似乎是一个更大、更不可能的变化，也许打字员的手指从e上滑落了。

关键是要估计 P(C∣W)P(C|W)P(C∣W)，我们必须同时考虑c的概率和从c变为w的概率，因此将这两个因素正式分开会更清晰。

🏛️ 5 Python的实现
该项目的实现按照 4.2 的表达式，分为四部分进行实现。

5.1 选择机制：argmaxargmaxargmax
在Python中，选择最大概率通过关键参数argmax进行计算。

5.2 候选模型：c∈candidatesc\in candidatesc∈candidates
首先是一个新概念：对单词的简单编辑是指删除（删除一个字母）、换位（交换两个相邻字母）、替换（将一个字母更改为另一个）或插入（添加一个字母）

本项目将单词进行一次简单编辑的结果作为候选纠错单词集合。

In [ ]
#函数 edits1返回一组所有已编辑的字符串（无论是否为单词），只需一次简单的编辑即可完成：
def edits1(word):
“All edits that are one edit away from 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®>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)
这可能是一个很大的集合。

对于长度为 n 的单词，将有 n 次删除、n-1 次交换、26n 次更改和 26(n+1) 次插入，总共有 54n+25 次（其中包括一些重复）。例如，

In [ ]
len(edits1(‘somthing’))
442
但是，如果我们将候选纠正结果限制在已知的单词上（在字典中）

那么候选集合就会小得多：

In [ ]
def known(words):
return set(w for w in words if w in WORDS)

known(edits1(‘somthing’))
{‘something’, ‘soothing’}
本项目还考虑需要两次简单编辑的更正情况。

这会产生更多的可能性，但通常只有少数是已知单词：

我们说edits2(W)edits2(W)edits2(W)的结果与WWW的编辑距离为 2 。

在真实的纠错任务中，往往由于错误复杂，需要根据任务选择简单编辑的次数， 例如论文 《基于贝叶斯纠错的AR辅助飞机装配数据纠错方法》中考虑到三次简单编辑。
In [ ]
def edits2(word):
return (e2 for e1 in edits1(word) for e2 in edits1(e1))

print(‘二次编辑生成候选集长度：’,len(set(edits2(‘something’))))

print(‘二次编辑在字典中的候选集：’,known(edits2(‘something’)))

注意输入的待纠错单词不同

print(‘二次编辑在字典中的候选集：’,known(edits2(‘somthing’)))
二次编辑生成候选集长度： 114324
二次编辑在字典中的候选集： {‘soothing’, ‘smoothing’, ‘something’, ‘seething’}
二次编辑在字典中的候选集： {‘seething’, ‘soothing’, ‘loathing’, ‘something’, ‘sorting’, ‘scathing’, ‘nothing’, ‘smoothing’}
5.3 语言模型
我们通过计算每个单词在大约一百万个单词的文本文件big.txt中出现的次数来估计单词P(word)P(word)P(word)的概率。

它是来自Project Gutenberg的公共领域书籍摘录以及来自维基词典 和英国国家语料库的最常用词列表的拼接。

函数words将文本分解为单词，然后变量WORDS保存每个单词出现频数，PPP估计每个单词的概率：

In [ ]
def words(text):
return re.findall(r’\w+', text.lower())

WORDS = Counter(words(open(‘work/big.txt’).read()))

def P(word, N=sum(WORDS.values())):
return WORDS[word] / N

不同词的个数

print(len(WORDS))

一共出现的个数

print(sum(WORDS.values()))

出现最多的10个词

print(WORDS.most_common(10))

出现概率最大的单词，及其概率

print(max(WORDS, key=P))
print(P(‘the’))

未出现的单词概率

print(P(‘unmentioned’))
32198
1115585
[(‘the’, 79809), (‘of’, 40024), (‘and’, 38312), (‘to’, 28765), (‘in’, 22023), (‘a’, 21124), (‘that’, 12512), (‘he’, 12401), (‘was’, 11410), (‘it’, 10681)]
the
0.07154004401278254
0.0
我们可以看到有 32198 个不同的词，它们一起出现了 1115585 次，

其中the是最常见的词，出现了 79,809 次（或大约 7% 的概率），而其他词出现的可能性较小：

5.4 错误模型
原作者定义了一个有缺陷的错误模型，它认为所有编辑距离为 1 的已知单词比编辑距离为 2 的已知单词的概率无限大，并且无限比编辑距离为 0 的已知单词的可能性更小。

所以我们可以让候选（单词）按优先级顺序生成一个非空候选列表：

1.原始单词，如果在词表中

2.编辑距离一远的已知单词列表，如果有的话

3.编辑距离两处的已知单词列表，如果有的话

4.原始单词，如果不在词表中

然后我们不需要乘以P(w∣c)P(w|c)P(w∣c)因子，因为处于所选优先级的每个候选单词都有相同的概率（根据提出的缺陷模型）

在真实的情况中，对不同的候选单词进行排序是整个纠错问题的难点，一般需要根据具体任务进行分析，建立自己的方法。

原作者采用的方法考虑的是对单词的修改次数，实际中还考虑每个候选单词之间的转移概率等因素。

简单讲，原作者认为，当该单词没有出现在词表中为错误单词，此时一次简单编辑单词概率高于两次简单编辑单词概率。

In [ ]
def correction(word):
return max(candidates(word), key=P)

def candidates(word):
return known([word]) or known(edits1(word)) or known(edits2(word)) or [word]
🏛️ 6 评估
原作者从牛津文本档案库 (Oxford Text Archive)下载了 Roger Mitton 的 Birkbeck 拼写错误语料库.

从这个库中, 取出了两个集合, 作为要做拼写检查的目标.

第一个集合用来作为在开发中作为参考, 第二个作为最后的结果测试.

由于原作者并没有提供提取的集合文件，也没有给出处理的代码。原代码也有少量错误。
目前全网也只是做了简单的翻译工作。并没有研究该步骤的具体效果。

本项目修缮错误后，选择维基百科纠错数据集进行测试。

In [65]

import re
from collections import Counter

def words(text):
return re.findall(r’\w+', text.lower())

WORDS = Counter(words(open(‘work/big.txt’).read()))

def P(word, N=sum(WORDS.values())):
“Probability of word.”
return WORDS[word] / N

def correction(word):
“Most probable spelling correction for word.”
return max(candidates(word), key=P)

def candidates(word):
“Generate possible spelling corrections for word.”
return (known([word]) or known(edits1(word)) or known(edits2(word)) or [word])

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)

def edits1(word):
“All edits that are one edit away from 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®>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)

def edits2(word):
“All edits that are two edits away from word.”
return (e2 for e1 in edits1(word) for e2 in edits1(e1))

################ Test Code

def unit_tests():
assert correction(‘speling’) == ‘spelling’ # insert
assert correction(‘korrectud’) == ‘corrected’ # replace 2
assert correction(‘bycycle’) == ‘bicycle’ # replace
assert correction(‘inconvient’) == ‘inconvenient’ # insert 2
assert correction(‘arrainged’) == ‘arranged’ # delete
assert correction(‘peotry’) ==‘poetry’ # transpose
assert correction(‘peotryy’) ==‘poetry’ # transpose + delete
assert correction(‘word’) == ‘word’ # known
assert correction(‘quintessential’) == ‘quintessential’ # unknown
assert words(‘This is a TEST.’) == [‘this’, ‘is’, ‘a’, ‘test’]
assert Counter(words(‘This is a test. 123; A TEST this is.’)) == (
Counter({‘123’: 1, ‘a’: 2, ‘is’: 2, ‘test’: 2, ‘this’: 2}))
assert len(WORDS) == 32198
assert sum(WORDS.values()) == 1115585
assert WORDS[‘the’] == 79809
assert P(‘quintessential’) == 0
assert 0.07 < P(‘the’) < 0.08
return ‘unit_tests pass’

def spelltest(tests, verbose=False):
“Run correction(wrong) on all (right, wrong) pairs; report results.”
import time
start = time.process_time()
good, unknown = 0, 0
n = len(tests)
for right, wrong in tests:
w = correction(wrong)
good += (w == right)
if w != right:
unknown += (right not in WORDS)
if verbose:
print(‘correction({}) => {} ({}); expected {} ({})’
.format(wrong, w, WORDS[w], right, WORDS[right]))
dt = time.process_time() - start
print('{:.0%} of {} correct ({:.0%} unknown) at {:.0f} words per second ’
.format(good / n, n, unknown / n, n / dt))

def Testset(lines):
“Parse ‘right: wrong1 wrong2’ lines into [(‘right’, ‘wrong1’), (‘right’, ‘wrong2’)] pairs.”
return [(right.replace(‘\n’,‘’), wrong)
for (wrongs,right) in (line.split(‘->’) for line in lines)
for wrong in wrongs.split()]

if name == ‘main’:
print(unit_tests())

print(spelltest(Testset(open('work/test.txt'))))

unit_tests pass
62% of 4292 correct (29% unknown) at 29 words per second
None
最终，在验证集上，原作者得到 75% 的正确率（以 41 个词/秒的速度处理单词），在最终测试集上，得到 68% 的正确率（以 35 个词/秒的速度)。

我们的模型可能由于数据分布不同，最终结果为62%（以 29 个词/秒的速度处理单词） ：

🏛 7 未来的工作
作者在原文章中针对测试数据集给出一系列的改进方案，由于测试集不同，我们仅给出简略说明.

详细的方案可以参考英文原文

P©P©P©语言模型中。可以区分语言模型中的两种错误来源。更重要的是对生词，即没见过的词语的处理。
错误模型：P(W∣C)P(W|C)P(W∣C) 到目前为止，误差模型很简单：编辑距离越小，误差就越小。这会导致一些问题。
选择机制：argmaxargmaxargmax 在训练集中，程序枚举了编辑距离 2 内的所有校正。测试集错误超出编辑距离2的比例更大。
最好的改进方法：将针对一个单词的纠错修改为根据前后的单词进行纠错。考虑单词的上下文信息。
🐱 8 项目总结
项目主要讲解从零实现一个单词拼写纠错模型

目前全网相关的资料大多含有部分错误，本项目对其进行了补充完善

该项目原作者代码报错，且中文翻译版本失效，因此有本项目的完成动机。

如果得到大家持续的关注，会考虑针对改进方案的后续版本。

特别注意:本项目是基于全网贝叶斯纠错相关资料的完善，所参考的资料来源均亦表明出处。