确定2个字符串匹配概率的最佳实践

Question

我需要编写代码以确定当其中一个字符串可能包含与第二个字符串的小偏差时是否匹配2个字符串,例如"南非"v"南非"或"英格兰"v"Enlgand".目前,我正在考虑以下方法

1. 确定字符串1中与字符串2中的字符匹配的字符百分比
2. 通过将1的结果与2个字符串的长度的比较相结合来确定匹配的真实概率,例如,虽然"SA"中的所有字符都在"南非"中找到,但是因为"SA"不是很可能匹配也可以在一系列其他国家名称中找到.

我将很高兴听到当前最佳实践是执行此类字符串匹配.

Answer 1

你可以看看Levenshtein的距离.这是两个字符串之间的距离.相同的字符串的距离等于0. 小猫和sitten等字符串的距离等于1,依此类推.距离是通过将一个字符串转换为另一个字符串的最小数量的简单操作来衡

链接中给出了伪代码中的更多信息和算法.

我还记得游戏编程宝石中提到过这个话题:第6卷:第1.6条最近的字符串匹配算法

Answer 2

为了使模糊字符串匹配成为理想选择,了解字符串的上下文非常重要.当它只是小错字时,Levenstein就足够了.当它是关于听错的声音时,你可以使用像soundex或metaphone这样的语音算法.大多数情况下,您需要结合以下算法,以及一些更具体的手动编写的东西.

• 尼德曼 - 翁施
• 探测法
• 音位
• Levenstein距离
• 位图
• 汉明距离

没有最好的模糊字符串匹配算法.这都是关于它所使用的上下文,所以你需要告诉我们你想在哪里使用字符串匹配.