搜索引擎 原理、技术与系统PDF电子书下载

前言 1

第一章 引论 1

目录 1

第一节 搜索引擎的概念 2

第二节 搜索引擎的发展历史 3

图1-1 2003年8月20日在天网上检索“伊拉克战争”的结果 3

图表目录 3

图1-2 2003年8月20日在搜狐上检索“伊拉克战争”的结果 6

第三节 一些著名的搜索引擎 7

图2-1 搜索引擎示意图 19

上篇 Web搜索引擎基本原理和技术 19

第二章 Web搜索引擎工作原理和体系结构 19

第一节 基本要求 19

图2-2 搜索引擎三段式工作流程 20

第二节 网页搜集 20

第三节 预处理 22

第四节 查询服务 24

第五节 体系结构 27

图2-3 搜索引擎的体系结构 28

第一节 引言 30

一、超文本传输协议 30

第三章 Web信息的搜集 30

二、一个小型搜索引擎系统 31

图3-1 TSE搜索引擎界面 32

图3-3 TSE网页快照页面 33

图3-2 TSE查询结果页面 33

图3-4 TSE系统结构 34

第二节 网页搜集 34

图3-5 Web信息的搜集 35

一、定义URL类和Page类 35

二、与服务器建立连接 39

图3-7 通过Socket建立连接 40

图3-6 Sockets和端口 40

三、发送请求和接收数据 41

四、网页信息存储的天网格式 42

第三节 多道搜集程序并行工作 45

一、多线程并发工作 46

一、记录未访问、已访问URL和网页内容摘要信息 47

第四节 如何避免网页的重复搜集 47

二、控制对一个站点并发搜集线程的数目 47

二、域名与IP的对应问题 48

第五节 如何首先搜集重要的网页 49

图3-8 Web像个海洋 51

第六节 搜集信息的类型 52

第七节 本章小结 53

图4-1 网页预处理系统结构 55

第四章 对搜集信息的预处理 55

第一节 信息预处理的系统结构 55

图4-2 原始网页库中的记录格式 56

第二节 索引网页库 56

图4-3 索引网页库算法 57

表4-1 网页索引文件 58

表4-2 URL索引文件 58

第三节 中文自动分词 58

图4-4 正向减字最大匹配算法流程 61

图4-5 切词算法流程 62

第四节 分析网页和建立倒排文件 63

图4-6 分析网页与建立倒排文件流程 63

图4-7 过滤网页中非正文信息算法 64

图4-8 正向索引表记录格式 64

图4-9 由正向索引建立反向索引 65

第五节 本章小结 65

第一节 查询服务的系统结构 66

图5-1 信息查询的系统结构 66

第二节 检索的定义 66

第五章 信息查询服务 66

一、结果集合的形成 67

图5-2 基本检索算法 67

第三节 查询服务的实现 67

二、查询结果显示 68

图5-3 动态摘要算法 69

图5-4 用户查询日志的记录格式 69

第四节 本章小结 70

第六章 可扩展搜集子系统 73

第一节 天网系统概述和集中式搜集系统结构 73

一、天网系统结构 73

中篇 对质量和性能的追求 73

二、集中式搜集系统 74

图6-1 天网系统概貌 74

图6-2 搜集系统的主控结构 75

表6-1 SOIF数据描述 76

表6-2 SOIF具体语法 78

第二节 利用并行处理技术高效搜集网页的一种方案 80

一、节点间URL的划分策略 81

图6-3 协调进程工作算法 82

图6-4 分布式Web搜集系统结构 83

二、关于性能的讨论 84

三、性能测试和评价 85

表6-3 参照序列，假设节点数为2 85

图6-5 负载方差 86

图6-7 分布式系统效率 87

图6-6 n个节点并行搜集系统及集中式系统性能随时间的变化 87

四、系统的动态可配置性设计 88

图6-8 URL两阶段映射 89

第三节 本章小结 90

一、引言 92

第一节 网页净化与元数据提取 92

第七章 网页净化与消重 92

二、DocView模型 95

三、网页的表示 96

图7-1 用DocView模型提取的网页要素 96

图7-2 净化后的网页 96

图7-3 HTML Tree结构 98

图7-4 内容块权值传递过程 99

四、提取DocView模型要素的方法 100

图7-5 有主题网页DocView模型生成过程 101

图7-6 计算网页特征项权值的算法 102

图7-7 正文段落识别过程 103

图7-8 基于anchor text的超链选取算法 104

五、模型应用及实验研究 105

图7-9 网页净化前后分类效果对比 106

表7-1 类别编号对照表 106

表7-2 消重实验结果 108

第二节 网页消重算法 108

一、消重算法 109

二、算法评测 111

表7-3 当N＝10、δ＝0.01时5种算法的查全率和准确率 112

表7-4 考察δ的取值对算法3和4的影响 113

图7-10 查全率随选取关键词个数的变化 113

表7-6 基于关键词的各算法的时间复杂度及性能（N＝10，δ＝0.01） 114

表7-5 分段签名算法的时间复杂度及性能 114

第八章 高性能检索子系统 115

第一节 检索系统基本技术 116

一、系统设计与结构 116

图8-1 检索系统集成框架结构 117

图8-2 天网WWW分布式检索系统构架 118

二、索引创建 119

三、检索过程 120

一、引言 122

第二节 倒排文件性能模型 122

二、倒排文件的概念 123

图8-3 倒排文件结构示意图 125

三、倒排文件的一种性能模型 125

表8-1 英汉词频统计排序对照 128

图8-4 英语单词和汉语字符的ITF分布 129

表8-2 一些典型磁盘的性能数据 130

四、结合计算机性能指标的考虑 130

第三节 混合索引技术 131

一、引言 131

二、混合索引原理 132

三、混合索引实现 134

一、引言 136

第四节 倒排文件缓存机制 136

图8-5 扩展词典树结构示例 136

图8-6 扩展词典匹配查找算法 136

二、倒排文件缓存 137

图8-7 搜索引擎检索系统缓存结构 138

三、负载特性 139

表8-3 数据集基本统计信息 139

图8-8 文档数据访问对象大小分布 140

图8-9 I/O与PAGE序列序号-频度分布 140

四、缓存策略的选择 141

图8-10 I/O与PAGE序列时间间隔分布 141

图8-11 I/O和PAGE序列中唯一模式串 141

第五节 本章小结 142

第九章 用户行为的特征及缓存的应用 143

第一节 用户查询与点击日志 144

一、用户查询词的分布情况 145

第二节 用户行为特征的统计分析 145

图9-1 查询词的分布情况 146

图9-2 查询词分布函数及其拟合函数 147

二、雷同查询词的衰减统计 147

图9-3 雷同查询词的衰减 148

三、相邻N项查询词的偏差分析 148

图9-4 相邻1000项查询词的频率的差的平方和 149

表9-1 用户在前5页的翻页情况统计 149

四、用户在输出结果中的翻页情况统计 149

图9-6 用户点击URL的分布情况 150

五、用户点击URL的分布情况 150

图9-5 用户翻页情况统计 150

六、考虑与不考虑查询项时点击URL分布的对比分析 151

图9-7 考虑查询项与否的URL分布情况 151

七、查询过程的自相似性 152

图9-10 相邻2000项中不同查询项的分布 153

图9-9 相邻1000项中不同查询项的分布 153

图9-8 相邻500项中不同查询项的分布 153

第三节 查询缓存的使用 154

一、基于用户行为的启示 154

图9-11 查询项分布的自相似性特征 154

图9-12 FIFO、LRU和带衰减的LFU的Cache命中率比较 156

二、缓存替换策略研究 156

表9-2 调整后的LFU与LRU命中率的比较 157

一、基本术语 157

第四节 用户行为与Web信息的分布特征 157

图9-13 3种替换策略的局部比较 157

二、海量Web信息的特征分析 158

图9-16 用户点击URL对应网页的镜像度 159

图9-15 用户点击URL对应网页的入度 159

图9-14 网页的被访问次数 159

表9-3 各网页参数的分布 160

图9-17 用户点击URL对应网页的目录深度 160

图9-18 站内网页的树状结构 161

第一节 传统IR的相关排序技术 163

第十章 相关排序与系统质量评估 163

一、链接分析 165

第二节 链接分析与相关排序 165

二、Web查询模式下的新信息 168

图10-1 Inktomi提供的几种搜索引擎技术的比较 169

图10-2 词典在系统中的地位 169

图10-3 新词学习 171

表10-1 新词学习对检索准确率的影响 171

第三节 相关排序的一种实现方案 172

一、形成网页中词项的基本权重 172

表10-2 影响权值的HTML标签 173

图10-4 网页的互联结构示意 174

二、利用链接的结构 174

三、收集用户反馈信息 175

表10-3 补偿因子定义表 176

四、计算最终的权重 178

第四节 搜索引擎系统质量评估 179

一、引言 179

二、查询类别分析与查询集的构建 180

表10-4 用户查询信息类别 181

三、评估实验的建立与分析 181

下篇 面向主题和个性化的Web信息服务 187

第十一章 中文网页自动分类技术 187

第一节 引言 187

第二节 文档自动分类算法的类型 187

第三节 实现中文网页自动分类的一般过程 189

图11-1 自动文档分类算法的分类 189

图11-3 中文网页分类器的工作原理图 190

图11-2 中文网页自动分类的一般过程 190

一、实验设置 191

第四节 影响分类器性能的关键因素分析 191

二、训练样本 192

表11-1 样本集中类别及实例数量的分布情况表 193

图11-4 WebSmart——一个网页实例集搜集和整理工具 194

图11-6 Macro-F1值随样本数的变化 195

图11-5 一种中文网页的分类体系 195

图11-7 Micro-F1值随样本数的变化 196

三、特征选取 196

图11-8 CHI、IG、DF、MI的比较（Macro-F1） 199

图11-9 CHI、IG、DF、MI的比较（Micro-F1） 199

四、分类算法 199

表11-2 kNN和NB算法的分类质量和分类效率比较 202

图11-10 kNN与NB分类结果的比较 202

图11-11 k的取值对分类器质量的影响（Marco-F1） 203

图11-12 k的取值对分类器质量的影响（Micro-F1） 203

表11-3 欧式距离与兰式距离的比较 204

图11-13 兰式距离法与欧式距离法对12个不同类别的分类情况 204

五、截尾算法 205

表11-4 基于层次模型的kNN与基本kNN的比较 205

图11-14 基于层次模型的kNN与基本kNN的比较 205

表11-5 RCut和SCut截尾算法的比较 206

六、一个中文网页分类器的设计方案 207

表11-6 一个分类器的设计方案 207

图11-15 RCut和SCut截尾算法的比较 207

第五节 天网目录导航服务 208

一、问题的提出 208

二、天网目录导航服务的体系结构 208

三、天网目录的运行实例 209

图11-16 天网目录的体系结构 209

图11-17 天网目录导航服务 210

第六节 本章小结 210

第十二章 搜索引擎个性化查询服务 212

第一节 基于Web挖掘的个性化技术 212

图12-1 Web个性化的实质 212

图12-2 Web挖掘的分类 213

一、Web挖掘技术 213

表12-1 典型Web个性化系统的比较 214

二、典型个性化Web服务系统的比较 214

三、基于Web挖掘的个性化技术的发展 215

第二节 天网知名度系统 216

一、系统结构 216

图12-4 个性化知名度示意图 217

图12-3 网页与实体相关度的建立 217

图12-5 “天网知名度”系统结构 218

二、网页与命名实体的相关度评价 219

表12-2 天网知名度系统与其他检索系统的横向比较结果 220

表12-3 天网知名度系统的纵向比较结果 221

第一节 主题信息的搜集 223

第十三章 面向主题的信息搜集与应用 223

一、主题信息分布的局部性 223

图13-1 页面对的平均相关性 224

二、一种主题信息搜集系统 224

图13-2 Foused Crawler的系统结构 225

一、模型设计 226

第二节 主题信息的一种搜集与处理模型及其应用 226

图13-3 用于表达网上主题新闻强度指标的立方体 228

二、应用实验：以“十六大”为主题 230

图13-4 十六大网页数量在10月22日～11月24日期间的变化情况 231

三、总结与讨论 232

参考文献 233

附录 术语 240

后记 246