【毕业学位论文】（Word原稿）PARADISE索引系统的改进及应用-计算机系统结构搜索引擎与网络信息挖掘

北京大学硕士学位论文 引系统的改进及应用 1 硕士研究生学位论文 题目： 引系统的改进及应用 姓 名： 赵东生 学 号： 10748236 院 系： 信息科学技术学院 专 业： 计算机系统结构 研究方向： 搜索引擎与 网络信息 挖掘 导 师： 李晓明 教授 二一年 五月 北京大学硕士学位论文 引系统的改进及应用 2 版权声明 任何收存和保管本论文各种版本的单位和个人，未经本论文作者同意，不得将本论文转借他人，亦不得随意复制、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权之问题，将可能承担法律责 任。北京大学硕士学位论文 引系统的改进及应用 3 摘 要 随着互联网信息的快速增长，搜索引擎的作用越来越重要。索引技术在网络服务中应用广泛，而索引系统是搜索引擎主要部分之一，它在搜索引擎中发挥着重要作用。基于倒排表的索引系统有着比较复杂的内部结构和逻辑，在设计和实现的时候有很多需要考虑的因素。 北京大学网络实验室独立开发了 统， 简称，它是一个开放式的搜索引擎平台， 提供了一组可配置、可替换的工具，用户可以根据自己的需要，定制相应的系统。 在将 索引系统应用到研究和工程领域的过程中，我们遇到了一些问题，针对这些问题，本文做了如下的一些工作： 1、重新设计并实现了 引系统。针对前一个版本的诸多问题，我们将整个索引进行了重新设计和实现。这个过程中，我们增加了用于改善性能的的缓存模块；重新实现了存储模块、文档表示模块，并增加了很多新的功能和接口；对于顶层的倒排、字典、正排模块，则完全重新进行了设计和实现，包括索引文件格式、跳查机制、索引流程等等 。 2、详细介绍了 引的改进情况。这包括单机索引文档数量的增加、索引构建速度的提升、检索速度的提升、可扩展性的增强等等。 3、介绍了 引系统的应用情况。首先，我们使用 加的 009 的 测，应用索引系统对较大规模的数据进行了处理。其次我们将索引系统应用到北京大学的校内搜索服务，取得了比较好的效果。 关键词 ：搜索引擎、 引系统、倒排表、索引改进北京大学硕士学位论文 引系统的改进及 应用 4 i of is eb is of of an is on to be of is its ab is an a of a as We to or To is in 1、 is We of of is to to is is of is to 2、 of of of in a so 3、 we to in 009 is to is to 录摘 要 . 3 . 错误 !未定义书签。 目录 . 5 第一章 引言 . 8 究背景 . 8 文主要工作 . 9 第二章 引系统概述 . 10 引相关工作 . 10 引情景 . 11 引模块结构 . 12 档表示 . 13 储模块 . 14 存模块 . 15 引分析模块 . 16 引压缩 . 16 排和字 典 . 19 排模块 . 22 引元信息模块 . 22 引流程 . 23 第三章 引系统的改进 . 27 引分析 . 27 块实现 . 27 用举例 . 29 存模块 . 29 能描述 . 29 扩展性的改进 . 30 索性能的改进 . 32 引字典 . 32 扩展性 . 32 典的压缩 . 33 查机制 . 34 查原理 . 34 块实现 . 35 引流程 改进 . 36 个索引的检索 . 37 第 4 章 引系统的应用 . 39 009 评测 . 39 介 . 39 索模型的相关研究 . 40 用的检索模型 . 41 展的 型 . 41 询词邻近分数 . 42 页的权重 . 42 询词出现分数 . 43 据集上的调优 . 44 京大学校内搜索 . 45 第五章 工程性经验总结 . 48 统设计的权衡 . 48 注于重点 . 48 单就是最好 . 49 试和测试 . 49 第六章 总结与展望 . 51 结 . 51 一步工作 . 51 参考文献 . 52 致谢 . 55 图表 1 索引 模块结构图 . 12 图表 2 域的属性及其描述 . 13 图表 3 文档表示模块 . 14 图表 4 存储模块 . 15 图表 5 缓存模块 . 15 图表 6 索 引分析模块 . 16 图表 7 索引 压缩模块 . 17 图表 8 缩算法举例 . 18 图表 9 写 索引 模块 . 20 图表 10 读 索引 模块 . 21 图表 11 字典模块 . 21 图表 12 正排模块 . 22 图表 13 索 引域元信息模块 . 23 图表 14 索引 段元信息模块 . 23 图表 15 基数为 2 的索引合并 . 25 图表 16 主要 过滤器及其功能 . 27 图表 17 索引分析器的例子 . 28 图表 18 缓存模块 主要 接口 . 30 图表 19 缓存模块 结构 . 31 图表 20 存策略实现 . 31 图表 21 使用缓存和不使用缓存的效果对比 . 32 图表 22 字典的 结构 . 33 图表 23 倒排表结构图 . 35 图表 24 跳查 表和跳查块 . 35 图表 25 跳查块结构 . 36 图表 26 改进前的索引流程 . 36 图表 27 改进后的索引流程 . 37 图表 28 型和查询词邻接的检索效果 . 44 图表 29 对查询词出现进行线性加权的 . 44 图表 30 对查询词出现进行因数加权的检 索效果对比 . 44 图表 31 应用 因数加权的检索效果 . 45 图表 32 北大校内搜索 . 46 图表 33 北京大学校内搜索构架 . 47 北京大学硕士学位论文 引系统的改进及应用 8 第一章 引言 究背景 随着互联网信息的快速增长，搜索引擎的作用越来越重要。互联网信息的增长速度是惊人的，而搜索引擎 做为人们获取互联网信息的重要入口，需要处理这些海量数据，一般来说，现在的商业搜索引擎处理的网页数量都超过 10亿。与此同时，坐在计算机前面的搜索引擎用户希望在很短的时间（例如， 1 秒钟）内找到他（她）所需要的结果。海量数据的处理和快速查询的需求构成了一对矛盾 ，文献 1从数据结构和算法的角度对信息检索系统进行了分析 。 查询用户需要的信息，这样的应用由来已久，传统的数据库系统就是为解决这样的问题而产生的。数据库系统向用户提供了 询语言，可以精确查找用户所需要的信息，虽然数据库系统支持对数据进行索引，并且也在 网络服务中应用广泛，但是数据库系统的性能无法满足互联网用户在海量信息中快速查找的需求。之所以如此，是因为数据库系统本身的主要作用并不是 提供 快速相关度 检索服务。搜索引擎并不需要像数据库系统那样，返回所有满足逻辑条件的结果，而是返回一定数量相关性较高的结果。 索引系统是搜索引擎主要部分之一，它在搜索引擎中发挥着重要作用，为快速检索提供了基本的支持。近些年来，对索引和检索的研究一直在发展。对于索引结构来说，从传统的文档号排序的倒排索引，到文档重要度排序的索引，以及只存储位置信息的索引等等，都在权衡各方面的取舍，以 希望能优化检索过程，取得较理想的检索效果和检索性能。一方面，随着搜索引擎处理的数据量的增长，分布式的索引系统应用越来越广泛，包括分布式的索引构建和分布式的检索。另一方面，搜索引擎的用户希望能够获得实时的信息， 例如对新闻和博客的搜索， 这就需要索引系统能够支持动态索引 10,11，即实时的抓取和索引机制，并且能够立即供检索使用。动态索引一般在内存建立，在适当的时机写到磁盘。 对排序结果相关性的研究也没有间断。对于检索模型而言，从最初的只能返回相关和不相关两种结果的布尔模型，到概率模型，以及由其演化而来的型，另外还有语言模型 34和向量空间模型，都是用来计算某个查询和文档之间相似度。这些模型都基于一个基本的假设，如果查询中的某个词在文档中出现，会增加文档的相关性。不同的模型会有不同的算法，而索引的结构，也会影响这些检索算法。另外，查询词在文档中出现的顺序、距离等，无疑也会影响文档的相关度。查询词的位置信息也是对检索结果排序的过程中需北京大学硕士学位论文 引系统的改进及应用 9 要重点考虑的因素。 网页的重要度也会对检索的排序结果产生影响。 5就是比较经典的一个衡量网页重要度的标准。 值根据随机游走模型和网络图的 链接分析（网页的入度、出度）计算出来。和 似的还有 法。 北京大学网络实验室独立开发的 统 3，是 简称，它是一个开放式的搜索引擎平台，提供了一组可配置、可替换的工具，用户可以根据自己的需要，定制相应的系统。 统为网络实验室的研究工作提供了支持，同时也应用到北京大学校内搜索服务中。 开源 的软件包，在网络上可以免费获得。 本文作者参与了 目的开发工作，主要负责索引模块的改进设计和实现。在分析了前一版本的诸多缺点后，本文作者对索引系统进行了改进，在保留前一个版本概念的基础上，重新设计和实现了整个模块。 文主要工作 第二章对改进的 引做了系统的介绍；第三章详细描述了本文对索引系统的改进； 统的应用情况在第四章进行了介绍；第五章总结了系统开发和改进过程中若干工程性经验；第六章对本文进行了总结。与索引和检索有关的相关工作，分别在第二章和第四章 给出。 北京大学硕士学位论文 引系统的改进及应用 10 第二章 引系统概述 引相关工作 对倒排索引比较全面的介绍，可以参考 关于倒排 索引的综述 2，这篇文章全面的介绍了倒排索引技术，并且给出了大量的参考文献，很有价值。常规的倒排索引技术，将倒排表按文档号的顺序排列，结构如下： 在查询过程中， 需要进行 两个倒排表的求交操作，以及相关度计算。如果倒排表很长，那么求交和相关度的计算是比较 耗时的 。在计算相关度的过程中， 查询词 t 在文档 d 中出现的次 数，即 fd,t 是考虑的主要因素，所以对于 fd,t 很小的文档所进行的 求交和相关度计算都是浪费的，结果并没有返回。基于这样的考虑， fd,36，这种索引将相对重要的文档放在倒排表的前面，检索过程中会优先考虑这些文档。但是这种索引存在两个问题，首先， fd,t 很大的文档不一定重要，比如文档很长的情况；其次， fd,t 排序的文档 可能 会增加索引的大小。因为传统文档号排序倒排索引会使用文档号差值的压缩，而按照词频排序的索引打乱了文档号的顺序。文章 36也提到了这种索引结构下如何进行索引 压缩。为了解决词频排序的索引的问题，文献 27给出了按照文档对查询词的重要度（ 序的索引，这种索引结构和前 者类似，不同的是，排序的依据是按某种方法计算出来的重要度。文章 29给出了将重要度排序的索引应用到向量空间检索模型上的实验结果，结果表明检索效果有很好的提升，并且作者进而提出了多种检索模式下，如何应用这种索引结构 28。 索引压缩技术在索引系统中比较重要，压缩会使索引 文件变小，减少磁盘访问时间，提升索引系统性能。索引的压缩技术在 13中进行了介绍，并且给出了各种算法的比较结果。 业 界也有比较成熟的索引系统 5它们 都得到了非常广泛的应用。其中是一个应用比较广泛的索引框架，由 件基金会开发。是 C+开发的，对语言模型 34的支持比较好。本文在设计引流程的过程中，也参考了 。 接下来将对改进后的 引系统进行介绍。 北京大学硕士学位论文 引系统的改进及应用 11 引情景 为了方便理解本文，明确相关概念，让我们考虑如下索引的情景。引入如下的 文档集 C，这个文档集包含 2 篇 文档 ， 我们要对这两篇文档建立倒排索引。每篇文档只包 含了 文档的 正文 ： 中国的大学 京大学 原始的文档可以切分为 词 （ 例如 ， 以切分为： “中国 ”， “的 ”，“大学 ”，共三个词 。词是建立倒排索引的基本对象。 字典 和 倒排索引 是搜索引擎最基本的数据结构。 倒排文件 主要存储的是每个词的 倒排表 （ 。倒排表由若干 倒排项 （ 组成，每个 倒排项 的形式为 。 其中 档号 ， 频 ， 文档中出现 位置 的列表。 前面所述的 文档集 C 对应的倒排索引文件（或者倒排文件）如下 : (对应 “北京 ”的 倒排表 ) (对应 “大学 ”的 倒排表 ) (对应 “的 ”的 倒排表 ) (对应 “中国 ”的 倒排表 ) 字典存储了每个词以及这个词对应的倒排表在倒排索引文件中的位置。 文档集 C 对应的字典文件如下： 北京 0 1 大学 3 2 的 9 1 中国 12 1 其中，我们假定倒排文件中的每个数字占据 1 个位置，那么 0， 3， 9， 12 分别是词 “北京 ”、 “大学 ”、 “的 ”、 “中国 ”对应的倒排表在倒排文件中的偏移。上表中第 3 列的数字是每个词的 息 ，它表示：这个词在多少个文档中出现过。“大学 ”在两个文档中都出现了，所以 2，其他词的 是 1。 如果说倒排文件存储的是词到文档号集合的映射，那么 正排索引 存储的是文档到 文档信息 的映射。 倒排索引 ： 词 文档集合 正排索引 ： 文档 文档信息 例如，文档集 C 的正排信息可以如下 : 5 北京大学硕士学位论文 引系统的改进及应用 12 4 这个正排文件存储了每篇文档对应的 及文档的长度。 引模块结构 如图所示，是整个索引模块的结构图。在 ，和索引模块交互的部分主要是预处理模块和检索模 块。预处理模块将原始的网页数据经过消重、去噪、提取锚文本、链接分析等一系列步骤，为索引模块提供结构化的 文档 数据。索引模块通过写索引的接口，将这些数据转化为倒排索引。检索模块则通过读索引的接口，读取索引的字典、倒排、正排等信息。 图表 1 索引 模块结构图 在索引模块中，比较底层的是模块是缓存模块、存储模块以及压缩模块，这三个模块的设计是一般化的，并不是只针对索引 ，可以应用到其他程序中 。文档表示模块也是比较基础的模块，提供了文档的一般化表示方法。 上层的模块包括 具有分析过滤功能的分析模块，保存索引构建后一些基本信息的元信息模块，以及较为核心的正排、字典、倒排模块。下面将会一一介绍这些模块的功能和设计。 北京大学硕士学位论文 引系统的改进及应用 13 档表示 在文本检索中，需要检索的对象形式是多种多样的。这个对象可以是 面，可以是一篇 式的 论文，也可以是一个文本文件等等。为了统一表示检索对象， 统设计并实现了文档表示模块。 文档表示 模块 是索引的最基本的模块，它 细化了 索引的检索粒度 并增加了检索 能力。 比较常见的做法是 将文档表示成为词集合（ 的方式，3系统 可以 将文档组织成为树状结构 ，但是却没有对应的检索模块 ，这是因为 言 更多用来 表示视觉的展示，而不是表达内容 上 的相关性。 同样， 在 引 中，文档（ 搜索引擎用户检索的基本对象。然而，仅仅将文档表示成词的集合（ 形式，粒度太粗，有时不能得到好的检索效果。 考了 文档表示方法，将文档表示为多个 域 （ 每个域又表示为词的集合。例如：一篇网页 P，可以表示为标题域（ 正文域（ 入链锚文本域（ ， 出链锚文本域（ 等。 其中，入链锚文本并不是网页 是其他网页 通过超链接 指向P 时，所使用的锚文本内容。但是，这些文本内容包含了一些 和网页 P 相关的 重要的信息，我们也认为是 P 的一个域。 每个域包含两部分的内容，即数据和属性。数据实际上就是内容对应的字符串，属性表示了这个域的一些特征。 档的域的属性有如下几种，下表也给出了他们的描述。 域的属性 描述 索引 (表示该域是否应该建 立倒排索引 分析 (这个域是否需要进行分析。每个分析域可以指定特定的分析器 存储 (该域是否需要存储到正排文件中 特殊 (类型为 32位整数。表示文档的某些属性，或者某个索引域的某些属性。 图表 2 域的属性及其描述 文档表示模块主要部分的类图如下所示： 北京大学硕士学位论文 引系统的改进及应用 14 图表 3 文档表示模块 每个文档由若干个域（ 成，而每个域由数据（ 属性（ 成，属性的取值可以是上面表格 中 提到的之一 ，或者是它们的组合 。 储模块 索引的存储模块是索引的基础模块之一，为索引的读写提供统一的接口。设计存储模块的目的，主要是为了增强程序的可扩展性。有了存储模块的支持， 通过给出相应的实现， 引的文件可以存储在内存、磁盘、闪存、磁带等介质上，也可以存储在分布式的文件系统上。 存储模块也增强了程序的可移植性，当索引在不同的系统之间移植时，不用修改上层的代码也能够完成。 存储模块的类图如下所示： 北京大学硕士学位论文 引系统的改进及应用 15 图表 4 存储模块 存模块 缓存模块是为了提高系统性能和可扩展性而设计的通用的模块。在引的读写过程中，很多数据不能完全放在内存中，这就需要在磁盘和内存之间建立一个缓存机制。虽然操作系统会提供这样的功能，但是操作系统提供的这个缓存功能太一般化， 没有 考虑索引系统数据访问的特点。为此，我们设计和实现了缓存模块。 缓存模块（ 设计如下所示： 图表 5 缓存模块 北京大学硕士学位论文 引系统的改进及应用 16 除了缓存对象（ 外， 其他的类都是模板类。由于缓存模块针对的是 数据存储 形式，采用模板类实现，增加了模块的实用范围。每个缓存由两部分构成，分别是缓存策略（ 缓存存储（ 用户需要缓存的数据以 缓存对象 的形式存储在 缓存存储