接近数据流中的重复检测

Question

我目前正在开发一个生成大量文本内容的流API.正如所料,API提供了大量重复项,我们还有业务要求来过滤接近重复的数据.

我对数据流中的重复检测进行了一些研究,并阅读了有关稳定布隆过滤器的信息.稳定布隆过滤器是用于在数据流中进行重复检测的数据结构,其具有误报率的上限.

但是,我想识别近似重复项,我还查看了最近邻问题和近似重复检测中使用的哈希算法,如LSH和MinHash.

我有点陷入困境,并寻找关于如何继续和我可以看到的论文/实施的指针？

Answer 1

1. 首先,将文本规范化为所有小写(或大写)字符,将所有非字母替换为空格,将所有多个空格压缩为1,删除前导和尾随空格; 为了速度,我会在文本的一个传递中执行所有这些操作.接下来获取MD5结果字符串的哈希值(或更快).对表中的MD5散列(作为两个64位整数)进行数据库查找(如果存在),它是完全重复的,如果不是,则将其添加到表中并继续下一步.您将希望根据时间或内存使用情况使旧哈希老化.

2. 要找到接近重复的标准化字符串需要转换为潜在的签名(子串的哈希值),请参阅Greg Linden 的SpotSigs论文和博客文章.假设例程Sigs()对给定字符串执行该操作,也就是说,给定规范化字符串x,Sigs(x)返回一小组(1-5)64位整数.您可以使用类似SpotSigs算法的方法来选择签名文本中的子字符串,但如果您对数据有所了解,那么使您自己的选择方法可以更好地执行.您可能还想查看simhash算法(代码在这里).

3. 鉴于Sigs()有效地找到近似重复的问题通常被称为集相似性连接问题.该SpotSigs文件概述一些试探法来修整一组新的需要进行比较,以一样的组数simhash的方法.