Dav*_* W. 17 algorithm fuzzy duplicates time-complexity record-linkage
我有一个大型数据库(可能在数百万条记录中),文本串相对较短(按街道地址,名称等顺序排列).
我正在寻找一种去除不精确重复的策略,模糊匹配似乎是首选方法.我的问题:许多文章和SO问题涉及将单个字符串与数据库中的所有记录进行匹配.我希望立即对整个数据库进行重复数据删除.
前者是线性时间问题(将值与一百万个其他值进行比较,每次计算一些相似性度量).后者是一个指数时间问题(将每个记录的值与每个其他记录的值进行比较;对于一百万条记录,这与前一个选项的1,000,000次计算相比,大约为5 x 10 ^ 11次计算).
我想知道是否有另一种方法,而不是我提到的"蛮力"方法.我想可能生成一个字符串来比较每个记录的值,然后对具有大致相等的相似性度量的字符串进行分组,然后通过这些组运行暴力方法.我不会达到线性时间,但它可能有所帮助.此外,如果我正确地考虑这一点,这可能会错过字符串A和B之间潜在的模糊匹配,因为它们与字符串C(生成的校验字符串)的相似性尽管彼此非常相似但是非常不同.
有任何想法吗？
PS我意识到我可能在时间复杂度上使用了错误的术语 - 这是一个我基本掌握的概念,但不够好,所以我可以在现场将算法放入适当的类别.如果我使用了错误的术语,我欢迎更正,但希望我至少得到了我的观点.
编辑
一些评论者提出,鉴于记录之间的模糊匹配,我的策略是选择要删除哪些(即给出"foo","boo"和"coo",这将被标记为重复并删除).我应该注意,我不是在寻找自动删除.其目的是在6000万个记录数据库中标记可能的重复数据,以供人工审查和评估之用.如果有一些误报,可以,只要它是一个大致可预测/一致的数量.我只需要了解复制品的普遍程度.但是如果模糊匹配传递需要一个月才能运行,那么这首先不是一个选项.
mcd*_*lla 13
看看http://en.wikipedia.org/wiki/Locality-sensitive_hashing.一种非常简单的方法是将每个地址(或其他)分成一组重叠的n-gram.该STACKOVERFLOW成为集合{STACKO,TACKO,ACKOV,CKOVE ......,RFLOW}.然后使用大型散列表或排序合并来查找碰撞的n-gram并使用模糊匹配器检查碰撞.因此,STACKOVERFLOW和SXACKOVRVLOX将发生冲突,因为两者都与冲突的n-gram ACKOV相关联.
复杂程度的另一个级别是选择一个随机散列函数 - 例如带有任意键的HMAC,以及你找到的n-gram,只保留散列值最小的那个.然后你必须跟踪更少的n-gram,但只有在两种情况下最小的散列值都是ACKOV才能看到匹配.在n-gram的长度和假命中的概率之间显然存在权衡.实际上,人们似乎要做的是通过连接同一记录中多个哈希函数的结果来使n非常小并获得更高的精度,因此您需要同时在多个不同的哈希函数中获得匹配 - 我认为这种可能性更好.尝试谷歌搜索"重复检测minhash"