近重复检测数据流中的(Near Duplicate Detection in Data Stream

我目前工作的一个流API生成大量的文本内容。正如预期的那样，在API给了很多重复的，我们也有一个业务需求近乎重复的数据进行过滤。

我做了一些研究数据流中的重复检测和阅读有关稳定布隆过滤器。稳定布隆过滤器是用于在数据流重复检测与对假阳性率的上限的数据结构。

但是，我想，以确定近重复，我也看着哈希算法像LSH和最小哈希了在近邻的问题和近重复检测使用。

我有点卡住，寻找指针，以如何进行和纸/实现，我可以看看？

Answer 1:

首先，归一化的文本以所有小写（或大写）字符，以空格替换所有的非字母，压缩所有多个白色空间为一个，除去前导和尾部的空白; 速度我将在文本的一个过程，执行所有这些操作。下一步采取的MD5哈希值（或东西快）结果字符串。做的数据库查找MD5哈希值（如两个64位整数）在一个表中，如果存在的话，它是一个精确的副本，如果没有，将其添加到表中，并继续执行下一步。您将要关闭老化或者基于时间或内存使用旧的哈希值。
要查找附近的复制标准化的字符串需要被转化成潜在的签名（子的哈希值），请参阅SpotSigs纸张和博客文章由格雷格·林登。假设常规Sigs()的确，对于给定的字符串，即给定的归一化的字符串x ， Sigs(x)返回一个小（1-5）组的64个整数。你可以使用类似SpotSigs算法来选择文本的签名子，而是使自己的选择方法，如果你了解你的数据可能会表现得更好。您可能还需要看看simhash算法（代码在这里）。
鉴于Sigs()的有效找到附近重复通常被称为问题集相似连接问题。所述SpotSigs文件概述一些试探法来修整一组新的需要进行比较，以一样的组数simhash方法。