python - 拼写更正可能性

Question

正如大多数拼写纠正导师所说，拼写错误的单词 x 的正确单词 W^ 是:

W^ = argmax_W P(X|W) P(W)

其中 P(X|W) 是可能性，P(W) 是语言模型。

在我学习拼写校正的教程中，讲师说 P(X|W) 可以通过使用混淆矩阵来计算，该矩阵跟踪我们语料库中的一个字母被错误键入另一个字母的次数.我正在使用万维网作为我的语料库，不能保证一个字母被错误地键入另一个字母。那么，如果我使用 X 和 W 之间的 Levenshtein 距离而不是使用混淆矩阵，可以吗？它有很大的不同吗？

我要计算 Lev 的方式。 python 中的距离是这样的:

from difflib import SequenceMatcher

def similar(a, b):
    return SequenceMatcher(None, a, b).ratio()

See this

下面是使我的问题更清楚的教程:Click here

附言。我正在使用 Python

Answer 1

有几件事要说。

1. 您用来预测最有可能修正的模型是一个简单的级联概率模型:用户输入 W 的概率，当 W 的意思时出现拼写错误 X 的条件概率。 P(X|W) 的正确术语是条件概率，而不是似然。 (可能性用于估计候选概率模型与给定数据的匹配程度。因此它在您机器学习模型时发挥作用，而不是在您应用模型来预测校正时发挥作用。)

2. 如果您对 P(X|W) 使用 Levenshtein 距离，您将得到介于 0 和 W 和 X 的长度之和之间的整数>。这不是合适的，因为您应该使用概率，它必须介于 0 和 1 之间。更糟糕的是，您得到的值会越大候选人与输入的差异更大。这与您想要的相反。

3. 不过，幸运的是，SequenceMatcher.ratio() 实际上并不是 Levenshtein 距离的实现。它是相似性度量 的实现，返回 0 和 1 之间的值。越接近 1，两个字符串越相似。所以这是有道理的。

4. 严格来说，您必须验证 SequenceMatcher.ratio() 实际上适合作为概率度量。为此，您必须检查所有可能的 W 拼写错误所获得的所有比率的总和是否为 1。SequenceMatcher.ratio( )，所以它实际上不是一个数学上有效的选择。

5. 但是，它仍然会为您提供合理的结果，我想说它可以用于拼写检查器的实际和原型(prototype)实现。但是，存在性能问题:由于 SequenceMatcher.ratio() 应用于一对字符串(候选 W 和用户输入 X)，您可能必须将其应用于来自字典的大量可能候选者以选择最佳匹配。当你的字典很大时，那会很慢。要改进这一点，您需要使用内置有近似字符串搜索 的数据结构来实现您的字典。你可能想看看 this existing post寻找灵感(它是针对 Java 的，但答案包括通用算法的建议)。