信息检索 实现和评价搜索引擎PDF电子书下载

第一部分 基础知识 1

第1章 绪论 1

1.1什么是信息检索 1

1.1.1 Web搜索 1

1.1.2其他搜索应用 2

1.1.3其他信息检索应用 2

1.2信息检索系统 3

1.2.1信息检索系统基础架构 3

1.2.2文档及其更新 5

1.2.3性能评价 5

1.3使用电子文本 6

1.3.1文本格式 6

1.3.2英文文本中的分词 9

1.3.3词项分布 10

1.3.4语言模型 11

1.4测试集 16

1.5开源信息检索系统 18

1.5.1 Lucene 19

1.5.2 Indri 19

1.5.3 Wumpus 19

1.6延伸阅读 20

1.7练习 21

1.8参考文献 22

第2章 基础技术 23

2.1倒排索引 23

2.1.1延伸例子：词组查找 24

2.1.2实现倒排索引 27

2.1.3文档和其他元素 31

2.2检索与排名 36

2.2.1向量空间模型 38

2.2.2邻近度排名 42

2.2.3布尔检索 44

2.3评价 46

2.3.1查全率和查准率 46

2.3.2排名检索的有效性指标 47

2.3.3创建测试集 51

2.3.4效率指标 52

2.4总结 53

2.5延伸阅读 54

2.6练习 55

2.7参考文献 56

第3章 词条与词项 58

3.1英语 58

3.1.1标点与大写 59

3.1.2词干提取 60

3.1.3停词 62

3.2字符 63

3.3字符n-gram 64

3.4欧洲语言 65

3.5 CJK语言 66

3.6延伸阅读 67

3.7练习 68

3.8参考文献 69

第二部分 索引 71

第4章 静态倒排索引 71

4.1索引的组成部分和索引的生命周期 71

4.2词典 72

4.3位置信息列表 75

4.4交错词典和位置信息列表 78

4.5索引的构建 81

4.5.1基于内存的索引构建法 82

4.5.2基于排序的索引构建法 85

4.5.3基于合并的索引构建法 87

4.6其他索引 90

4.7总结 90

4.8延伸阅读 91

4.9练习 91

4.10参考文献 92

第5章 查询处理 94

5.1排名检索的查询处理 94

5.1.1 document-at-a-time查询处理 95

5.1.2 term-at-a-time查询处理 99

5.1.3预计算得分贡献 103

5.1.4影响力排序 104

5.1.5静态索引裁剪 105

5.2轻量级结构 109

5.2.1广义索引表 110

5.2.2操作符 111

5.2.3例子 112

5.2.4实现 113

5.3延伸阅读 115

5.4练习 116

5.5参考文献 117

第6章 索引压缩 119

6.1通用数据压缩 119

6.2符号数据压缩 120

6.2.1建模和编码 121

6.2.2哈夫曼编码 123

6.2.3算术编码 126

6.2.4基于符号的文本压缩 129

6.3压缩位置信息列表 130

6.3.1无参数间距压缩 131

6.3.2参数间距压缩 133

6.3.3上下文感知的压缩方法 137

6.3.4高查询性能的索引压缩 139

6.3.5压缩效果 142

6.3.6解码性能 145

6.3.7文档重排 146

6.4压缩词典 147

6.5总结 151

6.6延伸阅读 152

6.7练习 152

6.8参考文献 153

第7章 动态倒排索引 155

7.1批量更新 155

7.2增量式索引更新 157

7.2.1连续倒排列表 158

7.2.2非连续倒排列表 163

7.3文档删除 165

7.3.1无效列表 165

7.3.2垃圾回收 166

7.4文档修改 170

7.5讨论及延伸阅读 171

7.6练习 172

7.7参考文献 172

第三部分 检索和排名 174

第8章 概率检索 174

8.1相关性建模 174

8.2二元独立模型 176

8.3 Robertson/Sparck Jones权重公式 177

8.4词频 179

8.4.1 Bookstein的双泊松模型 180

8.4.2双泊松模型的近似 182

8.4.3查询词频 183

8.5文档长度：BM25 183

8.6相关反馈 184

8.6.1词项选择 185

8.6.2伪相关反馈 186

8.7区域权重：BM25F 187

8.8实验对比 189

8.9延伸阅读 189

8.10练习 190

8.11参考文献 191

第9章 语言模型及其相关方法 194

9.1从文档中产生查询 194

9.2语言模型和平滑 196

9.3使用语言模型排名 198

9.4 Kullback-Leibler距离 200

9.5随机差异性 202

9.5.1一个随机模型 203

9.5.2精华性 204

9.5.3文档长度规范化 204

9.6段落检索及排名 205

9.6.1段落评分 206

9.6.2实现 206

9.7实验对比 207

9.8延伸阅读 207

9.9练习 208

9.10参考文献 208

第10章 分类和过滤 210

10.1详细示例 212

10.1.1面向主题的批过滤 212

10.1.2在线过滤 215

10.1.3从历史样本中学习 216

10.1.4语言分类 217

10.1.5在线自适应垃圾邮件过滤系统 220

10.1.6二元分类的阈值选择 223

10.2分类 225

10.2.1比值和比值比 226

10.2.2构造分类器 228

10.2.3学习模型 229

10.2.4特征工程 230

10.3概率分类器 231

10.3.1概率估计 231

10.3.2联合概率估计 235

10.3.3实际考虑 237

10.4线性分类器 239

10.4.1感知器算法 241

10.4.2支持向量机 241

10.5基于相似度的分类器 242

10.5.1 Rocchio法 242

10.5.2基于记忆的方法 243

10.6广义线性模型 243

10.7信息理论模型 246

10.7.1模型比较 246

10.7.2序列压缩模型 247

10.7.3决策树与树桩 249

10.8实验对比 251

10.8.1面向主题的在线过滤器 251

10.8.2在线自适应垃圾信息过滤 253

10.9延伸阅读 254

10.10练习 255

10.11参考文献 256

第11章 融合和元学习 258

11.1搜索结果融合 259

11.1.1固定临界值合成 260

11.1.2排名和得分合成 261

11.2叠加自适应过滤器 262

11.3叠加批分类器 263

11.3.1 holdout验证 264

11.3.2交叉验证 264

11.4 bagging 265

11.5 boosting 266

11.6多类排名和分类 267

11.6.1文档得分与类别得分 267

11.6.2文档排名融合与类别排名融合 268

11.6.3多类方法 269

11.7学习排名 272

11.7.1什么是学习排名 272

11.7.2学习排名的方法 273

11.7.3优化什么 273

11.7.4分类的学习排名 274

11.7.5排名检索的学习 274

11.7.6 LETOR数据集 275

11.8延伸阅读 276

11.9练习 277

11.10参考文献 277

第四部分 评价 279

第12章度量有效性 279

12.1传统的有效性指标 279

12.1.1查全率和查准率 280

12.1.2前k个文档的查准率（P@k） 280

12.1.3平均查准率 281

12.1.4排名倒数 281

12.1.5算术平均与几何平均 281

12.1.6用户满意度 282

12.2 TREC 282

12.3在评价中使用统计 283

12.3.1基础和术语 284

12.3.2置信区间 286

12.3.3比较评价 292

12.3.4被认为有害的假设检验 294

12.3.5配对和未配对差值 295

12.3.6显著性检验 296

12.3.7统计检验的效度和检验力 299

12.3.8报告指标的查准率 302

12.3.9元分析 303

12.4最小化判定工作 304

12.4.1为判定选择合适的文档 305

12.4.2对池进行抽样 309

12.5非传统的有效性指标 311

12.5.1分级相关性 311

12.5.2不完整判定和偏差判定 313

12.5.3新颖性和多样性 314

12.6延伸阅读 318

12.7练习 319

12.8参考文献 320

第13章 度量效率 324

13.1效率标准 324

13.1.1吞吐量和延迟 325

13.1.2汇总统计和用户满意度 327

13.2排队论 327

13.2.1肯德尔符号 328

13.2.2M/M/1排队模型 329

13.2.3延迟量和平均利用率 330

13.3查询调度 331

13.4缓存 332

13.4.1三级缓存 332

13.4.2缓存策略 334

13.4.3预取搜索结果 335

13.5延伸阅读 335

13.6练习 335

13.7参考文献 336

第五部分 应用和扩展 338

第14章 并行信息检索 338

14.1并行查询处理 338

14.1.1文档划分 339

14.1.2词项划分 341

14.1.3混合方案 343

14.1.4 冗余和容错 343

14.2 MapReduce 345

14.2.1基本框架 345

14.2.2合并 347

14.2.3辅助关键字 347

14.2.4机器失效 347

14.3延伸阅读 348

14.4练习 349

14.5参考文献 349

第15章 Web搜索 351

15.1 Web的结构 351

15.1.1 Web图 352

15.1.2静态与动态网页 353

15.1.3暗网 353

15.1.4 Web的规模 354

15.2查询与用户 355

15.2.1用户意图 355

15.2.2点击曲线 357

15.3静态排名 357

15.3.1基本PageRank 358

15.3.2扩展的PageRank 362

15.3.3 PageRank的性质 366

15.3.4其他链接分析方法：HITS和SALSA 369

15.3.5其他静态排名方法 371

15.4动态排名 371

15.4.1锚文本 372

15.4.2新颖性 373

15.5评价Web搜索 373

15.5.1指定页面发现 374

15.5.2用户隐式反馈 375

15.6 Web爬虫 376

15.6.1爬虫的组成 377

15.6.2抓取顺序 380

15.6.3重复与近似重复 381

15.7总结 383

15.8延伸阅读 384

15.8.1链接分析 384

15.8.2锚文本 385

15.8.3隐式反馈 386

15.8.4 Web爬虫 386

15.9练习 386

15.10参考文献 387

第16章 XML检索 392

16.1 XML的本质 393

16.1.1文档类型定义 395

16.1.2 XML模式 396

16.2路径、树和FLWOR 396

16.2.1 XPath 396

16.2.2 NEXI 397

16.2.3 XQuery 398

16.3索引和查询处理 399

16.4排名检索 401

16.4.1排名元素 402

16.4.2重叠元素 403

16.4.3可检索元素 404

16.5评价 404

16.5.1测试集 404

16.5.2有效性指标 405

16.6延伸阅读 405

16.7练习 407

16.8参考文献 407

第六部分 附录 410

附录A 计算机性能 410