搜索引擎原理技术与系统第二版.pdf
http://www.100md.com
2019年12月19日
 |
| 第1页 |
 |
| 第10页 |
 |
| 第13页 |
 |
| 第28页 |
 |
| 第46页 |
 |
| 第254页 |
参见附件(3534KB，279页)。
搜索引擎原理技术与系统第二版是基于第一版打造的升级版本，里面详细的介绍了互联网搜索引擎的原理，对于从事该方面的用户来说，这本书是非常值得一读的!
搜索引擎原理技术与系统介绍
《搜索引擎——原理技术与系统(第二版)》系统介绍了互联网搜索引擎的工作原理、实现技术及系统构建方案。《搜索引擎——原理技术与系统(第二版)》分三篇共13章。上篇介绍搜索引擎的基本原理和技术，讲述一个小型简单搜索引擎实现的具体细节；中篇详细讨论了大规模分布式搜索引擎系统的设计要点及其关键技术；下篇结合“中国Web信息博物馆”和“中国互联网数字资源财富库藏”的实践经验，介绍了构建大规模Web历史网页和非网页仓储系统的技术和方法，以及中文网页的自动分类与聚类、开放域问题系统的构建等。
《搜索引擎——原理技术与系统(第二版)》层次分明，由浅入深，上篇和中篇涉及内容提供了源代码地址；既有深入的理论分析，也有大量的实验数据和程序，具有学习和实用双重意义。
搜索引擎原理技术与系统部分章节
第一章 引论，上篇：Web搜索引擎基本原理和技术
第二章 Web搜索引擎工作原理和体系结构
第三章 Web信息的搜集
第四章 对搜集信息的预处理
第五章 信息查询服务
第六章 可扩展搜集子系统
第七章 网页净化与消重
第八章 高性能检索子系统
第九章 相关排序与系统质量评估
搜索引擎原理技术与系统概述
2005年4月，在华夏英才基金的支持下，本书的第一版问世。当时，互联网搜索引擎虽然在网民中已经不是一个陌生的概念，但是很少见到针对实际系统的构建，比较系统地介绍搜索引擎原理与实现技术的书。因此本书第一版的出版应该说比较及时，对不少年轻计算机技术人员起到了启蒙的作用。的确，在过去这些年里，我们多次收到读者的反馈，告知那本书对他们职业生涯的作用。最初的读者中，现在有许多都是搜索公司的骨干了。截止到2011年5月，《搜索引擎——原理、技术与系统》已经印刷了七次。一本比较专业的书，能得到那么多读者的喜欢，我们甚感欣慰。
同时我们也看到，随着互联网长盛不衰的发展，搜索的重要性日益突出；而且我们还看到一个现象，那就是相当一批有实力的互联网公司都有进入搜索领域的战略和行动，并不因为有了百度和谷歌就放弃那个市场。这种现象造成了搜索技术人才的很大缺口，尤其是有一定实际开发搜索引擎经验的人才缺口。很多高校看到这种需求，纷纷开设相关课程。许多学者看到这种需求，也纷纷写出各具特色的教材和专著。例如，郭军的《Web搜索》，董守斌和袁华的《网络信息检索》，以及刘奕群、马少平、洪涛和刘子正的《搜索引擎技术基础》。许多出版社也看到了这种需求，引进了大量相关的外版书籍。
那么，既然市场上已经有了这么多关于搜索引擎技术的书，为什么还要出版本书呢？其实这个想法我们4年前就有了，由于客观原因而耽误下来。最根本的原因是，搜索引擎技术的发展和对搜索引擎技术前沿认识的深入，使得我们感到原来书中的有些内容不再重要，而有些新的内容应该包括进去。
2003年秋，在编写本书第一版的时候，主要工作基础是“天网搜索”，它曾经是中国最好的，是我们引以为自豪的搜索引擎。围绕“天网搜索”的开发，北京大学网络实验室培养了一批优秀的学生。本书第一版的内容大都是那些同学实际工作经验的总结，因此一方面总体看的确比较实用，但另一方面某些部分也不够成熟和深入。同时，过去7年来，北京大学网络实验室在搜索引擎技术方面的研究工作也有了深入进展，尤其在搜索评测与高性能索引结构方面取得了一批前沿成果，这些都是在修订中要考虑的内容。
本书保留了第一版上篇的大部分内容，即搜索引擎的基本原理，过去这么些年并没有什么变化；删除了第一版中的第九，第十二和十三章，增加了第十，第十一和十三章，分别介绍基于搜索引擎技术开发并从2002年一直运行至今的“中国Web信息博物馆”、“中国数字财富库藏”及开放域问答系统。同时，较大幅度修订了第一版中的部分小节内容。总的来看，第二版中约45%的内容是新的，且总篇幅比第一版增加约30%。
鉴于我们在第一版中的一个特色——详细介绍了一个小型搜索引擎(TSE)并提供源代码，引起了许多读者的兴趣，纷纷和来邮件咨询，在此高兴地告诉读者：北京大学网络实验室将开放天网搜索系统的所有源代码。用该源代码构建的系统能搜集和处理上亿量级的网页，其体现的技术与本书中的几章内容相对应。
还有两个原因促使我们完成第二版的修订。一是2011年我们与百度合作承担一个国家项目“基于框计算的新一代搜索引擎与浏览器”，尽管规定的任务中没有要求，但我们认为能有这么一本书在项目完成之际面世，也是一件令人高兴的事情。二是2003年我们发起了“全国搜索引擎与网上信息挖掘学术研讨会”，首届在北京大学举办后，每年在全国各地由不同的高校轮流举办，很多人在会议组织工作中付出了巨大努力，他们是华南理工大学的董守斌、清华大学的李星、山东大学的马军、海南大学的雷景生、江西师范大学的王明文、大连理工大学的林鸿飞、西华大学的杜亚军，河北大学的袁方。今年已是第十届了，又回到北京大学来举办，本书的出版既是对本届会议的一个献礼，也是对过去10年来曾经为“全国搜索引擎与网上信息挖掘学术研讨会”做过贡献的所有朋友，以及参加会议的所有人员的感谢。
搜索引擎原理技术与系统截图
华夏英才基金学术文库
搜 索 引 擎
— 原理、技术与系统
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
第四章 对搜集信息的预处理................................................................................... 55
第一节 信息预处理的系统结构.................................................................................. 55
第二节 索引网页库...................................................................................................... 56
第三节 中文自动分词.................................................................................................. 58
第四节 分析网页和建立倒排文件.............................................................................. 64
第五节 本章小结.......................................................................................................... 66
第五章 信息查询服务............................................................................................... 67
第一节 查询服务的系统结构...................................................................................... 67
第二节 检索的定义...................................................................................................... 68
第三节 查询服务的实现.............................................................................................. 69
一、 结果集合的形成.............................................................................................. 69
二、 查询结果显示................................................................................................. 70
第四节 本章小结.......................................................................................................... 72
中篇 对质量和性能的追求..................................................................................... 73
第六章 可扩展搜集子系统....................................................................................... 75
第一节 天网系统概述和集中式搜集系统结构........................................................... 75
一、 天网系统结构................................................................................................. 75
二、 集中式搜集系统.............................................................................................. 76
第二节 利用并行处理技术高效搜集网页的一种方案............................................... 82
一、 节点间URL的划分策略.................................................................................. 83
二、 关于性能的讨论.............................................................................................. 86
三、 性能测试和评价.............................................................................................. 88
四、 系统的动态可配置性设计.............................................................................. 91
第三节 本章小结.......................................................................................................... 93
第七章 网页净化与消重........................................................................................... 95
第一节 网页净化与元数据提取.................................................................................. 95
一、 引言................................................................................................................. 95
二、 DocView模型.................................................................................................. 98
三、 网页的表示..................................................................................................... 99
四、 提取DocView模型要素的方法..................................................................... 103
五、 模型应用及实验研究.................................................................................... 108
第二节 网页消重算法................................................................................................ 112
一、 消重算法....................................................................................................... 112
iv
二、 算法评测....................................................................................................... 115
第八章 高性能检索子系统..................................................................................... 120
第一节 检索系统基本技术........................................................................................ 121
一、 系统设计与结构............................................................................................ 121
二、 索引创建....................................................................................................... 124
三、 检索过程....................................................................................................... 126
第二节 倒排文件性能模型........................................................................................ 127
一、 引言............................................................................................................... 128
二、 倒排文件的概念............................................................................................ 129
三、 倒排文件的一种性能模型............................................................................ 131
四、 结合计算机性能指标的考虑........................................................................ 136
第三节 混合索引技术................................................................................................ 138
一、 引言............................................................................................................... 138
二、 混合索引原理............................................................................................... 139
三、 混合索引实现............................................................................................... 141
第四节 倒排文件缓存机制........................................................................................ 144
一、 引言............................................................................................................... 144
二、 倒排文件缓存............................................................................................... 145
三、 负载特性....................................................................................................... 147
四、 缓存策略的选择............................................................................................ 149
第五节 本章小结........................................................................................................ 149
第九章 用户行为的特征及缓存的应用................................................................. 151
第一节 用户查询与点击日志.................................................................................... 152
第二节 用户行为特征的统计分析............................................................................ 154
一、 用户查询词的分布情况................................................................................ 154
二、 雷同查询词的衰减统计................................................................................ 155
三、 相邻N项查询词的偏差分析......................................................................... 156
四、 用户在输出结果中的翻页情况统计............................................................ 158
五、 用户点击URL的分布情况............................................................................ 159
六、 考虑与不考虑查询项时点击URL分布的对比分析.................................... 160
七、 查询过程的自相似性.................................................................................... 161
第三节 查询缓存的使用............................................................................................ 164
一、 基于用户行为的启示.................................................................................... 164
二、 缓存替换策略研究........................................................................................ 165
v
第四节 用户行为与WEB信息的分布特征................................................................. 167
一、 基本术语....................................................................................................... 167
二、 海量Web信息的特征分析............................................................................. 168
第十章 相关排序与系统质量评估......................................................................... 173
第一节 传统IR的相关排序技术................................................................................ 173
第二节 链接分析与相关排序.................................................................................... 176
一、 链接分析....................................................................................................... 176
二、 Web查询模式下的新信息............................................................................ 178
第三节 相关排序的一种实现方案............................................................................ 182
一、 形成网页中词项的基本权重........................................................................ 183
二、 利用链接的结构............................................................................................ 185
三、 收集用户反馈信息........................................................................................ 187
四、 计算最终的权重............................................................................................ 189
第四节 搜索引擎系统质量评估................................................................................ 191
一、 引言............................................................................................................... 191
二、 查询类别分析与查询集的构建.................................................................... 192
三、 评估实验的建立与分析................................................................................ 193
下篇 面向主题和个性化的WEB信息服务.......................................................... 196
第十一章 中文网页自动分类技术......................................................................... 197
第一节 引言................................................................................................................ 197
第二节 文档自动分类算法的类型............................................................................ 197
第三节 实现中文网页自动分类的一般过程............................................................. 199
第四节 影响分类器性能的关键因素分析................................................................. 201
一、 实验设置....................................................................................................... 201
二、 训练样本....................................................................................................... 202
三、 特征选取....................................................................................................... 207
四、 分类算法....................................................................................................... 210
五、 截尾算法....................................................................................................... 216
六、 一个中文网页分类器的设计方案................................................................ 218
第五节 天网目录导航服务........................................................................................ 219
一、 问题的提出................................................................................................... 219
二、 天网目录导航服务的体系结构.................................................................... 220
三、 天网目录的运行实例.................................................................................... 221
第六节 本章小结........................................................................................................ 221
vi
第十二章 搜索引擎个性化查询服务..................................................................... 223
第一节 基于WEB挖掘的个性化技术......................................................................... 223
一、 Web挖掘技术................................................................................................ 224
二、 典型个性化Web服务系统的比较................................................................. 225
三、 基于Web挖掘的个性化技术的发展............................................................. 226
第二节 天网知名度系统............................................................................................ 227
一、 系统结构....................................................................................................... 227
二、 网页与命名实体的相关度评价.................................................................... 231
第十三章 面向主题的信息搜集与应用................................................................. 235
第一节 主题信息的搜集............................................................................................ 235
一、 主题信息分布的局部性................................................................................ 235
二、 一种主题信息搜集系统................................................................................ 236
第二节 主题信息的一种搜集与处理模型及其应用................................................. 238
一、 模型设计....................................................................................................... 238
二、 应用实验：以“十六大”为主题................................................................ 242
三、 总结与讨论................................................................................................... 244
参考文献................................................................................................................... 245
附录. 术语................................................................................................................ 256
后记........................................................................................................................... 264
vii
图 示
图1-1 2003年8月20日在天网上检索“伊拉克战争”的结果................3
图1-2 2003年8月20日在搜狐上检索“伊拉克战争”的结果................5
图2-1 搜索引擎示意图................................................................................17
图2-2 搜索引擎三段式工作流程................................................................18
图2-3 搜索引擎的体系结构........................................................................26
图3-1 TSE搜索引擎界面..............................................................................31
图3-2 TSE查询结果页面..............................................................................32
图3-3 TSE网页快照页面..............................................................................32
图3-4 TSE系统结构.....................................................................................33
图3-5 Web信息的搜集.................................................................................34
图3-6 Sockets和端口....................................................................................39
图3-7 通过Socket建立连接.........................................................................40
图3-8 Web象个海洋.....................................................................................51
图4-1 网页预处理系统结构........................................................................55
图4-2 原始网页库中的记录格式................................................................56
图4-3 索引网页库算法................................................................................57
图4-4 正向减字最大匹配算法流程............................................................61
图4-5 切词算法流程....................................................................................62
图4-6分析网页与建立倒排文件流程.........................................................64
图4-7 过滤网页中非正文信息算法............................................................64
图4-8 正向索引表记录格式........................................................................65
图4-9 由正向索引建立反向索引................................................................65
图5-1 信息查询的系统结构........................................................................67
图5-2 基本检索算法....................................................................................69
图5-3 动态摘要算法....................................................................................71
图5-4 用户查询日志的记录格式................................................................71
图6-1 天网系统概貌....................................................................................76
图6-2 搜集系统的主控结构........................................................................78
图6-3 协调进程工作算法............................................................................85
图6-4 分布式Web搜集系统结构.................................................................86
图6-5 负载方差...........................................................................................89
图6-6 n个节点并行搜集系统及集中式系统性能随时间的变化...............90
图6-7 分布式系统效率................................................................................91
viii
图6-8 URL两阶段映射.................................................................................92
图7-1 用DocView模型提取的网页要素.....................................................99
图7-2 净化后的网页....................................................................................99
图7-3 HTML Tree 结构.............................................................................101
图7-4 内容块权值传递过程......................................................................102
图7-5 有主题网页DocView模型生成过程...............................................105
图7-6 计算网页特征项权值的算法..........................................................105
图7-7 正文段落识别过程..........................................................................106
图7-8 基于anchor text的超链选取算法....................................................107
图7-9 网页净化前后分类效果对比..........................................................109
图7-10 查全率随选取关键词个数的变化................................................ 117
图8-1 检索系统集成框架结构..................................................................122
图8-2 天网WWW检索分布式系统构架...................................................123
图8-3 倒排文件结构示意图......................................................................130
图8-4 英语单词和汉语字符的ITF分布....................................................136
图8-5 扩展词典树结构示例......................................................................143
图8-6 扩展词典匹配查找算法..................................................................144
图8-7 搜索引擎检索系统缓存结构..........................................................145
图8-8 文档数据访问对象大小分布..........................................................148
图8-9 IO与PAGE序列序号-频度分布......................................................148
图8-10 IO与PAGE序列时间间隔分布.....................................................149
图8-11 IO和PAGE序列中唯一模式串......................................................149
图9-1 查询词的分布情况..........................................................................154
图9-2 查询词分布函数及其拟合函数......................................................155
图9-3 雷同查询词的衰减..........................................................................156
图9-4 相邻1000项查询词的频率的差的平方和....................................157
图9-5用户翻页情况统计...........................................................................158
图9-6 用户点击URL的分布情况..............................................................159
图9-7 考虑查询项与否的URL分布情况..................................................160
图9-8 相邻500项中不同查询项的分布..................................................162
图9-9 相邻1000项中不同查询项的分布................................................162
图9-10 相邻2000项中不同查询项的分布..............................................163
图9-11 查询项分布的自相似性特征........................................................163
图9-12 FIFO、LRU和带衰减的LFU的缓存命中率比较.........................166
图9-13 3种替换策略的局部比较..............................................................166
图9-14 网页的被访问次数........................................................................169
ix
图9-15 用户点击url对应网页的入度.......................................................170
图9-16 用户点击url对应网页的镜像度...................................................170
图9-17 用户点击url对应网页的目录深度...............................................171
图9-18 站内网页的树状结构....................................................................171
图10-1 Inktomi提供的几种搜索引擎技术的比较....................................179
图10-2 词典在系统中的地位....................................................................180
图10-3 新词学习.......................................................................................181
图10-4 网页的互联结构示意....................................................................185
图11-1 自动文档分类算法的分类............................................................199
图11-2 中文网页自动分类的一般过程....................................................200
图11-3 中文网页分类器的工作原理图....................................................200
图11-4 WebSmart —一个网页实例集搜集和整理工具...........................204
图11-5 一种中文网页的分类体系............................................................205
图11-6 Macro-F1值随样本数的变化..........................................................206
图11-7 Micro-F1值随样本数的变化..........................................................206
图11-8 CHI、IG、DF、MI的比较(Macro-F1).....................................209
图11-9 CHI、IG、DF、MI的比较(Micro-F1).....................................210
图11-10 kNN与NB分类结果的比较..........................................................213
图11-11 k的取值对分类器质量的影响(Marco-F1)..............................214
图11-12 k的取值对分类器质量的影响(Micro-F1)...............................214
图11-13 兰式距离法与欧式距离法对12个不同类别的分类情况........215
图11-14 基于层次模型的kNN与基本kNN的比较...................................216
图11-15 RCut和SCut截尾算法的比较.......................................................218
图11-16 天网目录的体系结构..................................................................220
图11-17 天网目录导航服务......................................................................221
图12-1 Web个性化的实质.........................................................................224
图12-2 Web挖掘的分类.............................................................................224
图12-3 网页与实体相关度的建立............................................................228
图12-4 个性化知名度示意图....................................................................228
图12-5 “天网知名度”系统结构............................................................230
图13-1 页面对的平均相关性....................................................................236
图13-2 Foused Crawler的系统结构...........................................................237
图13-3 用于表达网上主题新闻强度指标的立方体................................240
图13-4 十六大网页数量在10月22至11月24期间的变化情况........244
x
表 格
表4-1 网页索引文件.......................................................................................................58
表4-2 URL索引文件........................................................................................................58
表6-1 Soif数据描述..........................................................................................................78
表6-2 Soif具体语法..........................................................................................................80
表6-3 参照序列，假设节点数为2...............................................................................89
表7-1 类别编号对照表.................................................................................................110
表7-2 消重实验结果.....................................................................................................111
表7-3 当N=10、δ =0.01时5种算法的查全率和准确率.....................................116
表7-4 考察δ 的取值对算法3和4的影响..............................................................117
表7-5 分段签名算法的时间复杂度及性能..............................................................118
表7-6 基于关键词的各算法的时间复杂度及性能 (N=10, δ =0.01)..................118
表8-1 英汉词频统计排序对照................................................................................... 134
表8-2 一些典型磁盘的性能数据............................................................................... 136
表8-3 数据集基本统计信息....................................................................................... 146
表9-1 用户在前5页的翻页情况统计...................................................................... 158
表9-2 调整后的LFU与LRU命中率的比较.............................................................. 166
表9-3 各网页参数的分布............................................................................................ 169
表10-1新词学习对检索准确率的影响..................................................................... 182
表10-2 影响权值的HTML标签................................................................................. 184
表10-3 补偿因子定义表.............................................................................................. 188
表10-4 用户查询信息类别.......................................................................................... 193
表11-1 样本集中类别及实例数量的分布情况表................................................... 203
表11-2 kNN和NB算法的分类质量和分类效率比较.............................................. 213
表11-3 欧式距离与兰式距离的比较........................................................................ 215
表11-4 基于层次模型的kNN与基本kNN的比较................................................... 216
表11-5 RCut和SCut截尾算法的比较......................................................................... 217
表11-6 一个分类器的设计方案................................................................................. 218
表12-1 典型Web个性化系统的比较......................................................................... 225
表12-2 天网知名度系统与其他检索系统的横向比较结果................................. 232
表12-3 天网知名度系统的纵向比较结果................................................................ 234
xi第一章 引论
第一章 引论
信息的生产、传播、搜集与查询是人类最基本的活动之一。考虑以文字为载
体的信息，传统上有图书馆、相应的编目体系和专业人员帮助我们很快找到所需
的信息，其粒度通常是“书”或者“文章”。随着计算机与信息技术的发展，有了
信息检索(Information Retrieval，IR)学科领域，有了关于图书或者文献的全文
检索系统，使我们能很方便地在“关键词”的粒度上得到相关的信息。
我们注意到，上述全文检索系统一般工作在一个规模相对有限、内容相对稳
定的馆藏(collection)上，被检索的对象通常是经过认真筛选和预先处理的(例
如人工提取出了“作者” ， “标题”等元数据，形成了很好的“摘要”等) ，并且系
统需要同时响应的查询数量通常都不会太大(例如每秒钟10个左右) 。
1994年左右，万维网(World Wide Web，简记为WWW或Web)出现。它
的开放性(openness)和其上信息广泛的可访问性(accessibility)极大地鼓励了
人们创作的积极性。作为一个信息源， Web和上述全文检索系统的工作对象相比，具有许多不同的特征，它们给信息检索领域带来了新的发展机遇和技术挑战。
规模大。在短短的10年左右时间，人类至少生产了40亿网页[Google,2004]，而人类有文字上万年以来产生了大约1亿本书；中国网上到2004年初大致有了约
3 亿网页[天网,2004]，而中华民族有史以来出版的书籍大约不过 275 万种。尽管
书籍的容量和质量是一般网页不可比的，但在对应的时间背景上考察其文字的总
体数量，我们不能不为人类在Web上创造文字的激情惊叹!
内容不稳定。除了不断有新的网页出现外，旧的网页会因为各种原因被删除
(有研究指出50%网页的平均生命周期大约为50天[Cho and Garcia-Molina,2000,Cho,2002])；
从原则上讲，读者数和作者数在同一个量级，形式和内容的随意性很强，权
威性相对也不高，也不太可能进行人工筛选和预处理。
与生俱来的数字化、网络化。传统载体上的信息，人们目前正忙于将它们数
字化、上网(花费极高)，而网络信息天生如此。这个特性是一把双刃剑：一方面
便于我们搜集和处理，另一方面也会使我们感到太多，蜂拥而至，鱼目混珠。
而作为要在Web上提供服务的信息查询系统，如搜索引擎和数字图书馆，通
常要具备同时对付大量访问的能力(例如每秒钟1000个查询)，而且响应时间还
要足够的快(例如1秒钟) 。
本书旨在介绍构建这类搜索引擎的有关技术。传统的 IR 是其基础，同时也
充分讨论了由上述Web信息的特征所带来的新问题及其解决方案。
· 1 ?第一章 引论
第一节 搜索引擎的概念
如上所述，本书的主要内容是介绍搜索引擎的工作原理和实现技术。搜索引
擎，在本书指的是一种在 Web 上应用的软件系统，它以一定的策略在 Web 上搜
集和发现信息，在对信息进行处理和组织后，为用户提供Web信息查询服务。从
使用者的角度看，这种软件系统提供一个网页界面，让他通过浏览器提交一个词
语或者短语，然后很快返回一个可能和用户输入内容相关的信息列表(常常会是
很长一个列表，例如包含1万个条目)。这个列表中的每一条目代表一篇网页，至
少有3个元素：
标题：以某种方式得到的网页内容的标题。最简单的方式就是从网页的<TITLE>标签中提取的内容。(尽管在一些情况下并不真正反映网页的<br/><br/>
内容)。本书第七章会介绍其他形成“标题”的方法。<br/><br/>
URL：该网页对应的“访问地址”。有经验的 Web 用户常常可以通过这个元<br/><br/>
素对网页内容的权威性进行判断，例如 http:www.people.com 上面的内容通常就<br/><br/>
比 http:notresponsible.net(某个假想的个人网站)上的要更权威些(不排除后者<br/><br/>
上的内容更有趣些) 。<br/><br/>
摘要：以某种方式得到的网页内容的摘要。最简单的一种方式就是将网页内<br/><br/>
容的头若干字节(例如512)截取下来作为摘要。本书第七章会介绍形成“摘要”<br/><br/>
的其他方法。<br/><br/>
通过浏览这些元素，用户对相应的网页是否真正包含他所需的信息进行判<br/><br/>
断。比较肯定的话则可以点击上述URL，从而得到该网页的全文。图1-1是2003<br/><br/>
年 8 月 20 日在天网搜索引擎(http:e.pku.edu.cn)上的一个例子，用户提交了查<br/><br/>
询词“伊拉克战争”，系统返回一个相关信息列表。列表的每一条目所含内容比上<br/><br/>
述要丰富些，但核心还是那三个元素。如果用户主要是想从军事角度关心伊拉克<br/><br/>
战争，第一条目可能就是很好的选择，不仅摘要看起来军事味道要浓一些，而且<br/><br/>
从URL(http:mil.eastday.com)上能看到提供信息的大概是一个专门的军事题材<br/><br/>
网站。如果用户主要是想关心伊拉克战争对全球经济的影响，则后面的条目可能<br/><br/>
会更相关些。<br/><br/>
这个例子提示了我们一个重要的情况，即搜索引擎提供信息查询服务的时<br/><br/>
候，它面对的只是查询词。而有不同背景的人可能提交相同的查询词，关心的是<br/><br/>
和这个查询词相关的不同方面的信息，但搜索引擎通常是不知道用户背景的，因<br/><br/>
此搜索引擎既要争取不漏掉任何相关的信息，还要争取将那些“最可能被关心”<br/><br/>
的信息排在列表的前面。这也就是对搜索引擎的根本要求。除此以外，考虑到搜<br/><br/>
索引擎的应用环境是Web，因此对大量并发用户查询的响应性能也是一个不能忽<br/><br/>
· 2 ?第一章 引论<br/><br/>
略的方面。<br/><br/>
作为对搜索引擎工作原理的基本了解，这里有两个问题需要首先澄清。 第一，当用户提交查询的时候，搜索引擎并不是即刻在Web上“搜索”一通，发现那些<br/><br/>
相关的网页，形成列表呈现给用户；而是事先已“搜集”了一批网页，以某种方<br/><br/>
式存放在系统中，此时的搜索只是在系统内部进行而已。第二，当用户感到返回<br/><br/>
图1-1 2003年8月20日在天网上检索“伊拉克战争”的结果<br/><br/>
结果列表中的某一项很可能是他需要的，从而点击URL，获得网页全文的时候，他此时访问的则是网页的原始出处。于是，从理论上讲搜索引擎并不保证用户在<br/><br/>
返回结果列表上看到的标题和摘要内容与他点击 URL 所看到的内容一致(上面<br/><br/>
那个“伊拉克战争”的例子就是如此! ) ，甚至不保证那个网页还存在。这也是搜<br/><br/>
索引擎和传统信息检索系统的一个重要区别。这种区别源于前述Web信息的基本<br/><br/>
特征。为了弥补这个差别，现代搜索引擎都保存网页搜集过程中得到的网页全文，并在返回结果列表中提供“网页快照”或“历史网页”链接，保证让用户能看到<br/><br/>
和摘要信息一致的内容。<br/><br/>
第二节 搜索引擎的发展历史<br/><br/>
早在 Web 出现之前，互联网上就已经存在许多旨在让人们共享的信息资源<br/><br/>
· 3 ?第一章 引论<br/><br/>
了。那些资源当时主要存在于各种允许匿名访问的 FTP 站点(anonymous ftp)，内容以学术技术报告、研究性软件居多，它们以计算机文件的形式存在，文字材<br/><br/>
料的编码通常是PostScript或者纯文本(那时还没有HTML)。<br/><br/>
为了便于人们在分散的FTP资源中找到所需的东西， 1990年加拿大麦吉尔大<br/><br/>
学(University of McGill)计算机学院的师生开发了一个软件，Archie。它通过定<br/><br/>
期搜集并分析FTP系统中存在的文件名信息，提供查找分布在各个FTP主机中文<br/><br/>
件的服务。Archie 能在只知道文件名的前提下，为用户找到这个文件所在的 FTP<br/><br/>
服务器的地址。Archie 实际上是一个大型的数据库，再加上与这个大型数据库相<br/><br/>
关联的一套检索方法。该数据库中包括大量可通过FTP下载的文件资源的有关信<br/><br/>
息，包括这些资源的文件名、文件长度、存放该文件的计算机名及目录名等。尽<br/><br/>
管所提供服务的信息资源对象(非HTML文件)和本书所讨论搜索引擎的信息资<br/><br/>
源对象(HTML网页)不一样，但基本工作方式是相同的(自动搜集分布在广域<br/><br/>
网上的信息，建立索引，提供检索服务) ，因此人们公认 Archie 为现代搜索引擎<br/><br/>
的鼻祖。<br/><br/>
值得一提的是，即使是在 10 多年后的今天，以 FTP 文件为对象的信息检索<br/><br/>
服务技术依然在发展，尤其是在用户使用界面上充分采用了Web风格。北大天网<br/><br/>
文件检索系统就是一个例子(见http:bingle.pku.edu.cn) 。不过鉴于本书写作定位<br/><br/>
的关系，后面将主要讨论网页搜索引擎的相关问题。<br/><br/>
以 Web 网页为对象的搜索引擎和以 FTP 文件为对象的检索系统一个基本的<br/><br/>
不同点在于搜集信息的过程。前者是利用 HTML 文档之间的链接关系，在 Web<br/><br/>
上一个网页、一个网页的“爬取”(crawl)，将那些网页“抓”(fetch)到本地后<br/><br/>
进行分析；后者则是根据已有的关于FTP站点地址的知识(例如得到了一个站点<br/><br/>
地址列表)，对那些站点进行访问，获得其文件目录信息，并不真正将那些文件下<br/><br/>
载到系统上来。因此，如何在 Web 上“爬取”，就是搜索引擎要解决的一个基本<br/><br/>
问题。在这方面，1993年Matthew Gray开发了World Wide Web Wanderer，它是<br/><br/>
世界上第一个利用HTML网页之间的链接关系来监测Web发展规模的“机器人”<br/><br/>
(robot)程序。刚开始时它只用来统计互联网上的服务器数量，后来则发展为能<br/><br/>
够通过它检索网站域名。鉴于其在Web上沿超链“爬行”的工作方式，这种程序<br/><br/>
有时也称为“蜘蛛” (spider) 。因此，在文献中crawler, spider, robot一般都指的是<br/><br/>
相同的事物，即在Web上依照网页之间的超链关系一个个抓取网页的程序，通常<br/><br/>
也称为“搜集”。在搜索引擎系统中，也称为网页搜集子系统。<br/><br/>
现代搜索引擎的思路源于Wanderer， 不少人在Matthew Grey工作的基础上对<br/><br/>
它的蜘蛛程序做了改进。1994年7月，Michael Mauldin将John Leavitt的蜘蛛程<br/><br/>
序接入到其索引程序中，创建了大家现在熟知的 Lycos，成为第一个现代意义的<br/><br/>
搜索引擎。在那之后，随着Web上信息的爆炸性增长，搜索引擎的应用价值也越<br/><br/>
来越高，不断有更新、更强的搜索引擎系统推出(下一节会有介绍)。这其中，特<br/><br/>
· 4 ?第一章 引论<br/><br/>
别引人注目的是Google(http:www.google.com) ，虽然是个姗姗来迟者(1998年<br/><br/>
才推出)，但由于其采用了独特的PageRank技术，使它很快后来居上，成为当前<br/><br/>
全球最受欢迎的搜索引擎(作者 2003 年初访问印度，就听到总统阿卜杜勒·卡<br/><br/>
拉姆讲他经常用Google在网上查找信息! )。<br/><br/>
图1-2 2003年8月20日在搜狐上检索“伊拉克战争”的结果<br/><br/>
在中国，据我们所知，对搜索引擎的研究起源于“中国教育科研网” (CERNET)<br/><br/>
一期工程中的子项目，北京大学计算机系的项目组在陈葆珏教授的主持下于1997<br/><br/>
年 10 月在 CERNET 上推出了天网搜索 1.0 版本。该系统在这几年里不断发展，目前已成为中国最大的公益性搜索引擎(http:e.pku.edu.cn) 。在这之后，几位在<br/><br/>
美国留学的华人学者回国创业，成立了百度公司，于2000年推出了“百度”商业<br/><br/>
搜索引擎(http:www.baidu.com) ，并一直处于国内搜索引擎的领先地位。我们看<br/><br/>
到慧聪公司也在中国推出了一个大规模搜索引擎(http:www.zhongsou.com) ，用<br/><br/>
起来感觉也不错，但往后发展如何，还有待时间的考验。<br/><br/>
当我们谈及搜索引擎的时候，不应该忽略另外一个几乎是同期发展出来的事<br/><br/>
物：基于目录的信息服务网站。1994 年 4 月，斯坦福(Stanford)大学的两名博<br/><br/>
士生，David Filo和杨致远(Gerry Yang)共同创办了Yahoo!门户网站，并成功地<br/><br/>
使网络信息搜索的概念深入人心。1996 年中国出现了类似的网站，“搜狐” ，? 5 ?第一章 引论<br/><br/>
(http:www.sohu.com) 。在许多场合，也称Yahoo!之类的门户网站提供的信息查<br/><br/>
找功能为搜索引擎。但从技术上讲，这样的门户中提供的搜索服务和前述搜索引<br/><br/>
擎是很不同的。这样的门户依赖的是人工整理的网站分类目录，一方面，用户可<br/><br/>
以直接沿着目录导航，定位到他所关心的信息；另一方面，用户也可以提交查询<br/><br/>
词，让系统将他直接引导到和该查询词最匹配的网站。图 1-2 就是我们在搜狐上<br/><br/>
查询“伊拉克战争”的结果。和图 1-1 相比，不难看到其风格是很不相同的。在<br/><br/>
需要区别的场合，我们可以分别称“自动搜索引擎” 和 “目录搜索引擎” ， 或者 “网<br/><br/>
页搜索引擎”和“网站搜索引擎”。一般来讲，前者的信息搜索会更全面些，后者<br/><br/>
则会准确些。在没有特殊说明的情况下，本书中所讨论的 “搜索引擎”不包括Yahoo!<br/><br/>
和搜狐这样的搜索方式。<br/><br/>
随着网上信息越来越多，单纯靠人工整理网站目录取得较高精度查询结果的<br/><br/>
优势逐渐退化——对海量的信息进行高质量的人工分类已经不太现实。目前有两<br/><br/>
个发展方向。一是利用文本自动分类技术，在搜索引擎上提供对每篇网页的自动<br/><br/>
分类，这方面最先看到的例子是Google的“网页分类”选项，但它分类的对象只<br/><br/>
是英文网页。在中文方面，文本自动分类的研究工作有很多，但我们知道的第一<br/><br/>
个在网上提供较大规模网页自动分类服务的是北大网络实验室冯是聪和龚笔宏等<br/><br/>
人的工作[冯是聪,2003]，他们于 2002 年 10 月在天网搜索上挂接了一个 300 万网<br/><br/>
页的分类目录。另一个发展方向是将自动网页爬取和一定的人工分类目录相结合，希望形成一个既有高信息覆盖率，也有高查询准确性的服务。<br/><br/>
互联网上信息量在不断增加，信息的种类也在不断增加。例如除了我们前面<br/><br/>
提到的网页和文件，还有新闻组，论坛，专业数据库等。同时上网的人数也在不<br/><br/>
断增加，网民的成分也在发生变化。一个搜索引擎要覆盖所有的网上信息查找需<br/><br/>
求已出现困难，因此各种主题搜索引擎，个性化搜索引擎，问答式搜索引擎等纷<br/><br/>
纷兴起。这些搜索引擎虽然还没有实现如通用搜索引擎那样的大规模应用，但随<br/><br/>
着互联网的发展，我们相信它们的生命力会越来越旺盛。另外，即使通用搜索引<br/><br/>
擎的运行现在也开始出现分工协作，有了专业的搜索引擎技术和搜索数据库服务<br/><br/>
提供商。例如美国的Inktomi，它本身并不是直接面向用户的搜索引擎，但向包括<br/><br/>
Overture(原GoTo)、LookSmart、MSN、HotBot等在内的其他搜索引擎提供全文<br/><br/>
网页搜集服务。从这个意义上说，它是搜索引擎数据的来源。<br/><br/>
搜索引擎出现虽然只有10年左右的历史， 但在Web上已经有了确定不移的地<br/><br/>
位。据CNNIC统计，它已经成为继电子邮件之后的第二大Web应用。虽然它的基<br/><br/>
本工作原理已经相当稳定，但在其质量、性能和服务方式等方面的提高空间依然<br/><br/>
很大，研究成果层出不穷，是每年WWW学术年会1<br/><br/>
的重要论题之一。<br/><br/>
1<br/><br/>
International WWW Conference Committee, 网址 http:www.iw3c2.org.<br/><br/>
· 6 ?第一章 引论<br/><br/>
第三节 一些著名的搜索引擎<br/><br/>
为了让感兴趣的读者有目的的试一试，我们整理了一些当前主流的搜索引<br/><br/>
擎，包括网址，首页面图片及其介绍。在这些搜索引擎中，排在最前面的几个搜<br/><br/>
索引擎提供多语言的支持，可以满足不同母语读者的需求。<br/><br/>
主流搜索引擎的选定参考了[Sullivan,2004]，主流搜索引擎是指非常有名，或<br/><br/>
者被广泛使用的搜索引擎。为使读者有感性认识特别加入了每个网站的相关页面。<br/><br/>
Google, http:www.google.com<br/><br/>
四次荣获Searchenginewatch[Searchenginewatch,2004]读者选举出的“最杰出搜<br/><br/>
索引擎”称号的Google作为在网络上搜索页面的首选是无愧于这个称号的。它基<br/><br/>
于搜集器2<br/><br/>
的服务既保证了能够覆盖广泛的网页，同时在查询效果上也表现得极其<br/><br/>
优秀。<br/><br/>
为了方便的检索到所需网页，Google提供几种可供选择的方法。利用Google<br/><br/>
首页搜索框上面的标签，可以容易的检索网络上的网页，图像，网上论坛，新闻<br/><br/>
和Open Directory提供的经过人工整理后的网页目录。<br/><br/>
Google还因为提供许多其它特性而闻名，例如网页快照，保证您在存有网页<br/><br/>
的服务器暂时出现故障时仍可浏览该网页的内容，或者可以浏览到不是最新版的<br/><br/>
该网页的内容；拼写检查，如果您查询词包含错误的拼写，它会提示正确的查询<br/><br/>
2<br/><br/>
自动搜索引擎的搜集子系统<br/><br/>
· 7 ?第一章 引论<br/><br/>
词；股票行情查询；街区地图查询等特殊功能。更多的特性可以查看Google的帮<br/><br/>
助大全。此外，Google 工具条因为提供了方便存取 Google 和它的特性而为其赢<br/><br/>
得了一定的声誉。<br/><br/>
Google除了提供无需付费的排序结果，还有自己的竞价排名程序。与其他提<br/><br/>
供此项服务的公司一样，依据点击才有花费，竞价排名程序在Google的返回结果<br/><br/>
中放置广告。Google还提供自己的无需付费的排序结果给其它一些搜索引擎。<br/><br/>
Google最初起源于斯坦福大学的BackRub项目，当时是由学生Larry Page和<br/><br/>
Sergey Brin 主要负责。到了 1998年，BackRub更名为 Google，并且走出校园成<br/><br/>
为一个公司。<br/><br/>
AllTheWeb, http:www.alltheweb.com<br/><br/>
作为一个优秀的基于搜集器的搜索引擎，AllTheWeb 提供广泛的网络覆盖与<br/><br/>
显著的相关性。除了提供网页查询，AllTheWeb 还提供新闻，图像，视频和音频<br/><br/>
的检索。 AllTheWeb于1999年5月推出，先是由FAST运作； 2003年4月Overture<br/><br/>
收购了AllTheWeb；后来Yahoo!买下了Overture，现在的AllTheWeb由Yahoo!运<br/><br/>
作。<br/><br/>
Ask Jeeves, http:www.askjeeves.com<br/><br/>
Ask Jeeves最初获得名声是在1998和1999年。作为自然语言搜索引擎，能<br/><br/>
够让用户通过输入问题来得到查询结果，并且所得到的结果看起来好像是对的。<br/><br/>
· 8 ?第一章 引论<br/><br/>
事实上，技术并不是Ask Jeeves运行很好的原因。在幕后，公司曾经指定100<br/><br/>
个编辑人员监视查询日志。然后这100个人上网查找与最常用查询词最相关的网<br/><br/>
页链接。目前，Ask Jeeves 仍然在使用人来参与结果的查找，但是现在编辑只有<br/><br/>
10个人左右。尽管如此，通过人的参与提供答案仍然是一个卖点，尤其对于那些<br/><br/>
新接触网络的人，他们会想使用 Ask Jeeves。对于通常的查询，人工选择的匹配<br/><br/>
结果让人感觉非常的相关。如果显示出来，这些结果出现在查询结果页面的最上<br/><br/>
端。除了人工参与外，Ask Jeeves还利用基于搜集器的技术提供查询结果给用户。<br/><br/>
这些结果来自它所拥有的Teoma搜索引擎。<br/><br/>
HotBot, http:www.hotbot.com<br/><br/>
HotBot提供便于访问三个搜索引擎(HotBot, Google, Ask Jeeves)的入口，但<br/><br/>
是不同于元搜索引擎3<br/><br/>
，它不能将各搜索引擎的返回结果综合显示。<br/><br/>
HotBot在1996年初次登场， 因为其庞大的由Inktomi提供的基于搜集器的检<br/><br/>
索页面和质量，而成为搜索者喜欢的引擎。特别是它的不同寻常的颜色和接口，还为它赢得了有经验的网民的注意。<br/><br/>
3<br/><br/>
元搜索引擎又称集合型搜索引擎，是将多个独立的搜索引擎集合在一起形成的检索工具，即<br/><br/>
搜索引擎之搜索引擎。<br/><br/>
· 9 ?第一章 引论<br/><br/>
1999 年，HotBot 因为采用 Direct Hit 的 clickthrough 结果作为排序列表获得<br/><br/>
了恶名。Direct Hit当年出现时是一个很热的搜索引擎。不幸的是，Direct Hit的<br/><br/>
结果与同期登场的Google不能相比。HotBot的声望开始下降。<br/><br/>
Teoma, http:www.teoma.com<br/><br/>
Teoma是基于搜集器的搜索引擎，2001年9月被Ask Jeeves收购。它索引的<br/><br/>
网页比同样基于搜集器的竞争对手Google的少。然而对于通常的查询检索，索引<br/><br/>
网页多少并不会产生很大的分别，自从 2000 年 Teoma 出现，就因为它很好的网<br/><br/>
页相关性赢得了称赞。一些人喜欢Teoma的“相关检索”特性，您先输入一个简<br/><br/>
单词语搜索，然后， Teoma会为您提供其它相关搜索词作为参考。“专家推荐资源”<br/><br/>
部分也是Teoma的一个特色，指导用户去访问不同主题的链接。<br/><br/>
· 10 ?第一章 引论<br/><br/>
Lycos, http:www.lycos.com<br/><br/>
Lycos是一个资格最老的搜索引擎，1994年开始提供服务。在1999年4月它<br/><br/>
停止了自己基于搜集器的结果，取而代之的是利用LookSmart人工整理的常用查<br/><br/>
询分类结果和其它基于搜集器的搜索引擎，如：Yahoo!，Inktomi等搜集器提供的<br/><br/>
结果。那么用户为什么不直接使用其他的搜索引擎而还要使用 Lycos 呢？你也许<br/><br/>
是喜欢Lycos提供的一些特性。<br/><br/>
在搜索框的下方 Lycos 会建议其他的与用户检索主题相关的查询词，也许正<br/><br/>
是用户想看和感觉更确切的查询词。在这之下，就是 Lycos 提供的与其他搜索引<br/><br/>
擎一样的既相关又广泛覆盖的结果。<br/><br/>
Lycos属于Terra Lycos公司， 它是在2000年10月由Lycos合并了Terra网络<br/><br/>
公司后形成的公司。Terra Lycos公司还有HotBot搜索引擎。<br/><br/>
· 11 ?第一章 引论<br/><br/>
WiseNut, http:www.wisenut.com<br/><br/>
与Teoma类似，WiseNut是基于搜集器的搜索引擎，在2001年出现的时候吸<br/><br/>
引了大家的注意力。WiseNut 的结果也有很好的相关性，并且有很大的数据库，几乎像 Google、AllTheWeb 和 Inktomi 一样大。然而，WiseNut 的数据库更新很<br/><br/>
慢，查询结果经常是几个月前的内容。 LookSmart在2002年4月并购了WiseNut。<br/><br/>
Overture, http:www.overture.com<br/><br/>
· 12 ?第一章 引论<br/><br/>
最初叫GoTo，2001年更名为Overture。Overture是一个非常流行的竞价排名<br/><br/>
搜索引擎，它提供广告给许多搜索引擎排在检索结果的上方。Overture在2003年<br/><br/>
3 月购买了 AllTheWeb，2003 年 4 月又收购了 AltaVista。Yahoo 在 2003 年 10 月<br/><br/>
购买了Overture。<br/><br/>
Vivisimo, http:www.vivisimo.com<br/><br/>
Vivisimo 于2000年6月由卡耐基-梅隆大学(CMU)推出，作为不同于基于<br/><br/>
搜集器的元搜索引擎，有自己的独到之处。它把其他搜索引擎的返回结果利用自<br/><br/>
动聚类的办法来满足不同类型客户的需要。在搜索引擎上，任何人搜索同一个词<br/><br/>
的结果都是一样。这样明显不能满足访问者。科学家搜索“星球” ，可能是希望了<br/><br/>
解星球的知识，但普通人可能是想找“星球大战”电影，但搜索引擎所给的都是<br/><br/>
一样的结果。如何满足这些不同类型的访问者，需要对搜索结果进行个性化处理。<br/><br/>
搜索结果排序从单一化到个性化，Vivisimo已经迈出了一步。<br/><br/>
Baidu(百度), http:www.baidu.com<br/><br/>
百度于 2000 年推出，是目前在中国最成功的一个商业搜索引擎，主要提供<br/><br/>
中文信息检索，并且为门户站点提供搜索结果服务。搜索范围涵盖了中国内地、香港、台湾、澳门、新加坡等华语地区以及北美、欧洲的部分站点。拥有的中文<br/><br/>
信息总量达到1亿2千万网页以上，并且还在以每天几十万页的速度快速增长。<br/><br/>
· 13 ?第一章 引论<br/><br/>
Tianwang(天网), http:e.pku.edu.cn<br/><br/>
于1997年10月开始提供服务，是中国最早的搜索引擎。它由北京大学网络<br/><br/>
与分布式系统实验室开发并维护运行，搜集了中国范围内大量的网络信息资源，尤其较全面地覆盖了中国教育科研网(CERNET)内的资源。天网目前索引的信<br/><br/>
· 14 ?第一章 引论<br/><br/>
息资源除已经超过3亿的网页外， 还包括2000多万各种非网页类型的文件，是目<br/><br/>
前世界上最大的中文搜索引擎之一。在系统功能上，天网除提供通常的关键词和<br/><br/>
短语检索外，还有自动网页分类目录。本书所介绍的技术内容主要就是以天网为<br/><br/>
背景展开的。<br/><br/>
· 15 ?<br/><br/>
上篇 Web搜索引擎基本原理和技术<br/><br/>
上篇的主要目的是向读者介绍典型Web搜索引擎的基本工作原理，并通过一<br/><br/>
个实例具体展示该工作原理中各个环节的一种实现方法，以期使读者很快从技术<br/><br/>
上对搜索引擎系统的全貌有一个透彻的了解。<br/><br/>
我们首先指出，所谓“搜索引擎”，说到底是一个计算机应用软件系统，或<br/><br/>
者说是一个网络应用软件系统。从网络用户的角度看，它根据用户提交的类自然<br/><br/>
语言查询词或者短语，返回一系列很可能与该查询相关的网页信息，供用户进一<br/><br/>
步判断和选取。为了有效地做到这一点，它大致上被分成三个功能模块，或者三<br/><br/>
个子系统；即网页搜集，预处理和查询服务。第二章详细分析了这三个部分的主<br/><br/>
要功能和其中需要关注的种种问题。应该指出，在实践中这三个部分是相对独立<br/><br/>
的，它们的工作形成了搜索引擎工作的三个阶段，通常分别由人工启动。同时我<br/><br/>
们注意到，在早期的搜索引擎中，系统处理的网页数量少，预处理部分的工作比<br/><br/>
较简单，只是涉及到汉语的分词(英文还没有这个问题)和建索引，因此也有将<br/><br/>
分词合并到网页搜集过程中，将建索引归到查询服务子系统中，从而整个系统看<br/><br/>
起来只有两个模块的安排1。<br/><br/>
在介绍了基本原理后，第三、四、五章分别就上述三个阶段中的技术要求给<br/><br/>
出了一种实现方案。为了便于读者对搜索引擎技术在短时间内有一个全面实在的<br/><br/>
掌握，这三章的基本写作风格是提出问题，给出解决思路，然后是对应程序实现<br/><br/>
要点的注释和讲解。如果要掌握每一个细节(例如需要开发一个搜索引擎) ，要求<br/><br/>
读者对C++程序设计语言比较熟悉。然而，从了解现代搜索引擎技术原理的需求<br/><br/>
来看，中篇和下篇并不很依赖这三章的内容，因此对C++程序设计语言不熟的读<br/><br/>
者可以跳过这三章，直接阅读中篇和下篇，或者不一定要一句句探究那些程序段<br/><br/>
落的逻辑。程序代码可以在[TSE,2004]下载。<br/><br/>
对于希望动手构建搜索引擎的读者来说，掌握了这一篇的内容，直接用我们<br/><br/>
提供的实例代码，应该能够很快(例如一周)构建出一个可用的小型通用搜索引<br/><br/>
擎。同时我们指出，一个实用的大规模搜索引擎还有许多其它重要问题要解决，集中在效率和质量两个方面，我们安排在中篇讨论。<br/><br/>
1<br/><br/>
1997年10月我们在CERNET上发布的天网1.0版本就是这种结构，每抓来一个网页就立即在<br/><br/>
内存分词，然后将得到的结果存入数据库中，供建索引程序直接使用。<br/><br/>
· 16 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
第二章 Web搜索引擎工作原理和体系结构<br/><br/>
本章介绍搜索引擎的基本工作原理和它作为一种网络应用软件的体系结构。<br/><br/>
在后面的三章中，我们将以一个实际的例子，具体展开在这些原理基础上实现的<br/><br/>
一种方案。通过这几章学习，读者将得到一个可实际运行搜索引擎的实现细节。<br/><br/>
第一节 基本要求<br/><br/>
如在第一章第二节所述，搜索引擎是一个网络应用软件系统，如图2-1所示，对它有如下基本要求。<br/><br/>
能够接受用户通过浏览器提交的查询词或者短语，记作q，例如“非典” ， “伊<br/><br/>
拉克战争” ， “床前明月光”等等。<br/><br/>
在一个可以接受的时间内返回一个和该用户查询匹配的网页信息列表，记作<br/><br/>
L。上一章讲过，这个列表的每一条目至少包含三个元素(标题，网址链接，摘<br/><br/>
要) 。<br/><br/>
搜索引擎<br/><br/>
q1,q2,… L1,L2,…<br/><br/>
网页数据库<br/><br/>
图2-1 搜索引擎示意图<br/><br/>
这里有几个问题需要注意，它们对应上面黑体的文字：<br/><br/>
向广大用户提供服<br/><br/>
务的<br/><br/>
的内容，其中最简单、最常见<br/><br/>
“可以接受的时间”，也就是响应时间。对于在 Web 上面<br/><br/>
软件来说，这个时间不能太长，通常也就在“秒”这个量级。这是衡量搜索<br/><br/>
引擎可用性的一个基本指标，也是和传统信息检索系统的一个差别。更进一步的，这样的响应时间要求不仅要能满足单个用户查询，而且要能在系统设计负载的情<br/><br/>
况下满足所有的用户。也就是说，系统应该在额定吞吐率的情况下保证秒级响应<br/><br/>
时间。这其中详细的分析将在中篇第八章展开。<br/><br/>
“匹配”，指的是网页中以某种形式包含有 q<br/><br/>
· 17 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
的形<br/><br/>
列表”，这蕴含着一种“序” (rank) 。在绝大多数情况下，L是相当长的，例如<br/><br/>
引擎一般采用如图 2-2 所示的称之为三段式的工作流<br/><br/>
程，<br/><br/>
第二节 网页搜集<br/><br/>
搜索引擎这样一个软件系统应该是何种工作方式？如果说软件系统是工作<br/><br/>
在某<br/><br/>
还是即时。我们都有经验，在网络比较畅<br/><br/>
通的<br/><br/>
引擎服务的基础应该是一批预先搜集好的网页<br/><br/>
式就是q在其中直接出现。不过后面我们会看到，如果一个搜索引擎就是以<br/><br/>
百分之百满足这种简单的包含关系为目标，即使实现了也并不就达到了最好的效<br/><br/>
果。<br/><br/>
“<br/><br/>
超过1万个条目(这是和图书馆全文检索系统的又一个不同，那里返回的列<br/><br/>
表通常较短，例如几十个条目)。这不仅是由于 Web 上的信息量大，也由于搜索<br/><br/>
引擎的查询方式简单。简单，意味着抽象；抽象，意味着有更多的具体事物可能<br/><br/>
是它的体现。对于一个长长的列表，很少有用户有耐心都审视一遍(不仅是因为<br/><br/>
长，还因为大多数使用搜索引擎的用户通常都是“找到为止” ，而不是“不全部找<br/><br/>
到不罢休”，加上这个列表中和一个用户关心的其实只占很少的比例)。有分析统<br/><br/>
计表明，用户平均察看返回结果不超过 2 页[Baldi, et al.,2003],[Wang, et<br/><br/>
al.,2001],[单松巍,2003]。<br/><br/>
现代大规模高质量搜索<br/><br/>
即：网页搜集、预处理和查询服务。<br/><br/>
搜集 预处理 服务<br/><br/>
图2-2 搜索引擎三段式工作流程<br/><br/>
个数据集合上的程序的话，这个软件系统操作的数据不仅包括内容不可预测<br/><br/>
的用户查询，还要包括在数量上动态变化的海量网页，并且这些网页不会主动送<br/><br/>
到系统来，而是需要由系统去抓取。<br/><br/>
首先，我们考虑抓取的时机：事先<br/><br/>
情况下，从网上下载一篇网页大约需要1秒钟左右，因此如果在用户查询的<br/><br/>
时候即时去网上抓来成千上万的网页，一个个分析处理，和用户的查询匹配，不<br/><br/>
可能满足搜索引擎的响应时间要求。不仅如此，这样做的系统效益也不高(会重<br/><br/>
复抓取太多的网页)；面对大量的用户查询，不可能想象每来一个查询，系统就到<br/><br/>
网上“搜索”一次。<br/><br/>
因此我们看到，大规模搜索<br/><br/>
· 18 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
(直接或者间接1) 。这一批网页如何维护？可以有两种基本的考虑。<br/><br/>
定期搜集，每次搜集替换上一次的内容，我们称之为“批量搜集”。由于每<br/><br/>
次都是重新来一次，对于大规模搜索引擎来说，每次搜集的时间通常会花几周。<br/><br/>
而由于这样做开销较大，通常两次搜集的间隔时间也不会很短(例如早期天网的<br/><br/>
版本大约每3个月来一次，Google在一段时间曾是每隔28天来一次)。这样做的<br/><br/>
好处是系统实现比较简单，主要缺点是“时新性” (freshness)不高，还有重复搜<br/><br/>
集所带来的额外带宽的消耗。<br/><br/>
增量搜集，开始时搜集一批，往后只是(1)搜集新出现的网页， (2)搜集<br/><br/>
那些在上次搜集后有过改变的网页， (3)发现自从上次搜集后已经不再存在了的<br/><br/>
网页，并从库中删除。由于除新闻网站外，许多网页的内容变化并不是很经常的<br/><br/>
(有研究指出 50% 网页的平均生命周期大约为 50 天 [Cho and<br/><br/>
Garcia-Molina,2000]，[Cho,2002]) ，这样做每次搜集的网页量不会很大(例如我<br/><br/>
们在 2003 年初估计中国每天有 30-50 万变化了的网页)，于是可以经常启动搜集<br/><br/>
过程(例如每天) 。30万网页，一台PC机，在一般的网络条件下，半天也就搜集<br/><br/>
完了。这样的系统表现出来的信息时新性就会比较高，主要缺点是系统实现比较<br/><br/>
复杂；这种复杂还不仅在于搜集过程，而是还在于下面要谈到的建索引的过程。<br/><br/>
上面讲的是系统网页数据库维护的基本策略。在这两种极端的情况之间也可<br/><br/>
能有一些折中的方案，J. Cho 博士在这方面做过深入的研究[Cho and<br/><br/>
Garcia-Molina,2000]，[Cho,2002]，根据一种网页变化模型和系统所含内容时新性<br/><br/>
的定义，提出了相应优化的网页搜集策略。其中一个有趣的结论是：在系统搜集<br/><br/>
能力一定的情况下，若有两类网页(例如“商业”和“教育” ) ，它们的更新周期<br/><br/>
差别很大(例如“商业”类网页平均更新周期是“天”，而“教育”类网页平均更<br/><br/>
新周期是“月” ) ，则系统应该将注意力放在更新慢的网页上[Cho and<br/><br/>
Garcia-Molina,2000]，以使系统整体的时新性达到比较高的取值。<br/><br/>
在具体搜集过程中，如何抓取一篇篇的网页，也可以有不同的考虑。最常见<br/><br/>
的一种是所谓“爬取” ：将 Web 上的网页集合看成是一个有向图，搜集过程从给<br/><br/>
定起始 URL 集合 S(或者说“种子”)开始，沿着网页中的链接，按照先深、先<br/><br/>
宽、或者某种别的策略遍历，不停的从S中移除URL，下载相应的网页，解析出<br/><br/>
网页中的超链接 URL，看是否已经被访问过，将未访问过的那些 URL 加入集合<br/><br/>
S。 整个过程可以形象地想象为一个蜘蛛 (spider) 在蜘蛛网 (Web) 上爬行 (crawl)。<br/><br/>
后面我们会看到，真正的系统其实是多个“蜘蛛”同时在爬。<br/><br/>
这种方式的好处除了概念很漂亮，一般实现起来也不困难外，还有很重要的<br/><br/>
一条是容易通过一定的策略，使搜集到的网页相对比较“重要”。前面提过，任何<br/><br/>
1<br/><br/>
所谓“间接”，指的是提供搜索服务的系统可能利用别人已经事先抓好的数据，元搜索引擎就<br/><br/>
是如此。<br/><br/>
· 19 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
搜索引擎是不可能将Web上的网页搜集完全的，通常都是在其他条件的限制下决<br/><br/>
定搜集过程的结束(例如磁盘满，或者搜集时间已经太长了)。因此就有一个尽量<br/><br/>
使搜到的网页比较重要的问题，这对于那些并不追求很大的数量覆盖率的搜索引<br/><br/>
擎特别重要。研究表明[Najork and Wiener,2001]，按照先宽搜索方式得到的网页集<br/><br/>
合要比先深搜索得到的集合重要(这里当然有一个重要性的指标问题) 。 这种方式<br/><br/>
的一个困难是要从每一篇网页中提取出所含的URL。由于HTML的灵活性，其中<br/><br/>
出现URL的方式各种各样，将这个环节做得彻底不容易(例如我们现在还没有很<br/><br/>
好的简单办法从JavaScript脚本中提取URL) 。同时，由于Web的“蝴蝶结”形状<br/><br/>
[Broder, et al.,2000]， 这种方式搜集到的网页不大会超过所有目标网页数量2<br/><br/>
的23。<br/><br/>
另外一种可能的方式是在第一次全面网页搜集后，系统维护相应的 URL 集<br/><br/>
合 S，往后的搜集直接基于这个集合。每搜到一个网页，如果它发生变化并含有<br/><br/>
新的 URL，则将它们对应的网页也抓回来，并将这些新 URL 也放到集合 S 中；<br/><br/>
如果 S 中某个 url 对应的网页不存在了，则将它从 S 中删除。这种方式也可以看<br/><br/>
成是一种极端的先宽搜索，即第一层是一个很大的集合，往下最多只延伸一层。<br/><br/>
还有一种方法是让网站拥有者主动向搜索引擎提交它们的网址(为了宣传自<br/><br/>
己，通常会有这种积极性)，系统在一定时间内(2天到数月不等)定向向那些网<br/><br/>
站派出“蜘蛛”程序，扫描该网站的所有网页并将有关信息存入数据库中。大型<br/><br/>
商业搜索引擎一般都提供这种功能。<br/><br/>
第三节 预处理<br/><br/>
得到海量的原始网页集合，距离面向网络用户的检索服务之间还有相当的距<br/><br/>
离。宏观地看，服务子系统是一个程序。采用 Wirth 关于“程序 = 算法+数据结<br/><br/>
构”的观点来考察这个程序，一个合适的数据结构是查询子系统工作的核心和关<br/><br/>
键。这里只是指出：现行最有效的数据结构是“倒排文件” (inverted file) ；倒排<br/><br/>
文件是用文档中所含关键词作为索引，文档作为索引目标的一种结构(类似于普<br/><br/>
通书籍中，索引是关键词，书的页面是索引目标) 。 我们在第八章中有进一步分析。<br/><br/>
下面讨论从网页集合形成这样的倒排文件过程中的几个主要问题，即我们所说的<br/><br/>
“预处理”。主要包括四个方面，关键词的提取，“镜像网页”(网页的内容完全相<br/><br/>
同，未加任何修改)或“转载网页” (near-replicas，主题内容基本相同但可能有<br/><br/>
一些额外的编辑信息等，转载网页也称为“近似镜像网页” )的消除，链接分析和<br/><br/>
网页重要程度的计算。<br/><br/>
1. 关键词的提取<br/><br/>
2<br/><br/>
所谓“目标网页”指的是搜索引擎设计覆盖的网页范围。例如Google是全球，天网是全中国。<br/><br/>
· 20 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
随便取一篇网页的源文件(例如通过浏览器的“查看源文件”功能)，我们<br/><br/>
可以看到其中的情况纷乱繁杂。除了我们从浏览器中能够正常看到的文字内容外，还有大量的HTML标记。根据天网统计，网页文档源文件的大小(字节量)通常<br/><br/>
大约是其中内容大小的 4 倍(例如http:net.pku.edu.cn就是如此!)。另外，由于<br/><br/>
HTML文档产生来源的多样性，许多网页在内容上比较随意，不仅文字不讲究规<br/><br/>
范、完整，而且还可能包含许多和主要内容无关的信息(例如广告，导航条，版<br/><br/>
权说明等)。这些情况既给有效的信息查询带来了挑战，也带来了一些新的机遇，在后面的章节将会有进一步的论述。这里我们只是指出，为了支持后面的查询服<br/><br/>
务，需要从网页源文件中提取出能够代表它的内容的一些特征。从人们现在的认<br/><br/>
识和实践来看，所含的关键词即为这种特征最好的代表。于是，作为预处理阶段<br/><br/>
的一个基本任务，就是要提取出网页源文件的内容部分所含的关键词。对于中文<br/><br/>
来说，就是要根据一个词典Σ，用一个所谓“切词软件”，从网页文字中切出Σ所<br/><br/>
含的词语来。在那之后，一篇网页主要就由一组词来近似代表了， p = {t1, t2, …, tn}。<br/><br/>
一般来讲，我们可能得到很多词，同一个词可能在一篇网页中多次出现。从效果<br/><br/>
(effectiveness)和效率(efficiency)考虑，不应该让所有的词都出现在网页的表示<br/><br/>
中，要去掉诸如“的” ， “在”等没有内容指示意义的词，称为“停用词” (stop word)。<br/><br/>
这样，对一篇网页来说，有效的词语数量大约在200个左右。<br/><br/>
2. 重复或转载网页的消除<br/><br/>
与生俱来的数字化和网络化给网页的复制以及转载和修改再发表带来了便<br/><br/>
利，因此我们看到 Web 上的信息存在大量的重复现象。天网在 2003 年的一次大<br/><br/>
规模统计分析表明，网页的重复率平均大约为4。也就是说，当你通过一个URL<br/><br/>
在网上看到一篇网页的时候，平均还有另外 3 个不同的 URL 也给出相同或者基<br/><br/>
本相似的内容。这种现象对于广大的网民来说是有正面意义的，因为有了更多的<br/><br/>
信息访问机会。但对于搜索引擎来说，则主要是负面的；它不仅在搜集网页时要<br/><br/>
消耗机器时间和网络带宽资源，而且如果在查询结果中出现，无意义地消耗了计<br/><br/>
算机显示屏资源，也会引来用户的抱怨，“这么多重复的，给我一个就够了” 。因<br/><br/>
此，消除内容重复或主题内容重复的网页是预处理阶段的一个重要任务。第七章<br/><br/>
对此有详细的分析论述。<br/><br/>
3. 链接分析<br/><br/>
前面提到，大量的HTML标记既给网页的预处理造成了一些麻烦，也带来了<br/><br/>
一些新的机遇。从信息检索的角度讲，如果系统面对的仅仅是内容的文字，我们<br/><br/>
能依据的就是“共有词汇假设”(shared bag of words) ，即内容所包含的关键词集<br/><br/>
合，最多加上词频(term frequency 或 tf、TF)和词在文档集合中出现的文档频<br/><br/>
率(document frequency 或df、DF)之类的统计量。而TF和DF这样的频率信<br/><br/>
· 21 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
息能在一定程度上指示词语在一篇文档中的相对重要性或者和某些内容的相关<br/><br/>
性，这是有意义的。有了HTML标记后，情况还可能进一步改善，例如在同一篇<br/><br/>
文档中， <H1>和<H1>之间的信息很可能就比在<H4>和<H4>之间的信息更重要。<br/><br/>
特别地，HTML文档中所含的指向其他文档的链接信息是人们近几年来特别关注<br/><br/>
的对象，认为它们不仅给出了网页之间的关系，而且还对判断网页的内容有很重<br/><br/>
要的作用。例如“北大学报”这几个字在北京大学学报社会科学版的主页上是没<br/><br/>
有的，因此一个仅靠内容文字分析的搜索引擎就不可能返回该主页作为结果。但<br/><br/>
是北京大学主页上是用“北大学报(社)”作为链接信息指向了北京大学学报社会<br/><br/>
科学版的主页。因此在很好利用链接信息的搜索引擎中应该能返回北京大学学报<br/><br/>
社会科学版的主页。<br/><br/>
4. 网页重要程度的计算<br/><br/>
搜索引擎返回给用户的，是一个和用户查询相关的结果列表。列表中条目的<br/><br/>
顺序是很重要的一个问题。由于面对各种各样的用户，加之查询的自然语言风格，对同样的q0返回相同的列表肯定是不能使所有提交q0的用户都满意的(或者都达<br/><br/>
到最高的满意度) 。 因此搜索引擎实际上追求的是一种统计意义上的满意。人们认<br/><br/>
为Google目前比天网好，是因为在多数情况下前者返回的内容要更符合用户的需<br/><br/>
要，而不是所有情况下都如此。如何对查询结果进行排序有很多因素需要考虑，后面将有深入的讨论。这里只是概要解释在预处理阶段可能形成的所谓“重要性”<br/><br/>
因素。顾名思义，既然是在预处理阶段形成的，就是和用户查询无关的。如何讲<br/><br/>
一篇网页比另外一篇网页重要？人们参照科技文献重要性的评估方式，核心想法<br/><br/>
就是“被引用多的就是重要的” 。 “引用”这个概念恰好可以通过HTML超链在网<br/><br/>
页之间体现得非常好，作为Google创立核心技术的PageRank就是这种思路的成功<br/><br/>
体现[Page, et al.,1998]。除此以外，人们还注意到网页和文献的不同特点，即一些<br/><br/>
网页主要是大量对外的链接，其本身基本没有一个明确的主题内容，而另外有些<br/><br/>
网页则被大量的其他网页链接。从某种意义上讲，这形成了一种对偶的关系，这<br/><br/>
种关系使得人们可以在网页上建立另外一种重要性指标[Kleinberg,1998]。这些指<br/><br/>
标有的可以在预处理阶段计算，有的则要在查询阶段计算，但都是作为在查询服<br/><br/>
务阶段最终形成结果排序的部分参数。<br/><br/>
第四节 查询服务<br/><br/>
如上述，从一个原始网页集合S开始，预处理过程得到的是对S的一个子集<br/><br/>
的元素的某种内部表示，这种表示构成了查询服务的直接基础。对每个元素来说，这种表示至少包含如下几个方面：<br/><br/>
· 22 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
z 原始网页文档<br/><br/>
z URL和标题<br/><br/>
z 编号<br/><br/>
z 所含的重要关键词的集合(以及它们在文档中出现的位置信息)<br/><br/>
z 其他一些指标(例如重要程度，分类代码等)<br/><br/>
而系统关键词总体的集合和文档的编号一起构成了一个倒排文件结构，使得<br/><br/>
一旦得到一个关键词输入，系统能迅速给出相关文档编号的集合输出。<br/><br/>
然而，如同我们在第一章提到的，用户通过搜索引擎看到的不是一个 “集合” ，而是一个“列表”。如何从集合生成一个列表，是服务子系统的主要工作。从搜索<br/><br/>
引擎系统功能划分的角度，有时候将倒排文件的生成也作为服务子系统的一部分<br/><br/>
功能，但我们这里将它划分到预处理阶段中觉得更方便些。换句话讲，服务子系<br/><br/>
统是在服务进行的过程中涉及的相关软件程序，而为这些软件程序事先准备数据<br/><br/>
的程序都算在预处理子系统中。下面来看对服务子系统的要求和其工作原理，主<br/><br/>
要有三个方面。<br/><br/>
1. 查询方式和匹配<br/><br/>
查询方式指的是系统允许用户提交查询的形式。考虑到各种用户的不同背景<br/><br/>
和不同的信息需求，不可能有一种普适的方式。一般认为，对于普通网络用户来<br/><br/>
说，最自然的方式就是“要什么就输入什么”。但这是一种相当模糊的说法。例如<br/><br/>
用户输入“北京大学”，可能是他想了解北京大学目前有些什么信息向外发布，想<br/><br/>
看看今年的招生政策(于是希望看的是北大网站上的内容) ， 也可能是他想了解外<br/><br/>
界目前对北京大学有些什么评价(于是希望看到的是其他权威网站上关于北大的<br/><br/>
消息)。这是两种相当不同的需求。在其他一些情况下，用户可能关心的是间接信<br/><br/>
息，例如“喜马拉雅山的高度” ，8848 米应该是他需要的，但不可能包含在这短<br/><br/>
语中。而用户输入“惊起一滩鸥鹭”则很可能是想知道该词的作者是谁，或者希<br/><br/>
望能提醒前面几句是什么。尽管如此，用一个词或者短语来直接表达信息需求，希望网页中含有该词或者该短语中的词，依然是主流的搜索引擎查询模式。这不<br/><br/>
仅是因为它的确代表了大多数的情况，还因为它比较容易实现。这样，一般来讲，系统面对的是查询短语。就英文来说，它是一个词的序列；就中文来说，它是包<br/><br/>
含若干个词的一段文字。一般地，我们用q0表示用户提交的原始查询，例如，q0 =<br/><br/>
“网络与分布式系统实验室”。它首先需要被“切词”(segment)或称“分词”，即把它分成一个词的序列。如上例，则为“网络 与 分布式 系统 实验室”<br/><br/>
(注意，不同的分词软件可能得出不同的结果，这里用的是北大计算语言所的在<br/><br/>
线分词软件) 。 然后需要删除那些没有查询意义或者几乎在每篇文档中都会出现的<br/><br/>
词(例如“的” ) ，在本例中即为“与”。最后形成一个用于参加匹配的查询词表，q = {t1, t2, …, tm}，在本例中就是q = {网络，分布式，系统，实验室}。前面讲过，? 23 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
倒排文件就是用词来作为索引的一个数据结构，显然，q中的词必须是包含在倒排<br/><br/>
文件词表中才有意义。有了这样的q， 它的每一个元素都对应倒排文件中的一个倒<br/><br/>
排表(文档编号的集合)，记作L(ti)，它们的交集即为对应查询的结果文档集合，从而实现了查询和文档的匹配。上述过程的基本假设是：用户是希望网页包含所<br/><br/>
输入查询文字的。<br/><br/>
2. 结果排序<br/><br/>
上面，我们了解了得到和用户查询相关的文档集合的过程。这个集合的元素<br/><br/>
需要以一定的形式通过计算机显示屏呈现给用户。就目前的技术情况看，列表是<br/><br/>
最常见的形式(但人们也在探求新的形式，如Vivisimo 引擎将结果页面以类别的<br/><br/>
形式呈现)。给定一个查询结果集合，R={r1, r2, …, rn}，所谓列表，就是按照某种<br/><br/>
评价方式，确定出R中元素的一个顺序，让这些元素以这种顺序呈现出来。笼统<br/><br/>
地讲，ri和q的相关性(relevance)是形成这种顺序的基本因素。但是，有效地定<br/><br/>
义相关性本身是很困难的，从原理上讲它不仅和查询词有关，而且还和用户的背<br/><br/>
景，以及用户的查询历史有关。不同需求的用户可能输入同一个查询，同一个用<br/><br/>
户在不同的时间输入的相同的查询可能是针对不同的信息需求。为了形成一个合<br/><br/>
适的顺序，在搜索引擎出现的早期人们采用了传统信息检索领域很成熟的基于词<br/><br/>
汇出现频度的方法。大致上讲就是一篇文档中包含的查询(q)中的那些词越多，则该文档就应该排在越前面；再精细一些的考虑则是若一个词在越多的文档中有<br/><br/>
出现，则该词用于区分文档相关性的作用就越小。这样一种思路不仅有一定直觉<br/><br/>
上的道理，而且在倒排文件数据结构上很容易实现。因为，当我们通过前述关键<br/><br/>
词的提取过程，形成一篇文档的关键词集合，p = {t1, t2, …, tn}的时候，很容易同<br/><br/>
时得到每一个ti在该文档中出现的次数，即词频，而倒排文件中每个倒排表的长度<br/><br/>
则对应着一个词所涉及的文档的篇数，即文档频率。然而，由于网页编写的自发<br/><br/>
性、随意性较强，仅仅针对词的出现来决定文档的顺序，在Web上做信息检索表<br/><br/>
现出明显的缺点，需要有其他技术的补充。这方面最重要的成果就是前面提到过<br/><br/>
的PageRank。通过在预处理阶段为每篇网页形成一个独立于查询词(也就和网页<br/><br/>
内容无关)的重要性指标，将它和查询过程中形成的相关性指标结合形成一个最<br/><br/>
终的排序，是目前搜索引擎给出查询结果排序的主要方法。<br/><br/>
3. 文档摘要<br/><br/>
搜索引擎给出的结果是一个有序的条目列表，每一个条目有三个基本的元<br/><br/>
素：标题，网址和摘要。其中的摘要需要从网页正文中生成。一般来讲，从一篇<br/><br/>
文字中生成一个恰当的摘要是自然语言理解领域的一个重要课题，人们已经做了<br/><br/>
多年的工作并取得了一些成果。但相关的技术用到网络搜索引擎来有两个基本困<br/><br/>
难。一是网页的写作通常不规范，文字比较随意，因此从语言理解的角度难以做<br/><br/>
· 24 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
好；二是复杂的语言理解算法耗时太多，不适应搜索引擎要高效处理海量网页信<br/><br/>
息的需求。我们做过统计，即使是分词这一项工作(文本理解的基础) ，在高档微<br/><br/>
机上每秒钟也只能完成10篇左右网页的处理。因此搜索引擎在生成摘要时要简便<br/><br/>
许多，基本上可以归纳为两种方式，一是静态方式，即独立于查询，按照某种规<br/><br/>
则，事先在预处理阶段从网页内容提取出一些文字，例如截取网页正文的开头512<br/><br/>
个字节(对应256个汉字)，或者将每一个段落的第一个句子拼起来，等等。这样<br/><br/>
形成的摘要存放在查询子系统中，一旦相关文档被选中与查询项匹配，就读出返<br/><br/>
回给用户。显然，这种方式对查询子系统来说是最轻松的，不需要做另外的处理<br/><br/>
工作。但这种方式的一个最大的缺点是摘要和查询无关。一篇网页有可能是多个<br/><br/>
不同查询的结果，例如当用户分别查询“北大计算机网络”和 “北大分布式系统” ，我们实验室的主页 http:net.pku.edu.cn 在两种情况下应该都作为结果返回。当用<br/><br/>
户输入某个查询，他一般是希望摘要中能够突出显示和查询直接对应的文字，希<br/><br/>
望摘要中出现和他关心的文字相关的句子。因此，我们有了“动态摘要”方式，即在响应查询的时候，根据查询词在文档中的位置，提取出周围的文字来，在显<br/><br/>
示时将查询词标亮。这是目前大多数搜索引擎采用的方式。为了保证查询的效率，需要在预处理阶段分词的时候记住每个关键词在文档中出现的位置。<br/><br/>
除上述外，查询服务返回的内容还有一些细节的支持。例如，对应一个查询<br/><br/>
往往会有成千上万的结果，返回给用户的内容通常都是按页组织的，一般每页显<br/><br/>
示10个结果。统计表明[Wang, et al.,2001]， 网络用户一般没有耐心一页页看下去，平均翻页数小于 2。这告诉我们将第一页的内容组织好非常重要。如果希望用户<br/><br/>
多用搜索引擎，就要让第一页的内容尽量有吸引力。<br/><br/>
第五节 体系结构<br/><br/>
在上述工作原理的基础上，作为一个网络应用软件，我们可以勾画出搜索引<br/><br/>
擎的体系结构，如图 2-3 所示，其中的大部分模块和前面的原理描述有直接的对<br/><br/>
应。这里需要特别讨论的是还没有专门提及的“控制器”模块。<br/><br/>
网页的搜集，如果只是为了做些简单的实验，不过上万篇网页的话，许多矛<br/><br/>
盾都不会出现，可以用最简单的工具(例如wget<br/><br/>
3)完成。但如果是为了向大规模<br/><br/>
搜索引擎稳定地提供网页数据，通常需要每天搜集上百万网页，而且是持续进行，情况则要复杂许多，核心是要综合解决效率、质量和“礼貌”的问题。这就是“控<br/><br/>
制器”的作用。<br/><br/>
3<br/><br/>
http:www.gnu.orgsoftwarewgetwget.html<br/><br/>
· 25 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
图2-3 搜索引擎的体系结构<br/><br/>
所谓效率，在这里就是如何利用尽量少的资源(计算机设备、网络带宽、时<br/><br/>
间)来完成预定的网页搜集量。在批量搜集的场合，我们通常考虑半个月左右能<br/><br/>
搜集到的网页，自然是越多越好。由于网页之间存在的独立性，利用许多台计算<br/><br/>
机同时来做这项工作是一个吸引人的想法，在第六章有专门的论述。这里需要指<br/><br/>
出三点：第一，即使是用一台计算机来搜集网页，也应该注意并发性的开发和利<br/><br/>
用。由于从网上抓取一篇网页通常需要秒量级的等待网络通信时间，同时启动多<br/><br/>
个抓取进程线程，或者利用操作系统提供的异步通信机制，让多个网络通信时间<br/><br/>
重叠起来，让网络通信时间和存放网页的磁盘访问时间重叠起来是很有意义的。<br/><br/>
同时启动抓取进程的数量取决于硬件条件和搜集软件的设计，一般情况下可以上<br/><br/>
百个，做得好也可能上千个(即上千个进程也不会造成CPU成为瓶颈) 。<br/><br/>
在效率问题上应该指出的第二点是并不是设备越多越好。在用若干台计算机<br/><br/>
形成一个机群的安排下，它们共同分享出口网络带宽，随着设备量的增加，这个<br/><br/>
网络带宽(或者是周围的某个环境带宽)很快就成为瓶颈。经验表明实际上用不<br/><br/>
了超过10台计算机。人们曾经有过分布式搜集的想法，即让多台设备分布在网络<br/><br/>
上的不同位置，从而克服上述带宽瓶颈问题；理论上是对的。但对于维护千万到<br/><br/>
用户行为日志<br/><br/>
数据库<br/><br/>
控制器 搜集器<br/><br/>
原始数据库<br/><br/>
索引器<br/><br/>
索引数据库<br/><br/>
检索器<br/><br/>
用户接口<br/><br/>
WWW<br/><br/>
日志分析器<br/><br/>
用户<br/><br/>
· 26 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
亿量级的搜索引擎来说似乎还用不上，具体实现起来的麻烦会超过可能带来的好<br/><br/>
处(也许 Google 那样的针对多个国家用户的巨型搜索引擎需要用这种技术) 。影<br/><br/>
响搜集效率的第三点发生在网络的另一端，即服务器方，它可能来不及提供所需<br/><br/>
的网页。这除了有些Web服务器所处的网络条件比较差，或者有太多其他人访问<br/><br/>
外，搜索引擎太频繁对它们发出网页请求也是一个重要原因。落实到技术上，就<br/><br/>
是要有一个访问策略或者 URL 规划，不要让搜集器启动的抓取进程都集中在少<br/><br/>
数几个网站上。<br/><br/>
将搜集活动的关注过分集中在几个网站上，或者在一小段时间里从一个网站<br/><br/>
抓取太多的网页还可能引起其他的严重后果，即所谓“礼貌”问题。一般来讲，网站的管理人员都很愿意让自己的网页被搜索引擎索引，从而有可能得到更多的<br/><br/>
访问流量；但这只是问题的一方面。问题的另一方面是网站绝不希望由于搜索引<br/><br/>
擎的“密集”抓取活动阻碍了普通用户通过浏览器的访问，使那些用户得到这个<br/><br/>
网站访问起来很困难的印象，从而不再光顾。不加控制的网页抓取，给网站造成<br/><br/>
的现象有时候和制造拒绝服务(Denial of Servide, DoS)攻击的黑客造成的现象一<br/><br/>
样。因此，管理良好的网站常常会有一个监视器运行，监视是否有来源于单个IP<br/><br/>
地址的过分密集的访问。一旦出现这种情况，要么会通告该IP地址的拥有者注意<br/><br/>
行为，或者会干脆屏蔽来自它的访问，更有甚者，还可能在网上公布该IP地址作<br/><br/>
为黑名单。因此，适当地规划网页的抓取，限制单位时间内对一个网站抓取网页<br/><br/>
的数量(例如每天不超过2万个，或者至少每隔30秒才对同一个网站发出下一个<br/><br/>
网页请求，等等)，是大规模搜索引擎必须要认真对待的问题。总之，搜索引擎需<br/><br/>
要和网站“和睦相处”，它们是相互依存的。<br/><br/>
所谓质量问题，指的是在有限的时间，搜集有限的网页，希望它们尽量是比<br/><br/>
较 “重要”的网页， 或者说不要漏掉那些很重要的网页。哪些网页是比较重要的？<br/><br/>
也是仁者见仁，智者见智的，不可能有一个统一认可的标准。如果让重要性和流<br/><br/>
行度等同起来，即越多人看过的网页越重要，至少是直觉上有一定道理的。这样，我们可以考虑一个网站从主页开始向下，按照链接的深度将网页组织成一层层的，上层中的网页统计上会比下层的网页重要些。这样一种认识通过 PageRank 得到<br/><br/>
了加强，即较靠近主页的网页通常 PageRank 值较高。这样，首先得到尽量多的<br/><br/>
主页，然后从主页开始的先宽搜索就应该是一个较好的策略。闫宏飞论文[闫宏<br/><br/>
飞,2002]是支持这种观点的一个工作。<br/><br/>
网页搜集过程中还有一个基本的问题是要保证每个网页不被重复抓取。由于<br/><br/>
一篇网页可能被多篇网页链接， 在spider爬取过程中就可能多次得到该网页的url。<br/><br/>
于是如果不加检查和控制，网页就会被多次抓取。遇到循环链接的情况，还会使<br/><br/>
爬取器陷死。解决这个问题的有效方法是使用两个表，unvisited_table 和<br/><br/>
visited_table。前者包含尚未访问的 url，后者记录已访问的 url。系统首先将要搜<br/><br/>
集的种子 url 放入 unvisited_table，然后 spider 从其中获取要搜集网页的 url，搜<br/><br/>
· 27 ?第二章 Web搜索引擎工作原理和体系结构<br/><br/>
集过的网页 url 放入 visited_table 中，新解析出的并且不在 visited_table 中的 url<br/><br/>
加入unvisited_table。此方法简单明了，适合在单个节点上实现。但是当搜集子系<br/><br/>
统涉及到多个节点的时候，如何避免各个节点之间的重复工作就复杂了，还要考<br/><br/>
虑网络的通信量、负载平衡、以及单个节点性能瓶颈等问题。这些问题的细节将<br/><br/>
在第六章讨论。<br/><br/>
· 28 ?第三章 Web信息的搜集<br/><br/>
第三章 Web信息的搜集<br/><br/>
从第二章的学习中，我们知道搜索引擎一般采用三段式的工作流程，即：网<br/><br/>
页搜集，预处理和查询服务。为了便于读者对搜索引擎技术很快有一个全面实在<br/><br/>
的掌握，从本章开始的连续三章，我们讲解一个完整的搜索引擎TSE (Tiny Search<br/><br/>
Engine)的实现，编程语言采用 C++，代码可以在[TSE,2004]下载。TSE 包括三<br/><br/>
段式工作流程，分别对应本章的Web信息的搜集，第四章搜集信息的预处理和第<br/><br/>
五章的信息查询服务。<br/><br/>
作为三章内容的一个起始，在本章第一节中简单介绍了互联网上的HTTP协<br/><br/>
议和 TSE 系统框架。然后主要内容集中在 TSE 的 Web 信息搜集部分。在后续的<br/><br/>
章节叙述中，文档也是指网页，我们不加以区分。<br/><br/>
第一节 引言<br/><br/>
一、 超文本传输协议<br/><br/>
超文本传输协议(Hypertext Transfer Protocol, HTTP)1<br/><br/>
是Web的基础协议。为<br/><br/>
了本章的完整，首先对HTTP进行简要的介绍，然后重点讲解如何实现Web信息的<br/><br/>
收集。<br/><br/>
HTTP是一个简单的协议。客户进程建立一条同服务器进程的TCP连接，然<br/><br/>
后发出请求并读取服务器进程的应答。服务器进程关闭连接表示本次响应结束。<br/><br/>
服务器进程返回的内容包含两个部分，一个“应答头” (response header)， 一个“应<br/><br/>
答体” (response body) ，后者通常是一个HTML文件，我们称之为“网页” 。<br/><br/>
在 Linux(或 window)环境下，有一个简单的方法可以让我们来感受一下<br/><br/>
HTTP 协议的工作情况，即运行一个 Telnet 的客户程序与一个 HTTP 服务器程序<br/><br/>
通信。<br/><br/>
下面是获取北京大学主页的例子(注意，下面显示的从服务器得到的内容不<br/><br/>
包括上述“应答头” )。<br/><br/>
1<br/><br/>
关于HTTP协议的详细介绍可以参看RFC2068 Hypertext Transfer Protocol -- HTTP1.1<br/><br/>
[RFCs,2004]。此外，在很多书中都有专门的章节进行介绍，如： 《TCP-IP详解卷三：TCP事务<br/><br/>
协议，HTTP，NNTP和UNIX域协议》的第13章HTTP：超文本传送协议； 《UNIX技术大全—<br/><br/>
Internet卷》的第21章超文本传输协议简介。<br/><br/>
· 29 ?第三章 Web信息的搜集<br/><br/>
[webg@BigPc ] telnet www.pku.cn 80 连接到服务器的80号端口<br/><br/>
Trying 162.105.129.12... 由Telnet客户输出<br/><br/>
Connected to rock.pku.cn (162.105.129.12). 由Telnet客户输出<br/><br/>
Escape character is ‘^]’. 由Telnet客户输出<br/><br/>
GET 我们只输入了这一行<br/><br/>
<html> Web服务器输出的第一行<br/><br/>
<head><title>北京大学<title>…… 这里省略了很多行输出<body><html><br/><br/>
Connection closed by foreign host. 由Telnet客户输出<br/><br/>
我们只输入了GET ，服务器却返回了很多字节。这样，从该Web服务器的<br/><br/>
根目录下取得了它的主页。Telnet 的客户进程输出的最后一行信息表示服务器进<br/><br/>
程在输出最后一行后关闭了TCP连接。<br/><br/>
一个完整的HTML文档以<HTML>开始， 以<HTML>结束。大部分的HTML<br/><br/>
命令都像这样成对出现。HTML文档含有以<HEAD>开始、以<HEAD>结束的首<br/><br/>
部和以<BODY>开始、以<BODY>结束的主体部分。标题通常由客户程序显示在<br/><br/>
窗口的顶部。关于HTML规范的详细介绍可以参看[W3C,1999]。<br/><br/>
在接下去的几节中，将通过一个小的搜索引擎系统TSE (运行在Red Hat Linux<br/><br/>
8.0以上的系统中)[TSE,2004]的循序渐进实现，一边讲原理技术，一边讲代码，描述Web信息搜集的过程，本处的Web信息搜集主要指网页信息。<br/><br/>
网页搜集子系统，就是第一章第二节和第二章第五节中讲到的 spider，可以<br/><br/>
用CC++、Perl、Java，Python等语言来编写，可以运行在Intel, Sparc, Mac等平<br/><br/>
台上的 Unix 或 Window 系统下。网页“爬取器” (gatherer) ，指网页搜集子系统<br/><br/>
中根据URL完成一篇网页抓取的进程或者线程，通常一个spider会同时启动多个<br/><br/>
gatherer 并行工作。Spider 设计是否合理将直接影响它访问 Web 的效率，影响搜<br/><br/>
集数据的质量，另外，在设计spider时还必须考虑它对网络和被访问站点的影响，因为 spider 一般都运行在速度快、带宽高的主机上，如果它快速访问一个速度比<br/><br/>
较慢的目标站点，就有可能会导致该站点出现拥塞甚至宕机。Spider 还应遵守一<br/><br/>
些协议(例如：robot限制协议[Wong,1997]) ，尊重被访问站点管理员确定的内容<br/><br/>
保护策略。<br/><br/>
· 30 ?第三章 Web信息的搜集<br/><br/>
二、 一个小型搜索引擎系统<br/><br/>
TSE是一个适合教学用的搜索引擎，设计的目标之一是让它足够小，便于任<br/><br/>
何一个对搜索引擎感兴趣的人都可以利用自己有限的硬件资源(例如自己的台式<br/><br/>
机)搭建；让它尽量简单，让具有一般程序设计基础的爱好者可以全部理解；让<br/><br/>
它的功能相对完整，能够反映一个大规模搜索引擎的主要成分。<br/><br/>
首先从 TSE 的外部表现形式来看它所能完成的工作，然后给出 TSE 系统结<br/><br/>
构图。搜索引擎是通过浏览器界面展现给用户的，图3-1是TSE的用户界面。<br/><br/>
北大校庆<br/><br/>
搜索<br/><br/>
·2004 北大网络实验室<br/><br/>
图3-1 TSE搜索引擎界面<br/><br/>
在查询输入框输入查询短语并回车 (或者点击 “搜索”按钮) ，即可得到相<br/><br/>
关资料。查询时关键词之间不需要使用“and” ，因为TSE会在关键词之间自动添<br/><br/>
加“and”。TSE提供符合您查询条件的全部网页。<br/><br/>
例如：想查北大校庆，只需在图3-1的搜索框中输入“北大校庆”，然后回车。<br/><br/>
图 3-2 是 TSE 的查询返回结果。为方便解释起见，我们用 A，B，C 标识其中的<br/><br/>
几个部分。<br/><br/>
1) “A”表示统计栏，包括用户输入的查询词，有关查询结果和搜索时间<br/><br/>
(一般搜索响应时间不超过1秒钟)的统计数字；<br/><br/>
2) “B”表示一条查询结果， 包括该网页网址、网页摘要(在摘要信息中，您的原始查询字词，都用红色字体表示，以便阅读) 。<br/><br/>
3) “C”表示网页快照。通过链接访问网页失效时，可以访问 TSE 的缓存<br/><br/>
网页；或者网络拥塞的时候，可以通过访问缓存网页避免直接访问该网<br/><br/>
· 31 ?第三章 Web信息的搜集<br/><br/>
页。<br/><br/>
图3-2 TSE查询结果页面<br/><br/>
图3-3 TSE网页快照页面<br/><br/>
点击图 3-2 中的“网页快照”链接，得到图 3-3 所示的 TSE 网页快照页面。<br/><br/>
· 32 ?第三章 Web信息的搜集<br/><br/>
图中最上部分标明此网页来自TSE的网页快照。用户输入的查询短语如果被系统<br/><br/>
分成多个关键词，用不同颜色表示，并增加链接便于点击相应关键词直接到达正<br/><br/>
文中该关键词出现的位置。正文部分取自网页原文的缓存，其中包含用户查询关<br/><br/>
键词的文字加亮显示。<br/><br/>
图3-4 TSE系统结构<br/><br/>
图 3-1，3-2，3-3 展示了 TSE 的查询服务功能，为了完成上述功能，需要网<br/><br/>
页搜集和预处理两个部分的支持。图3-4所示为TSE系统结构，对应于搜索引擎<br/><br/>
三段式工作流程， 是图中左侧的A表示搜集部分，中间的B表示整理 (即预处理)<br/><br/>
部分和右侧的C表示服务部分。其中黄色圆柱形图表示数据产品，按照统一并且<br/><br/>
简单易懂的格式存储，除本系统使用外，可以提供给其他科研机构使用；椭圆形<br/><br/>
绿色图表示系统流程中的内部数据，由于与系统中使用的数据结构结合紧密，不<br/><br/>
适合作为数据产品提供给其他研究机构；矩形蓝色表示系统流程的程序部分(过<br/><br/>
程)，是数据产品与内部数据之间的桥梁。系统起始于 A 搜集，结束于 C 服务，整个流程可以重复进行，从而达到系统的更新。图 3-4 中的各个数据产品，内部<br/><br/>
数据和过程在后续章节相应部分细致讲解。在 TSE 中不包括 PageRank 的计算和<br/><br/>
日志挖掘，这两个过程主要是对查询结果的排序产生作用，在实际应用中的搜索<br/><br/>
引擎是必不可少的，但是对于讲解搜索引擎的工作过程不是必需的。<br/><br/>
本章后续内容讲解搜集部分 (对应图3-4的A) ； 第四章讲解预处理部分(对<br/><br/>
应图中的B) ；第五章讲解服务部分(对应图中的C)。<br/><br/>
第二节 网页搜集<br/><br/>
在 TSE 中网页搜集对应图 3-4 的左侧部分，我们将它细化为图 3-5 所示。网<br/><br/>
页搜集的过程是从URL库(初始时包含用户指定的起始种子URL集合，可以是<br/><br/>
· 33 ?第三章 Web信息的搜集<br/><br/>
1 个或多个)获得输入，解析 URL 中标明的 Web 服务器地址、建立连接、发送<br/><br/>
请求和接收数据，将获得的网页数据存储在原始网页库，并从其中提取出链接信<br/><br/>
息放入网页结构库，同时将待抓取的URL放入URL库，保证整个过程的递归进<br/><br/>
行，直到URL库为空。<br/><br/>
图3-5 Web信息的搜集<br/><br/>
搜索引擎为了提供检索服务，需要保存网页原文。网页搜集子系统不但要能<br/><br/>
够获取以.html, .htm, .txt结尾的URL对应的网页(在本章后面的小节对于搜集信<br/><br/>
息类型会有更详细的阐述)，还应该能够获取不是以.html 结尾的 URL，比<br/><br/>
如.pdf，.doc，因为.pdf，.doc等文件可以通过转换程序生成为.html或者.txt文件，同样为搜索引擎提供检索服务。作为搜索引擎的起始流程，搜集的网页要按照一<br/><br/>
定的格式存储，便于后续组织和提供服务。<br/><br/>
传统应用的实现在系统结构定下来后，重点是确定其中的数据结构。而面向<br/><br/>
对象方法具有更好的特性，我们是采用C++面向对象的方法结合源代码讲述。针<br/><br/>
对系统实现的描述，依据重要名词定义为类的原则，重点讲解URL类和Page类。<br/><br/>
本章后续部分是把 TSE 中的搜集部分分解开来讲解，包括：定义 URL 类，定义<br/><br/>
Page类，与服务器建立连接，构造请求消息体并发送给服务器，获取服务器返回<br/><br/>
的网页元信息(或者称为网页头信息)和获取网页信息(或者称为网页体信息) 。<br/><br/>
一、 定义URL类和Page类<br/><br/>
1. 定义URL类<br/><br/>
TSE程序首先必须要做的一件事情是根据一个给定的URL，组成消息体，发<br/><br/>
送给该 URL 指向的服务器。为此，定义 Url 类。关于 URL 的详细介绍可以参看<br/><br/>
· 34 ?第三章 Web信息的搜集<br/><br/>
RFC2396 Uniform Resource Identifiers (URI): Generic Syntax[RFCs,2004]。<br/><br/>
下面是URL类的定义，对应文件Url.h。<br/><br/>
enum url_scheme{<br/><br/>
SCHEME_HTTP,SCHEME_FTP,SCHEME_INVALID<br/><br/>
};<br/><br/>
class CUrl<br/><br/>
{<br/><br/>
public:<br/><br/>
string m_sUrl; URL字串<br/><br/>
enum url_scheme m_eScheme; 协议名<br/><br/>
string m_sHost; 主机名<br/><br/>
int m_nPort; 端口号<br/><br/>
string m_sPath; 请求资源<br/><br/>
public:<br/><br/>
CUrl;<br/><br/>
~CUrl;<br/><br/>
bool ParseUrl( string strUrl );<br/><br/>
private:<br/><br/>
void ParseScheme ( const char url );<br/><br/>
};<br/><br/>
URL可以是HTTP， FTP等协议开始的字符串， TSE主要是针对HTTP协议，为了不失一般性，在 url_scheme 中定义了 SCHEME_HTTP，SCHEME_FTP，SCHEME_INVALID，分别对应HTTP协议，FTP协议和其他协议。一个URL由<br/><br/>
6个部分组成：<br/><br/>
<scheme>:<net_loc><path>;<params>?<query><fragment><br/><br/>
除了scheme部分，其他部分可以不在URL中同时出现。<br/><br/>
Scheme 表示协议名称，对应于URL类中的m_eScheme.<br/><br/>
Net_loc 表示网络位置，包括主机名和端口号，对应于URL类中的m_sHost<br/><br/>
和m_nPort.<br/><br/>
下面四个部分对应于URL类中的m_sPath.<br/><br/>
· 35 ?第三章 Web信息的搜集<br/><br/>
Path 表示URL 路径.<br/><br/>
Params 表示对象参数.<br/><br/>
Query 表示查询信息，也经常记为request.<br/><br/>
Fragment 表示片断标识.<br/><br/>
为了程序的简化，URL 类的实现主要是解析出 net_loc 部分，用于组成消息<br/><br/>
体，发送给服务器。<br/><br/>
其中 void CUrl::ParseUrlEx(const char url, char protocol, int lprotocol,char host, int lhost, char request, int lrequest, int port) 执行具体的字符串匹配找<br/><br/>
出协议名，主机名，请求信息和端口号，找到后赋给 Url 类的成员变量保存。在<br/><br/>
URL类中还有些是TSE抓取过程中的细节函数， 如char CUrl::GetIpByHost(const<br/><br/>
char host)，CUrl::IsValidHost(const char host)，bool CUrl::IsVisitedUrl(const char<br/><br/>
url)等，此处就不一一介绍了。读者可以通过阅读TSE的代码获得这部分的具体<br/><br/>
实现。<br/><br/>
2. 定义Page类<br/><br/>
有了 URL，搜集系统就可以按照 URL 标识抓取其所对应的网页，网页信息<br/><br/>
保存在Page类中。<br/><br/>
下面是Page类的定义，对应文件Page.h。<br/><br/>
class CPage<br/><br/>
{<br/><br/>
public:<br/><br/>
string m_sUrl;<br/><br/>
网页头信息<br/><br/>
string m_sHeader;<br/><br/>
int m_nLenHeader;<br/><br/>
int m_nStatusCode;<br/><br/>
int m_nContentLength;<br/><br/>
string m_sLocation;<br/><br/>
bool m_bConnectionState; 如果连接关闭， 是false， 否则为true<br/><br/>
string m_sContentEncoding;<br/><br/>
string m_sContentType;<br/><br/>
string m_sCharset;<br/><br/>
· 36 ?第三章 Web信息的搜集<br/><br/>
string m_sTransferEncoding;<br/><br/>
网页体信息<br/><br/>
string m_sContent;<br/><br/>
int m_nLenContent;<br/><br/>
string m_sContentNoTags;<br/><br/>
link, in a lash-up state<br/><br/>
string m_sContentLinkInfo;<br/><br/>
为搜索引擎准备的链接，in a lash-up state<br/><br/>
string m_sLinkInfo4SE;<br/><br/>
int m_nLenLinkInfo4SE;<br/><br/>
为历史存档准备的链接， in a lash-up state<br/><br/>
string m_sLinkInfo4History;<br/><br/>
int m_nLenLinkInfo4History;<br/><br/>
为搜索准备的链接，in a good ......</div>
<!--DuYiHuaAdd EndContent--></div>
<div id="txtThisUrl"><br/> <a href="http://www.100md.com/html/file/201912/190196.htm" target="_blank">http://www.100md.com/html/file/201912/190196.htm</a></div>
<div id="txttips"><br/>您现在查看是摘要介绍页，<a href="http://www.100md.com/about/help.htm">
详见PDF附件(3534KB，279页)</a>。</div>
<script language="javascript" type="text/javascript" src="http://www.100md.com/comm/v2019/login.js"></script>
<script language="javascript" type="text/javascript" src="http://www.100md.com/comm/v2019/after.js"></script>
<div id="theRInfo"><script language="javascript" type="text/javascript" src="http://www.100md.com/rjs/file/201912/190196.js"></script><script language="javascript" type="text/javascript" src="http://www.100md.com/comm/v2019/related.js"></script></div>
</div><div id="right"><script language="javascript" type="text/javascript" src="http://www.100md.com/comm/v2019/right.js"></script></div>
</div><div id="copyright"><script language="javascript" type="text/javascript" src="http://www.100md.com/comm/v2019/copyright.js"></script></div></body></html>
搜 索 引 擎
— 原理、技术与系统
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
第四章 对搜集信息的预处理................................................................................... 55
第一节 信息预处理的系统结构.................................................................................. 55
第二节 索引网页库...................................................................................................... 56
第三节 中文自动分词.................................................................................................. 58
第四节 分析网页和建立倒排文件.............................................................................. 64
第五节 本章小结.......................................................................................................... 66
第五章 信息查询服务............................................................................................... 67
第一节 查询服务的系统结构...................................................................................... 67
第二节 检索的定义...................................................................................................... 68
第三节 查询服务的实现.............................................................................................. 69
一、 结果集合的形成.............................................................................................. 69
二、 查询结果显示................................................................................................. 70
第四节 本章小结.......................................................................................................... 72
中篇 对质量和性能的追求..................................................................................... 73
第六章 可扩展搜集子系统....................................................................................... 75
第一节 天网系统概述和集中式搜集系统结构........................................................... 75
一、 天网系统结构................................................................................................. 75
二、 集中式搜集系统.............................................................................................. 76
第二节 利用并行处理技术高效搜集网页的一种方案............................................... 82
一、 节点间URL的划分策略.................................................................................. 83
二、 关于性能的讨论.............................................................................................. 86
三、 性能测试和评价.............................................................................................. 88
四、 系统的动态可配置性设计.............................................................................. 91
第三节 本章小结.......................................................................................................... 93
第七章 网页净化与消重........................................................................................... 95
第一节 网页净化与元数据提取.................................................................................. 95
一、 引言................................................................................................................. 95
二、 DocView模型.................................................................................................. 98
三、 网页的表示..................................................................................................... 99
四、 提取DocView模型要素的方法..................................................................... 103
五、 模型应用及实验研究.................................................................................... 108
第二节 网页消重算法................................................................................................ 112
一、 消重算法....................................................................................................... 112
iv
二、 算法评测....................................................................................................... 115
第八章 高性能检索子系统..................................................................................... 120
第一节 检索系统基本技术........................................................................................ 121
一、 系统设计与结构............................................................................................ 121
二、 索引创建....................................................................................................... 124
三、 检索过程....................................................................................................... 126
第二节 倒排文件性能模型........................................................................................ 127
一、 引言............................................................................................................... 128
二、 倒排文件的概念............................................................................................ 129
三、 倒排文件的一种性能模型............................................................................ 131
四、 结合计算机性能指标的考虑........................................................................ 136
第三节 混合索引技术................................................................................................ 138
一、 引言............................................................................................................... 138
二、 混合索引原理............................................................................................... 139
三、 混合索引实现............................................................................................... 141
第四节 倒排文件缓存机制........................................................................................ 144
一、 引言............................................................................................................... 144
二、 倒排文件缓存............................................................................................... 145
三、 负载特性....................................................................................................... 147
四、 缓存策略的选择............................................................................................ 149
第五节 本章小结........................................................................................................ 149
第九章 用户行为的特征及缓存的应用................................................................. 151
第一节 用户查询与点击日志.................................................................................... 152
第二节 用户行为特征的统计分析............................................................................ 154
一、 用户查询词的分布情况................................................................................ 154
二、 雷同查询词的衰减统计................................................................................ 155
三、 相邻N项查询词的偏差分析......................................................................... 156
四、 用户在输出结果中的翻页情况统计............................................................ 158
五、 用户点击URL的分布情况............................................................................ 159
六、 考虑与不考虑查询项时点击URL分布的对比分析.................................... 160
七、 查询过程的自相似性.................................................................................... 161
第三节 查询缓存的使用............................................................................................ 164
一、 基于用户行为的启示.................................................................................... 164
二、 缓存替换策略研究........................................................................................ 165
v
第四节 用户行为与WEB信息的分布特征................................................................. 167
一、 基本术语....................................................................................................... 167
二、 海量Web信息的特征分析............................................................................. 168
第十章 相关排序与系统质量评估......................................................................... 173
第一节 传统IR的相关排序技术................................................................................ 173
第二节 链接分析与相关排序.................................................................................... 176
一、 链接分析....................................................................................................... 176
二、 Web查询模式下的新信息............................................................................ 178
第三节 相关排序的一种实现方案............................................................................ 182
一、 形成网页中词项的基本权重........................................................................ 183
二、 利用链接的结构............................................................................................ 185
三、 收集用户反馈信息........................................................................................ 187
四、 计算最终的权重............................................................................................ 189
第四节 搜索引擎系统质量评估................................................................................ 191
一、 引言............................................................................................................... 191
二、 查询类别分析与查询集的构建.................................................................... 192
三、 评估实验的建立与分析................................................................................ 193
下篇 面向主题和个性化的WEB信息服务.......................................................... 196
第十一章 中文网页自动分类技术......................................................................... 197
第一节 引言................................................................................................................ 197
第二节 文档自动分类算法的类型............................................................................ 197
第三节 实现中文网页自动分类的一般过程............................................................. 199
第四节 影响分类器性能的关键因素分析................................................................. 201
一、 实验设置....................................................................................................... 201
二、 训练样本....................................................................................................... 202
三、 特征选取....................................................................................................... 207
四、 分类算法....................................................................................................... 210
五、 截尾算法....................................................................................................... 216
六、 一个中文网页分类器的设计方案................................................................ 218
第五节 天网目录导航服务........................................................................................ 219
一、 问题的提出................................................................................................... 219
二、 天网目录导航服务的体系结构.................................................................... 220
三、 天网目录的运行实例.................................................................................... 221
第六节 本章小结........................................................................................................ 221
vi
第十二章 搜索引擎个性化查询服务..................................................................... 223
第一节 基于WEB挖掘的个性化技术......................................................................... 223
一、 Web挖掘技术................................................................................................ 224
二、 典型个性化Web服务系统的比较................................................................. 225
三、 基于Web挖掘的个性化技术的发展............................................................. 226
第二节 天网知名度系统............................................................................................ 227
一、 系统结构....................................................................................................... 227
二、 网页与命名实体的相关度评价.................................................................... 231
第十三章 面向主题的信息搜集与应用................................................................. 235
第一节 主题信息的搜集............................................................................................ 235
一、 主题信息分布的局部性................................................................................ 235
二、 一种主题信息搜集系统................................................................................ 236
第二节 主题信息的一种搜集与处理模型及其应用................................................. 238
一、 模型设计....................................................................................................... 238
二、 应用实验：以“十六大”为主题................................................................ 242
三、 总结与讨论................................................................................................... 244
参考文献................................................................................................................... 245
附录. 术语................................................................................................................ 256
后记........................................................................................................................... 264
vii
图 示
图1-1 2003年8月20日在天网上检索“伊拉克战争”的结果................3
图1-2 2003年8月20日在搜狐上检索“伊拉克战争”的结果................5
图2-1 搜索引擎示意图................................................................................17
图2-2 搜索引擎三段式工作流程................................................................18
图2-3 搜索引擎的体系结构........................................................................26
图3-1 TSE搜索引擎界面..............................................................................31
图3-2 TSE查询结果页面..............................................................................32
图3-3 TSE网页快照页面..............................................................................32
图3-4 TSE系统结构.....................................................................................33
图3-5 Web信息的搜集.................................................................................34
图3-6 Sockets和端口....................................................................................39
图3-7 通过Socket建立连接.........................................................................40
图3-8 Web象个海洋.....................................................................................51
图4-1 网页预处理系统结构........................................................................55
图4-2 原始网页库中的记录格式................................................................56
图4-3 索引网页库算法................................................................................57
图4-4 正向减字最大匹配算法流程............................................................61
图4-5 切词算法流程....................................................................................62
图4-6分析网页与建立倒排文件流程.........................................................64
图4-7 过滤网页中非正文信息算法............................................................64
图4-8 正向索引表记录格式........................................................................65
图4-9 由正向索引建立反向索引................................................................65
图5-1 信息查询的系统结构........................................................................67
图5-2 基本检索算法....................................................................................69
图5-3 动态摘要算法....................................................................................71
图5-4 用户查询日志的记录格式................................................................71
图6-1 天网系统概貌....................................................................................76
图6-2 搜集系统的主控结构........................................................................78
图6-3 协调进程工作算法............................................................................85
图6-4 分布式Web搜集系统结构.................................................................86
图6-5 负载方差...........................................................................................89
图6-6 n个节点并行搜集系统及集中式系统性能随时间的变化...............90
图6-7 分布式系统效率................................................................................91
viii
图6-8 URL两阶段映射.................................................................................92
图7-1 用DocView模型提取的网页要素.....................................................99
图7-2 净化后的网页....................................................................................99
图7-3 HTML Tree 结构.............................................................................101
图7-4 内容块权值传递过程......................................................................102
图7-5 有主题网页DocView模型生成过程...............................................105
图7-6 计算网页特征项权值的算法..........................................................105
图7-7 正文段落识别过程..........................................................................106
图7-8 基于anchor text的超链选取算法....................................................107
图7-9 网页净化前后分类效果对比..........................................................109
图7-10 查全率随选取关键词个数的变化................................................ 117
图8-1 检索系统集成框架结构..................................................................122
图8-2 天网WWW检索分布式系统构架...................................................123
图8-3 倒排文件结构示意图......................................................................130
图8-4 英语单词和汉语字符的ITF分布....................................................136
图8-5 扩展词典树结构示例......................................................................143
图8-6 扩展词典匹配查找算法..................................................................144
图8-7 搜索引擎检索系统缓存结构..........................................................145
图8-8 文档数据访问对象大小分布..........................................................148
图8-9 IO与PAGE序列序号-频度分布......................................................148
图8-10 IO与PAGE序列时间间隔分布.....................................................149
图8-11 IO和PAGE序列中唯一模式串......................................................149
图9-1 查询词的分布情况..........................................................................154
图9-2 查询词分布函数及其拟合函数......................................................155
图9-3 雷同查询词的衰减..........................................................................156
图9-4 相邻1000项查询词的频率的差的平方和....................................157
图9-5用户翻页情况统计...........................................................................158
图9-6 用户点击URL的分布情况..............................................................159
图9-7 考虑查询项与否的URL分布情况..................................................160
图9-8 相邻500项中不同查询项的分布..................................................162
图9-9 相邻1000项中不同查询项的分布................................................162
图9-10 相邻2000项中不同查询项的分布..............................................163
图9-11 查询项分布的自相似性特征........................................................163
图9-12 FIFO、LRU和带衰减的LFU的缓存命中率比较.........................166
图9-13 3种替换策略的局部比较..............................................................166
图9-14 网页的被访问次数........................................................................169
ix
图9-15 用户点击url对应网页的入度.......................................................170
图9-16 用户点击url对应网页的镜像度...................................................170
图9-17 用户点击url对应网页的目录深度...............................................171
图9-18 站内网页的树状结构....................................................................171
图10-1 Inktomi提供的几种搜索引擎技术的比较....................................179
图10-2 词典在系统中的地位....................................................................180
图10-3 新词学习.......................................................................................181
图10-4 网页的互联结构示意....................................................................185
图11-1 自动文档分类算法的分类............................................................199
图11-2 中文网页自动分类的一般过程....................................................200
图11-3 中文网页分类器的工作原理图....................................................200
图11-4 WebSmart —一个网页实例集搜集和整理工具...........................204
图11-5 一种中文网页的分类体系............................................................205
图11-6 Macro-F1值随样本数的变化..........................................................206
图11-7 Micro-F1值随样本数的变化..........................................................206
图11-8 CHI、IG、DF、MI的比较(Macro-F1).....................................209
图11-9 CHI、IG、DF、MI的比较(Micro-F1).....................................210
图11-10 kNN与NB分类结果的比较..........................................................213
图11-11 k的取值对分类器质量的影响(Marco-F1)..............................214
图11-12 k的取值对分类器质量的影响(Micro-F1)...............................214
图11-13 兰式距离法与欧式距离法对12个不同类别的分类情况........215
图11-14 基于层次模型的kNN与基本kNN的比较...................................216
图11-15 RCut和SCut截尾算法的比较.......................................................218
图11-16 天网目录的体系结构..................................................................220
图11-17 天网目录导航服务......................................................................221
图12-1 Web个性化的实质.........................................................................224
图12-2 Web挖掘的分类.............................................................................224
图12-3 网页与实体相关度的建立............................................................228
图12-4 个性化知名度示意图....................................................................228
图12-5 “天网知名度”系统结构............................................................230
图13-1 页面对的平均相关性....................................................................236
图13-2 Foused Crawler的系统结构...........................................................237
图13-3 用于表达网上主题新闻强度指标的立方体................................240
图13-4 十六大网页数量在10月22至11月24期间的变化情况........244
x
表 格
表4-1 网页索引文件.......................................................................................................58
表4-2 URL索引文件........................................................................................................58
表6-1 Soif数据描述..........................................................................................................78
表6-2 Soif具体语法..........................................................................................................80
表6-3 参照序列，假设节点数为2...............................................................................89
表7-1 类别编号对照表.................................................................................................110
表7-2 消重实验结果.....................................................................................................111
表7-3 当N=10、δ =0.01时5种算法的查全率和准确率.....................................116
表7-4 考察δ 的取值对算法3和4的影响..............................................................117
表7-5 分段签名算法的时间复杂度及性能..............................................................118
表7-6 基于关键词的各算法的时间复杂度及性能 (N=10, δ =0.01)..................118
表8-1 英汉词频统计排序对照................................................................................... 134
表8-2 一些典型磁盘的性能数据............................................................................... 136
表8-3 数据集基本统计信息....................................................................................... 146
表9-1 用户在前5页的翻页情况统计...................................................................... 158
表9-2 调整后的LFU与LRU命中率的比较.............................................................. 166
表9-3 各网页参数的分布............................................................................................ 169
表10-1新词学习对检索准确率的影响..................................................................... 182
表10-2 影响权值的HTML标签................................................................................. 184
表10-3 补偿因子定义表.............................................................................................. 188
表10-4 用户查询信息类别.......................................................................................... 193
表11-1 样本集中类别及实例数量的分布情况表................................................... 203
表11-2 kNN和NB算法的分类质量和分类效率比较.............................................. 213
表11-3 欧式距离与兰式距离的比较........................................................................ 215
表11-4 基于层次模型的kNN与基本kNN的比较................................................... 216
表11-5 RCut和SCut截尾算法的比较......................................................................... 217
表11-6 一个分类器的设计方案................................................................................. 218
表12-1 典型Web个性化系统的比较......................................................................... 225
表12-2 天网知名度系统与其他检索系统的横向比较结果................................. 232
表12-3 天网知名度系统的纵向比较结果................................................................ 234
xi第一章 引论
第一章 引论
信息的生产、传播、搜集与查询是人类最基本的活动之一。考虑以文字为载
体的信息，传统上有图书馆、相应的编目体系和专业人员帮助我们很快找到所需
的信息，其粒度通常是“书”或者“文章”。随着计算机与信息技术的发展，有了
信息检索(Information Retrieval，IR)学科领域，有了关于图书或者文献的全文
检索系统，使我们能很方便地在“关键词”的粒度上得到相关的信息。
我们注意到，上述全文检索系统一般工作在一个规模相对有限、内容相对稳
定的馆藏(collection)上，被检索的对象通常是经过认真筛选和预先处理的(例
如人工提取出了“作者” ， “标题”等元数据，形成了很好的“摘要”等) ，并且系
统需要同时响应的查询数量通常都不会太大(例如每秒钟10个左右) 。
1994年左右，万维网(World Wide Web，简记为WWW或Web)出现。它
的开放性(openness)和其上信息广泛的可访问性(accessibility)极大地鼓励了
人们创作的积极性。作为一个信息源， Web和上述全文检索系统的工作对象相比，具有许多不同的特征，它们给信息检索领域带来了新的发展机遇和技术挑战。
规模大。在短短的10年左右时间，人类至少生产了40亿网页[Google,2004]，而人类有文字上万年以来产生了大约1亿本书；中国网上到2004年初大致有了约
3 亿网页[天网,2004]，而中华民族有史以来出版的书籍大约不过 275 万种。尽管
书籍的容量和质量是一般网页不可比的，但在对应的时间背景上考察其文字的总
体数量，我们不能不为人类在Web上创造文字的激情惊叹!
内容不稳定。除了不断有新的网页出现外，旧的网页会因为各种原因被删除
(有研究指出50%网页的平均生命周期大约为50天[Cho and Garcia-Molina,2000,Cho,2002])；
从原则上讲，读者数和作者数在同一个量级，形式和内容的随意性很强，权
威性相对也不高，也不太可能进行人工筛选和预处理。
与生俱来的数字化、网络化。传统载体上的信息，人们目前正忙于将它们数
字化、上网(花费极高)，而网络信息天生如此。这个特性是一把双刃剑：一方面
便于我们搜集和处理，另一方面也会使我们感到太多，蜂拥而至，鱼目混珠。
而作为要在Web上提供服务的信息查询系统，如搜索引擎和数字图书馆，通
常要具备同时对付大量访问的能力(例如每秒钟1000个查询)，而且响应时间还
要足够的快(例如1秒钟) 。
本书旨在介绍构建这类搜索引擎的有关技术。传统的 IR 是其基础，同时也
充分讨论了由上述Web信息的特征所带来的新问题及其解决方案。
· 1 ?第一章 引论
第一节 搜索引擎的概念
如上所述，本书的主要内容是介绍搜索引擎的工作原理和实现技术。搜索引
擎，在本书指的是一种在 Web 上应用的软件系统，它以一定的策略在 Web 上搜
集和发现信息，在对信息进行处理和组织后，为用户提供Web信息查询服务。从
使用者的角度看，这种软件系统提供一个网页界面，让他通过浏览器提交一个词
语或者短语，然后很快返回一个可能和用户输入内容相关的信息列表(常常会是
很长一个列表，例如包含1万个条目)。这个列表中的每一条目代表一篇网页，至
少有3个元素：
标题：以某种方式得到的网页内容的标题。最简单的方式就是从网页的