6

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

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

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

我有点卡住并寻找有关如何进行的指示以及我可以查看的文件/实施？

4

2 回答 2

6

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

  2. 要查找接近重复的规范化字符串，需要将其转换为潜在的签名（子字符串的哈希），请参阅 Greg Linden 的SpotSigs论文和博客文章。假设例程Sigs()对给定字符串执行此操作，即给定标准化字符串x，Sigs(x)返回一个小的 (1-5) 64 位整数集。您可以使用SpotSigs算法之类的方法来选择文本中的子字符串作为签名，但是如果您对数据有所了解，则使用自己的选择方法可能会更好。您可能还想查看 simhash 算法（代码在此处）。

  3. 鉴于Sigs()有效地找到附近重复的问题通常称为集合相似性连接问题。该论文概述了一些启发式方法，以减少需要与该方法SpotSigs进行比较的新集合的数量。simhash

于 2012-05-01T15:43:59.523 回答
1

http://micvog.com/2013/09/08/storm-first-story-detection/有一些不错的实现说明

于 2013-09-18T05:25:34.517 回答