基本信息

内容简介

目录

译者序

前言

序言

基本信息

作者： (美)Stefan Büttcher (加)Charles L.A.Clarke (加)Gordon V.Cormack

译者： 陈健 黄晋

丛书名： 计算机科学丛书出版社：机械工业出版社

ISBN：9787111359906

上架时间：2011-12-16

出版日期：2012 年1月

开本：16开

页码：1

版次：1-1

所属分类： 计算机

内容简介

《信息检索：实现和评价搜索引擎》从多个视角对信息检索技术进行了深入讲解，内容涵盖了信息检索系统的架构、基础技术、词条和词项、静态和动态倒排索引、查询处理、索引压缩技术、概率模型、语言模型、分类和过滤、融合和元学习、评价方法以及并行信息检索、web检索和xml检索等具体应用。本书以模块化的方式进行组织，理论性强，体系完整，同时强调实践。作者以认真严谨的态度实现了书中绝大部分的主要方法，并详尽地描述了各种方法的适用环境以及取得的效果。

《信息检索：实现和评价搜索引擎》可作为高等院校信息管理与信息系统、计算机科学与技术、情报学、图书馆学以及电子商务等专业的高年级本科生和研究生的教材和参考书，对于从事信息检索与网络分析等实际工作的从业人员也具有较高的参考价值。

目录

《信息检索：实现和评价搜索引擎》

information retrieval: implementing and evaluating search engines

出版者的话

译者序

序

前言

符号

第一部分基 础 知 识

第1章绪论

1.1什么是信息检索

1.1.1web搜索

1.1.2其他搜索应用

1.1.3其他信息检索应用

1.2信息检索系统

1.2.1信息检索系统基础架构

1.2.2文档及其更新

1.2.3性能评价

1.3使用电子文本

1.3.1文本格式

1.3.2英文文本中的分词

.1.3.3词项分布

1.3.4语言模型

1.4测试集

1.5开源信息检索系统

1.5.1lucene

1.5.2indri

1.5.3wumpus

1.6延伸阅读

1.7练习

1.8参考文献

第2章基础技术

2.1倒排索引

2.1.1延伸例子：词组查找

2.1.2实现倒排索引

2.1.3文档和其他元素

2.2检索与排名

2.2.1向量空间模型

2.2.2邻近度排名

2.2.3布尔检索

2.3评价

2.3.1查全率和查准率

2.3.2排名检索的有效性指标

2.3.3创建测试集

2.3.4效率指标

2.4总结

2.5延伸阅读

2.6练习

2.7参考文献

第3章词条与词项

3.1英语

3.1.1标点与大写

3.1.2词干提取

3.1.3停词

3.2字符

3.3字符n?gram

3.4欧洲语言

3.5cjk语言

3.6延伸阅读

3.7练习

3.8参考文献

第二部分索引

第4章静态倒排索引

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

4.2词典

4.3位置信息列表

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

4.5索引的构建

4.5.1基于内存的索引构建法

4.5.2基于排序的索引构建法

4.5.3基于合并的索引构建法

4.6其他索引

4.7总结

4.8延伸阅读

4.9练习

4.10参考文献

第5章查询处理

5.1排名检索的查询处理

5.1.1document?at?a?time查询处理

5.1.2term?at?a?time查询处理

5.1.3预计算得分贡献

5.1.4影响力排序

5.1.5静态索引裁剪

5.2轻量级结构

5.2.1广义索引表

5.2.2操作符

5.2.3例子

5.2.4实现

5.3延伸阅读

5.4练习

5.5参考文献

第6章索引压缩

6.1通用数据压缩

6.2符号数据压缩

6.2.1建模和编码

6.2.2哈夫曼编码

6.2.3算术编码

6.2.4基于符号的文本压缩

6.3压缩位置信息列表

6.3.1无参数间距压缩

6.3.2参数间距压缩

6.3.3上下文感知的压缩方法

6.3.4高查询性能的索引压缩

6.3.5压缩效果

6.3.6解码性能

6.3.7文档重排

6.4压缩词典

6.5总结

6.6延伸阅读

6.7练习

6.8参考文献

第7章动态倒排索引

7.1批量更新

7.2增量式索引更新

7.2.1连续倒排列表

7.2.2非连续倒排列表

7.3文档删除

7.3.1无效列表

7.3.2垃圾回收

7.4文档修改

7.5讨论及延伸阅读

7.6练习

7.7参考文献

第三部分检索和排名

第8章概率检索

8.1相关性建模

8.2二元独立模型

8.3robertson/sp?rck jones权重公式

8.4词频

8.4.1bookstein的双泊松模型

8.4.2双泊松模型的近似

8.4.3查询词频

8.5文档长度：bm25

8.6相关反馈

8.6.1词项选择

8.6.2伪相关反馈

8.7区域权重：bm25f

8.8实验对比

8.9延伸阅读

8.10练习

8.11参考文献

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

9.1从文档中产生查询

9.2语言模型和平滑

9.3使用语言模型排名

9.4kullback?leibler距离

9.5随机差异性

9.5.1一个随机模型

9.5.2精华性

9.5.3文档长度规范化

9.6段落检索及排名

9.6.1段落评分

9.6.2实现

9.7实验对比

9.8延伸阅读

9.9练习

9.10参考文献

第10章分类和过滤

10.1详细示例

10.1.1面向主题的批过滤

10.1.2在线过滤

10.1.3从历史样本中学习

10.1.4语言分类

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

10.1.6二元分类的阈值选择

10.2分类

10.2.1比值和比值比

10.2.2构造分类器

10.2.3学习模型

10.2.4特征工程

10.3概率分类器

10.3.1概率估计

10.3.2联合概率估计

10.3.3实际考虑

10.4线性分类器

10.4.1感知器算法

10.4.2支持向量机

10.5基于相似度的分类器

10.5.1rocchio法

10.5.2基于记忆的方法

10.6广义线性模型

10.7信息理论模型

10.7.1模型比较

10.7.2序列压缩模型

10.7.3决策树与树桩

10.8实验对比

10.8.1面向主题的在线过滤器

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

10.9延伸阅读

10.10练习

10.11参考文献

第11章融合和元学习

11.1搜索结果融合

11.1.1固定临界值合成

11.1.2排名和得分合成

11.2叠加自适应过滤器

11.3叠加批分类器

11.3.1holdout验证

11.3.2交叉验证

11.4bagging

11.5boosting

11.6多类排名和分类

11.6.1文档得分与类别得分

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

11.6.3多类方法

11.7学习排名

11.7.1什么是学习排名

11.7.2学习排名的方法

11.7.3优化什么

11.7.4分类的学习排名

11.7.5排名检索的学习

11.7.6letor数据集

11.8延伸阅读

11.9练习

11.10参考文献

第四部分评价

第12章度量有效性

12.1传统的有效性指标

12.1.1查全率和查准率

12.1.2前k个文档的查准率

12.1.3平均查准率

12.1.4排名倒数

12.1.5算术平均与几何平均

12.1.6用户满意度

12.2trec

12.3在评价中使用统计

12.3.1基础和术语

12.3.2置信区间

12.3.3比较评价

12.3.4被认为有害的假设检验

12.3.5配对和未配对差值

12.3.6显著性检验

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

12.3.8报告指标的查准率

12.3.9元分析

12.4最小化判定工作

12.4.1为判定选择合适的文档

12.4.2对池进行抽样

12.5非传统的有效性指标

12.5.1分级相关性

12.5.2不完整判定和偏差判定

12.5.3新颖性和多样性

12.6延伸阅读

12.7练习

12.8参考文献

第13章度量效率

13.1效率标准

13.1.1吞吐量和延迟

13.1.2汇总统计和用户满意度

13.2排队论

13.2.1肯德尔符号

13.2.2m/m/1排队模型

13.2.3延迟量和平均利用率

13.3查询调度

13.4缓存

13.4.1三级缓存

13.4.2缓存策略

13.4.3预取搜索结果

13.5延伸阅读

13.6练习

13.7参考文献

第五部分应用和扩展

第14章并行信息检索

14.1并行查询处理

14.1.1文档划分

14.1.2词项划分

14.1.3混合方案

14.1.4冗余和容错

14.2mapreduce

14.2.1基本框架

14.2.2合并

14.2.3辅助关键字

14.2.4机器失效

14.3延伸阅读

14.4练习

14.5参考文献

第15章web搜索

15.1web的结构

15.1.1web图

15.1.2静态与动态网页

15.1.3暗网

15.1.4web的规模

15.2查询与用户

15.2.1用户意图

15.2.2点击曲线

15.3静态排名

15.3.1基本pagerank

15.3.2扩展的pagerank

15.3.3pagerank的性质

15.3.4其他链接分析方法：hits和salsa

15.3.5其他静态排名方法

15.4动态排名

15.4.1锚文本

15.4.2新颖性

15.5评价web搜索

15.5.1指定页面发现

15.5.2用户隐式反馈

15.6web爬虫

15.6.1爬虫的组成

15.6.2抓取顺序

15.6.3重复与近似重复

15.7总结

15.8延伸阅读

15.8.1链接分析

15.8.2锚文本

15.8.3隐式反馈

15.8.4web爬虫

15.9练习

15.10参考文献

第16章xml检索

16.1xml的本质

16.1.1文档类型定义

16.1.2xml模式

16.2路径、树和flwor

16.2.1xpath

16.2.2nexi

16.2.3xquery

16.3索引和查询处理

16.4排名检索

16.4.1排名元素

16.4.2重叠元素

16.4.3可检索元素

16.5评价

16.5.1测试集

16.5.2有效性指标

16.6延伸阅读

16.7练习

16.8参考文献

第六部分附录

附录a计算机性能

译者序

Information Retrieval: Implementing and Evaluating Search Engines

由于手机、个人电脑、互联网等信息工具的快速发展和进化，个人可获取和管理的信息量呈爆发式增长，如何快速准确地找到所需的信息成为信息处理中的一个难题。信息检索技术是解决该问题的主要方法，其最初来源于图书内容的索引和检索，近些年来由于互联网的发展，以此为基础的搜索引擎技术使其受到了广泛的关注和研究。国内无论是高等院校相关专业方向的研究生，还是对搜索技术感兴趣的研究者和开发人员，都迫切需要一本全面专业的信息检索书籍。

国内引进了多本信息检索领域的书籍，本书是其中较新较有特色的一本。它以模块化的方式进行组织，从多个视角对信息检索技术进行了深入的解析，并补充了相关学科的基本知识，例如通用的符号数据压缩技术、统计分析、机器学习、数据库、Web结构、XML等等，使读者免去了查阅大量资料和其他书籍的麻烦。这本书理论性强，体系完整，同时也很强调实践。作者以认真严谨的态度对书中绝大部分的主要方法给出了实现细节和分析，并通过实验对比了这些方法，详尽地描述了各种方法的适用环境以及取得的效果，为信息检索在具体环境下的应用提供了很好的参考。在每一章最后的延伸阅读和参考文献部分，读者还可以了解到该章相关知识点的研究历史、发展和目前最新状况，也可据此对相关内容进行更深入的了解和研究。课后练习也经过了精心的设计，各章习题彼此关联、循序渐进，能够帮助读者更好地理解各章的知识点。

感谢原著作者无私地分享了他们在信息检索领域内的独特见解和研究成果。在过去几个月中，胡清兰、吴灿荣、李仕钊、黄锦捷、李蕾、黄蕉平、黄琎都参与了部分翻译、审校工作。感谢徐亚波老师及其学生给出的宝贵意见。当然，本书的翻译工作得以顺利完成，还要感谢机械工业出版社的王春华编辑和其他所有工作人员在各方面的支持和帮助。最后，对于给予我们无私帮助的那些人致以诚挚的谢意。

由于译者水平有限，书中疏漏在所难免，敬请读者批评指正。

陈健、黄晋

2011年6月29日

前言

Information Retrieval: Implementing and Evaluating Search Engines

信息检索奠定了现代搜索引擎的基石。在这本教材中，我们针对计算机科学、计算机工程和软件工程的研究生以及专业人员介绍了信息检索。选择的主题引起了大部分读者的兴趣，涵盖了算法、数据结构、索引、检索和评价的核心主题，为读者今后的学习提供广博的基础。同时考虑Web搜索引擎、并行系统和XML检索在已有和新的应用场景的特性。

我们的目的是在理论与实践之间取得平衡，稍微偏向于实践，强调实现和实验。只要有可能，本书中的方法都通过实验进行了对比和验证。每一章都包含了练习和学生项目。本书其中一位作者开发的一个多用户开源信息检索系统Wumpus，提供了模型实现，可作为学生练习的基础。可以通过

获取Wumpus。

本书组织

本书以模块化结构组织，可分为5个部分。第一部分提供了介绍性的材料。第二至第四部分，每部分专注于一个重要主题领域：索引、检索和评价。阅读完第一部分后，第二至第四部分都可以分别单独阅读。第五部分主要基于前面部分的内容来介绍具体的应用领域。

第一部分涵盖了信息检索的基础知识。第1章讨论基本概念，包括信息检索系统的架构、术语、文本特征、文档格式、词项分布、语言模型和测试集。第2章介绍3个重要主题（索引、检索和评价）的基础。这3个主题稍后在各自所属的部分（第二至第四部分）有详细介绍。这一章也为读者可以独立阅读每个主题或多或少地提供了基础。第一部分的最后一章，即第3章，继续介绍了在第1章中引入、在第2章中结束的部分主题。它涉及的问题与具体的自然（即人类）语言相关，特别是分词（tokenization）——为了进行索引和检索而将一个文档转化成一个词项序列的过程。一个信息检索系统必须能够处理由多种自然语言混合的文档，而这一章就是从这方面讨论几种主要语言的重要特性。

第二部分主要讨论倒排索引的创建、访问和维护。第4章讨论建立和访问静态（static）索引的算法，这种索引适用于不常变动的文档集，即当文档发生变动时，有足够的时间来重新从头建立索引。第5章讨论索引访问和查询过程，这一章介绍一种轻量级的方法来处理文档结构，并使用这种方法来支持布尔约束。第6章介绍索引压缩。第7章提出用于维护动态（dynamic）文档集的算法，也就是文档的更新相对于查询次数是频繁的，同时要求更新必须迅速。

第三部分介绍了检索方法和算法。第8章和第9章介绍并比较两种基于文档内容的重要排名检索方法：概率模型和语言模型。通过使用文档结构、反馈和查询扩展，可考虑利用一些显式的相关信息来提高这些方法的有效性。我们讨论了每种方法的细节。第10章介绍用于文档分类和过滤的技术，包括用于分类的基本的机器学习算法。第11章介绍将证据和参数调整进行整合的技术，以及元学习算法及其在排名中的应用。

信息检索评价是第四部分的主题，用独立的章节分别介绍了有效性和效率。第12章给出了基本的有效性度量指标，探讨了用于评价有效性的统计基础，并讨论了一些在最近10年里提出的度量指标，它们已经超出了传统信息检索评价方法的范围。第13章介绍了从响应时间和吞吐量来评价信息检索系统性能的方法。

第五部分是全书的最后一部分，内容涉及一些具体的应用领域，借用并扩展了来自前四个部分的一些基本内容。第14章介绍了并行搜索引擎的架构和操作。第15章讨论了关于Web搜索引擎的一些主题，包括链接分析、抓取和重复检查。第16章介绍了XML文档集上的信息检索。

书中的每一章都包含了一个小节为深入阅读提供了参考文献，还提供了一组练习题。练习题一般偏向于考查和扩展相应章节介绍的概念。有些练习只需用铅笔和纸花上几分钟就能做好；有些则是需要大量编程的项目。这些参考文献和练习题同时也为我们提供了机会来学习一些在该章的正文部分没有涵盖的重要概念和主题。

下面的示意图展示了本书的各章和各部分之间的关系。箭头表示各章之间的依赖关系。本书的组织使得读者可以关注主题的不同方面。从数据库系统实现的观点来教授的课程可以包括第1~2、4~7和13~14章。专注于理论的传统信息检索课程可以包括第1~3、8~12和16章。关于Web检索基础的课程可以包括第1~2、4~5、8和13~15章。每一种涵盖的章节数约占全书的1/2~2/3，可以在一个3~4个月的研究生课程中完成。

本书的组织。各章之间的箭头表示它们之间的依赖关系

背景

我们假设读者拥有计算机科学、计算机工程、软件工程或相关学科的本科相当的基本背景知识，包括：（1）基本数据结构的概念，例如链表数据结构、B?树和哈希函数；（2）算法和时间复杂度分析；（3）操作系统、磁盘设备、内存管理和文件系统。另外，我们假设一些读者熟悉初等概率论和统计学，包括如随机变量、分布和概率群分布函数等概念。

致谢

我们的很多同事花费了大量的时间帮助我们审阅了与其专业领域相关的章节的草稿。我们在这里特别感谢Eugene Agichtein，Alina Alt，Lauren Griffith，Don Metzler，Tor Myklebust，Fabrizio Silvestri，Mark Smucker，Torsten Suel，Andrew Trotman，Olga Vechtomova，William Webber和Justin Zobel为我们提出了很多宝贵的意见。同时感谢匿名审稿人为我们提供了积极的意见和反馈。

有几个班的研究生起草了早期的一些材料。我们感谢他们的耐心和忍耐。4个学生——Mohamad Hasan Ahmadi，John Akinyemi，Chandra Prakash Jethani和Andrew Kane——非常严谨地审阅了草稿，帮助我们找出和解决了很多问题。另外3个学生——Azin Ashkan，Maheedhar Kolla和Ian Mackinnon——志愿帮助我们在2007年秋季学期进行了一次课内评价，对第一部分中的很多练习有很大的贡献。Jack Wang校对了第3章中关于CJK语言的材料。Kelly Itakura提供了日文输入。

Web站点

.

序言

Information Retrieval: Implementing and Evaluating Search Engines

学术巨匠齐聚一堂编撰了一部信息检索的优秀教材。Stefan Büttcher、Charles Clarke和Gordon Cormack以合计超过五十年的研究经验，组成了横跨三代的信息检索研究泰斗组合。Büttcher是Clarke的博士生，而Clarke是Cormack的博士生。他们三人都以对信息检索的深入洞察和建立实用搜索系统的热情而闻名，这种组合在一个充满世界级的研究专家的领域中是很少见的。

本书涵盖了搜索引擎的各个重要组成部分，从爬虫到索引到查询过程。大部分章节用于介绍索引、检索方法和评价的核心主题。重点放在实现和实验上，以让读者了解到信息检索系统的底层细节，包括索引压缩和索引更新策略，同时让读者理解在实际中哪一种方法效果更好。关于评价的两章提供了评价搜索引擎的方法论和统计学基础，使得读者能够知道：例如改变搜索引擎的排名公式是否对检索结果的质量有一个正面的影响。关于分类的一章介绍了对高级搜索操作非常有用的机器学习技术，例如如何将查询限制在某种特定语言书写的文档中，或者如何过滤搜索结果中的不良信息。关于并行信息检索和Web搜索的章节描述了从一个基本的信息检索系统变为一个涵盖数十亿文档并同时为成千上万的用户服务的大规模检索服务系统时所必须做出的改变。

通过引用数以百计的研究文献，作者对当今信息检索研究状况给出了指导性的概述，这个概述的高度远远超过了那些一般的综述。通过使用一个运行样例集和一个通用框架，他们具体描述了在每个环节中的重要方法——为什么这些方法行得通，它们是如何实现的，以及它们是如何工作的。为了写这本书，作者几乎实现和测试了每一个重要的方法，进行了数百次实验，并增加了对实验结果的阐述。每一章最后的练习题鼓励读者自己动手去建立系统并进行探索。

这本书是所有信息检索研究者和从业人员的必读教材！

Amit Singhal，Google Fellow