《信息检索导论》学习笔记——第1章

最近尝试入门文本处理。我看书习惯把课本上我认为较为重点的部分和自己看书时的疑问记下来,开了博客后就想着把这些笔记分享出来供需要的人借鉴,同时也算记录自己的学习、成长过程。有不足之处还请多多宽容,多多指教~

前言

本书前8章介绍信息检索的基础知识,特别是搜索引擎的核心理论。第1章(布尔检索)主要介绍倒排索引,并说明如何通过这种索引实现简单的布尔查询;第2章(词项词典及倒排记录表)介绍索引之前的文档预处理过程,并讨论在不同的功能和速度要求下对倒排索引进行改进的方法;第3章(词典及容错式搜索)主要介绍词典搜索的数据结构,并给出查询存在拼写错误或者与被搜索的文档中的词汇不能精确匹配时的处理方法;第4章(索引构建)主要介绍基于文本集合构建倒排索引的几个算法 ,这类算法适用于大规模文档集的索引构建;第5章(索引压缩)主要介绍倒排索引的压缩技术,包括词典的压缩和倒排记录表的压缩技术,这些技术对于实现大型搜索引擎的亚秒级查询响应十分关键。前五章中介绍的索引和查询仅针对布尔检索,即一篇文档和查询要么匹配,要么不匹配。那么如何度量查询和文档的匹配程度呢?对这个问题的回答构成了第6、7章(文档评分、词项权重计算及向量空间模型&一个完整搜索系统中的评分计算)词项权重计算和评分算法的主要内容;第8章(信息检索的评价)主要介绍信息检索系统的评价技术,即根据检索系统返回结果的相关性对不同系统进行评价,从而可以在基准文档集和查询上对不同系统的性能进行比较。


第1章 布尔检索

本章涉及到的部分术语:

术语 解释
文档 检索系统的检查对象
文档集/语料库 所有的文档组成的集合
ad hoc检索任务 信息需求动态变化,而文档集相对静止,如Web搜索引擎
过滤任务 信息需求在一段时间内不变,而文档集则变化频繁,如信息订阅
正确率(precision) 返回的结果中真正和信息需求相关的文档所占的百分比
召回率(recall) 所有和信息需求真正相关的文档中被检索系统返回的百分比
文档频率 出现某个词项的文档数目
词项频率 词项在某个文档中出现的次数

信息检索是从大规模非结构化数据(通常是文本)的集合(通常保存在计算机上)中找出满足用户信息需求的资料(通常是文档)的过程。

分类(classification)已知文档内容所属的类别集合,而聚类(clustering)未知。

1.1 一个信息检索的例子

线性扫描方式(greeping):用于小规模文档集,不需要做额外的处理。

非线性扫描方式(布尔检索模型):事先给文档建立索引(index),对每篇文档都事先记录它是否包含词表中的某个词,得到一个由布尔值构成的词项-文档关联矩阵(该矩阵由布尔值0、1构成)。布尔检索模型接受布尔表达式查询,即通过AND、OR及NOT等逻辑操作符将词项连接起来的查询。在该模型下,每篇文档只被看成是一系列词的集合。

但是当文档数量增大,词项-文档矩阵为稀疏矩阵,矩阵中的大部分元素为0,此时只记录原始矩阵中1的位置的表示方法比词项-文档矩阵效果更好。这种思路引出信息检索中的一个核心概念——倒排索引(inverted index)。

倒排索引的两个部分:

左部为(词项)词典(dictionary),每个词项都有一个记录出现该词项的所有文档的列表,这个表中的每个元素称为倒排记录(posting),每个词项对应的整个表称为倒排(记录)表,所有词项的倒排记录表一起构成全体倒排记录表(postings)。一般地,提到倒排记录时,采用(词项,文档ID)这种二元组的表示方法。

倒排索引的两个部分中,词典部分往往放在内存中,而指针指向的每个倒排记录往往存放在磁盘上。

1.2 构建倒排索引的初体验

建立索引的主要步骤:

  1. 收集需要建立索引的文档。如:

  2. 词条化(tokenization):将每篇文档转换成一个个词条的列表。如:

  3. 进行语言学预处理,产生归一化的词条来作为词项。如:

  4. 对所有文档按照其中出现的词项来建立倒排索引,索引中包括一部词典和一个全体倒排记录表。

基于排序的索引构建方法(sort-based indexing):每篇文档的所有词项加上文档ID → 二元组(词项,文档ID)按照词项字母顺序排序 → 同一词项进行合并 → 将词项和文档ID分开,词项存储在词典中,每个词项有一个指针指向倒排记录表。词典中还会存储一些其他概要信息,如每个词项的文档频率(document frequency)。同样地,每个倒排记录表也可以存储词项频率(term frequency)

1.3 布尔查询的处理

使用倒排索引和基本布尔检查模型处理一个查询,以一个简单“与”查询为例:Brutus AND Calpurnia

  1. 在词典中定位Brutus,返回其倒排记录表;
  2. 在词典中定位Calpurnia,返回其倒排记录表;
  3. 对两个倒排记录表求交集。

其中,交集(intersection)操作很关键,算法如下:

假设两个倒排记录表的大小分别是$x$和$y$,那么下述求交集的过程需要$O(x+y)$ 次操作。即查询的时间复杂度为$O(N)$,其中N是文档集合中文档的数目。

1
2
3
4
5
6
7
8
9
10
11
INTERSECT(p1,p2) //p1,p2为指针
ANSWER ← <>
while p1 ≠ NIL and p2 ≠ NIL
do if docID(p1) = docID(p2)
then ADD(answer,docID(p1))
p1 ← next(p1)
p2 ← next(p2)
else if docID(p1) < docID(p2)
then p1 ← next(p1)
else p2 ← next(p2)
return answer

查询优化(query optimization) :指通过组织查询的处理过程使处理工作量最小。对布尔查询进行优化要考虑的一个主要因素是倒排记录表的访问顺序。按照词项的文档频率(即倒排记录表的长度)从小到大依次处理,如果我们先合并两个最短的倒排记录表,那么所有中间结果的大小都不会超过最短的倒排记录表(原理:多个集合的交集元素个数肯定不大于其中任何一个集合的元素个数),这样处理所需要的工作量最少。

在这里词项的文档频率可以在访问之前决定倒排记录表的访问次序。

查询优化算法如下:

1
2
3
4
5
6
7
8
INTERSECT(<t1,t2,...,tn>)
terms ← SORTBYINCREASEINGFREQUENCY(<t1,t2,...,tn>)
result ← postings(first(terms))
terms ← rest(terms)
while terms ≠ NIL and result ≠ NIL
do result ← INTERSECT(result,postings(first(terms)))
terms ← rest(terms)
return result

当倒排记录表的长度相差很大时,可以使用一些策略加速合并过程。如对于中间结果表,合并算法可以就地对失效元素进行二分查找。或者将长倒排记录表用哈希方式存储。

1.4 对基本布尔操作的扩展及有序检索

和布尔检索模型相对的是排序检索模型或有序检索模型(ranked retrieval model),后者是采用一个或者多个词来构成自由文本查询(free text query)。有序检索系统要能够确定哪篇文档最能满足用户的需求。

布尔查询表达上更精确,为搜索专家所喜欢,但大部分用户很少使用。

小结

第1章介绍了基本倒排索引的结构和构建,整个索引包含词典和倒排记录表两部分;介绍了布尔检索模型,并考察了通过线性时间复杂度的合并方法和简单的查询优化方法进行高效检索。

文章作者: Elody
文章链接: http://Elody-07.github.io/《信息检索导论》前言&第1章/
版权声明: 本博客所有文章除特别声明外,均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 Elody的博客