拼写检查

小象实战讲义 · 自然语言处理

在上一节中，我们学习了如何利用朴素贝叶斯模型进行垃圾邮件分类。本节我们将探讨一个看似不同但底层原理相通的任务：拼写检查。无论是输入法、搜索引擎还是文本编辑器，自动拼写纠错功能都极大地提升了我们的效率。我们将深入剖析如何利用概率模型，特别是噪声信道模型，来构建一个基础的拼写检查系统。学完本节，你将理解如何将“用户想输入什么”和“用户实际输入了什么”这两个概率分布结合起来，找到最可能的正确单词。

💡 核心导读

• 噪声信道模型：将拼写纠错建模为从“正确单词”经过一个“噪声信道”产生“错误单词”的过程，目标是反推出最可能的正确单词。
• 贝叶斯推理：核心公式为 P(正确词 | 错误词) ∝ P(错误词 | 正确词) * P(正确词)，其中 P(正确词) 是语言模型，P(错误词 | 正确词) 是错误模型。
• 候选模型：如何从一个错误单词高效地生成所有可能的正确候选词，通常基于编辑距离（如插入、删除、替换、交换）。
• 混淆矩阵：用于统计和建模常见的拼写错误模式（例如，字母 c 容易被误打成 g）。
• 从单词到句子：拼写检查的思想可以扩展到句子级别，处理更复杂的上下文和多个错误。

噪声信道模型与贝叶斯公式

拼写检查的核心思想可以概括为：给定一个观察到的（可能是错误的）单词 w，我们想要找到最有可能的、用户原本想输入的正确单词 c。

这正是一个典型的噪声信道模型的应用场景：

1. 发送端：用户想输入一个正确的单词 c。
2. 噪声信道：由于打字疏忽、记忆错误等原因，单词 c 在传输过程中被“污染”，变成了错误的单词 w。
3. 接收端：我们观察到错误的单词 w，需要逆向推断出最可能的原始单词 c。

用数学语言描述，我们的目标是找到使得后验概率 P(c | w) 最大的 c： $$\hat{c} = \arg\max_{c \in C} P(c | w)$$ 其中 C 是所有可能正确单词的集合。

根据贝叶斯公式，我们可以将这个后验概率分解： $$P(c | w) = \frac{P(w | c) \cdot P(c)}{P(w)}$$ 对于给定的错误单词 w，分母 P(w) 是一个常数，不影响最大化过程。因此，我们的目标等价于： $$\hat{c} = \arg\max_{c \in C} P(w | c) \cdot P(c)$$

这个公式包含两个关键部分：

• P(c)：语言模型（Language Model）。它表示单词 c 在语言中出现的先验概率。例如，"the" 的概率远高于 "thy"。这可以通过在大型语料库中统计词频来估计。
• P(w | c)：错误模型（Error Model）或噪声模型。它表示当用户想输入正确单词 c 时，却错误地输入了 w 的概率。这需要我们对常见的拼写错误模式进行建模。

构建拼写检查器的关键组件

基于上述公式，一个完整的拼写检查系统需要四个核心组件：

1. 选择机制（Selection Mechanism）：即 argmax 操作，负责从所有候选词中选出综合得分最高的一个。
2. 候选模型（Candidate Model）：给定一个错误单词 w，高效地生成所有可能的正确候选词集合 C。这是缩小搜索空间的关键。
3. 语言模型（Language Model）：提供先验概率 P(c)。
4. 错误模型（Error Model）：提供似然概率 P(w | c)。

候选模型：生成可能的正确词

候选模型的目标是，对于一个错误单词（如 "wrok"），快速找出所有与之“相似”的正确单词（如 "work", "walk", "word" 等）。

一种经典且有效的方法是考虑编辑距离为1的所有可能变换。即，假设错误是由一次基本的编辑操作引起的。这些操作通常包括：

• 替换（Substitution）：将一个字母替换成另一个字母。work -> pork (w->p)
• 删除（Deletion）：删掉一个字母。work -> wok (删除 r)
• 插入（Insertion）：增加一个字母。work -> woork (在 o 后插入 o)
• 交换（Swap/Transposition）：交换相邻两个字母的顺序。work -> wrok (交换 r 和 o)

对于一个长度为 n 的正确单词，其可能产生的单次编辑错误数量是：

• 替换：n * 25 种可能（每个位置可替换为其他25个字母）。
• 删除：n 种可能（删除每个位置的一个字母）。
• 插入：(n+1) * 26 种可能（在 n+1 个间隙中插入26个字母之一）。
• 交换：n-1 种可能（交换相邻的 n-1 对字母）。

候选模型的工作是反向的：给定错误单词 w，我们对其应用所有可能的“逆向编辑操作”（例如，对 "wrok" 尝试交换相邻字母得到 "work"），并将生成的结果与词典比对，保留那些是合法单词的结果作为候选集 C。

下面我们用代码演示如何为一个错误单词生成编辑距离为1的候选词。

def generate_candidates(word):
    """生成与输入单词编辑距离为1的所有候选词（不考虑是否在词典中）"""
    letters = 'abcdefghijklmnopqrstuvwxyz'
    splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    
    # 删除（Delete）：删除一个字母
    deletes = [L + R[1:] for L, R in splits if R]
    # 交换（Swap）：交换相邻两个字母
    swaps = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R) > 1]
    # 替换（Replace）：替换一个字母
    replaces = [L + c + R[1:] for L, R in splits if R for c in letters]
    # 插入（Insert）：插入一个字母
    inserts = [L + c + R for L, R in splits for c in letters]
    
    # 返回所有可能候选词的集合（去重）
    return set(deletes + swaps + replaces + inserts)

# 测试生成候选词
error_word = "wrok"
candidates = generate_candidates(error_word)
print(f"错误单词 '{error_word}' 的编辑距离为1的候选词有 {len(candidates)} 个。")
print("前20个候选词示例：", sorted(list(candidates))[:20])

错误单词 'wrok' 的编辑距离为1的候选词有 234 个。
前20个候选词示例： ['arok', 'awrok', 'brok', 'bwrok', 'crok', 'cwrok', 'drok', 'dwrok', 'erok', 'ewrok', 'frok', 'fwrok', 'grok', 'gwrok', 'hrok', 'hwrok', 'irok', 'iwrok', 'jrok', 'jwrok']

可以看到，仅编辑距离为1就生成了 234 个候选词。在实际系统中，我们通常会用一个词典来过滤，只保留其中是真实单词的候选。

语言模型与错误模型

语言模型 P(c) 相对容易获得。我们可以从一个大规模文本语料库中统计每个单词的出现频率，并进行平滑处理（如加一平滑），得到其先验概率。例如： $$P(\text{“work”}) = \frac{\text{“work” 在语料中的出现次数}}{\text{语料总词数}}$$

错误模型 P(w | c) 是更具挑战性的部分。它需要量化“从 c 错写成 w”的可能性。一种实用的方法是利用混淆矩阵（Confusion Matrix）。

混淆矩阵统计了常见的拼写错误对。例如，我们可以从已对齐的“正确-错误”拼写对语料中，统计出：

• 字母 c 被错误替换为 g 的次数（例如 "cat" 打成 "gat"）。
• 字母 e 被错误删除的次数（例如 "the" 打成 "th"）。
• 在字母 r 和末尾 e 之间错误插入 a 的次数（例如 "there" 打成 "therae"）。

然后，使用最大似然估计或平滑技术，可以从这些计数中估计出概率 P(错误字母 | 正确字母, 操作类型)。

例如，课件中展示了一个有趣的发现：在统计中，字母 C 被误打成 G 有36次，G 被误打成 C 有32次，说明 C 和 G 是容易混淆的字母对。

综合计算与纠错

有了候选集 C、语言模型概率 P(c) 和错误模型概率 P(w|c)，我们就可以为每个候选词 c 计算得分 score(c) = P(w|c) * P(c)，并选择得分最高的作为纠正结果。

假设我们有一个极简的词典和已知的概率，我们可以模拟这个过程：

# —— 重新构建上文用到的微型数据（本节各代码块相互独立，可单独运行）
def generate_candidates(word):
    """生成与输入单词编辑距离为1的所有候选词（不考虑是否在词典中）"""
    letters = 'abcdefghijklmnopqrstuvwxyz'
    splits = [(word[:i], word[i:]) for i in range(len(word) + 1)]
    
    # 删除（Delete）：删除一个字母
    deletes = [L + R[1:] for L, R in splits if R]
    # 交换（Swap）：交换相邻两个字母
    swaps = [L + R[1] + R[0] + R[2:] for L, R in splits if len(R) > 1]
    # 替换（Replace）：替换一个字母
    replaces = [L + c + R[1:] for L, R in splits if R for c in letters]
    # 插入（Insert）：插入一个字母
    inserts = [L + c + R for L, R in splits for c in letters]
    
    # 返回所有可能候选词的集合（去重）
    return set(deletes + swaps + replaces + inserts)
error_word = "wrok"
candidates = generate_candidates(error_word)

# 假设我们有一个小词典和先验概率（语言模型）
vocab_prior = {
    'work': 0.005,  # P(work)
    'walk': 0.003,  # P(walk)
    'word': 0.002,  # P(word)
    'wok': 0.0001,  # P(wok)
    'rock': 0.001,  # P(rock)
}
# 假设我们有一个简单的错误模型：对于 swap 操作，概率为0.01；对于其他单次编辑，概率为0.001
def simple_error_prob(error_word, correct_word):
    """极简错误模型：如果两个单词可以通过一次交换得到，则概率较高"""
    # 检查是否可以通过一次交换得到
    if len(error_word) == len(correct_word):
        diff_pos = [i for i in range(len(error_word)) if error_word[i] != correct_word[i]]
        if len(diff_pos) == 2 and abs(diff_pos[0] - diff_pos[1]) == 1:
            # 相邻位置字母不同，可能是交换错误
            if error_word[diff_pos[0]] == correct_word[diff_pos[1]] and error_word[diff_pos[1]] == correct_word[diff_pos[0]]:
                return 0.01  # P(w|c) for swap
    # 其他单次编辑错误
    return 0.001

# 纠错函数
def correct_spelling(error_word, vocab_prior):
    candidates_from_vocab = [c for c in vocab_prior.keys() if c in generate_candidates(error_word) or c == error_word]
    if not candidates_from_vocab:
        return None, []
    
    scored_candidates = []
    for c in candidates_from_vocab:
        score = simple_error_prob(error_word, c) * vocab_prior[c]
        scored_candidates.append((c, score))
    
    # 按得分排序
    scored_candidates.sort(key=lambda x: x[1], reverse=True)
    return scored_candidates[0][0], scored_candidates

# 执行纠错
error_word = "wrok"
correction, all_scores = correct_spelling(error_word, vocab_prior)
print(f"错误单词 '{error_word}' 的纠正结果为：'{correction}'")
print("\n所有候选词及其得分：")
for word, score in all_scores:
    print(f"  {word}: {score:.6f}")

错误单词 'wrok' 的纠正结果为：'work'

所有候选词及其得分：
  work: 0.000050
  wok: 0.000000

在这个简化示例中，"work" 因为其较高的先验概率 P(work)=0.005 和相对较高的错误转换概率 P("wrok"|"work")=0.01（被识别为交换错误），其综合得分最高，因此被选为纠正结果。

从单词到句子的拼写检查

上述模型是针对单个单词的。在实际应用中，拼写检查往往需要在句子层面进行，因为上下文信息至关重要。例如，对于错误句子 "no much effert"：

1. 候选模型：需要为每个错误位置生成多个候选（如 "no" -> ["not", "on", "no"]，"effert" -> ["effort", "effect", "exert"]），并组合成多个可能的句子候选。
2. 语言模型：此时需要使用 n-gram 语言模型（如二元或三元语法）来计算整个句子序列的概率 P(c1, c2, ..., cn)，而不仅仅是单个单词的概率。"not much effort" 作为一个序列的概率，很可能远高于 "no much effect"。
3. 错误模型：同样需要考虑句子中每个单词的错误概率。
4. 选择机制：在所有可能的句子候选（可能是指数级）中，找到使 P(句子|错误句子) 最大的那个。通常可以使用动态规划（如维特比算法）来高效搜索。

这个过程与统计机器翻译和语音识别的解码过程在本质上是一致的，都是噪声信道模型在不同领域的应用。

📝 动手练一练

1. 概念辨析：在拼写检查的贝叶斯公式 argmax P(c|w) = argmax P(w|c)P(c) 中，P(c) 和 P(w|c) 分别被称为语言模型和错误模型。请尝试解释，如果只使用 P(c)（即选择最常见的词）进行纠错，或者只使用 P(w|c)（即选择最可能打错的词）进行纠错，分别可能会在什么情况下失败？并各举一个例子。

2. 代码实践：回顾上面生成候选词的代码 generate_candidates。请思考，如果错误是由两次编辑操作导致的（编辑距离为2），例如 "wrokn" 可能是 "work" 经过一次相邻交换（or->ro）和一次末尾插入（n）产生的。如何修改或扩展代码，使其能生成编辑距离为2的候选词？请描述你的思路（不需要写完整代码）。

def generate_candidates_ed2(word):
    candidates_ed1 = generate_candidates(word)
    candidates_ed2 = set()
    for cand in candidates_ed1:
        candidates_ed2.update(generate_candidates(cand))
    return candidates_ed2

📝 动手练一练

1. 概念辨析：在噪声信道模型公式 $\hat{c} = \arg\max_{c \in C} P(w | c) \cdot P(c)$ 中，$P(c)$ 和 $P(w|c)$ 分别被称为什么模型？它们各自的作用是什么？

2. 手算与代码：假设我们有一个极简的语言模型，它只包含三个单词及其概率：P(“the”) = 0.5, P(“then”) = 0.3, P(“than”) = 0.2。同时，我们有一个极简的错误模型，它规定：对于任意候选正确词 $c$，如果观察到的错误词 $w$ 与 $c$ 的编辑距离为1，则 P(w|c) = 0.1；如果编辑距离为0（即完全匹配），则 P(w|c) = 0.9；否则为0。 现在观察到输入 “thne”。按本节的四操作口径（插入、删除、替换、相邻交换各算一次）逐一核对：“thne” 与 “then” 的编辑距离为1（交换第3、4位的 n 和 e），与 “the” 的编辑距离为1（删除 n），与 “than” 的编辑距离为2（第3位 n→a、第4位 e→n 两次替换，没有更短的路径）。 a) 请手动计算，对于候选词 “then”, “than”, “the”，各自的 $P(w|c) * P(c)$ 得分是多少？ b) 根据噪声信道模型，系统最终会选择哪个词作为纠错结果？

# 用真正的编辑距离驱动错误模型：距离为 1 给 0.1，完全匹配给 0.9，其余为 0
language_model = {"the": 0.5, "then": 0.3, "than": 0.2}

def damerau(a, b):
    """含相邻交换的编辑距离（插入/删除/替换/交换四种操作，即本节定义的口径）"""
    rows, cols = len(a) + 1, len(b) + 1
    dp = [[0] * cols for _ in range(rows)]
    for i in range(rows):
        dp[i][0] = i
    for j in range(cols):
        dp[0][j] = j
    for i in range(1, rows):
        for j in range(1, cols):
            cost = 0 if a[i-1] == b[j-1] else 1
            dp[i][j] = min(dp[i-1][j] + 1, dp[i][j-1] + 1, dp[i-1][j-1] + cost)
            if i > 1 and j > 1 and a[i-1] == b[j-2] and a[i-2] == b[j-1]:
                dp[i][j] = min(dp[i][j], dp[i-2][j-2] + 1)  # 相邻交换算一次
    return dp[rows-1][cols-1]

def error_model(w, c):
    d = damerau(w, c)
    if d == 0:
        return 0.9
    if d == 1:
        return 0.1
    return 0.0

observed_word = "thne"
candidates = ["then", "than", "the"]

scores = {}
for cand in candidates:
    d = damerau(observed_word, cand)
    score = error_model(observed_word, cand) * language_model[cand]
    scores[cand] = score
    print(f"编辑距离('{observed_word}'->'{cand}') = {d}, 得分 = {score:.3f}")

best_candidate = max(scores, key=scores.get)
print(f"\n最佳纠错候选词是: '{best_candidate}' (得分: {scores[best_candidate]:.3f})")

编辑距离('thne'->'then') = 1, 得分 = 0.030
编辑距离('thne'->'than') = 2, 得分 = 0.000
编辑距离('thne'->'the') = 1, 得分 = 0.050

最佳纠错候选词是: 'the' (得分: 0.050)

本章小结

本节我们深入探讨了基于概率模型的拼写检查技术。核心在于利用噪声信道模型和贝叶斯公式，将纠错任务分解为估计语言模型概率 P(c) 和错误模型概率 P(w|c) 两部分。我们学习了如何通过考虑单次编辑操作（替换、删除、插入、交换）来构建候选模型，以及如何综合所有信息找到最可能的正确单词。最后，我们还看到了这一框架可以自然地扩展到句子级别的纠错，并与机器翻译等任务共享相同的理论基础。

📋 行动清单

• 理解并能够推导拼写检查的核心公式：argmax P(c|w) = argmax P(w|c)P(c)。
• 掌握四种基本的单字符编辑操作，并能手动为一个短单词列出其编辑距离为1的所有候选词。
• 思考：在中文拼写检查或拼音输入法纠错中，噪声信道模型应该如何定义？c 和 w 分别代表什么？（例如，c 是正确汉字，w 是输入的拼音串）。

—— 小象教研组