搜索引擎重复网页发现技术解析

中科院软件所  作者：张俊林
 
一. 介绍
 
统计结果表明，近似镜像网页数占总网页数的比例高达全部页面的29%,而完全相同的页面大约占全部页面的22%。这些重复网页有的是没有一点改动的拷贝，有的在内容上稍作修改，比如同一文章的不同版本，一个新一点，一个老一点，有的则仅仅是网页的格式不同（如 HTML, Postscript）,文献[Models and Algorithms for Duplicate Document Detection 1999年]将内容重复归结为以下四个类型:
 
1.如果2篇文档内容和格式上毫无差别，则这种重复叫做full-layout duplicate。
 
2.如果2篇文档内容相同，但是格式不同，则叫做full-content duplicates
 
3.如果2篇文档有部分重要的内容相同，并且格式相同，则称为partial-layout duplicates
 
4.如果2篇文档有部分重要的内容相同，但是格式不同，则称为partial-content duplicates
 
近似重复网页发现技术就是通过技术手段快速全面发现这些重复信息的手段.如何快速准确地发现这些内容上相似的网页已经成为提高搜索引擎服务质量的关键技术之一。发现重复或者近似网页对于搜索引擎有很多好处:
 
1. 首先，如果我们能够找出这些重复网页并从数据库中去掉，就能够节省一部分存储空间，进而可以利用这部分空间来存放更多的有效网页内容，同时也提高了web检索的质量。
 
2. 其次，如果我们能够通过对以往搜集信息的分析，预先发现重复网页，在今后的网页搜集过程中就可以避开这些网页，从而提高有效网页的搜集速度。有研究表明重复网页随着时间级别不发生太大变化,所以这种从重复页面集合中选择部分页面进行索引是有效的.
 
3. 另外，如果某个网页的镜像度较高，也就预示着该网页相对重要，在搜集网页时应赋予它较高的优先级，而当搜索引擎系统在响应用户的检索请求并对输出结果排序时，应该赋予它较高的权值。
 
4. 从另外一个角度看,如果用户点击了一个死链接,那么可以将用户引导到一个相同页面,这样可以有效的增加用户的检索体验.因而近似镜像网页的及时发现有利于改善搜索引擎系统的服务质量。
 
二. 基本处理流程
 
通过分析现有技术,可以归纳出以下几个解决该问题的核心技术点,每个不同的技术基本上是由这几个技术点构成,无非是具体采纳的技术不同而已:
 
1. 文档对象的特征抽取:将文档内容分解,由若干组成文档的特征集合表示,这一步是为了方面后面的特征比较计算相似度.
 
2. 特征的压缩编码:通过HASH编码等文本向数字串映射方式以方便后续的特征存储以及特征比较.起到减少存储空间,加快比较速度的作用.
 
3. 文档相似度计算:根据文档特征重合比例来确定是否重复文档.
 
4. 聚类算法:通过叠代计算算出哪些文档集合是根据相似度计算是相近的;
 
5. 工程化问题:出于海量数据计算速度的考虑,提出一些速度优化算法以使得算法实用化.
 
我们可以从几个不同的角度对于现有的方法进行分类:
 
l 按照利用的信息，现有方法可以分为以下三类
 
1．只是利用内容计算相似
 
2．结合内容和链接关系计算相似
 
3．结合内容，链接关系以及url文字进行相似计算
 
评价:现有绝大部分方法还是利用文本内容进行相似识别,其它两种利用链接关系以及URL文字的方法还不是很成熟,而且从效果看引入其它特征收效并不明显,所以从实际出发还是选择利用内容进行相似计算的算法.
 
l 按照特征提取的粒度现有方法可以分为以下三类
 
1. 按照单词这个级别的粒度进行特征提取.
 
2. 按照SHINGLE这个级别的粒度进行特征提取.SHNGLE是若干个连续出现的单词,级别处于文档和单词之间,比文档粒度小,比单词粒度大.
 
3. 按照整个文档这个级别的粒度进行特征提取
 
评价:
 
目前这个领域里面很多工作借鉴类似于信息检索的方法来识别相似文档,其本质和SHINGLE等是相同的，都是比较两个文档的重合程度，但是区别是SHINGLE是将若干单词组成片断，粒度比较大，而信息检索类方法其实是用单词作为比较粒度，粒度比较小，粒度越大计算速度越快，而粒度越小计算速度越慢，所以信息检索类方法是不实用的，而且对SHINGLE的改进以及新提出的方法的发展趋势也是粒度越来越大，这样才能解决实际使用中速度的问题。粒度最大的极端情况是每个文档用一个HASH函数编码（比如MD5），这样只要编码相同就说明文档完全相同，但是粒度太大带来的问题是对于细微的变化文档无法判别，只能判断是否完全相同，至于部分相同以及相同的程度无法判断.
 
所以，现有方法也可以从以下角度分类：粒度。最小粒度：单词；中等粒度：SHINGLE；最大粒度：整个文档；可见SHINGLE类方法其实是在速度和精确程度上的一种折中方法。可以探讨不同粒度的效果，比如以句子为单位进行编码，以段落为单位编码等不同粒度的编码单位，还可以考虑动态的编码：首先以自然段落编码进行判别，如果发现部分相似，然后针对不同的部分再以细小粒度比如句子甚至单词级别的比较 所谓SUPER SHINGLE就是将粒度放大得到的。粒度越大，好处是计算速度越快（对于MD5整个文档来说，每个文档一个HASH编码，然后排序，将相同的找出，是速度最快的），缺点是会遗漏很多部分相似的文档；粒度越小，好处是招回率比较高，缺点是计算速度减慢。
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算法等;这三种策略是方法加快速度和准确性的发展方向.