l 按照去处重复的级别进行分类,去处重复三个级别:
1. 镜像站点:根据站点内相似页面多少进行判断.实现相对简单.
2. 完全相同网页:实现相对简单并且速度比较块,可以根据页面MD5整个文档来说，每个文档一个HASH编码，然后排序，将相同的找出.
3. 部分相同页面:实现相对负责,目前大多工作在这个部分.
评价:
三个级别应该从最高级别到较低级别分别进行,因为有很大比例(22%)的内容是完全相同的,这个部分实现起来相对简单,而且如果这个部分已经识别,那么针对部分相同页面的计算量会大量减少,这样应该可以减少总体的计算时间..
l 按照去重的时机,可以分为以下三类
（1） 抓取页面的时候去重，这样可以减少带宽以及减少存储数量；
（2） 索引之后进行去重；
（3） 用户检索时候进行再次去重；增加准确性，耗费时间；
评价:
可以结合三个时机某个或者所有都结合,对于GOOGLE来说,很可能是结合了2和3两种方法, GOOGLE的很多思路建立在后台计算和实时计算联合，比如相关度计算，后台计算重要性得分，在用户输入查询后得到初始数据集合，然后根据这个数据集合之间文档的关系重新调整顺序；比如去处重复，首先在后台进行重复发现，为了增加精确度，在返回查询结果后，在返回文档集合内，又根据“描述”部分重新计算哪些文档是重复的，这样增加了准确性，估计其它很多相关算法也采取这种联合策略，为了加快速度，实时计算部分可以和CACHE部分结合进行计算。
l 按照不同的特征选择方法,有几种方式:
1. 完全保留特征
2. 特征选择,设置不同的选择策略来保留部分特征,抛弃其它特征
a. 比如对于单词级别的抛弃权重小的单词(I-MATCH)
b. 对于SHINGLE方法,可以保留部分SHINGLE抛弃其它SHINGLE
(1) 一种是保留FINGERPRINT第I个位置为0的SHINGLE,其它抛弃;
(2) 一种是每隔I个SHINGLE进行抽样保留,其它抛弃;这两种得到的文档SHINGLE数目是变长的;
(3) 一种是选择最小的K个SHINGLE,这种得到定长的SHINGLE数目;
(4) 用84个RABIN FINGERPRINT函数对于每个SHINGLE进行计算,保留数值最小的84个FINGERPRINT,这个方法是定长的.
对于SHINGLE类方法来说,还可以区分为:定长的和变长的block切分算法
定长算法：速度快，但是如果内容有稍微变化（比如插入或者删除一个字符或者单词），其影响会比较大。比如Shingle及其改进方法（Super-Shingle），CSC及其改进方法（CSC-SS）。
变长算法：速度相对慢，但是内容变化只是造成局部影响。比如CDC,TTTD等算法。
评价: 为了提高计算速度,一种策略是在特征提取的时候,抛弃部分特征,保留部分特征,通过减少特征数目来加快计算速度.另外一个策略是粒度尽可能加大,比如SUPER-SHINGLE,MEGA-SHINGLE甚至是文档基本;为了提高算法效果,策略是采取变长的内容切割算法比如CSC算法等;这三种策略是方法加快速度和准确性的发展方向.
一些初步的结论:
1. 对于信息检索类型的方法来说,由于其特征选择是基于单词的,所以计算速度是个根本的问题,所以基本上是不实用的;
2. 从利用的信息来看,实用的系统还是应该立足于只是利用文本内容来判别相似性,排除掉利用链接信息等方法;
3. 从算法特征抽取粒度来看,应该立足于SHINLGE类的粒度甚至是文档级别的粒度算法;而SHINGLE类别的算法又应该优先选择抛弃部分特征的算法以及变长的算法;
4. 从去重级别角度考虑,应该将完全相同的文档和部分相同的文档识别分开进行,而且首先进行完全相同文档的识别,这样会有效加快计算速度;
5. 从去重时机考虑,可以考虑结合后台去重以及实时去重,这样增加去重的效果;
6. 从压缩编码方法来看,最有效的方式可能是RABIN FINGERPRINT变体算法;
7. 从聚类方法来看,最有效的方式可能是UNION FIND算法,目前比较快的算法基本上都采用这个方法;
8. 从整体方法选择来看,应该选择改进的SHINLGE方法,在此基础上进行进一步的改进;
三. 方法效率比较
1. SHINGLING 方法:时间效率O((mn)2) ,其中 m是SHINGLE的大小,n是文档数目.计算时间为:3千万文档,10台机器算一天,或者一台机器算10天;
2. 改进的SHINGLE方法(On the Evolution of Clusters of Near-Duplicate Web Pages.):时间效率接近于线性的O(n),计算时间为:1亿5千万网页计算3个小时;
3. IMACH方法: 最坏的情况下时间复杂度是(O(d log d))，速度比较快
4. 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))，速度比较快。
咨 询 客 服