华夏英才基金学术文库
搜 索 引 擎
— 原理、技术与系统
Search Engine: Principle, Technology and Systems
李晓明 闫宏飞 王继民 著
by Li Xiaoming, Yan Hongfei and Wang Jimin
科 学 出 版 社
2 0 0 4
内 容 简 介
本书比较系统地介绍了互联网搜索引擎的工作原理、实现技术及其系统构建
方案。全书分三篇共 13 章内容，从基本工作原理概述开始，到一个小型简单搜索
引擎实现的具体细节，进而详细讨论了大规模分布式搜索引擎系统的设计要点及
其关键技术；最后面向主题和个性化的 Web 信息服务，阐述了中文网页自动分类
等技术及其应用。本书层次分明，由浅入深；既有深入的理论分析，也有大量的
实验数据，具有学习和实用双重意义。
本书可作为高等院校计算机科学与技术、信息管理与信息系统、电子商务等
专业的研究生或高年级本科生的教学参考书和技术资料，对广大从事网络技术、
Web 站点的管理、数字图书馆、Web 挖掘等研究和应用开发的科技人员也有很大
的参考价值。
前 言
随着互联网的不断发展和日益普及，网上的信息量在爆炸性增长，在 2004
年 4 月，全球 Web 页面的数目已经超过 40 亿，中国的网页数估计也超过了 3 亿。
目前人们从网上获得信息的主要工具是浏览器，而通过浏览器得到信息通常有三
种方式。第一，直接向浏览器输入一个关心的网址（URL ），例如
http://net.pku.edu.cn，浏览器返回所请求的网页，根据该网页内容及其包含的超链
文字（anchor text）的引导，获得自己需要的内容；第二，登录到某个知名门户网
站，例如 http://www.yahoo.com，根据该网站提供的分类目录和相关链接，逐步“冲
浪”浏览，寻找自己感兴趣的东西；第三，登录到某个搜索引擎网站，例如
http://e.pku.edu.cn，输入代表自己所关心信息的关键词或者短语，依据返回的相关
信息列表、摘要和超链接引导，试探寻找自己需要的内容。
这三种方式各有特点，各有自己最适合的应用场合。第一种方式的应用是最
有针对性的，例如要了解北京大学计算机系网络与分布式系统实验室在做些什么
工作，从某个渠道得知该实验室的网址为 http://net.pku.edu.cn，于是直接用它驱动
浏览器就是最有效的方式。第二种方式的应用类似于读报，用户不一定有明确的
目的，只是想看看网上有什么有意思的消息；当然这其中也可能是关心某种主题，
例如体育比赛，家庭生活等等。第三种方式适用于用户大致上知道自己要关心的
内容，例如“国有股减持”，但不清楚哪里能够找到相关信息（即不知道哪些 URL
能给出这样的信息）；在这种场合，搜索引擎能够为用户提供一个相关内容的网址
及其摘要的列表，由用户一个个试探看是否为自己需要的。现在的搜索引擎技术
已经能做到在多数情况下满足用户的这种需要。CNNIC 的信息统计指出，目前搜
索引擎已经成为继电子邮件之后人们用得最多的网上信息服务系统。
同时，随着网上信息资源规模的增长，尤其是其内容总体和我们社会的演化
发生着越来越密切的联系，研究网上存在的海量信息逐渐成为许多学科关注的一
个方向。为此，不少研究人员也有采样搜集特定内容、一定数量网页的需要。
本书以我们设计、实现并维护运行北大“天网”搜索引擎的经验，介绍
大规模搜索引擎的工作原理和实现技术。我们要向读者揭示，为什么向搜索
引擎输入一个关键词或者短语，就能够在秒钟内得到那么多相关的文档及其
摘要，而点击其中的链接就能够被引导到文档的全文，且其中相当一部分可
能正是用户需要的。
我们按照上、中、下三篇展开相关的内容。上篇讲搜索引擎的基本工作
原理，要解决的是为什么搜索引擎能提供如此信息查找服务的问题，以及它
在功能上有什么本质的局限性。这一篇的内容包括网页的搜集过程，网页信
息的提取、组织方式和索引结构，查询提交和响应的过程以及结果产生，等
i
等。这其中，虽然我们假定读者熟悉 URL，HTML，HTTP，CGI，MIME
等基本概念，但在上下文中也给予了必要的介绍，力图保持行文的流畅性。
这一部分内容对于需要构建小规模搜索引擎的研究人员会有直接的参考价
值。
中篇讨论和大规模实用搜索引擎有关的技术问题。所谓大规模在这里指
至少维护超过 1 千万的网页信息，提供相关的查询服务。所涉及的内容包
括并行分布处理技术的应用，数据局部性的开发，缓存技术的应用，以及搜
集的网页在提供服务之前的预处理问题和高效倒排文件的建立技术等等。这
一部分的讨论有比较强的计算机系统结构的风格，我们向读者展示计算机系
统结构课程中的那些概念是如何生动地体现在一个实际应用系统中的。这一
部分的内容对构建大规模数字图书馆的技术人员也应该有帮助。
下篇介绍挑战性更强一些的内容。一般地讲，前面所述可以称为是“通
用搜索引擎”，为最广泛的人群提供信息查询服务是它的基本宗旨。这意味
着它的应用模式必须尽量简单，即关键词或查询短语的提交和匹配响应。尽
管这已经可以解决许多问题了，但对有些重要的信息需求依然显得力不从
心。例如，一个人可能会关心最近半年来网上出现了哪些关于他（她）的信
息，一个企业可能要关心它做了一次大规模促销活动后一个月内网上有什么
反响，一个政府机构可能会关心在一项政策法规颁布后的网上舆论。面向主
题和个性化的信息查询服务就是我们试图描述的一种基本途径。这一部分内
容更多的和网上中文信息处理技术有关。更准确地讲，我们要介绍网络与并
行分布处理技术与中文处理技术的结合，从而实现大规模、高性能、高质量、
有针对性地网上信息查询服务。这一部分内容反过来可能对从事中文信息处
理的研究人员有启发作用。
本书的内容是集体智慧的结晶，主要概括了北大计算机系网络与分布式
系统实验室自 1996 年以来的研究成果。其中许多段落直接来自同学的博士
和硕士论文，他们是雷鸣、赵江华、冯是聪、单松巍、谢正茂、彭波、张志
刚、龚笔宏、孟涛、昝红英，等等。署名作者的主要工作是将这些内容系统
化，使其表述的风格统一。我们特别感谢陈葆珏教授，是她在北京大学计算
机系开创了搜索引擎这一研究方向，从而使我们能在其后发扬光大，还要感
谢刘建国和王建勇，是他们分别带领攻关队伍，实现了天网 1.0 和天网 2.0
版本。感谢黄蕊为本书进行的文字校对。最后，我们感谢国家“九五”攻关
计划，“973”计划和“985”计划的支持，是它们的不断支持使我们得以
将天网不断推上新的台阶，实现“让天网和中国网上信息资源规模同步成长”
的理想。
作者
2004 年 5 月于北大燕园
ii
目 录
前言
第一章 引论................................................................................................................. 1
第一节 搜索引擎的概念 ................................................................................................ 2
第二节 搜索引擎的发展历史 ........................................................................................ 3
第三节 一些著名的搜索引擎 ........................................................................................ 7
上篇 WEB搜索引擎基本原理和技术 .................................................................... 16
第二章 WEB搜索引擎工作原理和体系结构 .......................................................... 17
第一节 基本要求.......................................................................................................... 17
第二节 网页搜集.......................................................................................................... 18
第三节 预处理.............................................................................................................. 20
第四节 查询服务.......................................................................................................... 22
第五节 体系结构.......................................................................................................... 25
第三章 WEB信息的搜集.......................................................................................... 29
第一节 引言.................................................................................................................. 29
一、 超文本传输协议.............................................................................................. 29
二、 一个小型搜索引擎系统.................................................................................. 31
第二节 网页搜集.......................................................................................................... 33
一、 定义URL类和Page类...................................................................................... 34
二、 与服务器建立连接.......................................................................................... 39
三、 发送请求和接收数据...................................................................................... 41
四、 网页信息存储的天网格式.............................................................................. 42
第三节 多道搜集程序并行工作 .................................................................................. 45
一、 多线程并发工作.............................................................................................. 46
二、 控制对一个站点并发搜集线程的数目 .......................................................... 47
第四节 如何避免网页的重复搜集 .............................................................................. 47
一、 记录未访问、已访问URL和网页内容摘要信息 .......................................... 47
二、 域名与IP的对应问题 ...................................................................................... 48
第五节 如何首先搜集重要的网页 .............................................................................. 49
第六节 搜集信息的类型 .............................................................................................. 52
第七节 本章小结.......................................................................................................... 54
iii
评论1