【毕业学位论文】（Word原稿）一个大规模、高性能的搜索引擎系统的设计与实现

北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 1 页 摘要 本文首先回顾了 起源和发展。面对极其大量的信息，人们通常依靠搜索引擎来为他们在 进行导航，这给搜索引擎技术带来了巨大的挑战。自 1994 年问世以来，搜索引擎的发展经历了四代。我们对每一代搜索引擎及其特色进行了简要的陈述。 搜索引擎是一个集多种技术于一体的综合性系统。在本文的第二章，我们就搜索引擎涉及到的某些核心背景技术，如搜索技术、 术、超文本链分析技术、用户行为分析技术，进行了讨论，并说明了这些技术对搜索引擎发展的影响和作用。 “天网”是国家“九五”攻关项目中的一个子专题。在借 鉴和参考大量国内外相关研究的同时，根据中国 特点，我们设计了一个大规模、高性能的搜索引擎系统。在第三章，我们根据 特点和搜索引擎的功能，根据图论、集合论及关系模型构建了“天网”搜索引擎的理论模型，并且以理论模型为出发点，设计了整个系统的体系结构。 在文章的主体部分，我们以搜索引擎中数据流程为主线，描述了搜索引擎的几个子系统：搜集子系统、分析子系统、索引子系统、检索子系统以及用户界面和日志挖掘子系统。在这些章节中，特别强调“天网”所采用的相关技术和关键算法：分布式并行搜集技术、启发式搜集策略、 镜像消除技术、中英文特征项提取技术、高效索引技术、词典更新技术、超链分析技术、快速检索技术、相关度评价策略、 序算法、 略、中文词汇学习技术和用户行为分析技术。 最后，我们简要的介绍了系统的实现和性能，并对“天网”系统提出了一些今后的发展设想。 关键词 ：搜索引擎， 息提取，分布处理 北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 2 页 n of WW on on to 994, is a , to to is is a WW we a of In we a on In we In on we of 京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 3 页 目录 摘要 （中文） . 1 摘要（英文） . 2 目录 . 3 第一章 引言 . 5 起源和发展 . 5 索引擎作用、起源和发展 . 6 第二章 相关研究及技术 . 8 规模的搜索技术研究 . 8 R 相关技术的研究 . 10 文本链相关的研究 . 11 户行为的分析研究 . 14 第三章 天网搜索 引擎的体系结构 . 16 网搜索引擎的理论模型 . 16 集的定义 . 16 索引擎索引系统的定义 . 17 索的定义 . 18 索引擎系统的更新过程 . 18 网搜索引擎的系统结构和子系统划分 . 19 第四章 系统剖析 . 22 页的获取 . 22 组织结构和网页的发现和获取策略 . 22 行搜集 . 23 布式搜集系统 . 24 该首先去抓下哪个网页 . 26 北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 4 页 像网页的消除 . 27 页的分析 . 28 统 方法 . 28 文的编码处理 . 29 文和中文特征项提取 . 29 征项的权值 . 30 成网页的描述信息 . 32 引的生成 . 33 引的 结构 . 33 引系统的创建 . 35 典的结构和生成 . 36 页索引的生成 . 37 链分析 . 38 索 . 39 到相关网页 . 40 关度计算 哪个网页用户最想得到 . 41 序 保持检索的复杂度在 O(n) . 43 统 让大量的检索成为 0 时间检索 . 44 户界面和用户行为的 跟踪学习 . 46 户的界面技术 . 47 文新词学习技术 . 48 户行为对网页权值的影响 . 50 第五章 结论和展望 . 54 统的开发和实现 . 54 统的运行相关的数据和系统的性能 . 54 统发展的展望 . 55 参考文献 . 56 致谢 . 58 北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 5 页 第一章 引言 起源和发展 源于 1989 年欧洲粒子物理研究 室 ( 物理学家 1989 年 3 月提出的，第一个原型（基于文本）于 18 个月后运行。 1991 年 12 月在德克萨斯州的 1 超文本会议上进行了一次演示，并于 1993 年 2 月，随着第一个图形界面 1 核心技术是超文本和超媒体。通过将文本、图形、图象、音频、视频等信息的有机结合，给人们提供了丰富的信息表示空间。由于其界面友好、易学易用、内容丰富，很快便被政府机关、科研机构、商业企业 和个人所接受，成为人们日常信息交流的一个简单易用的工具。在 1993 年下半年， 不到三个月的时间里翻了一翻。在 1995 年 4 月， 网上的流量超过了其它其它服务的流量，成为 的第一大应用服务。到 1997 年 12 月，根据 究院在科学杂志上发布的数据 2，网上大约有 3 亿 2000 万网页。 在最近两年里， 得到了长足的发展，不仅成为企业必不可少的组成部分，并且开始走进千家万户。根据 究院在自然上发布的数据 3，截止到 1999 年 2 月， 共有网站 1600 万个，其中公开提供 务的网站 280 万个；共有 页大约 8 亿页，这些网页包含了 15T 字节的数据。按照 2000 年 4 月在波士顿举行的第 5 届搜索引擎年会的会议报告 4，我们可以知道现今的网页数目已经超过了 10 亿。 1994 年登陆中国，到现在仅仅 6 年的时间里发展速度惊人。根据国互联网络信息中心 )在 2000 年 1 月的统计信息表明 5，中国已有上网计算机 350 万台，其中 点 15153 个；上网人数 890 万。关于网页的北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 6 页 数目没有具体的统计数据，但根据科学杂志上提 供的集合估计法 2，通过中国几个主要搜索引擎获得的搜索数据（天网、新浪、搜狐、网易），我们可以估计到当前中国拥有的网页数已经超过 1000 万。 索引擎作用、起源和发展 发展给人们带来了巨大的方便，使得人们可以跨越时间和空间的界限来共享大量的信息。我们可以直接到其它的科研机构阅读我们感兴趣的文献；我们可以不用出户购买我们需要的东西；我们可以实时的了解国内外的新闻焦点 。但是，面对如此大量的信息，我们同时也开始感到无所适从。太多的信息使我们很难迅速定位我们真正需要的信息，而跟随超链在 漫游则会浪费大量的时间，而且很可能徒劳无功。因此，人们迫切需要有效的信息发现工具来为他们在 进行导航。 网上出现了两大类提供 航的系统。第一类是目录系统，它通过有专业知识的网页编辑人员对网上的网页进行精选，建立一个索引目录，来给用户提供服务。这类系统的优点是提供的网页准确率高，但覆盖的范围小，其典型代表是 二类是搜索引擎系统，它通过程序自动地从网上搜集和分析网页，建立索引，为用户服务。这类系统的的优点是涵盖的网页数量巨大，但搜索的准确率相对比较低，其典型代表是 下面我们主要进行搜索引擎相关的介绍和发现。 搜索引擎面世后，虽然抱怨不断，但它迅速成为人们网上搜索的有效工具。根据统计，大约 85%的用户使用搜索引擎去定位他们需要的信息 6；并且，几个著名的搜索引擎一直都稳定的处于全球访问量最大的 10 个网站之列 7。 搜索引擎出现于 1994 年，例如 们称这些搜索引擎为第 0 代搜索引擎。这些搜索引擎的目的是出于研究的目的，它们一般都索引少于 100 万个网页，极少重新搜集网页去发现新的网页并去刷新索引。这个时 期的搜索引擎的检索速度非常之慢，一般都要等待 10 秒甚至更长的时间。 北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 7 页 两年后，第 1 代搜索引擎出现了。这些搜索引擎一般每天能够接受 1000 万次检索，并保持一个大约 5000 万网页的索引为用户提供服务。这一代搜索引擎的先驱是 它们的实现方法也大不相同。 用大型的多处理器计算机来支持它们搜索引擎的运转；而 采用分布式方案来解决搜索引擎对计算能力的要求。 大概又有两年的时间，开始了一个搜索引擎空前繁荣的时期，我们统称这一时期的搜索引擎为第 2 代搜索引 擎。在这一时期，有几个发展的特点： 除了一般意义上的搜索以外，开始出现主题搜索和地域搜索。很多小型的垂直门户站点开始使用该技术。 由于搜索返回数据量过大，检索结果相关度评价成为研究的焦点。相关的研究又可以分为两类：一类是对超文本链的分析，在这方面 学的 统作出了很大的贡献；另一类是用户信息的反馈，统采用的就是这种方法。 开始使用自动分类技术。 在一定程度上使 用了该技术。 这一阶段的发展为搜索引擎拓展了生存空间，同时提高了搜索的质量和效率，为以后的发展奠定了坚实的基础。 现在我们正在进入第 3 代搜索引擎的发展时期。这一时期以尝试索引“整个标志。几个主流的搜索引擎，如 不断扩展自己的搜集能力，企图将整个 的数据都搜集到，建立索引并为用户提供服务。同时，第 2 代搜索引擎的相应技术进一步发展和完善，尤其是相关度评价技术。另外，个性化检索也成为研究的热点。根据用户注册的信息，以及用 户日常检索的行为，为用户提供最适合他期望的检索结果已经越来越受到各个搜索引擎的关注。 北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 8 页 第二章 相关研究及技术 搜索引擎是伴随 发展而迅速发展的一种技术。在起先的阶段，大家主要的着眼点还在于科学研究，所以相关的技术和算法都是公开的，没有什么秘密可言。但一段时期以后，当搜索引擎的巨大商业利益被发现后，很多以搜索引擎的研制和运营为其主要业务的公司兴起了，如 。很多的研究项目，当发展到一定的阶段，也就是可以商业化运作时，就从项目中剥离出来，成立自己的品牌公司。 学的 是典型的一例。 在商业竞争中，技术手段就被作为公司的头等机密保护了起来。很显然，透露了核心技术就意味着丧失了公司的一部分优势，就会在激烈的竞争中处于劣势。公司的竞争对搜索引擎技术的发展产生了两个方面的影响：一方面，竞争迫使每个搜索引擎公司都要投入大量的人力物力研究新的技术，促进了搜索引擎的发展；另一方面，由于各公司的技术相互保密，也导致了在研究上的大量的重复，而带来大量的人力物力上的浪费。 虽然各个公司在其核心技术上严格保密，但幸运的是还有很多的大学、科研机构在从事这一方面的研究， 这使得我们仍然可以找到有着很高学术价值的文章。另外各个公司虽然不透露核心技术，但是从它们对自己搜索引擎的宣传以及在一些国际会议上的演讲，我们仍然可以从大体上看到它们采用的核心技术的轮廓。 在下面的篇幅里，我们就当前影响到搜索引擎发展的一些相关技术做以下简要的回顾。 规模的搜索技术研究 据最大的一个特点就是数据量巨大，数据增长速度快。所以搜索引擎北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 9 页 如何能够最大限度、最高效的获取网络上的网页，成为搜索引擎的一个研究热点。分布处理（ 术是一个研究的 热点，并且被很多搜索引擎系统的应用证明是行之有效的技术。 统是 1994 年美国 息资源发现服务领域开展的研究工作成果。作为 息发现研究课题组的核心项目， 设计目标是在国家信息基础设施上提供资源发现服务。 考虑到大多数资源索引系统彼此间对信息收集缺乏协作，使它们对网络和服务器增加了不必要的负载。 计了有效的收集和分布 索引信息的方法。图 示了 整体结构 8910。 如图 示， 若干子系统组成。 信息资源站点 务器）上提供的资源中收集索引信息（如关键词，作者，标题等）。 一个或多个 取回索引信息、去掉重复的信息、存 储 下 来 并 提 供 一 个 查 询 界 面 。图 于在 复制 信息。 为了减少网络流量 、加快用户访问息资源的缓冲。 一个被称为 特殊 保存网上所有的 有关信息。 图 系统构成 北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 10 页 出了一个广域网信息搜集、查询的分布式体系结构，有很多设计思想被以后的其它系统借鉴和利用。但是， 统庞大、算法复杂、开销巨大，使得其仅仅停留在科学研究的阶段，而没有成为真正的 务。 为了对付网络上数以亿计的网页和 3月翻 一翻的增长速度，各个搜索引擎公司基本上都采取了分布和集群的搜索策略。按照 司总裁 000 年大会上的演讲， 在用 3,000 台运行 统的个人电脑在搜集 的网页，而且以每天 30 台的速度向这个微机集群里添加电脑，以保持与网络的发展相同步。 司也正在依赖强大的微机集群，逐步实现索引整个 设想。 R 相关技术的研究 搜索引擎最重要的作用就是从大量的网页中找到所需要的网页，笼统的讲，就是根据一些检索项找到相关信息的过程， 这也正是 究的核心内容。 计算机科学发展中是一个悠久历史的领域。从本世纪 70 年代起，基于图书馆、档案馆等地方对检索的需要， 始进入了一个蓬勃发展的时期。到90 年代， 研究已经相对成熟，出现了很多成熟的模型和算法。其中的向量空间模型 11和 tf*法 12对搜索引擎的检索技术起到很大的影响。早期的搜索引擎（在第一章中我们提到的第 0 代搜索引擎）基本上采用 相应技术。 但是，随着 发展和人们对搜索引擎检索质量要求的不断提高，原 有的仅仅依赖 术的搜索引擎检索策略已经不能满足人们的需要。其原因在于传统的 法有两个重要的内在假设： 1. 被索引的信息本身有着很高的质量，至少在信息的组织和内容上有着比较高的质量。在 现以前，传统的 所以能够行之有效至少在部分上是依赖这一点的。很多的 品一般都是针对一个特定的领域，如：北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 11 页 法律信息、医疗信息、环保信息等等。这样它们可以针对这个领域进行算法的优化，同时，也避免了对一词多义的处理。 2. 检索信息的用户有一定的相关技能和知识。也就是说，当用户面对一个很大的信息源时，他知道通过什么样的手段 去提高检索的准确率 (，但同时又不降低系统的招回率 (与此相对应的，传统的 统总是提供一套十分完善的复杂检索语法来满足用户的要求。 但不幸的是，这些假设在 都已不再成立： 1. 网页的质量参差不齐，大量的网页组织性、结构性比较差。同时，是一个无所不包的载体，它涉及到政治、经济、教育、生活等各个层面。这使得 的很多技术都没有了施展才能的余地。另外，网络上充斥着很多没有任何意义的网页，很多镜像的网页，如果不采取相应的技术处理，将会在很大程度上影响检 索质量。 2. 大部分检索用户是没有任何经验的。他们经常只输入一个或者两个检索词来检索他们需要的网页，但会得到大量的返回结果，很难达到满意的程度。很少的用户尝试使用逻辑运算来提高检索的质量。但遗憾的是，在这些用户输入中，很大一部分在表达上仍然存在各种各样的问题。 基于以上的讨论，人们发现，原有的 术已经不能适应 发展。必须改进原有的 应技术，研究新的适合 技术的算法，提高 索的质量。 文本链相关的研究 和传统 们发现 超 文本链。如果我们将每个网页认为是一个节点，每一条超文本链认为是一条有向边，那么整个 构成了一个庞大的有向图。这给我们了一个重要的启发，到底我们能利用图论的相应理论，从这个有向图中得到什么有用的信息呢？学的 3研究小组和 415系统开发小组同时注意到了这个问题。它们根据自己对这个有向图的理解，提出了自己各自的理论北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 12 页 模型。 统称它们的相应技术为 6。它们提出了一个“随机冲浪”模型来描述网络用户对网页的访问行为。 模型假设如下： 用户随机的选择一个网页作为上网的起始网页； 看完这个网页后，从该网页内所含的超链内随机的选择一个页面继续进行浏览； 沿着超链前进了一定数目的网页后，用户对这个主题感到厌倦，重新随机选择一个网页进行浏览，并重复 2 和 3。 按照以上的用户行为模型，每个网页可能被访问到的次数就是该网页的链接权值。如何计算这个权值呢？ 用以下公式进行计算： N 1 ,)1( （ 其中 表第 j 个网页的权值； 取 0、 1 值，代表从网页 i 到网页 j 是否存在链 接； 表网页 i 有多少个链向其它网页的链接； d 代表“随机冲浪”中沿着链接访问网页的平均次数。选择合适的数值，递归的使用以上公式，即可得到理想的网页链接权值。 它们的系统进行了测试，认为该方法能够大幅度的提高简单检索返回结果的质量，同时能够有效的防止网页编写者对搜索引擎的欺骗。当 即走出了大学，成立了 司，并且在竞争激烈的搜索引擎市场占有了一席之地，这也从另一个侧面反映了该技术的有效性。 究院 统中的相应技术称为 17。 择两种类型的网页： 1. 权威型网页：对于一个特定的检索，该网页提供最好的相关信息； 2. 目录型网页：该网页提供很多指向其它高质量权威型网页的超链。 北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 13 页 当遇到一个检索时， 利用检索的关键词得到一个网页的根集合。然后根据这个集合在整个网页有向图中位置来扩展这个根集合。具体办法是，将被链接的网页加入到这个根集合中，形成一个新的集合。重复上述步骤，使根集合扩展到一个包含 1,000 到 5,000 的网页集合。 得到这个集合后 ，就开始计算集合中每个网页的目录型权值和权威型权值。做法是采用目录型网页和权威型网页相互评价的办法，采用递归的算法进行计算。对于一个网页 p，用 表示网页 p 的权威型权值，用 表示它的目录型权值，并且用如下公式进行计算： a c a c （ 下面讨论该公式的矩阵表示。令所有选出来的网页都进行标号，我们得到所有网页的编号集 1,2,n 。令相邻矩阵 A 为一个 n*n 的矩阵，如果存在一个从网页 i 链接到网页 j 的超链，就令矩阵中的第（ i,j）项置 为 1，其它各项置为 0。同时，我们将所有网页的权威型权值 x 和目录型权值 y 都表示成向量形式 x = ( x n)， y = ( y n)。由此我们可以得到计算 x 和 y 的简单矩阵公式： )( （ 经过一定次数的递归运算后，会得到集合中每个网页的权威型权值和目录型权值。按照这两个不同的权值，分别取出前 k 个返回个用户。根据 统自己的测试数据，对于返回给用户的前 10 个检索结果， 统在 50%的情况下获得了高于 用户评价。 通过上面的分析，我们发现这两种方法有很多相似之处。它们都利用了网页和超链组成的有向图，根据相互链接的关系进行递归的运算。但是，两者又有很大的区别，主要在于运算的时机。 在网页搜集告一段落时，离线的使用一定的算法计算每个网页的链接权值，在检索时只需要从数据库中取出这些数据即可，而不用做额外的运算。这样做的好处是检索的速度快，但丧失了检索时北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 14 页 的灵活型。 用即时分析运算策略，每得到一个检索，它都要从数据库中找到相应的网页，同时提取出这些网页和链接构成的有向子 图，再运算获得各个网页的相应链接权值。这种方法虽然灵活性强，并且更加精确，但在用户检索时进行如此大量的运算，会导致检索效率的急剧下降。 户行为的分析研究 和传统 用户群相比，虽然搜索引擎的用户群的经验少，但他们的数量却十分巨大。（图 如 种知名的搜索引擎，每天都有多于 1000 万次的用户检索。通过对这些用户检索行为的统计分析，我们可以从中获取大量的有用信息，这些信息可以大大提高搜索引擎的结果的准确率，提高检索的质量。 8技术就是基于以上思想创立的。这项技术的主要特点是跟踪用户对检索结果的后继行为：哪些站点被用户选择浏览了？用户在这个站点上花费了多少时间？通过对这些数据的统计，搜索引擎就可以提高那些经常被用户选择，而且花了大量时间去浏览的站点的权值，惩罚那些被用户忽略的站点的权值。对于新加入系统的网页，系统则先给它们一个缺省的权值，然后由用户来决定它们的重要性。另外，系统还可以利用以前的用户检索行为来对以后的相似检索进行优化，帮助用户尽快发现自己需要的信息。 图 统 R 的用户群差别 北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 15 页 这个技术的另一个优点就是可以对一个固定的用户的行为进行跟踪和统 计，进而发现这个用户的喜好和对检索结果的期待，从而产生专门针对该用户的检索结果。这就是我们提到的个性化检索。 例如，一个做建筑材料的工程师，当他检索“ 他最大的可能是关注有关窗户的问题；一个计算机工程师，同样的检索则更关心微软的 过几次用户检索行为的跟踪学习，我们就可以获得这些信息，进而在以后的检索中，我们就对检索的输出结果进行针对用户的适应性调整。 司的总 裁搜索引擎 1999年年会上对他们的技术进行了高度的评价，并且将搜 索引擎使用的四种技术（ 1. 根据网页本身信息（ 2. 根据 超 链 链 接 关 系 （ 3. 人工编辑产生的目录系统（ 4. 根据用户行为（ 行了比较（得出根据用户行为的技术比其它几种技术无论在准确率和招回率上都有相当的优势。 另外值得一提的是微软的 索引擎。在 1998 年， 索引擎完全依赖于 仅是在 搜索引擎外加了一个 界面。但这正是微软发展搜索引擎的策略。通过用户检索日志的积累，微软获得了大量的 宝贵数据。进而对这些日志的统计分析，微软得到了例如用户检索的分布，用户检索的规律，热点站点的分布等重要的数据。依赖这些数据，微软在 1999 年 3 月发布了它们的第一个搜索引擎，并将其集成到 。 图 供的几种搜索引擎的比较 北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 16 页 第三章 天网搜索引擎的体系结构 为了方便日益增多的国内用户，促进 尤其是 中文信息的交流，增强全世界华人的凝聚力， “九五”攻关项目“计算机信息网络及其应用关键技术研究”中设立了“中文编码和分布式中英文信息发现”子专题，北京大学网络研究室承担了该子专题的部分研究开发工作，设计 开发了“天网”中英文搜索引擎（ 192021。 1997 年 10 月 29 日，天网搜索引擎正式在 提供查询服务，受到学术界广泛好评。软件世界（ 1998 年 7 月）将天网评为国内最值得关注的搜索引擎， 1998 年 12 月，天网通过了 鉴定。之后，天网又进行了大量的技术创新和系统的完善。到目前为止，天网总访问量已经突破 5,000,000，并且仍以每天大于 30,000 的访问量递增。 网搜索引擎的理论模型 集的定义 根据相关技术部分的讨论，我们在 搜索引擎研究中可以将 象为一个有向图。我们定义整个 应的有向图为 w e bw e bw e b (其中 所有网页的集合， 所有超链的集合。 网页的搜集其实相当于一个有向图遍历的过程，令 P 为搜索引擎已经访问的网页，而 L 为搜索引擎已经访问的超链，我们定义已经遍历的有向子图为 (下面我们定义搜索策略函数 的作用就是根据已经遍历的有向子图来选择下一个要搜集的 页面。 h e r w e bs e l e c t )( (北京大学硕士研究生学位论文 一个大规模 、高性能的搜索引擎系统 第 17 页 由公式 (我们获得一个待收集的网页 p。通过网页获取