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

搜索引擎重复网页发现技术分析andAlgorithmsforDuplicateDocumentDetection1999年]将内容重复归结为以下四个类型:4.如果2篇文档有部分重要的内容相同，但是格式不同，则称为partial-contentduplicates更多的有效网页内容，同时也提高了web检索的质量。系统在响应用户的检索请求并对输出结果排序时，应该赋予它较高的权值。术点,每个不同的技术基本上是由这几个技术点构成,无非是具体采纳的技术不同而已:3.文档相似度计算:根据文档特征重合比例来确定是否重复文档.1．只是利用内容计算相似1.按照单词这个级别的粒度进行特征提取.档的重合程度，但是区别是SHINGLE是将若干单词组成片断，粒度比较大，而信息检索类方法其实是用单词作为比较粒度，粒度比较小，粒度越大计算速度越快，而粒度越小计算速度越慢，所以信息检索类方法是不实用的，而且对SHINGLE的改进以及新提出的方法的发展趋势也是粒度越来越大，这样才能解决实际使用中速度的问题。粒度最大的极端情况是每个文档用一个HASH函数编码（比如MD5），这样只要编码相同就说明文档完全相同，但是粒度太大带来的问题是对于细微的变化文档无法判别，只能判断是否完全相同，至于部分相同以及相同的程度无法判断.SHINGLE就是将粒度放大得到的。粒度越大，好处是计算速度越快（对于MD5整个文档来说，每个文档一个HASH编码，然后排序，将相同的找出，是速度最快的），缺点是会遗漏很多部分相似的文档；粒度越小，好处是招回率比较高，缺点是计算速度减慢。2.完全相同网页:实现相对简单并且速度比较块,可以根据页面MD5整个文档来说，每个文档一个HASH编码，然后排序，将相同的找出.大量减少,这样应该可以减少总体的计算时间..l按照去重的时机,可以分为以下三类可以结合三个时机某个或者所有都结合,对于GOOGLE来说,很可能是结合了2和3两种方法,GOOGLE的很多思路建立在后台计算和实时计算联合，比如相关度计算，后台计算重要性得分，在用户输入查询后得到初始数据集合，然后根据这个数据集合之间文档的关系重新调整顺序；比如去处重复，首先在后台进行重复发现，为了增加精确度，在返回查询结果后，在返回文档集合内，又根据"描述"部分重新计算哪些文档是重复的，这样增加了准确性，估计其它很多相关算法也采取这种联合策略，为了加快速度，实时计算部分可以和CACHE部分结合进行计算。l按照不同的特征选择方法,有几种方式:1.完全保留特征(1)一种是保留FINGERPRINT第I个位置为0的SHINGLE,其对于SHINGLE类方法来说,还可以区分为:定长的和变长的block切分算法弃部分特征,保留部分特征,通过减少特征数目来加快计算速度.另外一个策略是粒度尽可能加大,比如SUPER-SHINGLE,MEGA-SHINGLE甚至是文档基本;为了提高算法效果,策略是采取变长的内容切割算法比如CSC算法等;这三种策略是方法加快速度和准确性的发展方向.一些初步的结论:2.从利用的信息来看,实用的系统还是应该立足于只是利用文本内容来判别相似性,排除掉利用链接信息等方法;5.从去重时机考虑,可以考虑结合后台去重以及实时去重,这样增加去重的效果;三.方法效率比较度比较快四.目前代表性解决方法分析1.Shingle方法(1997年)a.特征抽取篇文档就是由所有这些Shingle构成的.b.压缩编码(2)包含度:指的是两者相同的Shingle数目占某篇文档(4)SuperShingle:关于Shingle的Shingle,从更大结构上FingerPrint方法;对于组成文档的LIST进行FingerPrint方法计算;e.优化措施128bitMD5HASH方法;每篇文章压缩编码后由若干二元组构成;d.聚类方法:UnionFind算法(2)编码（构造bloomfilter集合元素）bloomfilter方法：对于两个已经编码的文档（两个长度为m的二值数组），通过bit逻辑运算AND计算，如果两者很多位置都同时为1，那么两个文档被认为是近似的。（4）优势5．内容+链接关系（2003年）1．特征抽取方法页的内容因素计算获得的分值通过链接传播到其他网页（传播关系见下列公式），多次叠代计算后得到每个页面的链接得分。2．相似度计算方法链接的作用并不明显。这可能跟这个方法的链接使用方法有关，因为通过链接计算的还是内容的情况。6．I-Match方法（2002年）（2）使用SHA1作为Hash函数，因为它的速度很快而且适用于任何长度。SHA-1生成一个20-byte或者160-bit的hash值并且使用一个安全的冲突消解算法，使得不同的标志串(tokenstreams)生成相同的hash值的概率非常低。.把元组插入树结构的时间复