您好、欢迎来到现金彩票网!
当前位置:双彩网 > 向量化 >

simhash如何进行文本查重?

发布时间:2019-07-01 06:19 来源:未知 编辑:admin

  可选中1个或多个下面的关键词,搜索相关资料。也可直接点“搜索资料”搜索整个问题。

  展开全部有1亿个不重复的64位的01字符串,任意给出一个64位的01字符串f,如何快速从中找出与f汉明距离小于3的字符串?

  WWW上存在大量内容近似相同的网页,对搜索引擎而言,去除近似相同的网页可以提高检索效率、降低存储开销。

  一篇文本提取出内容以后,经过基本的预处理,比如去除停词,词根还原,甚至chunking,最后可以得到一个向量。

  对每一个term进行hash算法转换,得到长度f位的hash码,每一位上1-0值进行正负权值转换,例如f1位是1时,权值设为 +weight, fk位为0时,权值设为 -weight。

  讲文本中所有的term转换出的weight向量按f对应位累加 最后得到一个f位的权值数组,位为正的置1,位为负的置0,那么文本就转变成一个f位的新1-0数组,也就是一个新的hash码。

  2. 相似的文本具有相似的hash值,如果两个文本的simhash越接近,也就是汉明距离越小,文本就越相似。

  因此海量文本中查重的任务转换位如何在海量simhash中快速确定是否存在汉明距离小的指纹。

  在文章的实验中(见最后),simhash采用64位的哈希函数。在80亿网页规模下汉明距离=3刚好合适。

  1. 枚举出所有汉明距离小于3的simhash指纹,对每个指纹在80亿排序指纹中查询。

  (这种方法需要进行C(64,3)=41664词的simhash指纹,再为每个进行一次查询)

  2. 所有接近的指纹排序到一起,这至多有41664排序可能,需要庞大的空间。

   假设我们有一个已经排序的容量为2d,f-bit指纹集。看每个指纹的高d位。该高低位具有以下性质:尽管有很多的2d位组合存在,但高d位中有只有少量重复的。

   现在找一个接近于d的数字d’,由于整个表是排好序的,所以一趟搜索就能找出高d’位与目标指纹F相同的指纹集合f’。因为d’和d很接近,所以找出的集合f’也不会很大。

   最后在集合f’中查找 和F之间海明距离为k的指纹也就很快了。

   总的思想:先要把检索的集合缩小,然后在小集合中检索f-d’位的海明距离

  按照例子,80亿网页 有2^34 个,那么理论上34位就能表示完80亿不重复的指纹。

  我们假设最前的34位的表示完了80亿指纹,假设指纹在前30位是一样的,那么后面4位还可以表示24个, 只需要逐一比较这16个指纹是否于待测指纹汉明距离小于3。

  因此在一次完整的查找中,限定前q位精确匹配(假设这些指纹已经是q位有序的,可以采用二分查找,如果指纹量非常大,且分布均匀,甚至可以采用内插搜索),之后的2d-q个指纹剩下64-q位需要比较汉明距离小于3。

  假设这些指纹已经按A部分排序好了,我们先按A的16位精确匹配到一个区间,这个区间的后BCD位检查汉明距离是否小于3。

  同样的假设,其次我们按B的16位精确匹配到另一个区间,这个区间的所有指纹需要在ACD位上比较汉明距离是否小于3。

  所以这里我们需要将全部的指纹T复制4份, T1 T2 T3 T4, T1按A排序,T2按B排序… 4份可以并行进行查询,最后把结果合并。这样即使最坏的情况:3个位分别落在其中3个区域ABC,ACD,BCD,ABD…都不会被漏掉。

  只精确匹配16位,还需要逐一比较的指纹量依然庞大,可能达到2d-16个,我们也可以精确匹配更多的。

  例如:将64位平分成4份ABCD,每份16位,在BCD的48位上,我们再分成4份,WXZY,每份12位, 汉明距离的3位可以散落在任意三块,那么A与WXZY任意一份合起来做精确的28位…剩下3份用来检查汉明距离。 同理B,C,D也可以这样,那么T需要复制16次,ABCD与WXYZ的组合做精确匹配,每次精确匹配后还需要逐一比较的个数降低到2d-28个。不同的组合方式也就是时间和空间上的权衡。

  2)每个Ti都关联一个pi和一个πi,其中pi是一个整数, πi是一个置换函数,负责把pi个bit位换到高位上。

  2013-01-14展开全部有1亿个不重复的64位的01字符串,任意给出一个64位的01字符串f,如何快速从中找出与f汉明距离小于3的字符串?

  WWW上存在大量内容近似相同的网页,对搜索引擎而言,去除近似相同的网页可以提高检索效率、降低存储开销。

  两篇文本相似度普遍的定义是比较向量化之后两个词袋中词的交集程度,有cosine,jaccard等等

  如果直接使用这种计算方式,时间空间复杂度都太高,因此有了simhash这种降维技术,

  但是如何从传统的向量相似度能用simhash来近似,论文没提,应该是有很长一段推导要走的。

  一篇文本提取出内容以后,经过基本的预处理,比如去除停词,词根还原,甚至chunking,最后可以得到一个向量。

  对每一个term进行hash算法转换,得到长度f位的hash码,每一位上1-0值进行正负权值转换,例如f1位是1时,权值设为 +weight, fk位为0时,权值设为-weight。

  讲文本中所有的term转换出的weight向量按f对应位累加最后得到一个f位的权值数组,位为正的置1,位为负的置0,那么文本就转变成一个f位的新1-0数组,也就是一个新的hash码。

  2. 相似的文本具有相似的hash值,如果两个文本的simhash越接近,也就是汉明距离越小,文本就越相似。

  因此海量文本中查重的任务转换位如何在海量simhash中快速确定是否存在汉明距离小的指纹。

  在文章的实验中(见最后),simhash采用64位的哈希函数。在80亿网页规模下汉明距离=3刚好合适。

  1. 对输入指纹,枚举出所有汉明距离小于3的simhash指纹,对每个指纹在80亿排序指纹中查询。

  (这种方法需要进行C(64,3)=41664次的simhash指纹,再为每个进行一次查询)

  2. 输入指纹不变,对应集合相应位置变。也就是集合上任意3位组合的位置进行变化,实际上就是提前准备41664个排序可能,需要庞大的空间。输入在这群集合并行去搜....

   假设我们有一个已经排序的容量为2d,f-bit指纹集。看每个指纹的高d位。该高低位具有以下性质:尽管有很多的2d位组合存在,但高d位中有只有少量重复的。

   现在找一个接近于d的数字d’,由于整个表是排好序的,所以一趟搜索就能找出高d’位与目标指纹F相同的指纹集合f’。因为d’和d很接近,所以找出的集合f’也不会很大。

   最后在集合f’中查找和F之间海明距离为k的指纹也就很快了。

   总的思想:先要把检索的集合缩小,然后在小集合中检索f-d’位的海明距离

  那么折中的想法是 前d- bits相同,留下3bit在(64-d)bit小范围搜索,可行否?

  d-bits的表示范围有2^d,总量N个指纹,平均 每个表示后面只有N/(2^d)个

  如此只能保证前d位精确的那部分N/(2^d)指纹没有遗漏汉明距离3的

  按照例子,80亿网页有2^34个,那么理论上34位就能表示完80亿不重复的指纹。

  我们假设最前的34位的表示完了80亿指纹,假设指纹在前30位是一样的,那么后面4位还可以表示24个,只需要逐一比较这16个指纹是否于待测指纹汉明距离小于3。

  因此在一次完整的查找中,限定前q位精确匹配(假设这些指纹已经是q位有序的,可以采用二分查找,如果指纹量非常大,且分布均匀,甚至可以采用内插搜索),之后的2d-q个指纹剩下64-q位需要比较汉明距离小于3。

  假设这些指纹已经按A部分排序好了,我们先按A的16位精确匹配到一个区间,这个区间的后BCD位检查汉明距离是否小于3。

  同样的假设,其次我们按B的16位精确匹配到另一个区间,这个区间的所有指纹需要在ACD位上比较汉明距离是否小于3。

  所以这里我们需要将全部的指纹T复制4份,T1 T2 T3 T4, T1按A排序,T2按B排序… 4份可以并行进行查询,最后把结果合并。这样即使最坏的情况:3个位分别落在其中3个区域ABC,ACD,BCD,ABD…都不会被漏掉。

  只精确匹配16位,还需要逐一比较的指纹量依然庞大,可能达到2d-16个,我们也可以精确匹配更多的。

  例如:将64位平分成4份ABCD,每份16位,在BCD的48位上,我们再分成4份,WXZY,每份12位,汉明距离的3位可以散落在任意三块,那么A与WXZY任意一份合起来做精确的28位…剩下3份用来检查汉明距离。同理B,C,D也可以这样,那么T需要复制16次,ABCD与WXYZ的组合做精确匹配,每次精确匹配后还需要逐一比较的个数降低到2d-28个。不同的组合方式也就是时间和空间上的权衡。

  2)每个Ti都关联一个pi和一个πi,其中pi是一个整数,πi是一个置换函数,负责把pi个bit位换到高位上。

http://chinoamobi.com/xianglianghua/233.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有