【毕业学位论文】（Word原稿）近似镜像网页检测算法及其评测-计算机网络技术

中文摘要 I 近似 镜像 网页检测 算法 及其 评测中文摘要 I 摘 要 随 着 网页数量的急剧增长，近似镜像（ 页的数量也在不断增加。近似镜像网页的存在，严重影响了搜索引擎的检索结果。如果我们能将 搜集到的网页中的 近似 镜像网页去掉， 可以提高搜集系统和索引系统效率， 用户查询时 也 不会出现大量内容重复的网页。去 除 镜像网页的 算法即是近似镜像网页检测算法。 本文 在大量实验和真实数据分析的基础上，得到了如下研究成果和结论： 1) 提出了一种全文分块签名的多指纹近似镜像网页检测算法。该算法利用 网页 的 标签树 结构选取文本块 生成 纹序列， 先 通过部分预消重处理 ，然后将预消重处理的结果网页对两两比较得到算法的最终结果 。设网页个数为 N，每个网页的 列长度为 m，则算法的 时间和空间复杂度分别是 )( 22 和 )( 2) 设定了针对近似镜像网页检测算法的评测与比较方法。该方法延续了传统的近似镜像网页检测算法的评测方法，并且重点分析了不同近似镜像检测算法结果的差集， 提出了 相对精确比 的概念，并以次作为算法优劣性的评判标准。 3) 本文在 1,000,000网页的数据集内 评测了全文分块签名的多指纹近似将向网页检测算法的性能，并利用天网现用的近似镜像网页检测算法作为基准程序，进行了优劣性的对比分析。 关键词： 万维网、搜索引擎、近似镜像、 I on to an in If we it we of be on a of of 1) a D5 of a by of in m of 2) By of s a of to is in to 3) to on ,000,000 in 录 录 摘要 . I 英文摘要 ） . 一章 引言 . 1 近似镜像网页背景介绍 . 1 近似镜像网页算法研究现况 . 5 基于内容的近似 镜像 网页检测（ . 5 基于链接 的近似 镜像 网页检测（ . 7 基于链接信息 的近似 镜像 网页检测（ . 8 本文研究的 主要内容 . 8 第二章 相关研究 . 10 相关研究介绍 . 10 本文的贡 献 . 12 第三章 近似镜像网页的定义 . 14 相同网页 . 14 相似网页 . 15 相似网页类 . 17 第四章 近似镜像网页检测算法 . 19 程序流程 . 19 算法描述 . 20 . 20 . 20 算法分析 . 21 第五章 近似镜像网页检测算法的评测 . 24 基准程序 . 24 评测指标的定义 . 25 查准率 （ . 25 查全率 / 覆盖率（ . 26 目 录 算法复杂度（ . 26 差集（ 分析和相对精确比 . 27 第六章 实验结果和结论 . 29 实验数据集 . 29 多指纹镜像网页检测算法的参数分析 . 29 测试数据集大小对实验结果的影响 . 33 同现有程序的比较 . 35 结论 . 36 进一步的工作 . 37 参考文献 . 39 致谢 . 41 第一章 引 言 - 1 - 第一章 引 言 近似镜像网页背景介绍 随着互联网的不断发展 ， 人们越来越多地在互联网上发布和获取信息 。 布、加工和处理的主要平台 。 传统的互联网应用技术大多是基于文档内容的 ， 与经典的信息检索技术和数据库技术有着密切的联系 。 但是 ，互联网中特有的许多问题 ， 使得互联网应用技术很难有效地应用 。 大量重复的网页文档 就是其中的一个 问题 。 我们都知道， 存在网页内容转载的情况，我们把转载的网页称为原始网页的 镜像 。如果是热门话题、重大新闻或经典文章，则转载的频率会很高。因此 ， 存在大量的镜像网页。 并且整个网页集会经常被各个服务器 备份 ，以提供更快的本地访问。 比较常见的 镜像 网页 是 技术文档 。例如 ， 考 手册（ 是一个 25 包含数千个网页的 网页集， 它 在 全球 有 超过 180 个 镜 像 。 其他常见的 镜像 网页 还 有 政府部门的法令、通告 。 例如，公安部颁布的计算机信息网络国际联网安全保护管理办法在国内的网站上有一百二十个镜像 。另外，还有 重大新闻、热点新闻 和 提供一定服务的网站和网页 ， 如 各类提供影视、音乐、图书服务的站点 。 大量的镜像网页并不是对原始网页的简单拷贝，而是将要转载的内容放在新的模板中再提供服务。 我们称这样的网页为近似镜像网页。 通过分析，我们将网上存在的 近似 镜像网页或网页 集 分为以下几种 ： 完全 重复的镜像 网页。例如 法律文件、 热门 网站的镜像站点等等。 产生这些近似 镜像 网页 的原因 一般来说 有： 第一章 引 言 - 2 - 镜像站点 ，即完全相同的网页存在于网络的不同位置。 动态 动态网页的 不固定的。即同一 个页面可以和多 个对应。 我们访问该页面时，是 应用 数来打开该内容的详细资料页面。 一般情况下，整个互联网上静态网页比动态网页质量要高很多。因此 ，很多 搜索引擎会优先收录静态网页，而在搜索结果中 ， 静态网页往往也比相同的内容的动态网页排名要靠前。 非法的重复： 网络 垃圾 、陷阱站点 等。 些站点甚至可生成无穷无尽、对搜索引擎毫无意义的网页，这些站点构成网页搜集系统的陷阱。一些提供数据库查询的网站便是典型的例子。 部分重复， 即 近似镜像 的网页。这些网页可能是在模板、格 式、站点管理员签名等方面 有所改动，但是网页正文部分的内容是几乎完全相同的。例如 ，相同的文档可能在网上存在不同格式的版本 。这些网页也有可能是内容部分重复的网页。例如未更新的文档 。这些 近似镜像 的网页正是本文研究 的重点和难点。产生这些 近似 镜像的 网页 的原因可能有： 更新频率：一个网页集的主要备份通常被及时更新，但是 其 镜像备份 可能 几 天、 几 周、 几各 月才被更新一次。 这些成套网页集的镜像备份由于其更新频率过低而通常是 过时的。 部分 镜像：每个镜像网页集覆盖主要备份的程度都是不同的。大多数情况下，网页集 合 是 被 全部 镜像 的 。在其他一些情况下，只有部分 网页 被拷贝，并且保留了 指向 其他镜像站点或是主要备份的 链接 。 不同的格式：主要 网页 和 备份 网页的格式可能是不一样的 。例如，一个网页可能用的是 件，而另一个采用 者式。 对于我们在搜索引擎方面的应用来说，我们希望不同格式的两个网页是“相似的”。 第一章 引 言 - 3 - 不同模板：商业网站中的网页通常都是 由 同一个模板 自动 生成的。这些网页被加入了一些导航条、广告、图片 、版权信息 等 网页 噪音 。 这样它们就会 和 其他网站中相同内容的网页 有 一 些 不同。 部分抓取： 搜集端可能 没有 足够 的资源来获取所有的数据 ，或者搜集端本身出现错误 。所以即使两个网页是完全重复的， 搜集端所抓取到的网页也可能 是 不一样的。 随着 站点和网页的增加， 近似 镜像 网页 的存在越来越引起了人们的重视。 人在 1996 年对 集到的 30,000,000 个网页进行实验得出结论：有近 18的网页是完全相同的。有 41的网页是具有 50的相似性et 1997。 人在 1999 年利用 索到的 25,000,000 个网页的数据集统计 得出 约 48的网页是重复的 et 2000。 国内的网页重复现象更为严重， 中国互联网上从 2002 年 12 月 至 2003 年 4月的 网页，去掉 完全拷贝 的 镜像网页后只剩 3000 万，再去掉转载 形成的近似镜像网页 后只剩余 1800 万。 从上面的数字我们可以看出， 随着互联网上网页的增多， 近似 镜像 网页 所占的比例也在 不断 增 大 。 近似 镜像 网页 的存在 已经成为了一个很严重的问题 。 它所带来的 代价就是： 资源的 浪费 ： 花费大量的时间抓取重复的网页并花费大量的磁 盘空间存取 ； 索 引负担 ： 建立索引时，必须对大量的重复网页建立索引，使倒排文件变得庞大 ； 影响服务效果 ： 庞大的倒排文件直接影响提供服务时的响应速度，并且检索结果中会出现大量的重复结果，毫无价值 ，降低用户满意 程 度。 第一章 引 言 - 4 - 所以， 如何快速准确地发现这些内容上 近似 镜像 网页 已经成为提高搜索引擎服务质量的关键技术之一。 近似 镜像 网页 检测 算法， 就是在这样的需求下产生的 。 近似 镜像 网页 检测算法，就是在给定大数据量的随机文件（即网页）的数据集， 从中发现 近似 镜像 网页 的算法。 在搜索引擎中， 如果我们能将 搜集到的网页中的 近似 镜像网页 去掉，而后再建索引提供服务， 这样 用户查询时 就 不会出现大量内容重复的网页。这个去 除 镜像网页的过程被称为 消重 。 所以，我们有时也称近似镜像网页检测算法为消重算法。 近似 镜像 网页 检测 算法 的目的是自动的识别网上的重复的文档，这样以下方面的任务就可以被更有效地执行。 网页存储： 近似镜像 网页 的 存储浪费了大量的空间。 如果我们能够找出这些 近似 镜像 网页 并从数据库中去掉，就能够节省一部分存储空间，进而可以存放更多的有效网页内容，同时也提高了 索的质量。 网页 搜集 ： 网页 搜集 器 为搜索 引擎及其他数据挖掘应用获取网页。 如果 我们能够通过对以往搜集信息的分析，预先发现 近似 镜像 网页 ，在今后的网页搜集过程中就可以避开这些重复的网页或者整个网页集，从而提高有效网页的搜集速度， 网页 搜集器 将可以更快的完成它的工作。 另外，如果某个网页的镜像度较高，也就预示着该网页相对重要。如果搜集网页时赋予它较高的优先级， 搜集器 在相同时间内就可以搜集到更多的重要网页。 网页排名： 在通常意义下， 镜像 度越高的网页越重要。 所以查询结果可以根据重复系数排名。 当搜索引擎系统在响应用户的检索请求并对输出结果排序时，应该赋予它较高的权值。另外， 如果 我们能发现近似镜像 的 网页 类 ，那么把它显示在查询结果里，或者提供整个 镜像 网页 类 的入口，将会是非常有用的。 网页 博物馆 ： 网页 博物馆或者档案 馆是 以 历史性的目的，存储现 在 引 言 - 5 - 的一个子集。如果网页 博物 馆不能存储整个的网络的话，它将优先存储那些已知 存在镜像 的 网页，尤其是 存在 镜像 的 网页集，因为 它 们展示的 是 一个连贯的知识 体系， 具有一定的重要性。 似 镜像 网页检测算法 研究现况 如果我们对于现有的各种 近似 镜像 网页 检测 算法进行整理分类，将得到以下几种主要的研究方向。 于内容的近似 镜像 网页检测（ 基于 关键词提取 的 近似 镜像 网页 检测 当前比较成功的搜索引擎系统大多是基于关键词匹配来完成用户的检索请求的。典型的系统即是北大的“天网”系统 天网 。通常这类系统在对已抓取回来的网页进行分析时，要提取网页中出现的关键词和摘要信息，并以关键词 或者摘要 作为网页的特征项 。 1. . . 30 29 20 . 1 网 页 的 向 量 空 间 表 示 第一章 引 言 - 6 - 如果我们令 ,., 21 来表示网页的集合， ,., 21 表示特征项集，它由网页集中的所有或部分特征项组成 。如图 示， 网页 特征项空间中的向量 ., 21 表示，其中： )( (示特征项 网页 的权值， 示特征项 网页 出现的频率，称为 项频， 表示网页集 P 中出现了特征项 网页数目的倒数，称为反向网页频率。 在很多的文档自动分类系统中，任意两个网页 相似度通常用其对应向量 夹角余弦值来定义（如公 式 (示） ，向量夹角越小（即夹角余弦值越大）表明其相似度越高。 ),c o s (et 2000 提 出了基于 文档向量空间模型 （ 的 5 种 近似镜像网页检测算法，并利用 2000 年的 “天网” 搜索引擎 系统 天网 对这 5 种算法进行了实际评测。 这些方法 被证明 是非常成功的，能够以极小的时间复杂度和空 间复杂度来获得较高的 查全率 ，同时保持了很高的 查准 度。 北大天网搜索引擎 系统 的现在所用 近似 镜像 网页 检测 算法就是在基于 et 2000算法基础上考虑了 网页噪音消除 后 的算法。本文就是该 算法 作为评测算法的基准程序的。 详 见 节。 基于 全文 分 段 匹配 的 近似 镜像 网页 检测 这类算法 采用 的是 一种对全文分段签名的 方法 。这种算法把一篇网页按一定的原则分成 m 段（如每 n 行作为一段 ，或利用文本的自然段等等 ），然后对每一段进行签名（即计算指纹），于是每一篇文档就可以用 对于两篇文档，当它们的 m 个签名中有 t 个相同时（ t 是系统定义的阈值），则第一章 引 言 - 7 - 认为它们是互为 近似 镜像网页 。 1998 提出的 近似镜像网页检测 算法就是一种全文分段签名的算法。作者使用的是将全文每 n 行作为一段的分段方法。 他还比较了 参数 n 的选择 对于 近似 镜像 网页检测效果的影响。 例如，将 全文做一 整段、每四行做一段、每两行做一段 等等 。 该算法使用对 三元组排序的方法避免了对所有网页作两 两比较，使算法复杂度有所降低。 本文所提出的 近似 镜像 网页 检测算法， 也 是 一种全文 分 块 的 近似 镜像 网页 检测算法。 并且 我们 针对海量数据的特点 将算法 做了一些优化。 基于模板消噪的 近似 镜像 网页 检测 模版 因素给 近似 镜像 网页 检测 算法 的准确性有 很大的影响。 由于大量的 近似镜像网页并不是对原始网页的简单拷贝，而是将要 转载的内容放在新的模板中再提供服务。因此模板中的内容就会干扰 算法 程序对 近似镜像 网页的判断，从而导致错误 的检测结果 。常见的错误 结果 有以下两种情况： 相同的主题内容，由于放在了不同的模板中（噪音内容不同）导致应 该被消掉但实际上被 近似 镜像 网页 检测 程序判断为非镜像网页而保留； 不同的内容，由于放在了相同的模板中导致不应该被消掉但实际上被 近似镜像网页检测程序 判断为镜像网页而消掉 。 基于模板 噪 音消除 的 近似 镜像 网页 检测 就是 先对网页进行净化，去掉网页的模板 噪音 内容，进而提取出网页的正文，然后 再结合其他 近似镜像网页检测 方法对网页的正文进行消重 的方法 。 于 链接 的 近 似镜像 网页 检测 （ 这里的链接，指的是 网页的入链。 我们可以用 所有连向 网页 u 的 网页 的标识 ,例如 为网页 如果两篇网 页中的 具有相近的特征项 ，我们就第一章 引 言 - 8 - 可以说两个网页是 近 似 的。 正如 1999的 研究显示 ， 基于连接的 近似 镜像 网页 检测 方法的缺点是那些只有少量入链的网页只有很少的引用数据，它们 一般不会 出现在查询中，也不可能显示在查询结果中。这样 ，那些还没有被其他网页链接的新网页就不可能在 近似 镜像 网页 检测 结果中显示 了 。 于 链接 信息的 近似 镜像 网页 检测 （ 链接信息，是指 出现或邻近于指向 网页 u 的 链接 边中的文字 。 即常见的链接信息窗口（ 实际上，很多网络信息提取任务都使用了链接信息窗 口 000。链接信息窗口通常包含一个人工创建的目标文 档的摘要。这个摘要包含了很明显的人工总结信息和人工分类信息。 文研究的主要内容 由于 多数 搜索引擎返回结果界面是一个个独立的网页，而不是网页集。所以本文中，我们主要分析针对单个网页的 近似 镜像 网页 检测 算法。关于针对网页集的 近似 镜像 网页 集的 检测 算法，可以参考 et 2000。 我们首先分析了 近似 镜像 网页 的 含义，明确了相同和相似网页的定义 ， 并在此定义的基础上，提出了一 种全文分 块 签名的多指纹 近似 镜像 网页检测算法。该算法利用网页的标签树结构选取文本块生成 纹序列，先通过部分 后将预消重处理的结果网页对两两比较得到算法的最终结果。设网页个数为 N，每个网页的 列长度为 m，则算法的时间和空间复杂度分别是 )( 22 和 )( 然后我们 设定了针对近似镜像网页检测算法的评测与比较方法。该方法延续了传统的近似镜像网页检测算法的评测方法，并且重点分析了不同近似镜像检测算法结果的差集， 提出了相对精确比的概念，并以次作为算法优劣性的评判第一章 引 言 - 9 - 标准。 最后， 本文在 1,000,000 网页的数据集内评测了全文分块签名的多指纹近似将向网页检测算法的性能，并利用天网现用的近似镜像网页检测算法作为基准程序，进行了优劣性的对比分析。 在 第 二 章 中，我们介绍了相关的研究工作，并提出了本文的贡献。在第 三 章中，我们讨论了网页的相似性标准。然后在第 四 章 中，我们介绍了 本文所使用的近似 镜像 网页 检测 算法。在第 五 章 中，我们 分析 了如何 评测 近似 镜像 网页 检测 算法的性能。 以及在第 六 章 中，我们 分析了 实验数据 并得出了结论 。 第 二 章 相关研究 - 10 - 第二章 相 关研究 关研究介绍 国际上对近似镜像文档检测算法的研究最初主要是针对大型文件系统的 ， 后来又被拓展应用于数字化图书馆项目和搜索引擎系统。美国 学的研究人员采用计算文档的重叠程度的方法来发现一个大型文件系统中的相似文件1993。作为 N. 型系统 995, 用于发现相似的数字化文档。 后来 基础上，提出了一种全文分段签名的近似 镜像 网页检测算法 998，并将此用于 统。 现在，世界上成功 的 搜索引擎 一个都有 一套 自己的 近似 镜像 网页检测算法，并不断改进着。 et 1997 提出了 一种有效的 识别文件的文本相似性的方法，并将这种方法用于 集到的 的所有网页。作者首先相对于 定义了与位置无关的 为网上所有资源的标识符。然后作者定义了相似度（ 包含度（ 个数学标准来度量文本之间的相似性。通过 计算所有网页对的相似度和包含度，作者识别了所有相似网页对，并 建立了所有相似网页类。并且将结果用于“ 务、网页搜索结果 的过滤 、广泛分布的镜像文件 的更新 和违反知识产权的剽窃行为 的检测 等等应用。 et 2000对 型系统的近似镜像检测算法 995 作了 进一步 改进 ，并应用于 学开发的 章 相关研究 - 11 - 搜索引擎系统 文章 提出了如何利用重复文本集和超文本网页集来提高搜索引擎抓取器、网页档案馆和网页排名函数等应用的效果。文章首先定义了 近似 镜像 网页 集的概念，并提出了一种有效的识别 近似 镜像 网页 集的算法。 这是一种 增式搜索最优子图的算法。对于处理大量网页十分有效。 作者 利用 集到的 25,000,000 个网页，约 150 数据集做了 实验 。 使用 不同 参数的 近似镜像 网页 检测 查重算法， 作者得 出 结论： 25,000,000 个网页中有 36 48的网页是重复的。 并且通过分析实验结果， 将这些网页集分为大量重复的网页集，多名服务器和噪音 等 种类 。 作者还 利用 近似 镜像 网页 集的结果改进了两个实际应用。 利用重复或相似网页的结果， 工作量减少了 40 。 相同时间内，搜集 器 抓取 到 35,000,000 个网页，约 250在 这些网页中，重复率由 48降低到 13 。并且消除了重复文档的 查询结果界面更加有序且方便于用户。 et 2000 利用文档的向量空间的表示， 为基于关键词匹配的搜索引擎系统提出了 5 种近似镜像网页检测算法，并利用“天网”系统 天网 对这 5 种算法进行了实际评测。另外 作者 还将它们与现有的方法进行了对比分析。 实际评测以及与现有方法进行对比分析后，表明这些方法是非常成功的，能够以极小的时间复杂度和空间复杂度来获得较高的 查全率 ，同时保持了很高的 查准率 。 文 章 所论述的近似镜像检测算法已成功地被用于消除“天网” 搜索引擎 系统的 近似 镜像 网页 ，同时它们也可广泛应用于数字化图书馆的搭建。 et 2004 针对 需求，设计了一种网页预处理的框架和方法。其预处理包括三个方面：网页净化，网页消重和网页整合，并最后将网页转化为一种通用的 式。算法首先对网页进行标签树构造，然后对标签树中的结点进行剪裁以达到净化的目的。算法针对主题网页、目录性网页和图片网页的不同特征，采用了不同的净化方法。该方法已经应用于天网搜索引擎系统的网页消重过程和网页自动分类系统。 “天网”搜索引擎系统现第 二 章 相关研究 - 12 - 在已经采用了这种预处理的框架。 本文采用的基准算法即是的 其中 包括网页净化的消重算法。 文的贡 献 从 近似 镜像 网页 检测 的背景和相关研究，我们可以看到 本 文的贡献在于： 可计算的相似性的衡量标准： 我们 精化 了 相同和 相似 网页 的标准。这个标准，除了是一个“ 正确 ”的标准外，我们还能有效地在 以上 的硬盘数据上进行计算。 我们的定义是精确性和在海量数据上的可计算性的折衷。 因为 网上的数据量是惊人的，大约在几亿网页和几百 数量级上，并且还在迅速增长着。所以，无论我们用什么 标准来定义 重复的网页，我们必须针对这么大的数据量。 对于多 指纹的 近似 镜像 网页 检测 的优化： 多 指纹 的 近似 镜像 网页检测算法 都基于这样 一个基本思想：为每个文档计算出一组指纹（ 若两个文档拥有一定数量的相同指纹，则认为这两个文档的内容重叠性较高，也即 两者是 互为 近似 镜像 的 。 假设数据集为 我们为每个网页生成 对于 似 镜像 的时间代价就是 )( 22 这样的计算量，对于 N 为上亿 个 数据集来说是不可能完成的。 所以， 一般的全文签名算法 都会对数据作一些处理以降低算法的复杂度 。1998 的 算法使用对 三元组排序的方法避免了对所有网页作两两比较，使算法复杂度有所降低。但是该算法的空间复杂度和时间复杂度仍然是相当大的，若应用于海量的搜索引擎系统，仍然难以取得理想的效果。 我们的算法在生成每个网页的指纹的时候，对于这 章 相关研究 - 13 - 序（例如可按照所对应文本块的大小）。这样，在比较网页指纹组的时候，我们只对于在前 0对于 任何一个 超文本链接 存在 得 M( 需要说明的是，我们定义两个超文本链接是相同的，当且仅当这两个超文本链接在各 自文本中所在的位置是相同的，它们的连接信息是相同的，并且它们所指向的页 面 是相同的。 正如我们在引 言 中介绍的，许多对于 近似镜像 网页的应用并不关心严格的相同 性 。所以，我们需要放宽定义 1来得出我们对于 相 似的网页的定义。 对于定义1 的不同的扩展，就会 得 到不同 的相似网页的定义和基于这个定义之上的 近似 镜像 网页 检测 算法。 因为存在各 种 方法来放宽这个定义，我们需要遵循两条原则： 我们需要一个符合我们直觉的相似性定义。也就是说，我们对于网页集的相似性定义，必须同我们实 际生活中说“两个复制很接近”相吻合。 我们必须能够在 大量网页上有效并且自动地计算其相似性。 在第 三章 的剩下的篇幅，我们将讨论符合这两条标准的扩展性定义。 第 三 章 相似网页的定义 - 15 - 似 网页 由定义 1 可以看出，对于定义 1 的放宽，包括对于网页内容和网页链接结构两方面定义的放松。在本文中， 我们主要 讨论 对于网页文本内容相似方面的扩展 ，而不考虑网页中所包含的超文本链接和链接信息等。 针对超文本链接和链接信息的相似网页的定义可以参考 1999。 所以 在本文中 ， 如果没有明确说明， 我们 所指的 网页是它的文本内容。 我们可以用很多种方式来定义两个网页 文本 内容 的相似性。例如，我们可以用信息提取中的 文档向量空间模型 的定义 计算两个网页向量的夹角来决定 网页的相似度 。我们也可以用数据挖掘技术 先将 网页 聚类 ，再定义每个组中的网页对为相似。第三个方法就是通过计算各个文章中相同块（例如句子或者段落）的个数来计算文本的重叠率。在所有的方法中，都有一个阈值来标记两个网页的相似程度（例如，相同的单词的个数、 n 维向量的距离或者相同的块的个数）。这个参数需要根据经验值调整以满足不同应用的需要。 即定义 2 的描述。 定义 2（相似的网页） 定义 ST(pi,一 个 判定网页对 (pi,相似程度的测试 ，且 0 ST(pi, 1。当 ST(pi, 1，网页 定一个相似程度测试 ST(pi, 阈值 t， 基于这个测试我们可以说这两个页面pi,果 ST(pi, t。记作 pi 在先前的工作 995 中，我们已经知道了这个对于近似 镜像 网页定义有效地接近了人们现实中对于相似内容的网页的定义。（这些文章中也讨论了如何进行文本块和阈值 et 1997 也报道了相似的结果。并且，这些参考文献同样显示了进行相似性检测的代价是很低的，所以在很大的网页集中计算页面的相似性是可行的。所以，我们在实验中采用的正是这种相似性的定义。 第 三 章 相似网页的定义 - 16 - 正如我们前面所说的，对于文本的相似性计算主要有计算空间向量夹角，聚类和计算文本重叠度三种方法。 et 2000和 et 2004采用的是基于文档向量空间模型的单 像 网页检测算法，但是由于 单指纹的方法很敏感，只要提取的关键词不同，那么生成的指纹一定不同。而且 ，指纹的差别不能体现网页的差别。 所以我们希望用多 对于聚类的方法 ，多用于 数据库记录的消重。由于聚类需要 )( 2相似度计算，因此开销很大。对于数据库记录还可以接受，但对于文档则比较困难。 所以我们在实验中使用的是计算文本重叠率的方法，并 扩展了 这个 方法 。为了计算文本的重叠率，我们首先 进行网页格式分析， 把每个 式的原始网页按照其 内部 标签 建立网页的标签树，提取标题和正文的文本 块 。 对于 每个文本块 ，我们生成一个 16 位的 纹。如果两个页面有多 于阈值 t 个的具有相同指纹的块，那么我们就称这两个页面是相似的。 定义 3 描述的就是我们算法的基本思想。 定义 3 定义 m (m 1)个 纹 的 测试 pi,下：假设 网页 个网页块 2, 页块按重要性排序），取前 m（ 网页块生成 纹 对于网页对 (pi,定义 pi, m0/m，其中 pi,个数。易得，给定 阈值 t，如果 pi,t， 则称 这两个页面 pi,作 pi 对于 大规模的网页 集合 来说，不能否认， m 个 纹 的 近似 镜像 网页 检测 算法的时间代价比较高，对于数量为 N 的网页集合来说，其时间代价为)( 22 我们可以对 m 个 纹 近似 镜像 网页 检测 算法进行合理的简化，以得到更更高的性能。最简单的例子是取 m=1，用单一的 纹 作为网页的指纹 ，即是常说的单 似 镜像 网页 检测 。但是由于 敏感性比较高，单 丢失文本中的一些信息，所以 近似 镜像 网页 检测 的准确性没有多 章 相似网页的定义 - 17 - 近似 镜像 网页 检测 的好（见 第六 章 的实验数据分析）。 尽管用代价高的算法性能可能会受影响， 我们需要在 近似 镜像 网页 检测 准确性和时间 复杂度 之间作一个权衡。 似 网页 类 显然 ，网页的相同性具有传递性，那么网页的相似性是否具有传递性呢？按照我们直观的理解，网页的相似性是具有传递性的，即对于任意三个网页 果 且 有 但是定义 2， 3 中对于网页的相似性的定义并不具有严格的传递性。即可能出现这种情况：存在 3 个网页， 似于 似于 是 不相似。那么我们是 希望这三个网页是相似的，还是希望仅仅考虑两个相似对？我们的选择是希望判断这三