【毕业学位论文】（Word原稿）锚文本在搜索引擎中的存储及应用-计算机系网络与分布式系统

本科生毕业论文 题目 ： (中文 ) 锚 文 本 在 搜 索 引 擎 中 的 存 储 及应用 (英文 ) 名： 张旭东 学 号： 00748015 院 系： 信息科学技术学院 专 业： 计算机科学与技术 指导教师： 闫宏 飞 二一六年七月九日 锚文本在搜索引擎中的存储及 应用 i 摘要 随着互联网的飞速发展，信息检索在实际生活中的作用越来越重要，在学术界也引起了研究学者的重视。互联网规模的不断扩大，使得作为网页之间的链接文本的锚文本的作用越来越大。 针对锚文本在搜索引擎中的研究 近十年才逐步开展起来的。锚文本在搜索引擎应用非常广泛，因此设计一种高效的锚文本的存储结构就显得非常重要。 本文在北京大学网络实验室天网组的智能中文搜索引擎平台 基础上 ，对原有 锚文本的存储结构进行了改进，设计了一 种新的附加信息存储结构，这种结构额外存储了锚文本的附加信息， 且 相比于以往的结构来讲又节省了存储空间。另外，本文使用锚文本新的存储结构在 设计并实现了相应的 检索 打分模块，用于 锚文本的检索。 我们 在 据集上，同时使用 文本新旧存储结构和打分模块，进行了锚文本的构建索引和检索的对比实验，实验结果发现新的结构下锚文本的存 储空间有了显著的减少，锚文本的检索效果相比于原先的检索方法 也有了提高。 关键 词：锚文本 域列表 域 存储 检索 锚文本在搜索引擎中的存储及 应用 i is a in s s in of of is of of in in a in its to an to in is on We of a of of of to as as of In we of on we of of of of of 文本在搜索引擎中的存储及 应用 录 第 1 章 引言 . 1 维网的起源和发展 . 1 息检索和搜索引擎 . 1 文本概述 . 2 文的贡献 . 3 文组织 . 3 第 2 章 相关研究 . 4 文本在搜索引擎中的可行性依据 . 4 文本存储的相关研究 . 5 文本应用的相关研究 . 5 展列表（ . 7 索引擎平台介绍 . 8 第 3 章 锚文本的存储结构及其实现 . 10 原有锚文本的存储结构及缺陷 . 10 有锚文本存储结构 . 10 有存储结构的缺陷 . 11 文本新型存储结构的实现 . 12 型存储结构的设计目标 . 12 型存储结构的设计和实现 . 12 内存中的结构 . 12 磁盘中的结构 . 14 据写入磁盘和从磁盘读取的过程 . 15 第 4 章 文本的检索算法和实现 . 16 原有锚文本检索算法 . 16 型存储结构下锚文本检索算法的实现 . 16 分器 . 16 分器 . 17 外链接静态打分器 . 17 外链接 分器 . 17 态打分器 . 17 . 18 确匹配打分器 . 18 接近打分器 . 18 第 5 章 锚文本的存储和检索的实验及评测 . 20 测集及实验环境介绍 . 20 . 20 锚文本在搜索引擎中的存储及 应用 据集 . 20 询集及标准结果集 . 21 测指标介绍 . 21 . 21 . 22 t k . 22 . 22 . 22 验环境 . 23 文本存储的实验 . 23 验方法 . 23 验结果 . 24 验结果分析 . 25 文本检索的实验 . 26 验方法 . 26 验结果 . 27 验结果分析 . 28 第 6 章 总结及展望 . 30 结 . 30 望 . 30 附录 . 32 文本存储实验中的实验数据 . 32 文本检索实验中的实验数据 . 33 致谢 . 34 参考文献 . 35 锚文本在搜索引擎中的存储及 应用 1 第 1 章 引言 万维网的起源和发展 万维网（ 起源于 1989 年欧洲粒子物理研究室( 万维网 的最初计划是由 物理学家 1989 年 3 月提出的，第一个原型（基于文本）于 18个月后运行。 此后，许多院校和业界公司纷纷加入到万维网的研究中来，开发大量基于万维网的应用程序。 万维网是一个分布式信息系统， 核心技术是超文本和超媒体。 在这样一个系统中 ， 用户可以通过超链接的指引，非常 容易地获取分布在不同机器上的信息；各种不同地区，职业 的人们可以自由地把本地的信息放到这个系统中去。这样，这个系统就成为一个全球区域的，包括大量信息的系统。 万维网 通过将文本、图形、图像 、音频、视频等信息的有机结合，给人们提供了丰富的信息表示空间。 二十多年来，万维网吸引了大量的用户和开发者，使其不断完善发展， 信息容量 有了 巨 大 增 长 。 以国内情况为例：根据 2010年中国互联网发展状况统计报告1，截至 2010年底，中国拥有的网页总数 超过 600亿，总字节数超过 1900网站数超过 190万，网民数量超过 信息检索和 搜索引擎 自 20 世纪 90 年代 以来 ， 万维网 的规模不断扩大， 信息的获取手段逐渐由媒体转向网络，社会信息量由于网络的壮大而变得空前的丰富 。如何从万维网中的海量信息取得有效信息成为 一个 重要 挑战。一个解决的办法就是信息检索（ 其概念由 1951 年 首次提出 信息检索是信息的潜在用户将信息需求转换为一张文献来源信息列表的过程或方法，而这些文献包含有对其有用的信息 ” 2。 经过十几年的发展 ， 以搜索引擎为代表的信息检索技术已经取得了巨大的成功 。用户可以通过搜索引擎很容易地获取他们所需要 的万维网 上的信息，大大提高了利用信息的效率。搜索引擎的基本原理和功能是：预先从互联网上大规模爬取大量网页，然后对这些抓取的网页进行分析处理，建立索引。当用户给出查询时，在建好的索引中查找和查询相关的结果，对结果按照相关性进行排序后返回给用户。 最 早 的 万 维 网 的 搜 索 引 擎 叫 做 它建于 1994年，当时它只有收集了 110000的网页，每天对于它的查询在 1500个左右。之后的十几年里，搜索引擎有了大规模的发展，在检索速度、索引网页数量、查询效果等方面有了巨大的提升。 008年称其索引的网锚文本在搜索引擎中的存储及 应用 2 页数量曾冲破 1万亿篇。 目前 ， 像 百度等搜索引擎已经深入到人们日常学习和工作中，成为获取信息不可或缺的工具。 在中国， 截止 2010年底，搜索引擎使用率达到 用户规模 为网民第一大应用，作为互联网的引擎，越来越呈现出其“新门户”的特点 1。 锚文本 概述 随着互联网规模的不断扩大，网页之间的超链接数目不断增加，而作为网页之间的链接文本的锚文本的数目不断增加。因此锚文本在搜索引擎中的地位就显得日益重要。 锚文本（ 是 本中的链接信息。例如，下面一篇网页中的 码片段表示指向网站 of 页的链接： of 其中，超链接指向的网页 ，显示在网页中的锚文本是 of 般来讲，我们将一篇文档的锚文本定义为指向这篇文档的链接所包含的文字信息，而非这篇文档所含链接中的文字信息。 以下若无特殊说明，我们将指向一篇文档的所有的链接的锚文本称作这篇文档的锚文本文档 （锚文本域） 。 以下图为例：网页 A， B， 对应锚文本分别为“ “北京大学”、“北大”，则北大首页的锚文本 域 应为“ 北京大学 , 北大” 。 随处可见的一个现象是，很多网页的内容并不包含对自身内容的精确描述。例如，公司是世界上最大的计算机制造商 官方主页（ 码的任何地方都不包含词项 电脑）。类似地，A :P e k i n g U n i v e r s i t 北 京 大 学C :北 大w w w . p k u . e d u . c 1 页的锚文本域 锚文本在搜索引擎中的存储及 应用 3 页的 码中也不包含单词 户）。 因此， 页本身携带的词项 （ 和用户用于描述同一网页的词项之间往往存在一定的差异。但是， 索者不一定要使用网页中的词项对网页进行查询，这时锚 文本中的词项就是一个很好的替代 2 。例如，链接上的锚文本都包含单词 我们可以对这些锚文本建立索引，使得词项 倒排表包含 词项 倒排表中也同样会包含文档 另外一个现象是，很多网页中的图像和视频十分丰富， 甚至 可能在图像中嵌入了文字。这种情况下，搜索引擎对抓取后的网页的 行分析时，就无法抽出具体的文本来构建索引。此时，我们同样可以使用指向这些网页的锚文本，它们之中很可能含有对目标 网页的图像或视频的一组描述。 本文的 工作及主要 贡献 在智能搜索引擎平台 ，原有的锚文本的存储 结构和检索模块，与网页正文的存储和检索没有差别，也是对锚文本 域 构建一个倒排索引。这种做法， 在存储空间上有很大浪费 ，并且 没有考虑存储锚文本的源网页和所在链接等额外信息和特征 ，使得我们在对锚文本的倒排索引检索时，无法引入锚文本区别于正文的一些特征，导致检索效果有所下降。 因此，本文在搜索引擎中主要有以下 工作及贡献 ： 1、 在 改进了旧有的 锚 文本的存储结构，设计和实现了锚文本 的新的 存储 结构。 新的结构比起原来的结构节省了存储空间，且能存储锚文本的一些附加信息。 2、 针对 锚文本的新的结构，设计和实现了检索打分模块。实验证明，新的打分模块的检索效果比起原有模块有所提升。 本文组织 本文的 组织如下，第一章对研究背景，研究目的和本文所作的贡献进行了整体介绍；第二章介绍了和本文相关的一些研究，如锚文本存储、检索方面的相关研究、新型存储结构扩展列表的介绍以及实验平台 介绍；第三章详细阐述了 锚文本旧有存储结构，以及新的存储结构的设计和实现；第四章叙述了 锚文本的旧有检索模块及其改进；第五章进行了 文本在存储和检索两方面的实验，对数据集、评测集及实验结果进行了分析；最后一章是本文的总结和工作展望。 锚文本在搜索引擎中的存储及 应用 4 第 2 章 相关研究 锚文本在搜索引擎中的可行性依据 早在 1994 年，人们已经发现将锚文本应用搜索领域，能让检索效果有很大提升。 人 3 通过实验观察发现，锚文本比起网页的其他特征，模糊性更少，使得基于锚文本方法的查询结果集比起基于其他特征方法的查询结果集，文章更加一致和集中。 另外， 通过考察锚文本的特征会发现，锚文本在行为上 和 实际用户查询 表现得非常相似：在互联网搜索中，用户提交的查询串一般都很短（ 2单词），概括总结了他们要寻找的网页的特征；类似地，锚文本通常也很短，且一般来讲，也是对它指向的目标网页做了一个总结。锚文本和查询串通常都不是完整句子，而且不是一个名词短语就是形容词和名词组合，很少 只用 动词 或形容词 ，即它们在语法特征上非常相似。因此，锚文本若作为查询串之外的一个辅助手段，对查询结果集进行筛选或扩展，是非常可能实现的。另外，锚文本和文章标题也有一定的相似之处，都是对一篇文章的总结，但不同之处在于，文章标题一般只是文章作者本人对这篇文章的总结， 有非常大的主观性， 而锚文本可以是不同人从不同角度，相对客观的对目标文章的总结，因此若将其用于对实际的搜索，有助于提高检索的客观性和准确率。 通常 ，一篇文档的锚文本域的长度远小于正文域的长度，而且相当数量的锚文本 是导航型的锚文本 （如 “ “ 等） ，没有实际意义 。为了克服锚文本的稀疏性的问题， 给定一个 u，收集网页集合 P，使得 P 中的每一个页面都和 u 属于同一站点，且至少有一个链接指向 u。 我们 将链接所在 源网页和 u 不属于同一站点，且 指向网页集合 P 中某一网页 的锚文本的集合 ， 称为 u 的扩展锚文本 。 在实际应用 中，扩展锚文本 既 可以作为一篇文档原始锚文本域的补充，也可以单独出来作为该文档的一个新的域。 以往对锚文本的研究中，由于使用的数据集的缘故，人们认为锚文本不适合ad 此 导航型检索（门户网站检索）等。而鉴于 果发现：锚文本对 ad 要在准确率的提升上。而在影响锚文本对检索效果的因素方面，以往的研究认为链接密度越高，锚文本效果越好；站外链接比站内链接对锚文本提升更有帮助。而 链接密度对锚文本效果无影响，而站内链接和站外链接至少一样有效。 另外， 他们发现 网页数目和锚文本效果呈正相锚文本在搜索引擎中的存储及 应用 5 关。 锚文本存储的相关研究 文献中对于锚文本存储的研究并不是很多。 索引擎的创始人 98 年曾提出了锚文本的一种存储结构 6。 锚文本所属 的 文档定义为其链接指向的文档，对锚文本像 对待 网页正文一样，建立倒排索引，索引中每个词项（ 应一个由多个记录文件（ 成的倒排表（ 对于锚文本域来讲，每个记录文件由一个 成，类似于于记录一个词在一篇文档中的各个位置。锚文本的 的一个命中（ 的结构定义如下：大小总共为为两个字节，其中大小写位占一个 体位占 3 个 文本中固定为 7），类型占 4 个 分其出现在标题， 标签还是锚文本），所属文档 的 占 4 个 锚文本中的位置占4 个 所以将后两个属性大小设为 4因为 虑到一篇文档包含的锚文本数目很少，且每个锚文本所含词数也较少。 锚文本应用的相关研究 引文中提到，锚文本是对其指向文档的概括精确描述，且和查询 词 及网页标题有很多 相似之处。基于 锚文本 的这些特性，人们将 它应用到 了搜索引擎中的不同方面，致力于提升 各类搜索任务的效果。 针对 锚文本 应用 的研究主要集中 于搜索引擎 的以下几个方面。 1、查询精化（ 使用锚文本建立了锚文本日志（ 锚文本日志由 对组成， 其中锚文本相当于查询日志查询串，锚文本所在链接 当于查询日志中的 外 ， 指向同一篇网页的所有锚文本可以视为 查询日志中的一个会话。这样就可以将锚文本和 基于日志技术的查询精化模型 进行结合。 他们发现利用锚文本日志进行查询精化的效果 ， 和基于查询日志的查询精化 的效果至少一样好。 定义见 ） 来进行查询精化。 他们图 2 索引擎中 每个 存储结构 锚文本在搜索引擎中的存储及 应用 6 考虑扩展锚文本的如下特征 ： 1、 进行 加权后的锚文本的出现次数（如指向相同目录、相同站点或不同站点） ； 2、锚文本包含的词数 ； 3、锚文本包含的字符数。然后 ， 将各段扩展锚文本按照上述各项属性分别进行排序，再将各类排序结果进行中位数排序，得到最终的候选锚文本的排序 结果 。 将锚文本引入跨语言的信息检索，以解决查询词翻译的稀疏性 的问题 。 他们先 从 锚文本集合中 提取 和该查询词经常共同出现的翻译 候选词。然后再将翻译候选词按照其和查询的相似度 （其中，假设权威性更高的锚文本中的翻译候选词更有可能作为最后的翻译词） 进行排序，选出最后的翻译词。 2、 正文域的检索 言模型的基础上， 提出了结合了 锚文本域 的 语言模型中，用于网页的导航型检索，其公式如下： 其中 i|指词第 i 个查询词在文档 出现的概率。 3、锚文本域的检索 索模型在锚文本域检索的效果，发现由 于锚文本域词频特征，文档长度特征和 征都和正文域有很大差异，据此提出 型（ A 于锚文本域的检索，公式如下： 4、链接分析 为了改进 法的主题漂移问题，谢海艇 12在 法过程中引入了锚文本相关权值 ，公式如下 。 其中 锚文本 n 和查询串的匹配度， 第 k 个查询词在锚文本中出现的次数， L 是锚文本长度。 W(i)为网页 i 的相关度权值。 代过程中的计算公式中，将 W(i)作为加权，使得 法和查询串更加符合： (2002)将 网页锚文本与查询词相似度计算结合，提出了 法 ，作为对 一种改进 。他们认为查询返回结果中 ， 排名较高的网页除了需要 较高之外，还需要锚文本和查询词有较高的相似性。如下式所示： d) = PR(d) * 1 + * d, Q) 锚文本在搜索引擎中的存储及 应用 7 其中 ， PR(d)为文档 d 的 ， d, Q)为利用锚文本计算的文档 d 和查询 Q 相似性， 为调整参数 。根据 人的实验 结果 ， 法在网页的检索优于当时的 陆一鸣 14等人 (2005)同样将 锚文本结合，提出 法， 他们认为，质量（ 高的源网 页，其可信度较高，其指向其他网页的锚文本的准确度也就较高，应 赋予 其 较高权重： = * PR(j) 其中， 第 PR(j)为经过正规化后的网页 这种算法在一定程度上是合理的，通常拥有较高 比较客观的。因为它的权威性决定了它必然是由具有丰富知识的网页作者编写的， 对其他网页的理解会比较客观。此外，由于考虑到 了 网 页 这种方法 对于恶意伪造错误描述具有低 页起到一定的抵制作用。 吴炜 15等人 (2008)提出了基于网页主题相关度 的 改进 们考虑了锚文本和 公式如下： 其中， i)为源网页的 w = i, 为 的锚文本 5、其他 以往对锚文本的研究都是假设锚文本之间是独立的。 实际互联网中垃圾链接(存在，使得简单将一篇文档不同锚文本的数量相加的做法是不够的。例如，两个指向一篇网页的锚文本的链接可能来自同一站点或镜像站点，或来自两个合作站点，甚至来自故意提升目标网页质量一个链接网。 在 这些情况下， 这两段锚文本的价值应给予降低，其累计权值应该小于其权值的算术 和。 锚文本的权值和其在 虑了影响 1、 站内链接关系； 2、 链接 所属 源站点和 目标站点的关系 ；3、 链接 各个源站点之间的关系等。 他们根据这些因素 引入站点独立模型（ 站点关系模型（ 计算上述因素影响下 的 一段锚文本的实际价值。 实验结果表明， 使用这两个模型的检索效果比 假设锚文本之间 独立时检索的效果 要 好。 展列表（ 我们知道，一篇文档有标题、作者、正文等域的信息，因此我们可以针对某个域来建立索引和检索。但当我们面对更加复杂的文档结构时，使用域也无法很锚文本在搜索引擎中的存储及 应用 8 好的信息。 例如对如下一篇 档描述： W. 果我们要在作者域中搜索名为 “ 的作者，若在搜索引擎中搜索 么这篇文档是否匹配？单词 单词 在这篇档中出现，而且它们是相邻的。但显然，这两个词是分别出现在两位作者姓名之中，因此这篇文档可能无法很好 匹配查询 “ 。 为了解决上述问题， 人在 书中提出了扩展列表（ 概念。一个扩展列表由多个扩展项组成，而一个扩展项（ 一个文档的连续区域，可以用词在文档中的位置表示。例如在刚才的作者信息的 档中，我们可以将作者的信息用扩展列表表示成： （ 1， 4），（ 4， 6） ， （ 7， 9） 其中，（ 1， 4）指构成第一个作者的三个词，（ W. 出现在 1、 2、3 三个位置上，用左闭右开区间表示；（ 4， 6）指第二个作者的两个词（ 现在 4， 5 位置上；（ 7， 9）指第三个作者的两个词出现在 7、 8 位置上。 ,2 1,4 2,7 2,8 2,23 3,2 3,6 4,3 4,13 :(1,3) 2:(1,5) 4:(9,15) 表 1 例 上面的表格显示了扩展列表是怎么工作的。例如我们要检索 标题域中含有词文档。表格中第一行表示词 表示，如 “ 1,2”指 号文档中的第 2个位置；第二行表示标题域的扩展列表，用 表示， 如 “ 1：（ 1,3） ” 指 1 号文档中第 1、 2 个位置是这篇文档的标题部分，依此类推（此处我们将一篇文档的标题、作者、正文统一看做一段文字，用连续的位置来记录）。在对词 行检索时，我们同时遍历 标题域的扩展列表，若发现某 个 的 和 扩展列表中的 某 一项 满足 如下条件 ： = & & 此评测时，只是将 每个查询的对应的 250 篇左右的文档做出相关性标注，采用最小测试集方法（ 标准结果集，先估算出待评测结果中 每个不在标准结果集出现的结果文档的相关概率，再进行检索结果的评测。 用的查询集 样包含 50 个查询主题，其中 21 个主题是单个查询词。对应标准结果集与 似。 测指标介绍 以下是实验中用到的几个检索效果指标。 测工具中使用的评测指标的公式和下列公式基本相同，只是引入了概率部分 （检索结果中的一个文档符合取某一个相关值的概率）。 于一个查询，记其相关文档集 D = , d m，每检索到一篇相关文档 D，算出并记下此时的准确率（未检索到得相关文档的准确率记为零）。将所有这些准确率除以 |D|，就 得到 各个查询对应的 的算术平均值，其公式如下： 其中 查询 j 下检索到相关文档 的准确率。 锚文本在搜索引擎中的存储及 应用 22 一个查询的相关文档集为 R 式为： 其中， 示检索结果中排在第 i 个位置的文档的相关性的值（ 0、 1、 2）。 t k k 表示检索结果的前 k 篇文档的准确率，其公式为： 其中， 示检索结果中排在第 i 个位置的文档的相关性的值（ 0、 1、 2）。 评测时， t k（总体的 k 值） 指在各个查询得到的k 的 算术平均 值 。 k 在实验中 取 10、 30、 50 三个值 。 于如下两个假设： 1、高度相关的文档比边际相关（ 文档更有用； 2、一篇相关文档在检索结果中排序越靠后，其对用户 来讲 越没有用 处 ，越不可能被用户查看。 其中 义如下： 示检索结果中排在第 i 个位置的文档的相关性的值（ 0、 1、 2）。 正规化因子，等于检索结果中的文档按照相关性从高到底排序时的 。 k 指各个查询对应的 k 的算术平均值。 k 在实验中取10、 30、 50。 一个查询的检索结果中，排序最靠前的那一篇相关文档的锚文本在搜索引