我们最近在工作中遇到了一个有趣的问题，我们在数据库中发现了重复的用户提交数据。我们意识到，大多数数据之间的 Levenshtein 距离仅仅是两个字符串之间的差异。这表明，如果我们只是将一个字符串中的字符添加到另一个字符串中，那么我们最终会得到相同的字符串，并且对于大多数事情来说，这似乎是我们解释重复项的最佳方式。
我们还想考虑错别字。所以我们开始考虑人们平均多久在网上每个单词打错字，并尝试在这个距离内使用这些数据。我们找不到任何这样的统计数据。
在为数据匹配创建这种阈值时，有什么方法可以解决拼写错误？
让我知道我是否可以澄清！
首先，Levenshtein 距离定义为将字符串 A 转换为字符串 B 所需的最小编辑次数，其中编辑是插入或删除单个字符，或将字符替换为另一个字符。因此，对于距离的某种定义，这在很大程度上是“两个字符串之间的差异”。=)
听起来您正在寻找一个距离函数 F(A, B)，它给出了字符串 A 和 B 之间的距离以及阈值 N，其中距离小于 N 的字符串是拼写错误的候选者。除了 Levenshtein 距离之外，您还可以考虑Needleman–Wunsch。它基本上是同一件事，但它允许您提供一个函数来确定给定字符与另一个字符的接近程度。您可以将该算法与一组反映 QWERTY 键盘上按键位置的权重一起使用，以很好地查找错别字。但是，这会对国际键盘产生问题。
如果你有 k 个字符串并且你想找到潜在的拼写错误，那么你需要进行的比较次数是 O(k^2)。此外，每次比较都是 O(len(A)*len(B))。所以如果你有一百万个字符串，如果你天真地做事，你会发现自己有麻烦。以下是有关如何加快速度的一些建议：
您可能会遇到的一个问题是“第一街”。与“第一街”有相当大的距离，即使您可能想认为它们是相同的。处理此问题的最简单方法可能是在进行比较之前将字符串转换为规范形式。因此，您可以将所有字符串设为小写，使用将“1st”映射到“first”的字典，等等。该字典可能会变得非常大，但我不知道有更好的方法来处理这个问题。
既然你用 php 标记了这个问题，我假设你想为此使用 php。PHP 有一个内置的 levenshtein() 函数，但两个字符串都必须是 255 个字符或更少。如果这还不够长，您将不得不自己制作。或者，您可以使用 Python 的 difflib 进行调查。
You should check out this book:
http://nlp.stanford.edu/IR-book/pdf/irbookonlinereading.pdf
Has a good chapter (3.3) on spell checking
The references at the end of the chapter lists some papers that discuss probabilistic models
Good luck