本书系统介绍了互联网搜索引擎的工作原理、实现技术及系统构建方案。全书分三篇共13章。上篇介绍搜索引擎的基本原理和技术，讲述一个小型简单搜索引擎实现的具体细节；中篇详细讨论了大规模分布式搜索引擎系统的设计要点及其关键技术；下篇结合“中国Web信息博物馆”和“中国互联网数字资源财富库藏”的实践经验，介绍了构建大规模Web历史网页和非网页仓储系统的技术和方法，以及中文网页的自动分类与聚类、开放域问题系统的构建等。
本书层次分明，由浅入深，上篇和中篇涉及内容提供了源代码下载地址；既有深入的理论分析，也有大量的实验数据和程序，具有学习和实用双重意义。
样章试读
目录
- 目录
第二版前言
第一版前言
第一章 引论 1
第一节 搜索引擎的概念 2
第二节 搜索引擎的发展历史 3
第三节 一些著名的搜索引擎 6
第四节 小结 11
上篇 Web搜索引擎基本原理和技术
第二章 Web搜索引擎工作原理和体系结构 15
第一节 基本要求 15
第二节 网页搜集 16
第三节 预处理 18
第四节 查询服务 20
第五节 体系结构 23
第六节 小结 25
第三章 Web信息的搜集 26
第一节 概述 26
一、超文本传输协议 26
二、一个小型搜索引擎系统 27
第二节 网页搜集 30
一、定义URL类和Page类 31
二、与服务器建立连接 35
三、发送请求和接收数据 37
四、网页信息存储的天网格式 38
第三节 多道搜集程序并行工作 40
一、多线程并发工作 41
二、控制对一个站点并发搜集线程的数目 42
第四节 如何避免网页的重复搜集 43
一、记录未访问、已访问URL和网页内容摘要信息 43
二、域名与IP的对应问题 43
第五节 搜集信息的类型 45
第六节 小结 46
第四章 对搜集信息的预处理 47
第一节 索引网页库 47
第二节 网页编码识别 50
一、基本而重要的概念 50
二、常用字符编码 52
三、常用字符编码算法 55
四、字符的输入和显示 57
五、编码识别 58
第三节 中文自动分词 60
第四节 分析网页和建立倒排文件 64
第五节 小结 67
第五章 信息查询服务 68
第一节 检索的定义 68
第二节 查询服务的实现 69
一、结果集合的形成 69
二、查询结果显示 70
第三节 小结 71
中篇 对质量和性能的追求
第六章 可扩展搜集子系统 75
第一节 天网系统概述和集中式搜集系统结构 75
一、天网系统结构 75
二、集中式搜集系统 76
第二节 利用并行处理技术高效搜集网页的一种方案 82
一、节点间URL的划分策略 82
二、关于性能的讨论 85
三、性能测试和评价 87
四、系统的动态可配置性设计 90
第三节 天网分布式搜集系统 92
第四节 对Deep Web的认识 93
一、Deep Web的成因 93
二、搜索Deep Web的方法 96
第五节 小结 98
第七章 网页净化与消重 100
第一节 网页净化与元数据提取 100
一、DocView模型 102
二、网页的表示 103
三、提取DocView模型要素的方法 108
四、模型应用及实验研究 112
第二节 网页消重算法 115
一、消重算法 116
二、算法评测 118
第三节 小结 121
第八章 高性能检索子系统 122
第一节 检索系统基本技术 122
一、系统设计与结构 122
二、索引创建 125
三、检索过程 127
第二节 适于查询的网页索引结构 129
一、倒排索引结构 129
二、平面位置索引 131
第三节 倒排索引压缩 135
一、倒排索引压缩技术 136
二、词典与倒排表的压缩 142
第四节 索引剪枝 150
一、静态索引剪枝方法 151
二、动态索引剪枝方法 153
第五节 混合索引技术 168
一、混合索引的原理 169
二、混合索引的实现 171
第六节 倒排文件缓存机制 173
一、倒排文件缓存 174
二、负载特性 176
三、缓存策略的选择 178
第七节 小结 178
第九章 相关排序与系统质量评估 180
第一节 传统IR的相关排序技木 180
第二节 链接分析与相关排序 182
一、链接分析 182
二、Web查询模式下的新信息 184
第三节 相关排序的一种实现方案 188
一、形成网页中词项的基本权重 189
二、利用链接的结构 190
三、收集用户反馈信息 192
四、计算最终的权重 194
第四节 信息检索技术评估 195
一、信息检索技术评估指标 197
二、TREC和CWIRF信息检索评估 206
三、搜索引擎技术评估 213
第五节 小结 217
下篇 Web信息资源的组织与应用服务
第十章 大规模Web历史网页仓储系统的构建 221
第一节 国外Web历史网页保存现状 221
一、Internet Archive 222
二、PANDORA 222
三、其他相关Web保存项目 223
第二节 中国Web信息博物馆的系统设计 224
一、Web InfoMall的设计目标 225
二、Web InfoMall的体系结构 225
第三节 历史网页的存储 227
一、数据的组织 228
二、存储结构 229
三、数据管理与压缩 230
四、存储性能 232
第四节 数据访问 232
一、PageID的索引 233
二、URI的索引 233
三、数据服务 234
四、性能与优化 235
第五节 网页的格式保存 236
第六节 小结 236
第十一章 大规模Web非网页信息仓储系统的构建 238
第一节 网络资源库藏相关工作 238
一、Ibiblio 239
二、Internet Archive 240
三、Wikimedia 240
四、中国互联网数字资源财富库藏 241
第二节 CDAL系统概况 242
第三节 CDAL系统设计 244
一、系统体系结构 244
二、可扩展的存储组织方案 244
第四节 网络资源描述信息获取 246
一、Ontology概述 247
二、描述信息获取机制 247
三、改进查询的方法 248
四、改进排序的方法 249
第五节 基于局部聚类思想的共现词汇算法 250
一、基本定义 251
二、FDC共现词汇算法 251
第六节 小结 252
第十二章 中文网页自动分类与聚类 253
第一节 文档自动分类算法的类型 253
第二节 实现中文网页自动分类的一般过程 254
第三节 影响分类器性能的关键因素分析 256
一、实验设置 256
二、训练样本 258
三、特征选取 262
四、分类算法 265
五、截尾算法 270
六、中文网页分类器的设计方案 272
第四节 天网目录导航服务 272
一、问题的提出 272
二、天网目录导航服务的体系结构 273
三、天网目录的运行实例 274
第五节 文本聚类方法 275
一、文本聚类的一般过程 275
二、文本间相似性的度量 276
三、常用聚类算法 276
四、聚类结果的评估 279
五、搜索引擎返回结果的聚类 280
第六节 小结 281
第十三章 开放域问答系统 283
第一节 概述 283
一、问答系统的历史 283
二、著名开放域问答系统介绍 284
三、开放域问答系统的通用体系结构 285
第二节 问句的分析 287
一、问句中的指代消解 287
二、问句分类 288
三、问句主题提取 290
第三节 文档和段落检索 290
一、检索模型的选用 291
二、查询生成 291
三、查询结果排序 293
四、增强索引的功能 295
第四节 答案提取和验证模块 295
一、生成候选答案集合 295
二、答案提取 296
第五节 问答系统的改进方法 299
一、问答系统中外部资源的利用 299
二、寻找特殊类问题的解决方案 301
三、通过系综方法构建问答系统 302
第六节 问答系统的评测 303
一、TREC问答系统评测 303
二、问答系统评测指标 304
第七节 实例：天网开放域问答系统 306
第八节 小结 308
参考文献 309
附录 术语 322
图表目录
图1-1 2012年3月在Google上检索“伊拉克战争”的结果 2
图1-2 2012年3月在Open Directory上检索“伊拉克战争”的结果 5
图2-1 搜索引擎示意图 15
图2-2 搜索引擎三段式工作流程 16
图2-3 搜索引擎的体系结构 23
图3-1 TSE搜索引擎界面 28
图3-2 TSE查询结果页面 29
图3-3 TSE网页快照页面 29
图3-4 TSE系统结构 30
图3-5 Web信息的搜集 31
图3-6 Sockets和端口 35
图3-7 通过Socket建立连接 36
图4-1 网页预处理系统结构 47
图4-2 原始网页库中的记录格式 48
图4-3 索引网页库算法 49
图4-4 字符的输入和显示流程 57
图4-5 GB2312，Big5和GBK字符编码分布 58
图4-6 正向减字最大匹配算法流程 62
图4-7 切词算法流程 63
图4-8 分析网页与建立倒排文件流程 65
图4-9 过滤网页中非正文信息算法 65
图4-10 正向索引表记录格式 65
图4-11 由正向索引建立反向索引 66
图5-1 信息查询的系统结构 68
图5-2 基本检索算法 69
图5-3 动态摘要算法 71
图5-4 用户查询日志的记录格式 71
图6-1 天网系统概貌 76
图6-2 搜集系统的主控结构 77
图6-3 协调进程工作算法 84
图6-4 分布式Web搜集系统结构 85
图6-5 负载方差 88
图6-6 并行搜集系统与集中式搜集系统的性能对比 89
图6-7 分布式系统效率 89
图6-8 URL两阶段映射 91
图6-9 天网分布式搜集系统P_Arthur体系结构 92
图6-10 人才招聘网站首页 94
图7-1 用DocView模型提取的网页要素 104
图7-2 净化后的网页 104
图7-3 HTML Tree结构 105
图7-4 内容块权值传递过程 107
图7-5 有主题网页DocView模型生成过程 109
图7-6 计算网页特征项权值的算法 109
图7-7 正文段落识别过程 111
图7-8 基于anchor text的超链选取算法 111
图7-9 网页净化前后分类效果对比 113
图7-10 查全率随选取关键词个数的变化 120
图8-1 检索系统集成框架结构 124
图8-2 天网WWW检索分布式系统构架 125
图8-3 倒排索引结构示意图 129
图8-4 按块组织的倒排链的结构 130
图8-5 位置索引的结构 131
图8-6 CLPS结构示意图 135
图8-7 倒排链中文档号之间的d-gaps分布图 146
图8-8 不同文档号分配下平均每个查询对应文档号序列的压缩大小 146
图8-9 不同压缩算法对文档号的解压速度 147
图8-10 不同文档号分配下平均每个查询对应词频序列的压缩大小 147
图8-11 不同压缩算法对词频的解压速度 148
图8-12 平均每个查询对应的位置信息需要的存储空间 149
图8-13 索引剪枝方法的分类 151
图8-14 MAXSCORE算法的示例 157
图8-15 WAND算法选择候选文档的过程 159
图8-16 基于最大块索引的支点文档号的选择示例 161
图8-17 Interval-Base剪枝方法中文档子区间划分的示例 161
图8-18 SAAT方法处理查询处理模式及分数累加器数量的变化 164
图8-19 当前支持高效SR+IR剪枝的索引结构 166
图8-20 扩展词典树结构示例 172
图8-21 扩展词典匹配查找算法 173
图8-22 搜索引擎检索系统缓存结构 174
图8-23 文档数据访问对象大小分布 176
图8-24 I/O与PAGE序列序号—频度分布 177
图8-25 I/O与PAGE序列时间间隔分布 177
图8-26 I/O和PAGE序列中唯一模式串 178
图9-1 Inktomi提供的几种搜索引擎技术的比较 185
图9-2 词典在系统中的地位 186
图9-3 新词学习 187
图9-4 网页的互联结构示意 191
图9-5 信息获取技术评估的“森林 197
图9-6 查准率和召回率基础定义图示 198
图9-7 查准率和召回率例子 198
图9-8 “省事的”11点标准召回率例子 199
图9-9 实践中召回率例子 200
图9-10 实际中的44个查询词的评价统计表初P-R图 202
图9-11 测试集在检索评估中的角色 208
图9-12 帮助判断相关结果页面的计算机辅助程序人口 211
图9-13 帮助判断相关结果页面的计算机辅助程序操作界面 211
图10-1 Web InfoMall体系结构 226
图10-2 网页数据的分割 229
图10-3 Web InfoMall的存储结构 230
图10-4 网页的引用压缩示意图 232
图11-1 CDAL提供的资源访问方式 243
图11-2 CDAL系统结构图 245
图11-3 基于Ontology的网络资源描述信息获取 248
图11-4 概念的属性及其词汇扩展（以电影类资源为例） 249
图11-5 获得描述信息的改进排序算法 250
图11-6 网络资源描述信息展示 250
图12-1 自动文档分类算法的分类 254
图12-2 中文网页自动分类的一般过程 255
图12-3 中文网页分类器的工作原理图 256
图12-4 WebSmart——一个网页实例集搜集和整理工具 259
图12-5 一种中文网页的分类体系 260
图12-6 Macro-F1值随样本数的变化 261
图12-7 Micro-F1值随样本数的变化 261
图12-8 CHI、IG、DF、MI的比较（Macro-F1） 264
图12-9 CHI、IG、DF、MI的比较（Micro-F1） 264
图12-10 kNN与NB分类结果的比较 267
图12-11 是的取值对分类器质量的影响（Marco-F1） 268
图12-12 忌的取值对分类器质量的影响（Micro-F1） 268
图12-13 兰式距离法与欧式距离法对12个不同类别的分类情况 269
图12-14 基于层次模型的kNN与基本kNN的比较 270
图12-15 RCut和SCut截尾算法的比较 272
图12-16 天网目录的体系结构 274
图12-17 天网目录导航服务 274
图12-18 文本聚类的一般过程 275
图12-19 层次聚类实例 277
图12-20 k-均值算法进行文本聚类的过程 278
图12-21 搜索结果聚类系统Carrot2 281
图13-1 START系统界面 285
图13-2 Ask Jeeves查询结果 285
图13-3 问答系统的通用体系结构 287
图13-4 天网开放域系统的体系结构 306
表4-1 网页索引文件 49
表4-2 URL索引文件 50
表6-1 SOIF数据描述 78
表6-2 SOIF具体语法 80
表6-3 参照序列，假设节点数为2 87
表7-1 类别编号对照表 113
表7-2 消重实验结果 115
表7-3 当N＝10、δ=0.01时5种算法的查全率和准确率 119
表7-4 考察δ的取值对算法3和4的影响 119
表7-5 分段签名算法的时间复杂度及性能 120
表7-6 基于关键词的各算法的时间复杂度及性能（N=10，a=0.01） 121
表8-1 MTF对序列<4，4，1，4，2>进行转换的过程 142
表8-2 对包含100万词条的词典使用不同编码所需要的空间 144
表8-3 平均每个查询对应词频链的空间大小（文档号按URL序分配） 148
表8-4 不同索引的组织结构及其支持的查询处理方式 155
表8-5 数据集基本统计信息 176
表9-1 新词学习对检索准确率的影响 188
表9-2 影响权值的HTML标签 189
表9-3 补偿因子定义表 192
表9-4 2004中文Web信息检索评测提交结果 210
表9-5 主题提取 212
表9-6 导航搜索 212
表9-7 用户查询信息类别 215
表10-1 网页存储性能（个/秒） 232
表10-2 网页访问性能（个/秒） 236
表11-1 几个网络资源库藏系统的特征 238
表11-2 CDAL中的资源分布 243
表12-1 样本集中类别及实例数量的分布情况表 258
表12-2 kNN和NB算法的分类质量和分类效率比较 267
表12-3 欧式距离与兰式距离的比较 269
表12-4 基于层次模型的kNN与基本kNN的比较 270
表12-5 RCut和SCut截尾算法的比较 271
表12-6 一个分类器的设计方案 272
表13-1 问题分类体系结构及TREC问答任务中间题的分布 289
表13-2 天网开放域系统在TREC2005中的表现 307
京公网安备 11010102004214号