10

我一直在使用 Double Metaphone 和 Caverphone2 进行字符串比较，它们在姓名、地址等方面效果很好（Caverphone2 最适合我）。但是，当您获取数字值（例如电话号码、IP 地址、信用卡号码等）时，它们会产生太多误报。

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

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

4

1 回答 1

5

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

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

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

于 2011-12-31T00:09:31.137 回答