1、北京大学信息科学技术学院 网络实验室硕士学位论文 1 北京大学 硕士研究生学位论文 题 目： 海量文档高速检索系统的设计与实现 姓 名： 谢翰 学 号： 10280040 系 别： 信息科学技术学院 专 业： 计算机软件与理论 研究方向： 网络与分布式系统 导 师： 李晓明教授 二零零五年六月 北京大学信息科学技术学院 网络实验室硕士学位论文 1 版权声明 任何收存和保管论文各种版本的单位和个人，未经本论文作者授权，不得将本论文转借他人 ，亦不得随意 复印、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权 益之问题，将可能承担法律责任。 北京大学信息科学技术学院 网络实验室硕士学位论文 2
2、 摘要 搜索引擎的检索 效率 是评价搜索引擎质量的一个重要指标， 面对互联网上信息量的不断增加 以及搜索引擎网页库的不断增大 ，对检索系统性能要求也越来越高。 本文详细 介绍 了一个搜索引擎检索系统的设计与实现， 针对搜索引擎检索系统的性能 问题 进行了研究， 讨论 了影 响检索性能的几个 因素 ，并 分别 提 出改进 的方法和途径。 这些方法包括设计出结构更加良好的倒排文件结构，改进整数压缩编码，引入倒排文件 cache，预先 计算关键词与文档 相关度，减少关键词相对位置计算开 销 ，改进站点聚类算法等。 另 外， 论文 还 阐 述 了 系统中使用的 新的相关度计算方法， 这个算法 使得在最
3、终的结果排序上 比原有系统 有了一些改进。 论文 的组织形式以 实 际 系统 中 各 模块为主线 ，这些模块 包括 倒排文件结构，底层数据接口，查询，计分和站点聚类等。在 论文 最后给出了系统的综合测试结果， 指出系统 中 还存在的不足， 并对后续工作提出了一些建议。 关键词 ：搜索引擎，检索系统，倒排文件，检索效率，相关度计算 北京大学信息科学技术学院 网络实验室硕士学位论文 3 The Design and Implementation of a High Performance Retrieval System XIE Han(Computer Software and Theory)
4、Directed by LI Xiaoming Abstract The performance of retrieving is crucial for modern search engine. This article introduces the design and implementation of a retrieval system for web search engine. Especially, we will discuss the factors that affect retrieval performance, and give the solutions for
5、 each of them, such as designing a new format for inverted file and a new encoding algorithm for integers, introducing cache for the index, pre-computing the similarity of terms and documents, and designing a better site grouping algorithm. A new ranking algorithm used in the system will be discusse
6、d too. The article is organized by modules, including inverted file, data interface, query, scoring and site grouping. In the last chapter we will make an overall evolution, and some advices for its further improvement will be given. Keywords: search engine, retrieval system, inverted file, performa
7、nce, ranking.北京大学信息科学技术学院 网络实验室硕士学位论文 4 目录 第 1 章 绪论 . 1 1.1 搜索引擎原理 . 1 1.2 倒排文件 . 2 1.3 检索系统分布式结构 . 4 1.4 现有系统的不足与本文的主要贡献 . 5 第 2 章 倒排文件设计 . 6 2.1 基本原则 . 6 2.2 整数压缩编码方法 . 7 2.3 系统使用的倒排文件结构定义 . 8 2.3.1 描述文件 . 8 2.3.2 索引文件 . 10 2.3.3 记录文件 . 10 第 3 章 底层数据组织 . 13 3.1 影响检索效率的主要因素 . 13 3.2 创建索引 . 15 3.3 获
8、得文档列表 . 18 3.3.1 接口与数据组织 . 18 3.3.2 性能测试 . 20 3.4 获得位置列表 . 23 3.5 模块的一些不足 . 26 第 4 章 查询过程 . 27 4.1 文档列表求交 . 27 4.2 相关 度计算 . 28 4.2.1 关键词与文档相关度 . 28 4.2.2 相对位置得分 . 30 4.3 站点聚类 . 31 4.4 查询模块接口 . 33 第 5 章 综合评测与总结 . 35 5.1 系统整体结构 . 35 5.2 实验设计 . 36 5.3 实验结果 . 37 5.4 总结 . 39 北京大学信息科学技术学院 网络实验室硕士学位论文 1 第
9、1章 绪论 1.1 搜索引擎原理 众所周 知 ，搜索引擎是从互联网上搜寻信 息的重要工具。随着互联网规模 的不断增大，网上信息量的不断增长，搜索引擎的作用越来越明显。互联网上搜索引擎虽然大小不同，功能各异，但它们都包含 以下 一些基本的功能模块。 1. 网页收集 网页收集是搜索引擎的第一步工作，要进行网页搜索显然必须先有一个网页库。除了少量手工加入的网页，大多数网页都是通过 被 称为 spider 的自动网页收集程序收集下来的。 spider 的基本工作原理很简单：以一些重要的网页为种子，先收集这些网页，提取这些网页上的链接，再收集被链向的网页。如此不断地循环下去，就可收集到互联网上大量的网页
10、。另外也可通 过端口扫描的方法发现隐藏的 web 服务器。评价 spider 的质量有几个重要的指标，包括网页收集的速度，网页质量与重复率，发现新增网页和变化网页的速度，动态网页的收集 策略 ，对对方 web 服务器的礼貌性等。目前大多数的研究都集中在网页质量和增量式的 网页 收集上。 2. 页面预处理 从互联网上收集到了网页，到真正的提供搜索服务还有很多的事情要做。首先是对网页进行一些预处理。对网页进行预处理的原因是，网页上的很多信息实际上与网页的主题毫无关系，比如广告，我们称这些为噪音信息。如果不把这些噪音信息去除则会影响到最后的查询质量。此 外，很多网页之间在排版，字体等方面 虽 不一样
11、，但正文的内容却是相同的，如是让它们都出现在查询结果中显然是多余的，必须去掉一个。还有一些无内容的垃圾网页，作弊网页，也必须在这个阶段消除掉。 3. 建立索引 从页面预处理模块得到了净化过 的 页面，要高效进行查询，还必须对页面建立从关键词到其出现位置的索引。这个索引称为倒排索引，对应的索引文件称为倒排文件。对于索引的建立应该说技术已经很成熟，关键是要定义出良好的索引北京大学信息科学技术学院 网络实验室硕士学位论文 2 结构，以支持检索模块对页网进行快速而准确的检索。 其次要保证 建立索引的速度，才能让新收集到的网页尽快地被查询到， 提高搜索引擎的时新性。 4. 网页检索 网页检索模块是最终与
12、搜索引 擎 用户交互的模块。系统根椐用户提供的查询，从建立好索引的网页库中 找 到与查询最相关的页面，根椐相关度 及 网页的重要性计算出一个综合的得分，把得分最高的 网页按顺序返回给用户。可以说，网页检索方面还有很多问题需要研究， 包括 ： 查询与网页相关度的计算，这直接影响查询结果的排序；查询的 响应时间 和系统吐吞率 ，一个大型的搜索引擎瞬间之内 就会有大量用户发出请求，面对这么多用户，如何以最快的速度响应，如果提高一段时间内可处理的 最大 查询个数 ，是现代搜索引擎面临的一个重要问 题 ； 检索系统的可扩展性和容错性也尤为重要，检索是搜索引 擎中对硬件需求最大的部分，往往是几百台甚至上万
13、台计算机协同工作， 这么多的计算机如 何 协调，在部分机器出现故障的时候如 何 让系统继续工作，也是一个 研究 领域。 除了这 上述 的 几 个基本模块，现代的搜索引擎还包含其它的一些功能。例如网页重要性的计算，网页的自动分类等。总之，搜索引擎的研究还远远没有到尽头，搜索引擎离它最终的目标还很远。本文将着重研究搜索引擎检索模块中的检索效率问题，同时也会涉及索引与相关度计算等方面。 1.2 倒排文件 倒排文件由搜索引擎的索引模块生成， 并被检索模块所使用。前面提到，倒排文件是从关键词到其出现位置 (occurrence)的一种索引。对于搜索引擎来说，关键词的出现位置信息必须包括出现 关键词 的文
14、档列表，以及 关键词 在 各文档 内的位置 列表 。一般而言倒排文件由索引文件和记录文件组成，索引文件 每个记录包含一个关键词和一个指针 ， 该指针 指向记录文件中 存放关键词信息的位置 。大致结构如下图所示： 北京大学信息科学技术学院 网络实验室硕士学位论文 3 图 1. 1 倒排文件 w or d1 w or d2 w or d3 ( w o r d2 s oc c u r r e nc e s ) ( w o r d3 s oc c u r r e nc e s ) 索引文件 记录文件 利用倒排文件，检索系统可以快速的找到查询词对应 的文档列表。对由多个关键 词所组成的查询，还可以根据各
15、个词在各 个文档中出现的位置，来计算 查询与 文档 的相关度。倒排索引是迄今为止发现的用于搜索引擎最好的索引结构，既方便建立，又很好的支持各种查询操作。在实际应用中的倒排文件远比上图的复杂 ： 为了更好的计算相关度，倒排文件中还要加入其它的一些信息，例如关键词在文档中的属性信息；为了提高检索效率，可能要调整倒排文件的结构，例如先存放出现关键词的所有文档列表，再存放所有的位置信息，把上图中位置信息的形式： 变换为： 通过这种变换，当我们不关心词在文档中位置 列表 的时候，就可以一次地读入词对应的文档列表，减少对外存的访问次数。在后面我们还将详细讨论倒排文件的设计，我们会发现倒排文件结构的好坏 直
16、接 影响检索速度。 北京大学信息科学技术学院 网络实验室硕士学位论文 4 1.3 检索系统分布式结构 现代搜索引擎搜索的网页都数量巨大， 目前 的北大天网 e.pku搜索引擎搜索的网页量就有 1.2 亿，而一般的商业搜索引擎搜索 的 网页量至 少都有数亿，甚至是达到 数 十亿。在这种情况下，一个单机的检索系统显然无法处理每秒成百上千的用户查询请求。此时，设计出一个结构良好的分布式检索系统显得尤为重要。一般成言，分布式检索系统至少包括两个部分：一台或多台用于接收入用户查询请求的前台服务器，和多个用于实际数据检索的 后 台服务器。 其结构如下图所示 ： 图 1. 2 检索系统分布式结构 q u e
17、 r y f r o m u s e r b r o a d c a s t 后台检索机群 前台服务器 当用户在搜索框中 填 入一个查询，点击搜索按钮，其查询就被随机的发送到任意一台前台服务器上。而前台服务器实际上并不保存网页的索引信息，它将用户的查询通过广 播的方式发送到后台的检索机群上。后台检索机群中，每台机器中都存放有部分网页的 倒排 索引，当 它 收入到广播过来的查询，便在其索引中查找出与查询其关的网页，并根据一定的相关度算法计算出得分，把相关 度最高 的若干个网页的文档号与得分一起发送回前台的服务器。前台服务器收集几个检索机器上的结果，按得分归并后把最相关的网页返回给用户。 由于时间
18、的关系本文必没有详细的研究检索系统的分布式结构，而是更多的关注各个检索节点上的效率。可以说，这两方面共同决定了一个检索系统的性能。 北京大学信息科学技术学院 网络实验室硕士学位论文 5 1.4 现有系统的不足 与本文的主要贡献 现有的天网检索系统 ，是从天网 1.0 开始，经过不断的完善和发展起来的。在几年里为老师和同学 们 的科研工作提供了一个重要的平台。但它还存在了一些问题需要我们去改善。例如以下几个方面： 1. 检索效率不高。每个检索节点检索的网页量大约在 二 百 多 万，每秒只能处理十几个的查询请求。主要原因是没有为倒排文件建立 cache，每次查询都要多次访问外存，磁盘成了系统的瓶颈
19、。此外， 其 分布式结构 也 不太好，前台服务器与检索节之间基于同步的多进程的交互方式，也影响和整个系统的效率。 2. 倒排文件信息量不够。现在的倒排文件中，关键词在文档中的属性信息很少，只用两个 bit 分别表示词是否在网页 title 和摘要中，并且不能为关键 词在文档中各个位置设立属性信息。由于 信 息量的缺乏，在计算词与文档相关性的时 候 ，往往不够准确。 3. 系统的可扩展性和容错性不足。系统现在运行在由一台前台服务器， 19个检索节点构成的分布式环境中。对于增加检索节点可能带来的广播风爆，以及增加前台服务器查询策略的变化，都没有考虑到。此外，数据没有冗余，当系统中部分机器出现故障，则会影响查询结果。 本文针对检索效率的 问题 进行了研究。设计出来更加良好的倒排文件结构，改进整数压缩算法，并增加倒排文件的信息量。通过有效 的 cache 策略，让索引尽量的在内存中 可 以找到，减少访问磁盘的 开销 。通过一些有效的预处理，减少了浮点运算的次数，也进一步的提高了检索效率。对于相关度计算，本文也做了一些 改进 ，使得在最后的结果排序上 更 符合用户需求 。此外，一个具有良好程序结构的可用系统，也很好的支持了文中提出的观点。在以下章节中，我们将详细的分析整个系统的设计 与 实现，以及设计背后 的 理论基础。
