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

搜索引擎中网页重复发现技术分析 中国科学院软件研究所作者:张1.统计结果显示，相似镜像页面的数量占页面总数的29%，而相同页面约占所有页面的22%。这些重复的网页，有的是不变的拷贝，有的是在内容上略有修改，比如同一篇文章的不同版本，一个新的，一个旧的，有的只是网页格式不同(比如HTML，Postscript)。文献[用于重复文档检测的模型和算法，1999]将内容重复分为以下四种类型:1.如果两个文档在内容和格式上没有区别，则这种复制称为全版面复制。2.如果两个文档内容相同但格式不同，则称为全文副本3。3.如果两个文档具有相同的重要内容和相同的格式，它们被称为部分布局副本4。4.如果两个文档具有相同的重要内容，但格式不同，则被称为部分内容重复的近似重复网页发现技术是通过技术手段快速、全面地发现这些重复信息的手段。如何快速准确地发现这些相似的网页，已经成为提高搜索引擎服务质量的关键技术之一。查找重复或相似的网页对搜索引擎有很多好处:1.首先，如果能找出这些重复的网页，并将其从数据库中删除，就可以节省一部分存储空空间，用于存储更有效的网页，提高web检索的质量。2.其次，如果能够通过对过去收集的信息进行分析，提前发现重复网页，就可以在以后的网页收集过程中避开这些网页，从而提高有效网页的收集速度。研究表明，重复的页面不会随时间发生太大的变化，因此从重复的页面集中选择一些页面进行索引是有效的。3.另外，如果一个页面的镜像度很高，说明这个页面相对重要，所以在收集页面的时候要给它更高的优先级，在搜索引擎系统响应用户的搜索请求和对输出结果进行排序的时候要给它更高的权重。4.从另一个角度来看，如果用户点击了一个死链接，可以将用户引导到同一个页面，可以有效增加用户的搜索体验。因此，及时发现近似镜像页面有利于提高搜索引擎系统的服务质量。2.基本处理流程通过分析现有技术，我们可以总结出以下几个关键技术点来解决这个问题。每种不同的技术基本上都是由这些技术点组成的，无非就是具体采用的技术:1。文档对象的特征提取:文档内容被分解并由组成文档的多个特征集来表示。这一步是为特征后面的特征比较计算相似性。2.特征的压缩编码:通过哈希编码等将文本映射为数字串的方式，方便后续的特征存储和特征比较，可以减少存储时间空，加快比较速度。3.文档相似度计算:根据文档特征的符合率判断文档是否重复。4.聚类算法:通过迭代计算，根据相似度计算出哪些文档集。5.工程问题:考虑到海量数据的计算速度，提出了一些速度优化算法，使算法实用化。我们可以从几个不同的角度对现有的方法进行分类:l根据所使用的信息，现有的方法可以分为以下三类:1。仅使用内容来计算相似度；2.结合内容和链接关系计算相似度；3.结合内容，链接和url字符的相似度计算和评价:现有的方法大多还是利用文本内容进行相似度识别，另外两种利用链接和URL字符的方法还不是很成熟，引入其他特征的效果也不明显。所以从实用的角度出发，我们还是选择使用内容进行相似度计算的算法。l根据特征提取的粒度，现有的方法可以分为以下三类:1.按照这个级别的词的粒度进行特征提取。2.基于瓦片粒度的特征提取。木瓦是若干个连续的词，其层次介于文档和词之间，比文档的粒度小。大于单词粒度。3.根据整个文档的粒度进行特征提取和评价:目前该领域的大量工作都是借鉴类似信息检索的方法来识别相似文档，其本质与SHINGLE等相同。，也就是比较两个文档的重合程度，但不同的是，SHINGLE是由几个词组成的，粒度比较大，而信息检索方法实际上是用词作为比较粒度。粒度比较小，粒度越大计算速度越快，粒度越小计算速度越慢，所以信息检索方法不实用。而且，对SHINGLE的改进和新提出方法的发展趋势也在增加粒度，以解决实际使用中的速度问题。在最大粒度的极端情况下，每个文档都是用哈希函数(比如MD5)编码的，所以只要编码相同，就说明文档是相同的。但是粒度太大带来的问题是，无法判断有细微变化的文档是否相同，但也无法判断其中部分是否相同。因此，现有的方法也可以从以下角度进行分类:粒度最小粒度:单词；中等粒度:木瓦；；最大粒度:整个文档；可以看出，瓦片类方法实际上是速度和精度的折中。可以探索不同粒度的效果，比如以句子为单位编码，以段落为单位编码等不同粒度的编码单位，也可以考虑动态编码:先通过自然的段落编码来判断，是否有部分相似，然后再比较小粒度的不同部分，比如句子甚至单词级别。所谓超级瓦片区就是放大粒度。粒度越大，计算速度越快(对于整个MD5文档，每个文档都有一个哈希码，然后排序找出相同的，速度最快)，但缺点是会漏掉很多部分相似的文档；粒度越小，优点是召回率越高，缺点是计算速度较慢。 l按照去重的级别分类，有三个去重级别:1。镜像站点:根据站点中相似页面的数量来判断。2.完全相同的页面:相对简单的实现和相对快速的比较。根据pageMD5，每个文档都可以用一个哈希进行编码，然后进行排序，找出相同的文档。3.部分相同页面:相对负责执行，目前大部分在该板块工作。评价:三个层次应该从最高层次到最低层次进行，因为有很大比例(22%)的内容是相同的，这一节实现起来比较简单。此外，如果已经识别了这一部分，则对于一些相同页面的计算量将大大减少，这将减少总的计算时间..l根据去重的时机，可以分为以下三类:(1)抓取页面时去重，(2)索引后进行去重；(3)当用户搜索时，重复被再次移除；增加准确性和消耗时间；评估:你可以将三个机会中的部分或全部结合起来。对于GOOGLE来说，大概是两种方法的结合:2和3。GOOGLE的很多想法都是基于后台计算和实时计算的结合，比如相关性计算，后台计算重要性分数，在用户输入一个查询后得到初始数据集，然后根据这个数据集中文档之间的关系重新调整顺序；例如，为了消除重复，首先在后台执行重复发现。为了增加准确性，在返回查询结果后，在返回的文档集中，根据“描述”部分重新计算哪些文档是重复的，从而增加准确性。估计其他很多相关算法也采用这种联合策略。为了加快计算速度，可以将实时计算部分和缓存部分结合起来。l根据特征选择方法的不同，有几种方式:1。完整保留特征；2.选择功能；设置不同的选择策略，保留一些特征，丢弃另一些特征；a.比如在词级丢弃权重低的词(I-match)；b.对于瓦片法，可以保留一些瓦片，丢弃另一些瓦片；(1)一种是保留指纹I位为0的瓦片，其他的丢弃；(2)一个是采样每个I带状疱疹，另一个是丢弃；通过这两种方法获得的瓦片式文档的数量是可变的；(3)一种是选择最小的k个瓦片，这将得到固定长度的瓦片数；(4)使用84个RABIN指纹函数计算每个瓦片，保留84个具有最小值的手指。这种方法的长度是固定的。对于瓦片类方法，也可以分为定长与变长块分割算法:快速，但如果内容稍有变化(比如插入或删除一个字符或单词)，其影响会更大。例如瓦片技术及其改进方法(超级瓦片技术)、CSC及其改进方法(CSC-SS)变长算法:速度比较慢，但是内容变化只造成局部影响。如CDC、TTTD等算法评价:为了加快计算速度，一种策略是在特征提取时舍弃一些特征，保留一些特征，通过减少特征的数量来加快计算速度。另一种策略是尽可能增加粒度，比如超级瓦片区、巨型瓦片区甚至基本文档；为了提高算法的效果，策略是采用变长内容切割算法，如CSC算法。这三种策略是加快速度和准确性的方法的发展方向。初步结论如下:1.对于信息检索方法，由于其特征选择是基于词的，计算速度是根本问题，所以基本不实用；2.从使用的信息来看，一个实用的系统应该还是基于仅仅使用文本内容来判断相似度，排除使用链接信息等方法；3.从特征提取的粒度来说，应该是基于SHINLGE类粒度甚至文档级粒度算法；但是，瓦片区的算法应该优先考虑那些丢弃一些特征和变长的算法。4.从去重级别来看，将完全相同的文档和部分相同的文档分开识别，先识别完全相同的文档，会有效加快计算速度；5.考虑到重复数据删除的机会，可以考虑结合后台重复数据删除和实时重复数据删除，增加重复数据删除效果；6.从压缩编码方法来看，最有效的方式可能是拉宾指纹变体算法；7.从聚类方法的角度来看，最有效的方式大概是UNIONFIND算法，目前比较快的算法基本都采用这种算法；8.从整体方法选择上，应选择改进的SHINLGE方法，并在此基础上进一步改进；三。方法效率比较1。shling方法:时间效率O((mn)2)，其中m是瓦片的大小，n是文档的数量。计算时间为:3000万个文档，10台机器算一天，或者1台机器算10天；2.改进的叠瓦方法(关于近似重复网页簇的演化。):时间效率接近线性O(n)，计算时间:1.5亿网页计算3小时；3.IMACH法:最坏情况下时间复杂度为(O(dlogd))，速度较快。4.BLOOMFILTER法:10k数据耗时约66ms考虑到计算效率，速度顺序如下:1。改进的木瓦方法；2.IMATCH方法；3.布鲁姆过滤法；4.木瓦方法； 四。当前代表性解决方案分析。1.瓦片法(1997)A.特征提取瓦片法:所谓瓦片法，类似于自然语言处理中常用的N-GRAM法，即将彼此连续出现的窗口大小为N的单词串视为一个瓦片。两者的区别在于，Shingle是这些字符串的集合，相同的字符串会合并成一个，而N-GRAM没有相同的合并步骤，因为它考虑了文本的线性结构。每个瓦片区都是文档的一个特征，文档由所有这些瓦片区组成。b.40位长的拉宾指纹法压缩编码；至于存储方式，类似于信息检索领域传统的倒排文档技术。仓库(2)编码(构建布隆过滤器集合元素)对分割的片段进行编码。Bloomfilter编码如下:整个文档由片段组成，文档用长度为m的二进制数组表示。当一个元素(内容片段)被编码并插入到集合中时，K个不同的哈希函数被用于编码，并且每个哈希函数将M个位置中的一个设置为1。这种技术被用来判断一个元素是否包含在一个集合中。(3)相似度计算方法bloomfilter法:对于两个编码后的文档(两个长度为m的二进制数组)，通过位逻辑运算和计算，如果两个位置同时为1，则认为这两个文档相似。(四)优点1。文档编码形式简洁，易于存储。2.因为计算相似度是位逻辑运算，所以速度很快。3.与Shingling相比，更容易判断文档包含关系。(一个文档包含另一个短文档)5。内容+链接关系(2003)1。特征提取方法该方法在提取特征时同时考虑了文档的内容因素和链接关系因素。内容因子:文档内容通过随机投影技术从高维空映射到低维空，用实数表示。两个文档的编号映射得越接近，它们就越相似。链接因子:通过考虑类似于PAGERANK的连接关系，将某个网页的内容因子计算得到的分值通过链接传播到其他网页(传播关系见下面公式)，经过多次重复计算得到每个页面的链接分值。2.相似度计算方法。每个文档由一个二进制组组成如果两个文档的每个项目之间的差小于规定值，则判断两个文档相似。3.效果仅采用内容准确率达到90%，两者组合准确率达到93%。可见链接的作用并不明显。这可能和这个方法的链接用法有关，因为是通过链接计算出来的内容。6.I-match方法(2002)(1)I-Match不依赖于完全的信息分析，而是利用数据集的统计特征提取文档的主要特征，丢弃非主要特征。输入一个文档，根据词汇的IDF值过滤掉一些关键特征，计算这个文档的唯一哈希值。那些具有相同散列值的文档是重复的。(2)使用SHA1作为哈希函数，因为它速度快，适合任意长度。SHA-1生成20字节或160位的哈希值，并使用安全的冲突解决算法，因此不同令牌流生成相同哈希值的概率非常低。。Put

欢迎分享，转载请注明来源：内存溢出

原文地址: http://outofmemory.cn/zz/784718.html