基于关键长句及正文长度预分类的网页去重算法研究

摘要：伴随互联网所包含网页数目的剧增，转载现象变得相当普遍。作为提高搜索引擎服务质量的关键问题之一，网页去重技术已经成为网页信息处理最为重要的环节。在对传统网页去重技术进行研究的基础上，针对网页正文的结构特征，提出了一种基于关键长句及正文长度预分类的网页去重算法的核心思想。实验证明，该算法具有较高的召回率及准确率，在重复网页的过滤中有着较好的应用前景与较高的研究价值。

关键词：网页去重；关键长句；预分类

中图分类号：TP312文献标识码：A文章编号：1672-7800（2012）010-0048-03

作者简介：周杨（1979-），女，硕士，军事经济学院基础部计算机教研室副教授，研究方向为网络安全。

0引言

互联网的持续高速发展致使网站数目及其包含的网页数目均呈爆炸式增长。为了使用户在海量信息中快速找到自己感兴趣的内容，搜索引擎应运而生，其重要使命在于准确、高效地为用户反馈有用的搜索结果。而在网页数目剧增的同时，转载现象也变得相当普遍。据统计，中国互联网中网页的重复率高达40%，搜索引擎的搜索结果中常会出现很多重复记录，这些重复信息不仅增加了搜索引擎的存储负担及查询效率，也使用户的体验度大大降低。因此，如何快速、准确地发现内容相似的网页已经成为提高搜索引擎服务质量的关键问题之一，而网页去重技术也无疑成为网页信息处理最为重要的环节。

1网页去重技术的主要流程

网页去重即是将所搜集到网页中的镜像及转载网页去掉的过程。几乎所有的网页去重技术都是基于这样一个基本思想：为每个网页文档计算出一组指纹，若两个文档拥有一定数量的相同指纹，则认为这两个文档的内容重叠性较高，也即二者是重复网页。

网页去重的主要流程包括网页去噪、特征提取、编码压缩、网页相似度计算及相似文档聚类等5个基本步骤，如图1所示。其中，网页去噪负责剔除网页中的干扰信息（导航、广告等）并提取文档的正文信息，以便提高网页解析的准确度；特征提取则是从网页文档中提取出可以表征网页信息的特征值，它可以是网页中的若干个片段或若干个词语，这些特征值组成一个特征向量，该特征向量主要用于计算网页间的相似度。为了便于向量间相似度的计算，所得到的特征向量通常都需要进行编码压缩处理（如用哈希函数将文字特征串转化为数字串），这样不仅便于文档的特征存储，也可以提高相似度的计算效率。网页间相似度的计算便是根据所提取的网页特征码，利用相似度计算函数计算网页间的相似性，计算方法会因特征码及其生成策略的不同而不同。相似文档的聚类是通过迭代网页相似度的计算过程，将相似的网页集合归为一类，这样一来，在搜索过程中搜索引擎便不会将相似的网页进行重复展示。

2基于关键长句及正文长度预分类的网页去重算法的核心思想

网页去重的关键是正文特征的提取及大规模内容的快速计算，其技术难点是如何有效提取出文档的特征码，并以此为依据进行查找，发现是否存在相似的文档。传统的文档特征提取技术主要包括基于上下文及基于语义两大类。基于上下文的文档特征提取技术，主要依据相似文档之间变动较小的特点，将文档中连续的一段词作为一个特征值；而基于语义的文档特征提取技术，则主要依据相似文档的主题内容应当相同，出现的关键词也应当相似的思想，将文档中重要性较高的词作为特征值来计算网页的相似度。这两种方法都存在各自的不足之处。基于上下文的特征提取方法没有考虑到文档所包含词语的语义信息，因此只能靠增加特征的数目来达到表征整个网页的内容信息，致使算法的效率及准确率均受到影响；而基于语义的特征提取方法虽然考虑了文档中词语重要性的不同，并且能够尽量选取重要性高的词语作为文档的特征值，但该方法并没有考虑到这些词语所处的上下文环境，因此会导致将两篇同一主题但并不重复的网页误判为重复。

网页去重算法通常运行于海量数据集中，因此，在设计算法时，不仅应考虑去重结果的好坏，还应考虑去重算法的运行效率。基于以上两类特征提取算法的优点及其所存在的不足之处，这里提出一种基于关键长句与长度预分类的网页去重算法，该方法能够有效提高网页去重的准确度及效率。

2.1基于关键长句的网页特征码提取

关键长句是指网页正文中包含关键词的最长句子，若同时包含多个关键词，则以权重大的关键词为准。这里的关键词是通过权重计算所得到的权重值较大的词语，当一个句子包含多个关键词时，以权重值较大的关键词为准是为了扩大长句的分布范围，从而达到提高表征度的目的。

2.2基于正文长度预分类的相似度计算

在传统的去重算法中，要判断一个新网页是否与本地库中的已有网页相似，通常需将该网页的特征码与库中所有网页的特征码进行对比，网页库越大，比较效率越低。由于网页搜索结果去重主要针对的是转载等相似度较高的情况，而相似网页都应具有相似的文章长度。若将网页按正文长度划分成不同的集合，那么在判断网页相似性的时候，则只需判断长度相近的集合内的网页，而不用与所有网页进行比较。这样就能够在一定程度上降低比较基数，从而提高效率。

根据对网页正文长度进行统计的实验结果，网页正文长度主要集中在300（字符）到4000之间。若将第一个文档区间的长度上限设为300，将相似度阈值设置为较为合理的0.8（微软亚洲研究院对去重算法参数调整的研究结果），根据这两个初始值，可依次得到后继文档的正文长度区间。对本地库中的100000个网页集合进行测试，得到其正文长度分布如图2所示。从该图中可以看出，依据相似度阈值理论进行正文长度区间的划分，其边界的设定更为合理，网页文档的分布相对均匀，因此有利于整体查找效率的提高。

2.3实验测试与分析

在实验中，首先用网页正文提取算法对人工挑选的重复网页集进行处理，再利用本文中的算法去处理这个混合的网页集合，最后经过人工对比，得到实验结果。实验中的重复网页集合是163对从百度和谷歌搜索得到的、经过人工筛选的重复网页，这些网页的正文长度分布均匀。将这些重复网页放入一个包含3000个网页的网页集中，这3326个网页便构成了用于测试与评估的网页数据集。

评估标准包括准确率（Precision）、召回率（Recall）和运行效率，这三项指标是去重领域算法的通用评估标准。由于本文的算法是对传统基于特征码算法（简称算法1）的一种综合改进，因此，这里主要是将基于关键长句及正文长度预分类的算法（简称算法2）与算法1进行对比。从表1可以看出，算法2的去重时间要明显低于算法1，而其正确率与召回率都明显高于算法1。

3结语

本文在研究传统网页去重技术的基础上提出了一种基于关键长句及正文长度预分类的网页去重算法。该算法结合了基于上下文及基于语义特征提取技术的优点，同时发挥语义的重要性及上下文之间的联系性，减少了所需特征的数量，大大提高了特征提取的准确度及效率。实验表明，该算法具有较高的召回率和准确率，在重复网页的过滤中有着很好的应用前景及较高的研究价值。未来网页去重的主要工作是借助大规模试验，进一步分析影响去重效果的因素，改善TF-IDF算法提取关键词的效率，并针对网页正文分页分布的情况，不断改进网页搜索策略，从而获取更优的网页去重算法。

参考文献：

[1]谢蕙，秦杰.基于元搜索的网页消重方法研究[J].计算机系统应用，2008（8）.

[2]张刚，刘挺.大规模网页快速去重算法[C].中国中文信息学会二十周年学术会议论文集（续集），2001.

[3]魏丽霞，郑家恒.基于网页文本结构的网页去重算法[J].计算机应用，2007（11）.

[4]吴平博，陈群秀，马亮.基于特征串的大规模中文网页快速去重算法研究[J].中文信息学报，2003（2）.