搜索引擎重复网页发现技术分析.pptx

搜索引擎重复网页发现技术分析中科院软件所作者：张俊林一.介绍统计结果表明，近似镜像网页数占总网页数的比例高达全部页面的 29%,而完全相同的页面大约占全部页面的 22%。这些重复网页有的是没有一点改动的拷贝，有的在内容上稍作修改，比如同一文章的不同版本，一个新一点，一个老一点，有的则仅仅是网页的格式不同（如 HTML,Postscript）,文献Modelsand Algorithms for Duplicate Document Detection 1999 年将内容重复归结为以下四个类型:1.如果 2 篇文档内容和格式上毫无差别，则这种重复叫做full-layout duplicate。2.如果2篇文档内容相同，但是格式不同，则叫做full-contentduplicates3.如果 2 篇文档有部分重要的内容相同，并且格式相同，则称为 partial-layout duplicates4.如果 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类方法其实是在速度和精确程度上的一种折中方法。可以探讨不同粒度的效果，比如以句子为单位进行编码，以段落为单位编码等不同粒度的编码单位，还可以考虑动态的编码：首先以自然段落编码进行判别，如果发现部分相似，然后针对不同的部分再以细小粒度比如句子甚至单词级别的比较 所谓 SUPERSHINGLE 就是将粒度放大得到的。粒度越大，好处是计算速度越快（对于 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 算法等;这三种策略是方法加快速度和准确性的发展方向.一些初步的结论:1.对于信息检索类型的方法来说,由于其特征选择是基于单词的,所以计算速度是个根本的问题,所以基本上是不实用的;2.从利用的信息来看,实用的系统还是应该立足于只是利用文本内容来判别相似性,排除掉利用链接信息等方法;3.从算法特征抽取粒度来看,应该立足于 SHINLGE 类的粒度甚至是文档级别的粒度算法;而 SHINGLE 类别的算法又应该优先选择抛弃部分特征的算法以及变长的算法;4.从去重级别角度考虑,应该将完全相同的文档和部分相同的文档识别分开进行,而且首先进行完全相同文档的识别,这样会有效加快计算速度;5.从去重时机考虑,可以考虑结合后台去重以及实时去重,这样增加去重的效果;6.从压缩编码方法来看,最有效的方式可能是 RABINFINGERPRINT 变体算法;7.从聚类方法来看,最有效的方式可能是 UNION FIND 算法,目前比较快的算法基本上都采用这个方法;8.从整体方法选择来看,应该选择改进的 SHINLGE 方法,在此基础上进行进一步的改进;三.方法效率比较1.SHINGLING 方法:时间效率 O(mn)2),其中 m 是 SHINGLE的大小,n 是文档数目.计算时间为:3 千万文档,10 台机器算一天,或者一台机器算 10 天;2.改进的 SHINGLE 方法(On the Evolution of Clusters ofNear-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 方法;至于存储方式则类似于传统信息检索领域的倒排文档技术,存储信息以记录某个特征在哪些文档中出现过,然后进一步计算文档的相似性;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.聚类方法首先对按照 Doc ID 进行排序;然后采取 Union Find 聚类方法,聚类结果就是相似文档集合;e.优化措施3.HP 实验室方法(2005 年)a.特征抽取基于内容的 Chunk 方法:变长而非定长的 Chunk 算法(TTTD 算法);将一篇文档分解为若干个长度不同的Chunk,每个Chunk作为文本的一个特征.与 shingle 方法相比这种变长 Chunk 方法能够增加系统招回率;b.压缩编码128bit MD5 HASH 方法;每篇文章压缩编码后由若干 二元组构成;c.文档相似度计算(1)构建所有文档和 Chunk 构成的二分图;(2)找到文档 A 包含的所有 CHUNK,计算这些 CHUNK 还被哪些其它文档包含;(3)计算这些文档和 A 的相似性;d.聚类方法:Union Find 算法e.优化措施:Bipartite 划分,本质上是将大规模数据分成小规模数据进行识别然后再合并结果.相当于分布计算;4bloom 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 代表链接关系代表的数值。如果两个文档每个项之间的差值都小于指定值，则判断两个文档是相似的。3效果只采取内容精度达到 90%，两者结合精度达到 93%。从中看出，链接的作用并不明显。这可能跟这个方法的链接使用方法有关，因为通过链接计算的还是内容的情况。6I-Match 方法（2002 年）（1）I-Match 不依赖于完全的信息分析，而是使用数据集合的统计特征来抽取文档的主要特征，将非主要特征抛弃。输入一篇文档，根据词汇的 IDF 值过滤出一些关键特征，并且计算出这篇文档的唯一的 Hash 值，那些 Hash 值相同的文档就是重复的。（2）使用 SHA1 作为 Hash 函数，因为它的速度很快而且适用于任何长度。SHA-1 生成一个 20-byte 或者 160-bit 的 hash值并且使用一个安全的冲突消解算法，使得不同的标志串(token streams)生成相同的 hash 值的概率非常低。.把元组插入树结构的时间复杂度是(O(d log d)，其他的如检索数据结构（hash 表）需要(O(d)。对重复(duplicate)的识别是在将数据插入 hash 数组或是树结构中进行的，任何的 hash 值的冲突就表示检测到一个重复内容。（3）最坏的情况下时间复杂度是(O(d log d)，速度比较快。