模糊匹配编号

Question

我一直在使用Double Metaphone和Caverphone2进行字符串比较，它们在名称，地址等方面的工作很好（Caverphone2对我来说最合适）。然而，它们产生太多的误报，当你到的数值，如电话号码，IP地址，信用卡号码等

所以我看了看Luhn和Verhoeff算法和他们本质上描述什么我想要，但不完全。他们似乎擅长验证，但似乎并不适合模糊匹配。有没有像Luhn和Verhoeff那样的行为，可以检测到包含两个相邻数字的单位错误和转置错误，用于类似于模糊字符串算法的编码和比较目的？

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

Answer 1

Levenshteinandfriends可能很适合找到特定字符串或数字之间的距离。但是，如果您想构建拼写更正器，则不希望在每个查询中都运行整个单词数据库。

Peter Norvig基于一些简单的“模糊匹配”拼写纠正器，基于谷歌拼写建议背后的一些技术，写了a very nice article。

如果您的字典有N条目，并且平均单词长度为L，则“蛮力Levenshtein”方法需要时间O(N*L^3)。 Peter Norvig的方法是在输入的某个编辑距离内生成所有单词，然后在字典中查找它们。因此它实现了O(L^k)，其中k是所考虑的最远的编辑距离。