全文除重

Report
全文除重
什么样的是重复的?
直接特征

将文章所有内容通过字符串哈希算法或者
MD5等生成特征串,通过memcached或者
数据库字段保存,存在的则认为是重复了
I-Match

I-Match算法基于的依据是,在文挡中,特
别高频的词和特别低频的词无法反应这一
个文挡的真实内容,所以在比较之前,先
将文挡中高频词和低频词去掉(注意:这里
的高频和低频指的是文档频率,并非关键
词在你当前网页中的密度)
I-Match示例









1.中国足球队在米卢的率领下首次获得世界杯决赛阶段的比赛资格,
新浪体育播报 。
2.米卢率领中国足球队员首次杀入世界杯决赛阶段,搜狐体育播报。
文档(1)中去掉高频:中国,在,的,获得,比赛,资格,新浪,
体育,播报
去掉低频:米卢
则剩下中频词有:足球队,率领,首次,世界杯,决赛,阶段
文档(2)中去掉高频:中国,搜狐,体育,播报
去掉低频:米卢,杀入
则剩下中频词有:率领,足球队,首次,世界杯,决赛 ,阶段
这样两篇文档进行按词频排序,只需对排序结果进行一次哈希
(MD5)运算,既可实现文章的查重。这种方法显示也存在些问题,比
如高低频词的阀值分别设多少,对于有干扰词的情况下,无法匹配出
重复,但他的优点在于运算量小(不考虑分词的运算量)。
最长公共子串LCS


最长公共子串LCS(longest common
subsequence)是一种求两个字符串最长公
共子串的问题。既A = abcabba,B =
cbabac,则LCS = caba。
比如计算文档差别的算法(Linux diff)来求
LCS(A,B)
叠瓦法(Shingling)

叠瓦法(Shingling)是一种经典特征切片的方
法,这种方法对方便的计算出文章相似度,
并计算重叠的比重,也非常简单易行,甚
至不需要用到分词技术。
Shingling切片示例



句子“海量数据全文除重有什么好的办法
呢?”
这句话如果采用5字长进行切片,则产生
的结果如下所示:
海量数据全--->量数据全文--->数据全文除-->全文除重有--->... --->的办法呢?
Simhash(谷歌)

Shingling, I-Match等方法都采用哈希方式,
特征值带有极大的随机性,而经典的
Simhash则从另一种角度产生哈希数值,使
得内容相近的内容,产生的数字的汉明间
距(Hamming Distance)很小,这样可以
通过汉明间距来判断内容的相似度。
Simhash继续讲



切片办法可以采用上文Shingling、N-Gram;
Simhash的基本原理:
以产生一个32位的Simhash为例,通过
一篇文档生成Simhash值,它的一般过程是这
样,将文档按照一定的方式切分为N个特征,
对每一个用一个哈希函数生成哈希值,再对3
2取余,这样,在得到的余数位置计数+1,
其余位置-1,进行N次迭代,再通过得到的
最终数组,产生 Simhash值,既将32长度的元
组中,计数大于0的位置置为1,其余位置为
0,得到一个新的2进制32bit的数字,该数
字既为Simhash值。
汉明间距(Hamming Distance)





在信息论中,两个等长字符串之间的汉明距离是两
个字符串对应位置的不同字符的个数。换句话说,
它就是将一个字符串变换成另外一个字符串所需要
替换的字符个数。 例如:
* 1011101 与 1001001 之间的汉明距离是 2。
* 2143896 与 2233796 之间的汉明距离是 3。
* "toned" 与 "roses" 之间的汉明距离是 3。
汉明重量是字符串相对于同样长度的零字符串
的汉明距离,也就是说,它是字符串中非零的元素
个数:对于二进制字符串来说,就是 1 的个数,所
以 11101 的汉明重量是 4。
百度怎么选特征?

将网页内容按指定标点符号分隔成N个字符
串,再按长度从长到短排序,取前M个字符
串做为当前网页的特征。
这次的重点

这次主要讲百度所使用的特征切取方式。
特征片段有多少呢?



假设一篇文章只选选取50个片段,一亿篇
的话5000000000
一个特征串有15汉字的话,是30字节。
5000000000 * 30.0/1024/1024/1024 ≈
140G
特征片段怎么用


重复文章的定位:两篇文章重复的片段数
达到某个阀值时,可以认为他们是重复的。
这样只需要比较片段重复的比例。
特征这么多怎么办?


上面讲的140G的特征,能放到一台只有8G
的内存的内存中去吗?
压缩:哈夫曼等?
布隆过滤器

布隆过滤器(Bloom Filter)是一种空间效率很
高的随机数据结构,它利用位数组很简洁
地表示一个集合,并能判断一个元素是否
属于这个集合。Bloom Filter的这种高效是
有一定代价的:在判断一个元素是否属于
某个集合时,有可能会把不属于这个集合
的元素误认为属于这个集合(false
positive)。
讲解1
下面我们具体来看Bloom Filter是如何用位
数组表示集合的。初始状态时,Bloom
Filter是一个包含m位的位数组,每一位都置
为0。

讲解2

为了表达S={x1, x2,…,xn}这样一个n个元素的
集合,Bloom Filter使用k个相互独立的哈希
函数(Hash Function),它们分别将集合
中的每个元素映射到{1,…,m}的范围中。对
任意一个元素x,第i个哈希函数映射的位置
hi(x)就会被置为1(1≤i≤k)。注意,如果一
个位置多次被置为1,那么只有第一次会起
作用,后面几次将没有任何效果。在下图
中,k=3,且有两个哈希函数选中同一个位
置(从左边数第五位)。
哈希过程
讲解3

在判断y是否属于这个集合时,我们对y应用
k次哈希函数,如果所有hi(y)的位置都是1
(1≤i≤k),那么我们就认为y是集合中的元
素,否则就认为y不是集合中的元素。下图
中y1就不是集合中的元素。y2或者属于这个
集合,或者刚好是一个false positive。
错误率推导


略去一堆的公式…
结果:为0的bit位为一半,即所用的空间为
存储空间2倍,我们这些采用的8哈希方
式,因此所占用内存空间为实际存储切片
数量的16倍。
1G的内存能放多少特征



1024 * 1024 * 1024 * 8 / 16 =
536870912 略大于5亿。
一篇文章取50个特征的话,能保存:
536870912.0/50 = 10737418 约为1000万
他还有什么缺点



在节省了巨大的存储空间与飞快的处理速
度之后,我们应该充分意识到Bloom Filter
的不足之处:
1、无法删除、修改数据(虽有改进版本
实现了这些功能,但存不了这么多东西
了)。
2、判断出重复的时候,无法得知跟谁重
复了。
还该做什么?


文档编号?
怎么存储与查询编号?
这是作业题
谢谢!

similar documents