streaming - 数据流中的近似重复检测

Question

我目前正在研究生成大量文本内容的流媒体 API。正如预期的那样，API 给出了很多重复数据，我们还有一个业务需求来过滤接近重复的数据。

我对数据流中的重复检测做了一些研究，并阅读了 Stable Bloom Filters .稳定布隆过滤器是用于数据流中重复检测的数据结构，具有误报率的上限。

但是，我想识别近似重复，并且我还查看了用于最近邻问题和近似重复检测的散列算法，如 LSH 和 MinHash。

我有点卡住了，正在寻找有关如何进行的指示以及我可以查看的论文/实现？

Answer 1

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

要查找接近重复的规范化字符串需要转换为潜在的签名(子字符串的哈希)，请参阅 SpotSigs纸和blog post格雷格·林登。假设例程Sigs()对给定的字符串执行此操作，即给定标准化字符串 x , Sigs(x)返回一小 (1-5) 组 64 位整数。你可以使用类似 SpotSigs 的东西算法来选择文本中的子字符串作为签名，但是如果您对数据有所了解，则使用自己的选择方法可能会表现得更好。您可能还想查看 simhash 算法(代码为 here)。

鉴于 Sigs()有效地找到接近重复项的问题通常称为 set similarity joins问题。 SpotSigs论文概述了一些启发式方法，以减少新集合需要与 simhash 进行比较的集合数。方法。