文件 1 文件 2 文件 3 文件 4词语 1 1 0 1 0词语 2 0 0 1词语 3 0 1 0—162 —基于内容特征码的重复网页检测方法探析上 海 大 学 东 方 贱 人[摘要]重复网页检测的关键问题是如何有效地提取相似网页内容的特征并对特征进行相似度比较本文概述了重复网页的定 义、检测流程，对重复网页的特征提取方法和比较算法进行了分析，并对目前常用的基于特征的检测算法进行了比较，总结了当前常 用特征提取和比较算法的不足和需要改进之处[关 键 词 ]重 复 网 页 相 似 网 页 特 征 码 算 法1. 引言随着因特网的大规模普及，各种数据资源呈几何爆炸式增长，因特 网已越来越成为人们获取信息的主要手段但是，因为信息在网络上 非常容易转载，致使互联网上充斥着大量的重复网页，有些重复网页拷 贝得一字不差，有的只是稍作修改，比如版本、格式不同，但内容基本是 一样因特网上的重复网页既浪费了太多系统存储资源，又加重了用 户浏览的负担，降低了搜索引擎的索引效率因此，如何检测并有效、 准确、快速地去除重复网页是提高搜索引擎质量的关键技术之一2. 重复网页定义重复网页的定义种类很多有文献引入了一个“相似网页”的数学 模型，相似的度量标准就是两个网页的内容大致相同，换句话说，就是 除了格式、大小写、作者签名等方面作了一些修改外，它们有相同的文 本内容。
而相似度又被精确地定义在介于 0 到 1 之间的一个数，这样 当两个文件的相似度接近 1 时，就很可能具有大致相同的内容，接近 0 时就表示两个文件几乎没有相同的内容本文所指的重复网页是针对网页正文来说的，网页正文基本相同 的网页，正文间的细微差别可能是由于转载时的变更，包括丢字、乱码、 改变了标题或节略造成的3. 重复网页检测流程一般来说，判断一个网页是否与其他网页重复的流程如图 1 所示： 首先将网页分解成由若干特征组成的特征集合，根据不同算法提取进 行重复性判断的网页特征，为了方便存储以及特征比较，加快比较速 度，用Hash 函数等文本向数字串映射的算法将提取的网页特征转化为 一个较易比较的字串(信息指纹），然后根据文档特征重合比例，也就是 这两个字串的相似程度来判断是否属于重复文档4. 检测过程的两个关键环节从相似网页识别所利用的信息看，相似网页识别算法可以分为三 类:基于文本内容的、基于文本内容和链接的及基于文本内容、链接和 URL的目前，相似网页识别算法主要还是基于网页文本内容的确定一个网页是否与另一个网页重复的过程主要有两个关键环 节:特征提取和特征比较4.1 特征提取两个文件是否重复，检测的最关键标准就是判断它们内容的相似 度，并参照一个评估数值来判断，我们把这个数值称为相似度。
这个值 越大，重复成分就越多;值越小，重复成分就越少，只有当两个文件的文 本相似度大于某个阈值时，才能判定它们为重复相似度的计算方法是首先提取两个文件文本的特征提取特征的 方法分为两种：(1)基于字符串比较的方法这是基于语法的一种方法，如 sif， shingling， COPS，MDR，YAP 3，KOALA这类方法要求从文本内容中选 取一些字符串，再把字符串映射到 Hash 函数表里，一个字符串对应一 个数字，最后统计 Hash 函数表中字符串的相同数目或者两者的比率， 作为相似度判定的标准常用简单的计算文本相似度的决策函数如下：第 1 种决策函数为|F(A)|JF(B)|第 2 种决策函数为 .VI(A，B)=|F(A)|^F(B)|令 F(A)表示文档 A 的指纹集，F (B)表示文档 B 的指纹集，S(A，B)表 示文档 A 和 B 的相似度，显然 ，无论哪种决策函数都有 S(A，B)=S(B，A)2)基于词频统计的方法这是基于语义的一种方法，如 CDSDG， CHECKSCAM词频统计法源于向量空间模型技术这种方法先统 计每篇文档中各个单词的出现频率，再依据单词频度形成特征向量，最 后采用点积、余弦或者类似方式度量两篇文档的特征向量，以此作为相 似度的依据。
被选择的特征项应具备下面这样一些特性：① 能够标识文本的主题内容；② 具有与其他文本的主题相区分的能力；③ 个数不能太多；④ 分离要比较容易实现特征选择的主要目的是在不损伤文本核心信息的情况下，尽量减 少处理的特征数目，以此来降低特征比较的维数，从而得以简化计算， 提高文本处理的速度与提高下一步的检索效率4.2 特征比较在相似网页的特征比较环节中，目前常用的主要技术是:编辑距离 算法和向量空间模型① 编辑距离算法这种算法是在两个字符串之间，将一个字符串转换成另一个字符 串编辑操作最少的次数可以使用的操作:用另一个字符替代一个字 符;插入一个字符;删除一个字符案例 1:字符串 A 为“我爰北京”，字符串 B 为“我爰你首都”，计算 A 转换为 B 的编辑距离A 转换为 B 的最小编辑操作：第 1 次:在“爰”字后面插入“你”字；第 2 次:将“北京”两字替换为“首都”两字因此，编辑距离为 2案例 2:有文件 A 和文件 B，计算两者特征之间的编辑距离文件 A 特征:海南景观椰林热带文化演员筹备组酒店陶醉三 亚；文件 B 特征：海南椰林热带文化演员晚会筹备组酒店陶醉三 亚文件 A 转换为文件 B 的最小编辑操作：第 1 次:在“海南”后面删除“景观”；第 2 次:在“演员”后面插入“晚会”。
因此，编辑距离为 2② 向量空间模型向量空间模型算法是每份文件被表示成一个 k 维向量，每一个向 量的值反映相应特征的重要程度(k 值是根据特征选择时所选定的特征 数量来决定）表 1 是一个词语矩阵的向量空间模型，文件中具有语义 代表的词语作为特征词表 1 文件词语矩阵表 1 是一个 3x4 的矩阵，每一行表示一个特征词语在文件中出现 的次数，每一列表示一个文件向量，每份文件被表示为一个 k 维的向量°计算文件向量之间的相似性采用余弦距离的公式：2a12xF1(R)xF1(Q) sim(R,Q) = 1-1 —N N2a2Fi2(R)x2ai2Fi2(Q)1=1 1=1其中，sim(R，Q)代表两个文件的相似性，^表示特征 i 的权值，N 表 示所选择的特征总数，F
向量空间模型或者编辑距 离这两种算法对于海量的网页数据，其工作量相当大，算法的时间复杂 度也都较大，严重影响算法在特征比较环节的效率，势必严重影响检测的效率5.基于特征码算法基于内容相似的网页检测算法中，一般包括采取提取特征，计算相 似度或重复度，去除重复三个步骤以下是常用的几种算法及优缺点SCAM 算法原本是用来剽窃检测的，对于网页的重复检测而言，它 的效率不高，而且用来存储向量要求的空间代价很高，所以使用这种方 法进行重复网页检测技术是得不偿失的DSC 算法效率不高，它的过滤算法常用的是从 25 个 shingles 中随 机抽取出一个 shingle,这样导致正确率不是很高，而且比较的次数过 多，导致效率下降它的改进算法 DSC-SS 是使用 SuperShingles，具体 来讲就是将几个 shingles 合在一起组成一个 supershingle，这样比较的次 数减少，效率提高，但是同时造成了一个问题，即在处理小文件时，出错 的几率比较高，这是 DSC-SS 的缺点I-Match 算法的效率和正确率比较平均，这方面比较理想，但是要 先把所有的文件全部存储在硬盘中，再进行处理，如果是网络中大量的 数据流，全部存储在硬盘上再处理会耗费很多时间，且占用大量的硬盘 空间。
清华大学使用的提取方法就是在文章中逗号、句号的前后各取 2 个汉字，作为字符串哈工大使用的方法则是在文章中每个句号的前 后各取 5个汉字，虽然提取汉字的方法不同，但是都是以标点符号作为 文中的提取标记，这种方法效率较高，因为提取字符串是线性时间的， 就把一个O(n2)时间复杂度的问题，转变成了 O(n)时间复杂度的问题，不 失为一种好方法哈工大在提取特征码时尽量把导航信息等干扰信息去除掉，再把 句号作为一个提取的位置，分别在句号两边提取 L/2 长的词串构成网页 的一个特征码之所以要在句号的两边分别取 L/2 长的词串，是因为在 L/2-1 和 L/2 处的字很难构成一个词，因此更能保证特征码的唯一性基于特征码抽取的网页去重方法，由于该算法将网页文本的比较_____________________________________________________科 技 信 息转化成为句子之间的比较，因此降低了算法的复杂度，该算法对于中文 的去重具有很好的效果，但多语种情况下就存在一些缺点，有很大的局 限性6 结束语基于特征码的网页去重算法，能有效地去除检索结果集合中内容 相同或相近的网页，将这项技术用于网络信息检索系统中，可以提高检 索质量，使返回给用户的结果更为精确，有较好的实际应用前景。
但是，目前大多数算法在检测重复网页特征的比较阶段一般都采 用传统的向量空间模型或编辑距离算法这两种方法都存在一个共同 的问题，就是算法复杂度过大考虑到搜索引擎系统处理的庞大数据 量，这样的时间复杂度和空间复杂度太大，不能满足实际应用的要求 因此，如果能够对其进一步改进，在效率方面将能够大大的提高同时 英文与中文的特征有很大的不同，中文和英文的单词分词方式和所表 达的意思差别很大，对于英文的高效特征提取算法，却可能不太适用于 中文所以现在在重复网页检测技术的研究中极需要一种算法可以兼顾这几方面的效率参考文献[1] 唐蓉.搜索引擎重复网页检测技术研究[D].重庆理工大学硕士 论文，2011.[2] 苏国荣.校园网搜索引擎排序的去重方法研究[D].国防科学技 术大学工程硕士论文,2010.[3] 段飞.相似网页识别算法的研究与实现[D].北京邮电大学硕士 论文，2010.[4] 张长利.网页相似性算法的研究与实现[D].吉林大学硕士论文，2005.[5] 韩冰.大规模文本去重策略研究[D]. 大连理工大学硕士论文，2008.[6] 杨武，唐蓉，任丽芸.重复网页检测算法综述[J].电脑知识与技 术,2010.。