搜索引擎网页去重算法分析

相关统计数据表明：互联网上近似重复的网页的数量占网页总数量的比例高达29{35d70732d1fe98e5cfea42b59418971da2b3cae7b4dfd8d770b8943d5ba7ed7b}，完全相同的网页大约占网页总数量的22{35d70732d1fe98e5cfea42b59418971da2b3cae7b4dfd8d770b8943d5ba7ed7b}.研究表明，在一个大型的信息采集系统中，30{35d70732d1fe98e5cfea42b59418971da2b3cae7b4dfd8d770b8943d5ba7ed7b}的网页是和另外70{35d70732d1fe98e5cfea42b59418971da2b3cae7b4dfd8d770b8943d5ba7ed7b}的网页完全重复或近似重复的。

即：互联网的网页中相当高的比例的网页内容是近似相同或完全相同的!

搜索爬虫抓取会产生网页重复的类型：

1.多个URL地址指向同一网页以及镜像站点

如：www.sina.com 和www.sina.com.cn

指向同一个站点。

2. 网页内容重复或近似重复

如抄袭、转摘的内容，垃圾信息等

网页内容近似重复检测的两种应用场合：

一：在用户搜索阶段

目标是根据与用户给定的查询词找到已有索引列表中近似重复的文档，并排序输出。

二：爬虫抓取发现阶段

对一个新的网页，爬虫程序通过网页去重算法，最终决定是否对其索引。

搜索引擎架构

近似重复网页类型，根据文章内容和网页布局格式的组合分为4种形式：

一：两篇文档在内容和布局格式上毫无区别，则这种重复称为完全重复页面。

二：两篇文档内容相同，但布局格式不同，则这种重复称为内容重复页面。

三：两篇文档有部分重要的内容相同，并且布局格式相同，则这种重复称为布局重复页面。

四：两篇文档有部分重要内容相同，但布局格式不同，则这种重复称为部分重复页面。

重复网页对搜索引擎的不利影响：

正常情况下，非常相似的网页内容不能或只能给用户提供少量的新信息，但在对爬虫进行抓取、索引和用户搜索 会消耗大量的服务器资源。

重复网页对搜索引擎的好处：

如果某个网页重复性很高，往往是其内容比较比较受欢迎的一种体现，也预示着该网页相对比较重要。应予以优先收录。当用户搜索时，在输出结果排序时，也应给与较高的权重。

重复文档的处理方式：

1.删除

2.将重复文档分组

近似重复网页举例：

近似重复网页举例

搜索引擎近似重复检测流程：

搜索引擎近似重复检测流程

通用网页去重算法框架：

通用网页去重框架

SimHash文档指纹计算方法

SimHash文档指纹计算方法

说明：

1)从文档中提取具有权值的 特征集合来表示文档。如：假设特征都是由词组成的，词的权值由词频TF 来确定。

2)对每一个词，通过哈希算法生成N位(通常情况是64位或更多)的二进制数值,如上图，以生成8位的二进制值为例。每个词都对应各自不同的二进制值。

3)在N维(上图为8维)的向量V中，分别对每维向量进行计算。如果词相应的比特位的二进制数值为1，则对其特征权值进行加法运算;如果比特位数值为0，则进行减法运算，通过这种方式对向量进行更新。

4)当所有的词都按照上述处理完毕后，如果向量V中第i维是正数，则将N位的指纹中第i位设置为1，否则为0。

Jacccard相似性计算方法：

Jacccard相似性计算方法

如上图，A和B代表2个集合，集合C代表集合A和B相同的部分。 A集合包含5个元素，B集合包含4个元素，而两者相同的元素有2个，即集合C的大小是2. Jaccard计算两个集合相同的元素占总元素的比例。

如图中，集合A和集合B共有7个不同的元素，相同元素个数2个，所以集合A和集合B的相似性为：2/7

在实际应用中，集合A 和 集合B 的特征都会经过哈希计算，转化成N位(64位甚至更多)的二进制数值，从而将集合A和B的相似性比较转化为二进制数值的比较，称为“海明距离”的比较。两个位数相同(如均为64位)相同位置上不同的二进制数值的个数称为“海明距离”。

对给定的文档A，假设经过特征抽取–哈希指纹运算后的二进制数值是：1 0 0 0 0 0 1 0

对给定的文档B, 假设经过特征抽取—哈希指纹运算后的二进制数值是：0 0 1 0 0 0 0 1

经过比较，文档A 和 B的 第1位、第3位、第7位、第8位四个位置的数值不同，即海明距离为4. 两个文档的二进制位数不同的个数越多，海明距离越大。海明距离越大，说明两个文档不相似性越大，反之，则越小。

不同搜索引擎可能会以不同的海明距离值 来判断两个网页内容是否近似重复。相关分析认为，一般情况下，对一个64位的二进制数值来说，将海明距离<=3作为判断是否近似重复的标准比较合理.

作者：AlbertTan

相关阅读：

搜索引擎是怎么删除重复网页的

搜索引擎催生网页垃圾内容

谷歌论文：大规模的超文本网页搜索引擎的分析

百度2013年中国网站发展趋势报告

搜索引擎如何抓取你的网页