我有一个大型数据库(可能在数百万条记录中),文本串相对较短(按街道地址,名称等顺序排列).
我正在寻找一种去除不精确重复的策略,模糊匹配似乎是首选方法.我的问题:许多文章和SO问题涉及将单个字符串与数据库中的所有记录进行匹配.我希望立即对整个数据库进行重复数据删除.
前者是线性时间问题(将值与一百万个其他值进行比较,每次计算一些相似性度量).后者是一个指数时间问题(将每个记录的值与每个其他记录的值进行比较;对于一百万条记录,这与前一个选项的1,000,000次计算相比,大约为5 x 10 ^ 11次计算).
我想知道是否有另一种方法,而不是我提到的"蛮力"方法.我想可能生成一个字符串来比较每个记录的值,然后对具有大致相等的相似性度量的字符串进行分组,然后通过这些组运行暴力方法.我不会达到线性时间,但它可能有所帮助.此外,如果我正确地考虑这一点,这可能会错过字符串A和B之间潜在的模糊匹配,因为它们与字符串C(生成的校验字符串)的相似性尽管彼此非常相似但是非常不同.
有任何想法吗？
PS我意识到我可能在时间复杂度上使用了错误的术语 - 这是一个我基本掌握的概念,但不够好,所以我可以在现场将算法放入适当的类别.如果我使用了错误的术语,我欢迎更正,但希望我至少得到了我的观点.
编辑
一些评论者提出,鉴于记录之间的模糊匹配,我的策略是选择要删除哪些(即给出"foo","boo"和"coo",这将被标记为重复并删除).我应该注意,我不是在寻找自动删除.其目的是在6000万个记录数据库中标记可能的重复数据,以供人工审查和评估之用.如果有一些误报,可以,只要它是一个大致可预测/一致的数量.我只需要了解复制品的普遍程度.但是如果模糊匹配传递需要一个月才能运行,那么这首先不是一个选项.
我正在编写一个爬虫来获取某些网站的内容,但内容可以重复,我想避免这种情况.所以我需要一个函数可以在两个文本之间返回相同的百分比来检测两个内容可能重复示例:
比较函数将文本2作为相同的文本1返回5/8%(其中5是文本的字数2相同的文本1(按字顺序比较),8是文本2的总字数).如果删除"some text",则将文本2作为相同的文本1(我需要检测情况).我该怎么做？