ZZ 什么是Shingling算法 网页去重——Shingling 算法

什么是Shingling算法 网页去重——Shingling 算法

 

　shingling算法用于计算两个文档的相似度，例如，用于网页去重。维基百科对w-shingling的定义如下： 
　　In natural language processing a w-shingling is a set of unique "shingles"—contiguous subsequences of tokens in a document —that can be used to gauge the similarity of two documents. The w denotes the number of tokens in each shingle in the set. 
　　维基百科用一个浅显的例子讲解了shingling算法的原理。比如，一个文档 
　　"a rose is a rose is a rose" 
　　分词后的词汇(token，语汇单元)集合是 
　　(a,rose,is,a,rose,is, a, rose) 
　　那么w=4的4-shingling就是集合: 
　　{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is), (a,rose,is,a), (rose,is,a,rose) } 
　　去掉重复的子集合： 
　　{ (a,rose,is,a), (rose,is,a,rose), (is,a,rose,is) } 
　　给定shingle的大小,两个文档A和B的相似度 r 定义为: 
　　r(A,B)=|S(A)∩S(B)| / |S(A)∪S(B)| 
　　其中|A|表示集合A的大小。 
　　因此,相似度是介于0和1之间的一个数值，且r(A,A)=1,即一个文档和它自身 100%相似。 

 网页去重——Shingling 算法　　相关知识点： 
　　Rabin的指纹生成算法思想如下：　　假设A([b1,…,bm])是包含m个二进制字符的二进制字符串，那么可以根据A构造相应的(m-1)度的多项式如下，其中t是不定元。 
　　A(t)=b1tm-1 + b2tm-2+…+bm-1t+bm (1)　　给定一个度为k的多项式P(t)，如下： 
　　P(t)=a1tk+a2tk-1+…+ak-1t+ak (2)　　那么A(t) 除以P(t)的余数f (t)的度数为(k-1)。对于给定的字符串A，定义A的指纹f(A)如下： 
　　f(A)=A(t) mod P(t) (3)　　如何计算特征记录： 
　　1.通过删除HTML标签、字母小写化等对网页的预处理将网页内容规范化;　　2.取Shingle大小为10(即w的值为10)，来构造每一个Shingle; 
　　3.对每个Shingle用Rabin的指纹生成算法计算每个Shingle的指纹;　　4.采用整除的方法且设定m为25，来选择部分Shingle组成这个网页的特征记录。 
　　步骤：　　第一步，计算每个文档的特征记录。这一步和总的文档数成线性关系。 
　　第二步，计算得到一个所有的Shingle以及每个Shingle所出现在的文档列表，且按Shingle值排序。为了实现这个目标，每个文档的特征记录被扩展二元组<SHINGLE，文档ID>列表。所有文档的特征记录扩展得到的列表最终将个庞大列表，因此我们对其进行划分、计算、合并来得到最终结果。　　第三步，检测任意两个文档是否有共同的Shingle，如果有则记录这个文及他们所包含的相同的Shingle的数目，然后组成一个列表。为了实现这个们以第二步中得到的有序的二元组<SHINGLE，文档ID>组成的列表文件为基通过为每个在多个文档中出现的Shingle初始化一个三元组<文档ID，文档然后统计所有的这样的三元组并合并有着相同文档ID对的三元组，得到一个三元祖<文档ID，文档ID，共同Shingle数>所组成的列表。最后再采用划分并的方式来得到最后的三元组<文档ID，文档ID，1>组成的列表，并按第档ID排序。这一步的计算需要最大的磁盘空间，因为由于Shingle以及文档都很庞大，计算初始化以及更多的中间临时结果都要消耗极大的存储空间。 
　　第四步，进行最后的完整的聚类。检查每个三元组<文档ID，文档ID，共同数>看其是否达到了所设定的相似度的临界值，如果是则判定他们相似并归(或增加一个这两个文档之间的某个关系)。　　终于理清了大概的思想，着手编程了。因为是做实验，在计算特征记录的第一步省略了，而且我只是做两个文本之间的相似度。在计算特征记录第三步时我用的开源的包com.planetj.math.rabinhash.RabinHashFunction32，该包中可以生成32位的哈希值，也可以使64位的，我采用的是32位。对第四步m值我在想是不是自己设置的，我刚开始时设置为25，但是发现经过指纹生成算法得到的值很少有能被其整除的。后来自己再用几个值试试。这里我还有个疑问，还需要保存能被m值整除的hash值所对应的Shingle?因为我觉得既然不同的Shingle对应的Hash值是一样的机会是很渺茫的。那言外之意的是只要对两个文档比较hash值就可以了。这里有个很严重的性能问题就是在第三步中，可能会有大量的在多个文档中都出现的Shingle，因为共享某些Shingle的文档ID对的数量可能是非常庞大的。太多的共享Shingle可以极大的增加这种文档对数量。 
　　在这基础上有人采取了Super-Shingle算法，其实就是将特征记录再使用一次指纹生成算法。　　自己按照上面的步骤编程，但是后来发现效率是很低的，如果是两个相同的文档，那相似度是为1，但是稍微修改，相似度就急剧下降。也不知道是不是自己编程出现的问题，做这些就是有些不好：就是不知道自己到底是对好是错。 我想出现这样的原因可能是因为得到的hash值很少能有被给定的值整除的。这样那就得到的特征记录就非常少

 

 

from :http://zz.shangdu.com/index-htm-m-cms-q-view-id-693.html