我目前正在开发一个可以生成大量文本内容的流 API。正如预期的那样,API 给出了大量重复数据,而且我们也有过滤接近重复数据的业务需求。
我对数据流中的重复检测做了一些研究,并阅读了。稳定布隆过滤器是用于数据流中重复检测的数据结构,具有误报率上限。
但是,我想识别近似重复项,并且我还研究了用于最近邻问题和近似重复项检测的散列算法,例如 LSH 和 MinHash。
我有点陷入困境,正在寻找有关如何进行的指示以及我可以查看的论文/实施?
首先,将文本标准化为所有小写(或大写)字符,用空格替换所有非字母,将所有多个空格压缩为一个,删除前导和尾随空格;为了速度,我将在一次文本中执行所有这些操作。接下来采取MD5
结果字符串的哈希(或更快的东西)。进行数据库查找MD5
表中的哈希(作为两个 64 位整数),如果存在,则它是一个exact重复,如果没有,请将其添加到表中并继续下一步。您将希望根据时间或内存使用情况使旧哈希值老化。
要查找接近的重复项,需要将规范化字符串转换为潜在的签名(子字符串的哈希值),请参阅SpotSigs
纸和博客文章 http://glinden.blogspot.com/2008/08/clever-method-of-near-duplicate.html作者:格雷格·林登。假设例程Sigs()
对于给定的字符串(即给定标准化的字符串)执行此操作x
, Sigs(x)
返回一小组 (1-5) 64 位整数。你可以使用类似的东西SpotSigs
算法来选择文本中的子字符串作为签名,但是如果您对数据有所了解,那么制定自己的选择方法可能会效果更好。您可能还想看看 simhash 算法(代码是here http://code.google.com/p/simhash/).
鉴于Sigs()
有效地找到邻近重复项的问题通常称为设置相似连接 http://bit.ly/JPTZ2I问题。这SpotSigs
论文概述了一些启发式方法,以减少新集合需要与旧集合进行比较的集合数量。simhash
method.
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)