网页消重
目录 |
网页消重是指删除重复的网页，在消重后的网页集上建立索引再提供服务，可以保证用户查询时不会出现大量重复的内容，同时也减少了存储空间。
网页消重的原因[1]
搜索过程中产生重复的原因主要有两个，一个是由于URL本身的构造原因产生搜索结果重复。例如，虚拟主机技术可能会使得多个不同域名映射到同一个IP，当搜索系统用这些域名进行搜索时，实际上搜索到的是同一个站点，导致搜索结果重复。这一类由于URL本身导致网页重复的问题相对来说比较容易解决，例如，可以通过建立IP与域名的对应表、比较网站前几页网页代码等方式解决。
网页重复的另一个重要原因是不同网站之间对相同的内容重复引用或同一站点在不同物理位置的镜像等而导致的，这对于一些热点内容和重要站点尤其如此。对于这类情况，由于大量重复网页不是直接对原有网页进行复制，而是将转载引用的内容放到自己网页的某个特定位置再提供给用户，或者在镜像时定制了网页的内容。这样，新的网页就可能在风格、布局、代码方面与原有网页有很大的差别，因而不能使用网页的形式特征来对网页消重，消重的依据只能是根据网页的内容特征。
网页消重的运用[1]
一般而言，基于内容的消重技术的基本思想是：为每一个网页计算出一组指纹(Fingerprint)，所谓指纹信息是指网页文本的一种信息特征，通常由一组词或者一组词加权重构成。从理论上说，不同网页的指纹是不同的，若两个网页指纹相同或相近，则可以认为这两个文档的内容重叠性较高，进而考虑进行消重操作。
常用的基于内容的网页消重有两个关键的方面，一是如何生成网页的指纹，二是如何通过比较指纹来判断网页是否重复。
生成网页的指纹有多种算法，使用比较广泛的算法有MD5散列值算法。MD5的全称是Message-Digest Algorithm5(信息—摘要算法)，由美国麻省理工学院于20世纪90年代初开发，经MD2、MD3和MD4发展而来。Message-Digest泛指字节串的Hash变换，就是把一个任意长度的字节串变换成一定长的大整数。可以用MD5算法对网页的文本产生指纹，通过比较不同文本的指纹，可以判断两个页面是否是相同的页面。MD5算法及其C语言实现源代码在RFC 1321(http：／／www．faqs．org／rfes／rfcl321．html)中有详细的描述。
第二个要解决的问题是用什么样的标准去判定两个网页是相同的。以MD5算法为例，由于MD5算法是一种严格的信息加密和防篡改算法，只要摘要内容有一个字节不同，其散列值就会不同，这样，如果用两个网页的全部正文的字节串作为生成指纹的内容，就很难保证能够尽量区分出的近似网页，因为，只要文本字节串稍有不同，其散列值就会不同。对其他计算指纹的算法也同样存在类似的问题。这样，就需要精心地选择用什么样的文本摘要去生成文本指纹，怎样用指纹进行比较。这方面，研究人员做了大量的工作。
美国斯坦福大学的Shivakumar等人提出了一种全文分段签名方法，其基本思想是把一个网页按一定的原则分成N段(例如每n行作为一段)，然后对每一段进行签名(即计算指纹)，于是每篇文档可以用N个指纹来表示。在进行网页的比较时，若网页N个签名中有M个相同(M是系统定义的阈值)，则认为这些网页是重复的。为了减少比较过程的空间复杂度和时间复杂度，全文分段签名方法还使用由文档标识、段标识和指纹构成的三元组对网页进行排序，避免了对所有网页做两两比较，使算法复杂度有所降低。
北大天网提出了另一种方法，即用向量空间来表示网页的文本内容，用MD5算法计算前N个特征向量的散列值(指纹)，当两个网页的这类指纹相同时，就认为两者互为近似网页。
网页消重的算法[2]
- 1．算法基础
当前比较成功的搜索引擎系统大多是基于关键词匹配和结合向量空间模型来完成用户的检索请求的。典型的系统包括Google和天网系统。通常这类系统在对已抓取回来的网页进行分析时，要提取网页中出现的关键词和摘要信息，并以关键词作为网页的特征项。
天网系统在搜集并分析一篇网页时，提取并记录了网页中出现的关键词，同时根据公式赋予每个关键词一个权值，这些关键词的权值构成一个向量空间，可以用来表示该网页。另外，我们还从网页中提取了512个字节的有效文字(指用户实际访问该网页时能看到的文字，在html和其他格式的网页中，有一些用户看不到的文字，它们告诉浏览器该执行什么样的操作及如何显示网页，包括字体、颜色、排版等信息)作摘要。当用户查询时，摘要同网页的标题、URL等信息一起显示给用户，供用户了解网页的内容，选择感兴趣的进行浏览。
- 2．算法描述
考虑到基于关键词匹配的搜索引擎系统的特点，结合使用网页的向量空间模型，我们提出了5种网页消重算法，用于快速、有效地发现Web上的转载网页。下面逐一介绍这几种算法。在以下的描述中，用Pi表示第i个网页，其权值最高的前N个关键词构成的特征项集合为
，其对应的特征向量为
，其摘要用Abstract(Pi)表示，前N个关键词拼接成的宇符串用Concatenate(Ti)表示，而先对前N个关键词按字母序排序后再拼接成的字符串用Concatenate(sort(Ti)表示。另外，用MD5(X)来表示字符串X的MD5散列值，用Mirror(Pi,Pj)表示Pi和Pj互为转载网页，用
表示“若A成立则B成立”。
- 算法1
- 算法2
- 算法3
| (MD5(Concatenate(Ti)) = MD5(Concatenate(Ti))) |  |
 |
- 算法4
| (MD5(Concatenate(sort(Ti))) = MD5(Concatenate(sort(Ti)))) | |
| |
- 算法5
- 3．算法分析
可以看出，我们设计的第1种算法采用了对网页摘要求MD5散列值的方法，当两个网页的散列值(占16个字节)相同时，就认为二者是互为转载的。由于MD5算法的严格性保证了当两个网页的摘要内容有一个字节不同时，其散列值就不同，这样就使得本来应作为转载处理的却没有被确定为转载网页。为此，我们又基于向量空间模型理论，提出了第2种和第5种算法。第5种算法表明，当两个网页的权值最高的前N个关键词集合相同时就认为二者是互为转载的网页。第2种算法比第5种要严格一些，它不仅要求两个转载网页的前N个关键词相同，其顺序也是一致的(按权值排序)，因而第2种算法有可能会漏掉一些转载网页。
算法2和算法5都只是要求转载网页的前N个特征项相同，没有考虑到这些特征项所构成向量的夹角大小。算法3和算法4则分别在算法2和算法5的基础上分别考虑了两个网页特征向量的相似度。但向量相似度的计算并没有使用夹角余弦值来定义，因为它只度量了两个向量的夹角大小，而没有考虑向量的长度。我们认为只有当两个向量的夹角小，同时其长度相差也小时，二者才是相似的。针对这一点，我们又设计了判断两个向量相似度的方法，即算法3和算法4的第二个条件
可以看出，SIM能够同时兼顾向量的夹角和长度两个因素。当两个网页内容毫不相关时(即它们的关键词集合没有交集)，Wi与Wj垂直，SIM的值为l。当两个网页相同时，SIM为0。当两个网页相似而不相同时，SIM的值介于0和1之间，于是SIM的值成为判断两个网页相似度的标准。另外，类似于算法5是对算法2的条件放松，算法4也是对算法3的放松。
后四种算法都对向量空间模型理论作了较大的简化。首先，我们只从网页中出现的所有关键词组成的M个特征向量提取了前N个(N<M)，这把理论模型的限制放松了。之所以可以这样做是因为：
1)特征向量的前N个分量绝对值大，基本能确定特征向量的方向。取较少的关键词能减少算法的复杂度。尽管有可能降低其准确度，降低多少，后面的实验将对其作出评测。
2)转载网页的制作人，对网页稍加改动变成相似网页时，不能改变其基本意思。而网页的基本意思一般通过其中出现的高频词来反映。后面的(M—N)个词出现的次数为l或2，相对而言，这些词的出现是不稳定的，当使用这些词来判断相似网页时，反而会漏掉一大批相似网页。
其次，后4种算法都要求前N个关键词组成的集合要相同。这却把理论模型的限制加强了。这主要是由于对算法复杂度的考虑，判断两集合交集大小需要先求出它们的交集。求交集运算的复杂度较大，而把一百万网页两两求交集，其10lz量级的运算量是我们不敢提及的。我们只能考虑用MD5算法对集合签名，实际上就是对关键词序列签名，来表示集合的相同与不同。签名算法有极高的敏感性，作用对象稍有不同就会给结果带来很大的差异，并且不可能从签名差异的大小来判断原签名对象差异的大小。作这样的简化后，有可能出现这样的情况，位置在N附近的词在排序上出现的微小变动，如第N个词与第N+1个词位置互换了，本来是两篇相似度很高的文章，可能会被我们的算法漏掉。这对算法的影响到底有多大，我们仍需通过实验来评测。