php – 如何使用Levenshtein距离和错别字帐来创建类似字符串的阈值？

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了php – 如何使用Levenshtein距离和错别字帐来创建类似字符串的阈值？，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1906字，纯文字阅读大概需要3分钟。

内容图文

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

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

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

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

解决方法:

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

听起来你正在寻找一个距离函数F(A,B),它给出了字符串A和B之间的距离以及一个阈值N,其中距离小于N的字符串是拼写错误的候选者.除了Levenshtein距离之外,您还可以考虑Needleman–Wunsch.它基本上是相同的,但它允许您提供一个函数,以确定给定角色与另一个角色的接近程度.您可以将该算法与一组权重结合使用,这些权重反映了QWERTY键盘上键的位置,可以很好地找到拼写错误.但这会与国际键盘产生问题.

如果您有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进行调查.

内容总结

以上是互联网集市为您收集整理的php – 如何使用Levenshtein距离和错别字帐来创建类似字符串的阈值？全部内容，希望文章能够帮你解决php – 如何使用Levenshtein距离和错别字帐来创建类似字符串的阈值？所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端