模糊匹配数

Question

我一直在使用Double Metaphone和Caverphone2进行字符串比较，它们在名称、地址等方面工作得很好(Caverphone2最适合我)。然而，当涉及到电话号码、ip地址、信用卡号码等数值时，它们会产生太多的误报。

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

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

Answer 1

Levenshtein and friends对于查找特定字符串或数字之间的距离可能很有用。但是，如果您想要构建一个拼写校正器，您不希望在每次查询时都遍历整个word数据库。

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

如果您的字典有N条目，并且平均单词的长度为L，那么"Brute force Levenshtein“方法将花费时间O(N*L^3)。相反，Peter Norvig的方法生成距离输入内容一定编辑距离内的所有单词，并在字典中查找它们。因此，它实现了O(L^k)，其中k是考虑的最远编辑距离。