【毕业学位论文】（Word原稿）海量文档高速检索系统的设计与实现

北京大学信息科学技术学院 网络实验室硕士学位论文 1 北京大学 硕士研究生学位论文 题 目： 海量文档高速检索系统的设计与实现 姓 名： 学 号： 系 别： 信息科学技术学院 专 业： 计算机软件与理论 研究方向： 网络与分布式系统 导 师： 教授 二零零五年六月 北京大学信息科学技术学院 网络实验室硕士学位论文 1 版权声明 任何收存和保管论文各种版本的单位和个人，未经本论文作者授权，不得将本论文转借他人 ，亦不得随意 复印、抄录、拍照或以任何方式传播。否则，引起有碍作者著作权益之问题，将可能承担 法律责任。 北京大学信息科学技术学院 网络实验室硕士学位论文 2 摘要 搜索引擎的检索 效率 是评价搜索引擎质量的一个重要指标， 面对互联网上信息量的不断增加 以及搜索引擎网页库的不断增大 ，对检索系统性能要求也越来越高。 本文详细 介绍 了一个搜索引擎检索系统的设计与实现， 针对搜索引擎检索系统的性能 问题 进行了研究， 讨论 了影 响检索性能的几个 因素 ，并 分别 提 出改进 的方法和途径。 这些方法包括设计出结构更加良好的倒排文件结构，改进整数压缩编码，引入倒排文件 先 计算关键词与文档 相关度，减少关键词相对位置计算开 销 ，改进站点聚类算法等。 另 外， 论文 还 阐述 了 系统中使用的 新的 相关度计算方法， 这个算法 使得在最终的结果排序上 比原有系统 有了一些改进。 论文 的组织形式以 实 际 系统 中 各 模块为主线 ，这些模块 包括 倒排文件结构，底层数据接口，查询，计分和站点聚类等。在 论文 最后给出了系统的综合测试结果， 指出系统 中 还存在的不足， 并对后续工作提出了一些建议。 关键词 ：搜索引擎，检索系统，倒排文件，检索效率，相关度计算 北京大学信息科学技术学院 网络实验室硕士学位论文 3 of a I he of is of a we of as a a of a A in be is by In we an be 网络实验室硕士学位论文 4 目录 第 1 章 绪论 . 1 索引擎原理 . 1 排文件 . 2 索系统分布式结构 . 4 有系统的不足与本文的主要贡献 . 5 第 2 章 倒排文件设计 . 6 本原则 . 6 数压缩编码方法 . 7 统使用的倒排文件结构定义 . 8 述文件 . 8 引文件 . 10 录文件 . 10 第 3 章 底层数据组织 . 13 响检索效率的主要因素 . 13 建索引 . 15 得文档列表 . 18 口与数据组织 . 18 能测试 . 20 得位置列表 . 23 块的一些不足 . 26 第 4 章 查询过程 . 27 档列表求交 . 27 关 度计算 . 28 键词与文档相关度 . 28 对位置得分 . 30 点聚类 . 31 询模块接口 . 33 第 5 章 综合评测与总结 . 35 统整体结构 . 35 验设计 . 36 验结果 . 37 结 . 39 北京大学信息科学技术学院 网络实验室硕士学位论文 1 第 1章 绪论 索引擎原理 众所周 知 ，搜索引擎是从互联网上搜寻信 息的重要工具。随着互联网规模 的不断增大，网上信息量的不断增长，搜索引擎的作用越来越明显。互联网上搜索引擎虽然大小不同，功能各异，但它们都包含 以下 一些基本的功能模块。 1. 网页收集 网页收集是搜索引擎的第一步工作，要进行网页搜索显然必须先有一个网页库。除了少量手工加入的网页，大多数网页都是通过 被 称为 一些重要的网页为种子，先收集这些网页，提取这些网页上的链接，再收集被链向的网页。如此不断地循环下去，就可收集到互联网上大量的网页。另外也可通 过端口扫描的方法发现隐藏的 价 括网页收集的速度，网页质量与重复率，发现新增网页和变化网页的速度，动态网页的收集 策略 ，对对方 前大多数的研究都集中在网页质量和增量式的 网页 收集上。 2. 页面预处理 从互联网上收集到了网页，到真正的提供搜索服务还有很多的事情要做。首先是对网页进行一些预处理。对网页进行预处理的原因是，网页上的很多信息实际上与网页的主题毫无关系，比如广告，我们称这些为噪音信息。如果不把这些噪音信息去除则会影响到最后的查询质量。此 外，很多网页之间在排版，字体等方面 虽 不一样，但正文的内容却是相同的，如是让它们都出现在查询结果中显然是多余的，必须去掉一个。还有一些无内容的垃圾网页，作弊网页，也必须在这个阶段消除掉。 3. 建立索引 从页面预处理模块得到了净化过 的 页面，要高效进行查询，还必须对页面建立从关键词到其出现位置的索引。这个索引称为倒排索引，对应的索引文件称为倒排文件。对于索引的建立应该说技术已经很成熟，关键是要定义出良好的索引北京大学信息科学技术学院 网络实验室硕士学位论文 2 结构，以支持检索模块对页网进行快速而准确的检索。 其次要保证 建立索引的速度，才能让新收集到的网页尽快地被查询到， 提高搜索引擎的时新性。 4. 网页检索 网页检索模块是最终与搜索引 擎 用户交互的模块。系统根椐用户提供的查询，从建立好索引的网页库中 找 到与查询最相关的页面，根椐相关度 及 网页的重要性计算出一个综合的得分，把得分最高的 网页按顺序返回给用户。可以说，网页检索方面还有很多问题需要研究， 包括 ： 查询与网页相关度的计算，这直接影响查询结果的排序；查询的 响应时间 和系统吐吞率 ，一个大型的搜索引擎瞬间之内 就会有大量用户发出请求，面对这么多用户，如何以最快的速度响应，如果提高一段时间内可处理的 最大 查询个数 ，是现代搜索引擎面临的一个重要问 题 ； 检索系统的可扩展性和容错性也尤为重要，检索是搜索引 擎中对硬件需求最大的部分，往往是几百台甚至上万台计算机协同工作， 这么多的计算机如 何 协调，在部分机器出现故障的时候如 何 让系统继续工作，也是一个 研究 领域。 除了这 上述 的 几 个基本模块，现代的搜索引擎还包含其它的一些功能。例如网页重要性的计算，网页的自动分类等。总之，搜索引擎的研究还远远没有到尽头，搜索引擎离它最终的目标还很远。本文将着重研究搜索引擎检索模块中的检索效率问题，同时也会涉及索引与相关度计算等方面。 排文件 倒排文件由搜索引擎的索引模块生成， 并被检索模块所使用。前面提到，倒排文件是从关键词到其出现位置 (一种索引。对于搜索引擎来说，关键词的出现位置信息必须包括出现 关键词 的文档列表，以及 关键词 在 各文档 内的位置 列表 。一般而言倒排文件由索引文件和记录文件组成，索引文件 每个记录包含一个关键词和一个指针 ， 该指针 指向记录文件中 存放关键词信息的位置 。大致结构如下图所示： 北京大学信息科学技术学院 网络实验室硕士学位论文 3 图 1 . 1 倒排文件 w o r d 1 w o r d 2 w o r d 3 ( w o r d 2 s o c c u r r e n c e s ) ( w o r d 3 s o c c u r r e n c e s ) 索引文件 记录文件 利用倒排文件，检索系统可以快速的找到查询词对应 的文档列表。对由多个关键 词所组成的查询，还可以根据各个词在各 个文档中出现的位置，来计算 查询与 文档 的相关度。倒排索引是迄今为止发现的用于搜索引擎最好的索引结构，既方便建立，又很好的支持各种查询操作。在实际应用中的倒排文件远比上图的复杂 ： 为了更好的计算相关度，倒排文件中还要加入其它的一些信息，例如关键词在文档中的属性信息；为了提高检索效率，可能要调整倒排文件的结构，例如先存放出现关键词的所有文档列表，再存放所有的位置信息，把上图中位置信息的形式： 变换为： 通过这种变换，当我们不关心词在文档中位置 列表 的时候，就可以一次地读入词对应的文档列表，减少对外存的访问次数。在后面我们还将详细讨论倒排文件的设计，我们会发现倒排文件结构的好坏 直接 影响检索速度。 北京大学信息科学技术学院 网络实验室硕士学位论文 4 索系统分布式结构 现代搜索引擎搜索的网页都数量巨大， 目前 的北大天网 索引擎搜索的网页量就有 ，而一般的商业搜索引擎搜索 的 网页量至 少都有数亿，甚至是达到 数 十亿。在这种情况下，一个单机的检索系统显然无法处理每秒成百上千的用户查询请求。此时，设计出一个结构良好的分布式检索系统显得尤为重要。一般成言，分布式检索系统至少包括两个部分：一台或多台用于接收入用户查询请求的前台服务器，和多个用于实际数据检索的 后 台服务器。 其结构如下图所示 ： 图 1 . 2 检索系统分布式结构 q u e r y f r o m u s e r b r o a d c a s t 后台检索机群 前台服务器 当用户在搜索框中 填 入一个查询，点击搜索按钮，其查询就被随机的发送到任意一台前台服务器上。而前台服务器实际上并不保存网页的索引信息，它将用户的查询通过广 播的方式发送到后台的检索机群上。后台检索机群中，每台机器中都存放有部分网页的 倒排 索引，当 它 收入到广播过来的查询，便在其索引中查找出与查询其关的网页，并根据一定的相关度算法计算出得分，把相关 度最高 的若干个网页的文档号与得分一起发送回前台的服务器。前台服务器收集几个检索机器上的结果，按得分归并后把最相关的网页返回给用户。 由于时间的关系本文必没有详细的研究检索系统的分布式结构，而是更多的关注各个检索节点上的效率。可以说，这两方面共同决定了一个检索系统的性能。 北京大学信息科学技术学院 网络实验室硕士学位论文 5 有系统的不足 与本文的主要贡献 现有的天网检索系统 ，是从天网 始，经过不断的完善和发展起来的。在几年里为老师和同学 们 的科研工作提供了一个重要的平台。但它还存在了一些问题需要我们去改善。例如以下几个方面： 1. 检索效率不高。每个检索节点检索的网页量大约在 二 百 多 万，每秒只能处理十几个的查询请求。主要原因是没有为倒排文件建立 次查询都要多次访问外存，磁盘成了系统的瓶颈。此外， 其 分布式结构 也 不太好，前台服务器与检索节之间基于同步的多进程的交互方式，也影响和整个系统的效率。 2. 倒排文件信息量不够。现在的倒排文件中，关键词在文档中的属性信息很少，只用两个 别表示词是否在网页 摘要中，并且不能为关键 词在文档中各个位置设立属性信息。由于 信 息量的缺乏，在计算词与文档相关性的时 候 ，往往不够准确。 3. 系统的可扩展性和容错性不足。系统现在运行在由一台前台服务器， 19个检索节点构成的分布式环境中。对于增加检索节点可能带来的广播风爆，以及增加前台服务器查询策略的变化，都没有考虑到。此外，数据没有冗余，当系统中部分机器出现故障，则会影响查询结果。 本文针对检索效率的 问题 进行了研究。设计出来更加良好的倒排文件结构，改进整数压缩算法，并增加倒排文件的信息量。通过有效 的 略，让索引尽量的在内存中 可 以找到，减少访问磁盘的 开销 。通过一些有效的预处理，减少了浮点运算的次数，也进一步的提高了检索效率。对于相关度计算，本文也做了一些 改进 ，使得在最后的结果排序上 更 符合用户需求 。此外，一个具有良好程序结构的可用系统，也很好的支持了文中提出的观点。在以下章节中，我们将详细的分析整个系统的设计 与 实现，以及设计背后 的 理论基础。 北京大学信息科学技术学院 网络实验室硕士学位论文 6 第 2章 倒排文件设计 本原则 前面提到过倒排文件的作用和基本结构，在新的系统中，为了 让 应用程序进行高效检索，并改进结果的排序，我们设计了新的倒排文件结构。在系统 的开发过程中，这个结构被修改了很多次，每个设计都各有利弊，最终确定的结构也不是在各方面都最优。但倒排文件的设计都必须遵循几个基本的原则： 文件必须是没有二义性，可以正确的还原出数据。例如当我们保存记录，在读取的时候就无法确定 处保存的是出现 该关键词的新的 一个 文档号，还是该 关键 词在 的下一个 出现位置。因此必须多保存一个词频信息，例如。 别表示词在 的出现次数。这样才可正确的还原出信息。 文件的规模应当尽量小，记录文件中每条记录应该占用尽可能小的空间，以减少读取记录时传输的数据量。方法是进行索引压缩 et 2002：使用变长的整数编码，用较少的空间保存较小的整数；整数使用差值存放，例如把文档号按升 序 排列，第一个文档号保存实际值，之后的都保存与前一个文档号的差值。关键词在文档中的位置也用类似的保存方法。差值表示法的另一个好 处 就是可以 更 方便的求多个文档列表的交集， 并且 更方便 的计算 多个 关 键 词 在同一 文档中的相对位置，在后面我们还会介绍。虽然对索引进行压缩会带来额外的数据解压 开销 ，但相对于它带来的好处，这种 开销 完全是值得的。 索引压缩减少了读取数据时从磁盘传输的数据量，但在检索 时 平均每个查询对磁盘的访问次数，更大的影响了检索效率。因此，设计倒排文件时，应当支持程序在最少次数内读取到需要的信息。例如在上一章中提到的，把文档列表连续的保存。 倒排文件的设计还必须考虑方便索引模块的建立， 以及 方便检索模块的操作，因此结构不应该太复杂。例如，在设计过程中参考了文献 彭波 ,2003中的倒排文件分块组织技 术，把文档根据属性的不同分块保存。表面上看查询时可以先读重要的文档列表，但在实现过程中却发现对于多个 关键 词组成 的 查询，操作起北京大学信息科学技术学院 网络实验室硕士学位论文 7 来 异 常 的 复杂，最终不 得不放弃。 数压缩编码方法 变长的整数编码可分为两类，字节对齐整数编码和非字节对齐整数编码。前者优势有较高的压缩比率，后者则有更高的压缩与解压效率。文献 彭波 ,2003认为，在搜索引擎的应用中，检索效率比索引数据占用的空间更为重要。文中对比了字节对齐编码 非字节对齐编码 et 1994，其压缩比率分别为 码时间比为 1:6。目前天网系统中使用的码在文献 赵江华 ,2002中有描述，它可对数值 从 0 至 230正整数进行压缩编码。用第一个字节的最高两位表示整数所占的字节数，则 1 字节的压缩整数包含 6 个有效位，可表示整数 0 至 63； 2 字节的压缩整数包含 14 个有效位，表示整数范围从 64 至 2143 字节可表示从 214 至 2224 字节可表示从222 至 230 在新的系统设计依然使 用 字节对齐的整数编码方式 ，用 示 ，但与 同， 用了可变长的位数来表示压缩整数的所占字节 数，并且根据计算机的字节序（ 用不相同的编码方式，加快解码速度。以 字节序为例，第一字节的最高位开始，如果连续 n 个位为 1，则表示压缩整数长度为 n+1 个字节 ，有效位从第一个为 0 的位开始 。例如第一个字节 110001101，从最高位开始连续出现 2 个 1，则说明整数占 3 个字节；又例如第一个字节 01100101，最高一位就是 0，说明整数占 1 个字节，该整数为的值为 99。由此我们可以得出， m 个字节的压缩整数可表示的整数 最大值 为28 m-(1。这种方法比 优势是只需一个字节就可表示从 0 至 127，对于小整数占多数的倒排文件来说，压缩率比较高，可以 为 每个 从 64 至 127 的整数节省去一个字节的空间。 但当整数的范围从 221 到 222，则会多占用一个字节。 扩展到无限大的正整数。以下是为 2576933 个文档建立倒排索引，对整数的使用情况统计： 北京大学信息科学技术学院 网络实验室硕士学位论文 8 表 数统计 整数范围 0 63 64 127 128 21616 22121 222 222 出现次数 2,822,189,488 245,763,951 1,191,448,544 21,135,917 206,389 29 节数 1 2 2 3 3 4 节数 1 1 2 3 4 4 可以算出，用 法节省了倒排文件的空间 45763951 245数的压缩率为 起 不小的提高。对于 编码方式略有不同，表示压缩整数长度的位从第一个字节的最低位开始，并且也先存放低 字节。这样做是为了提高编码和解码的效率。 统使用的倒排文件结构定义 新系统的倒排文件由描述文件，索引文件 和记录文件 组 成，下面分别对它们进行定义。 述文件 描述文件记录了倒排文件自身的属性信息。可用 = (= :” = 1* = (“|“)”|“”|“”|“,”|“:”|“”|“/”|“|“”|“?”|“=”|”“|”|” “|”t” 北京大学信息科学技术学院 网络实验室硕士学位论文 9 = * = “rn” 也就是说，描述文件包括零个或多个 的行，最后以一个空行为结尾。这与 议 消息头的定义类似。现在已定义的属性有： 性：表示倒排文件中使用整数的字节序，包含压缩整数和非压缩整数。如果我们使用统一 的节字 序 ，如 么在 机器上使用倒排文件则需要进行字节的交换，影响效率。所以我们允许自定义倒排文件的字节序。 属性值可以是 认值为 性：前面说过，索引文件中保存的是关键词和其位置信息在记录文件中的偏移量。为了节省空间 （主要是节省应用程序内存 开销 ） ，我们在这个文件格式中，使用了 32 位的偏移量。但是 32 位的偏移量最多可以表示 4当文档的数量比 较多，记录文件的大小肯定是要超 过 4。因此，这个格式中允许让记录文件中每个记录在某个边界上对齐，也就是说，让每个记录偏移量的 低 若干位总是 0，在索引文件中只保存高 32 位，再通过移位来获得记录的实 际 偏移量。 性就是表示移动的位数，默认为 0 位。由于要让记录在边界上对齐，势必引起一些空间的浪费。我们假设， n，倒排文件总关键词数为 m。则记录文件的大小应该在 4G 2 4G 2n 之间 (如果小于前者，则 于 足够了 )，平均每条记录的空间浪费是 2是，整个倒排文件中，浪费的空间总数为 m (2节。浪费的空间最大可能比例为 m (24G 2个属性信息 的意义在本格式中无定义，完全由应用程序决定。但规定属性信息必须是整字节的， 并且所有的属性信息必须等长 。 这个长度就是倒排文件的性。如果未标明，默认为 0。 性：压缩整数的编码方式。格式中有规定哪些整数是必须压北京大学信息科学技术学院 网络实验室硕士学位论文 10 缩 (如文档号 )，哪些是整数必须是非压缩 (如记录信息偏移量 )，但没有规定使用的压缩编码算法，应用程序可自行定义。 性默认为上节描述的 引文件 索引文件的结构比较简单，文件头用 4个字节的非压缩整数表示索引文件中总的关键词量，之后连续存放记录。用 = = = = * = = 可以看出，每个记录由 组成，分别表示关键词长度，关键 词 （长度为 关键词的出现位置 信息在记录文件中的偏移 量，以及关键词对应文档列表的字节长度。当我们要获得某个关键词的文档列表，首 先 获得关键词上述索引信息，把记录文件的文件指针移动到对应位置，再调用读操作，例如： (= = 由 个记录由文档列表信息（ 在 文档中 的 位置信息（ 成， 开始位置用一个压缩整数保存了 文档的个数，也就是词的文档频率（ 之后连续保存每个文档（ 信息，包括文档号（ 关键词在文档中的属性（ 关键词在本文档中位置列表的字节长度（ 组成，依次对应每一个文档。每个 词频（ 接下来用差值的形式连续存放各个位置（ 记录文件和索引文件的示意图 如图 ）。 可以看出，记录文件中每个记录里又包含了一级的索引，这个索引是从文档号到位置列表。但 是从 我们只保存了每个文档的位置列表的长度，并没有保存位置列表在记录文件中的实现位置，那么我们得到一个 后，如何读 取到位置列表呢？这就与我们对文档列表的访问方式有关。我们看到，这个记录中，只有 它两个都是变长整数，因此我们是不可能对文档列表进行随机访问的，只能顺序地读取。在搜索引擎的检索系统中，这种访问模式已经足够了。从图 中 我们又可以看出，所有的文档列表和位置列表都是连续存放的，所以，当我们读取文档列表的时候，只需把位置列表的长度累加起来，就可以得到下一个位置列表的相对于文档列表 末 尾的偏移。例如，第 文件中的实 际 位置为： 11_ _2 ni ig n l o s l i s tl o cl i s to 其中， 样的设计使程序在读取倒排文件的过程中，必须多保留一些信息，并增加了一些计算上的 开销 ，但北京大学信息科学技术学院 网络实验室硕士学位论文 12 由此带来的好处是减少了对空间的占用，这也就减少了读取磁盘的 开销 ，同时可能减少应用程序 空间 开销 。这个交换完全是值得的。 图 2 . 1 记录文件和索引文件的示意 X X X X 0 0 0 Y 0 0 0 Z Z Z Z 0 0 0 记录文件 索引文件 o f f s e t 1 = X X o f f s e t 2 = Y Y Y Y 北京大学信息科学技术学院 网络实验室硕士学位论文 13 第 3章 底层数据组织 响检索效率的主要因素 首先，我们有必 要 先了解一下一个查询被执行的过程。如图 示，当前台服务器通过广 播的方式把查询发送到检索节点上，检索节点首先对查询进行预处理，例如切词，如果支持布尔查询还必须对查询表达式进行分析生成一棵查询语法树。得到一系列的关键词之后，检索系统分别从倒排索引中找出各个关键词所对应的文档列表。一般而言，搜索引擎返回的各文档里都包含每个查询 关键 词，于是我们必须对获得到的文档列表求交集，查询的结果必然就落在这个交集里。接着对交集里的每一个文档，我们首先计算每个 关键 词与文档的相关度得分，再累加起来。这时候我们还没有利用到词在文档中的位置信息。例如我们的查询是“北京大学”，并且被切为“北京”和 “大学”两个 关键 词，那么，交集中这两个 词连续出现的文档显然相关度更高一些。此时我们就要利用到关键词在文档中的位置信息，对于那些连续出现这两 个 词的文档，再增加一些相对位置的得分。在算得每个文档与查询的相关度得分之后，我们还不能直接把排 好 序的结果返回给用户，因为结果中很多的文档都是在同一个站点之下的，对用户来说可能每个站点只需一个结果就够了，如果有需要可以再点击站内查询。于是，我们还需要根据站点对结果集进行聚类， 每个站点内只保留一个或两个结果， 把最重要的一些结果连同相关度得分返回给前台服务器。前台服务器收集到各 检索节点发来的结果，进行归并再把得分最高的返回给搜索引擎用户。 本文现在只关心检索节点做的事情，其中切词与检索效率关系不大，我们也不讨论。其它的包含以下五个部分： 1 获取文档列表 从倒排文件的结构中我们可以看出，要获得给定 关键 词的文档列表，首先要从索引文件中找到对应的入口，得到 后再到记录文件中读取文档列表信息。显然，从索引文件头开始顺序查找关键词是不现实的，与原有天网系统相同，我们把 个索引信息常驻内存。 而对于记录文 件中的文档列表信息，要让它们都常驻内存似乎就有一些困难了。但根据文献 王建勇等 ,2001， et 2001，用户查询词的分布具有很北京大学信息科学技术学院 网络实验室硕士学位论文 14 强的局部性，大多数经常被检索的词都是集中在一个很小的范围之内的。另外，该文献还提到，用户查询有一定的稳定性， 用 户在一段时间内发出的查询往往有一些相似。这两方面说明了对倒排文件使用 有效性，通过良好的 尽可能多的查询词在内存中找到对应的文档列表，减少访问磁盘的 开销 ，正是本系统中提高检索效率的一个重要方法。 2 文档列表求交集 前面提 到，从倒排索引中获得的文档列表一定是按文档号升序排列的，这就为我们求文档列表的交集带来了很多方便。新系统中，求文档交集的算法也有一些改进，由原来的每次两列进行求交，改为多列同时求交。但实验说明这一步操作并非影响检索效率的关键。 3 计算关键词与文档相关度 对各个关键词和文档求相关度得分是检索过程中使用 多的一个步骤，主要 是 浮点运算的操作。例如使用传统的 tf*计算方法，每个关键词相对于每篇文档，都至少要进行 3 次的取对数运算。虽然在检索系统中，对外存的访问时间是决定系统性能的关键，但如果可以节省相关度 计算的时间，也可以在一定的程度上提高检索效率。 4 计算相对位置 对于由多个 关键 词组成的查询，计算它们相对位置应该说是整个检索过程最耗时的部分。特别是当 关键 词都是高频词的时候，文档 列表 的交集 中的文档个数可能达到 上百 万个。此时读取每个词在每个文档中的位置信息，如果不进行特别处理，则要进行 上百 万次的读盘操作。如果对关键词在文档中的位置信息进行消耗的内存要比文档列表大得多。因此，提高计算相对位置的效率 也是改善系统整体性能的关键。 5 站点聚类 站点聚类不涉及对磁盘的操作，其效率并不会构成系统的瓶颈。但新的系 统还是改进了原有的算法，通过先聚类后排序的方式，减少了最终进行排序的文档量，从时间复杂度上对性能进行了优化。 在这一章里，我们主要讨论的是系统最 底 层的数据组织。这个模块为上层的模块提供了一个快速的访问索引文件的接口，同时它负责对文档列表和位置列表北京大学信息科学技术学院 网络实验室硕士学位论文 15 的 行 组织。我们将以模块的接口为主线来分析其数据组织。 建索引 要访问索引文件首先必须创建一个索引对象（ 其接口如下： 前三个参数分别是描述文件，索引文件和记录文件的文件名，最后一个参数 象可用的 文档列表 大值，必须根椐硬件条件来确定。在 件中我们可以看到如下的定义： _ _*; 当 调用时，描述文件和索引文件中的内容被一次地读入内存，索引文件中的索引信息被保存在 中，按照关键词升存排列，在查找时使用二分查找的方式。与原有系统使用散列查找的方法有所不同。原因是，使用散列将引起太多的内存浪费。可以大 致的计算一下，假设总的关键词数为 m，散列的空间至少需要 3m，则至少浪费 2m 个指针的空间。而 且 每个关键词入口还至少需要一个指针来解决散列函数的冲突，于是总的多余指针 开销 达到 3m 个。北京大学信息科学技术学院 网络实验室硕士学位论文 16 假设 m 等于 500 万，则浪费的总字节数为 3 500 万 系统地址长度，在 32 位系统下大约为 60由于关键词都已经一次性读入内存，对关键词的查找所占用的时间几乎可以乎略不计，在认真考虑之后系统使用了二分的查找方式。关键词列表在内存中的组织如下图： 图 3 . 1 关键词列表 t e r m _ e n t r y 1 t e r m _ e n t r y 2 t e r m _ e n t r 1 t e r m _ e n t r . t e r m _ l i s t i n d e x 关键词列表是一个指针的数 组， 各 指针指向的内存块中保存 的 关键词信息。但从图中我们 可以看出 ，这些内存块的长度并不一样，这是为了尽量节省内存的开销 而使用了变长结构，这个结构的定义如下： _ _; 8; 8; 北京大学信息科学技术学院 网络实验室硕士学位论文 17 ; ; 最后一个域 关键词的原