如何使用Levenshtein距离和拼写错误来创建类似字符串的阈值？

Question

我们最近遇到了一个有趣的问题,我们在数据库中发现了重复的用户提交数据.我们意识到大部分数据之间的Levenshtein距离只是所讨论的2个字符串之间的差异.这表明如果我们只是将一个字符串中的字符添加到另一个字符串中,那么我们最终会得到相同的字符串,对于大多数情况来说,这似乎是我们考虑重复项目的最佳方式.

我们也想说明错别字.因此,我们开始平均考虑人们在每个单词上在线制作拼写错误的频率,并尝试在此距离内使用这些数据.我们找不到任何这样的统计数据.

在为数据匹配创建这种阈值时,有没有办法解决拼写错误？

如果我能澄清,请告诉我!

Answer 1

首先,Levenshtein距离定义为将字符串A转换为字符串B所需的最小编辑数,其中编辑是插入,删除单个字符,或用另一个字符替换字符.因此,对于距离的某种定义,它是"两个字符串之间的差异".=)

It sounds like you're looking for a distance function F(A, B) that gives a distance between strings A and B and a threshold N where strings with distance less than N from each other are candidates for typos. In addition to Levenshtein distance you might also consider Needleman–Wunsch. It's basically the same thing but it lets you provide a function for how close a given character is to another character. You could use that algorithm with a set of weights that reflect the positions of keys on a QWERTY keyboard to do a pretty good job of finding typos. This would have issues with international keyboards though.

如果您有k个字符串并且想要找到潜在的拼写错误,则需要进行的比较次数为O(k ^ 2).另外,每个比较是O(len(A)*len(B)).所以如果你有一百万个字符串,如果你天真地做事,你会发现自己陷入困境.以下是关于如何加快速度的一些建议:

• 如果这是显而易见的道歉,但Levenshtein距离是对称的,所以请确保你不是计算F(A,B)和F(B,A).
• abs(len(A) - len(B))是字符串A和B之间距离的下限.因此,您可以跳过检查长度过于不同的字符串.

你可能遇到的一个问题是"第一圣" 距离"第一街"有很远的距离,即使你可能想要考虑那些是相同的.处理此问题的最简单方法可能是在进行比较之前将字符串转换为规范形式.因此,您可以将所有字符串设置为小写,使用将"1st"映射到"first"的字典等.该字典可能会变得非常大,但我不知道更好的方法来处理这个问题.

既然你用php标记了这个问题,我假设你想用php来做这件事.PHP有一个内置的levenshtein()函数,但两个字符串必须是255个字符或更少.如果时间不够长,你就必须自己做.或者,您可以使用Python的difflib进行调查.