模糊匹配数

Question

我一直在使用Double Metaphone和Caverphone2进行字符串比较,它们在名称,地址等方面做得很好(Caverphone2对我来说效果最好).但是,当您获得数字值时,例如电话号码,IP地址,信用卡号等,它们会产生太多的误报.

所以我看了Luhn和Verhoeff算法,它们基本上描述了我想要的东西,但并不完全.他们似乎擅长验证,但似乎并不是为模糊匹配而构建的.有什么行为像Luhn和Verhoeff,它可以检测到涉及两个相邻数字的单位错误和换位错误,用于编码和比较目的,类似于模糊字符串算法？

我想对一个数字进行编码,然后将其与100,000个其他数字进行比较,以找到完全相同的匹配.因此像7041234这样的东西会与7041324匹配作为可能的转录错误,但像4213704这样的东西不会.

Answer 1

Levenshtein 和 朋友可能适合查找特定字符串或数字之间的距离。但是，如果您想构建一个拼写校正器，您不希望在每次查询时都运行整个单词数据库。

Peter Norvig 写了一篇非常好的文章，介绍了基于谷歌拼写建议背后的一些技术的简单“模糊匹配”拼写纠正器。

如果你的字典有N条目，并且平均单词有长度L，那么“暴力编辑”方法将需要时间O(N*L^3)。Peter Norvig 的方法而是生成距输入一定编辑距离内的所有单词，并在字典中查找它们。因此它达到O(L^k)，其中 k 是考虑的最远编辑距离。