搜索引擎重复网页发现技术分析(续)

BLOOM FILTER方法:10k数据花费大约66ms;



从计算效率考虑,速度排序为:

1.    改进的SHINGLE方法;

2.    IMATCH方法;

3.    BLOOM FILTER方法;

4.      SHINGLE方法;





四.  目前代表性解决方法分析

1.   Shingle方法(1997年)

a.      特征抽取

Shingle方法:所谓Shingle类似于自然语言处理中常用的N-GRAM方法,就是将相互连续出现窗口大小为N的单词串作为一个Shingle,两者的不同点在于Shingle是这些串的集合,相同的串会合并为一个,而N-GRAM则由于考虑的是文本线性结构,所以没有相同合并步骤.每个Shingle就是文档的一个特征,一篇文档就是由所有这些Shingle构成的.



b.      压缩编码

40 bit长度 Rabin FingerPrint方法;至于存储方式则类似于传统信息检索领域的倒排文档技术,存储<Shingle,ID>信息以记录某个特征在哪些文档中出现过,然后进一步计算文档的相似性;



c.       文档相似度计算

(1)   相似度:任意两个文档A和B,相似度指的是两者相同的Shingle数目占两者Shingle数目总和的比例;

(2)   包含度:指的是两者相同的Shingle数目占某篇文档Shingle数目的比例;



d.      优化措施:

(1)   分布计算然后合并;

(2)   抛弃超高频出现Shingle,分析发现这些Shingle是无意义的片断;

(3)   完全相同文档保留一份进行聚类;(文档是否完全相同根据压缩编码后数值是否相同判断)

(4)   Super Shingle:关于Shingle的Shingle,从更大结构上计算相似性以节省存储空间;





2.      Google可能采取的方法

a.      特征抽取

类似于Shingle方法,不同点在于:对于每个单词根据HASH函数决定属于哪个LIST,这样每个文档由若干个这样的LIST构成;



b.      压缩编码

FingerPrint方法;对于组成文档的LIST进行FingerPrint方法计算; 



c.       文档相似度计算

            编辑距离(Edit Distance):如果两个文档有任何一个FingerPrint相似就判断为内容接近.



d.      聚类方法

首先对<FingerPrint,Doc ID>按照Doc ID进行排序;然后采取Union Find聚类方法,聚类结果就是相似文档集合;



e.      优化措施



3.   HP实验室方法(2005年)

a.      特征抽取

基于内容的Chunk方法:变长而非定长的Chunk算法(TTTD算法);将一篇文档分解为若干个长度不同的Chunk,每个Chunk作为文本的一个特征.与shingle方法相比这种变长Chunk方法能够增加系统招回率;



b.      压缩编码

128bit MD5 HASH方法;每篇文章压缩编码后由若干 <Chunk 长度, 定长HASH编码>二元组构成;



c.       文档相似度计算

(1)   构建所有文档和Chunk构成的二分图;

(2)   找到文档A包含的所有CHUNK,计算这些CHUNK还被哪些其它文档包含;

(3)   计算这些文档和A的相似性;



d.      聚类方法:Union Find 算法

e.       优化措施:Bipartite 划分,本质上是将大规模数据分成小规模数据进行识别然后再合并结果.相当于分布计算;



4．bloom filter(2005年)

(1).特征抽取方法

   基于内容的语块（Content-defined chunking CDC）：CDC将文档切分为变长的内容片断，切分边界由rabin fringerprint和预先制定的maker数值匹配来进行判断。

(2)编码（构造 bloom filter集合元素）

    对于切分的片断进行编码。bloom filter的编码方式如下：整个文档是由片断构成的，文档由长为m的二值数组表示。在将一个元素（内容片断）进行编码插入集合的时候，利用k个不同的hash函数进行编码，每个hash函数设置m个位置的某个位置为1。这种技术以前主要用来进行判断某个元素是否被集合包含。

（3）相似度计算方法

   bloom filter方法：对于两个已经编码的文档（两个长度为m的二值数组），通过bit逻辑运算AND计算，如果两者很多位置都同时为1，那么两个文档被认为是近似的。

（4）优势

     1．文档编码形式简洁，便于存储。

     2．由于计算相似性是BIT逻辑运算，所以速度快。

3．相对Shingling 方式来说便于判断文档包含关系。（某个文档包含另外一个短小的文档）



5．内容+链接关系（2003年）

1．特征抽取方法

       这个方法在抽取特征的时候同时考虑了文档的内容因素以及链接关系因素。

       内容因素：通过Random Projection技术将文档内容从高维空间映射到低维空间，并且由实数表示，如果两个文档映射后的数字越接近则表明两者内容越相似。

       链接因素：通过考虑类似于PAGERANK的连接关系，将某个网页的内容因素计算获得的分值通过链接传播到其他网页（传播关系见下列公式），多次叠代计算后得到每个页面的链接得分。

                 






2．相似度计算方法

       每个文档由二元组<RP,HM>构成，RP代表内容部分的数值，HM代表链接关系代表的数值。如果两个文档每个项之间的差值都小于指定值，则判断两个文档是相似的。

3．效果

  只采取内容精度达到90%，两者结合精度达到93%。从中看出，链接的作用并不明显。这可能跟这个方法的链接使用方法有关，因为通过链接计算的还是内容的情况。



6．I-Match方法（2002年）

（1）I-Match不依赖于完全的信息分析，而是使用数据集合的统计特征来抽取文档的主要特征，将非主要特征抛弃。输入一篇文档，根据词汇的IDF值过滤出一些关键特征，并且计算出这篇文档的唯一的Hash值，那些Hash值相同的文档就是重复的。

（2）使用SHA1作为Hash函数，因为它的速度很快而且适用于任何长度。SHA-1生成一个20-byte 或者160-bit 的hash值并且使用一个安全的冲突消解算法，使得不同的标志串(token streams)生成相同的hash值的概率非常低。.把<docid, hashvalue>元组插入树结构的时间复杂度是(O(d log d))，其他的如检索数据结构（hash表）需要(O(d))。对重复(duplicate)的识别是在将数据插入hash数组或是树结构中进行的，任何的hash值的冲突就表示检测到一个重复内容。

（3）最坏的情况下时间复杂度是(O(d log d))，速度比较快。