2

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

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

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

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

我要计算列夫的方式。python中的距离是这样的：

from difflib import SequenceMatcher

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

看到这个

这是使我的问题更清楚的教程：单击此处

PS。我正在使用 Python

4

2 回答 2

1

有几件事要说。

  1. 您用来预测最可能更正的模型是一个简单的级联概率模型：W用户输入的概率，以及拼写错误出现的条件概率。P(X|W) 的正确术语是条件概率，而不是可能性。（在估计候选概率模型与给定数据的匹配程度时使用可能性。因此，它在您对模型进行机器学习时起作用，而不是在您应用模型来预测校正时起作用。）XW

  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. 但是，它仍然会给你合理的结果，我想说它可以用于拼写检查器的实际和原型实现。但是，有一个性能问题：由于SequenceMatcher.ratio()应用于一对字符串（候选W和用户输入X），您可能必须将其应用于来自字典的大量可能的候选以选择最佳匹配。当您的字典很大时，这将非常慢。为了改善这一点，您需要使用内置了近似字符串搜索的数据结构来实现您的字典。您可能想查看这个现有的帖子以获得灵感（它是针对 Java 的，但答案包括一般算法的建议）。

于 2013-07-21T09:37:21.933 回答
0

Yes, it is OK to use Levenshtein distance instead of the corpus of misspellings. Unless you are Google, you will not get access to a large and reliable enough corpus of misspellings. There any many other metrics that will do the job. I have used Levenshtein distance weighted by distance of differing letters on a keyboard. The idea is that abc is closer to abx than to abp, because p is farther away from x on my keyboard than c. Another option involves accounting for swapped characters- swap is a more likely correction of sawp that saw, because this is how people type. They often swap the order of characters, but it takes some real talent to type saw and then randomly insert a p at the end.

The rules above are called error model- you are trying to leverage knowledge of how real-world spelling mistakes occur to help with your decision. You can (and people have) come with really complex rules. Whether they makes a difference is an empirical question, you need to try and see. Chances are some rules will work better for some kinds of misspellings and worse for others. Google how does aspell work for more examples.

PS All of the example mistakes above have been purely due to the use of a keyboard. Sometime, people do not know how to spell a word- this is whole other can of worms. Google soundex.

于 2013-07-21T09:17:17.493 回答