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

继续学习《信息检索与导论》~

词项词典及倒排记录表

回顾构建倒排索引的几个主要步骤:

  1. 收集需要建立索引的文档;
  2. 对这些文档中的文本进行词条化;
  3. 对第2步产生的词条进行语言学预处理,得到词项;
  4. 根据词项对所有文档建立索引。

本章涉及到的部分术语:

术语 解释
词条化(tokenization) 将原始的字符流转换成一个个词条(token)的过程
语言学预处理 建立词条的等价类,每个等价类对应一个词项,这些词项用于建立文档的索引
停用词 在文档和用户需求进行匹配时价值不大的常用词,需要彻底从词汇表中去除。

2.1 文档分析及编码转换

2.1.1 字符序列的生成

文档处理的第一步是将文件中或者Web服务器上的字节序列转换成线性的字符序列。为了实现这种转换,首先要正确判断出文档的编码方式,可以将该过程看做一个基于机器学习的分类问题来处理,但在实际中往往通过启发式方法来实现,也可以利用文档的元信息或者直接由用户手工选择来确定。

启发式方法:指人在解决问题时所采取的一种根据经验规则进行发现的方法。其特点是在解决问题时,利用过去的经验,选择已经行之有效的方法,而不是系统地、以确定的步骤去寻求答案,与算法相对立。

在后面的讨论中,假设文档只由一系列的文本字符构成。

2.1.2 文档单位的选择

对于长文档而言,存在“索引粒度”(indexing granularity)的问题。如果索引粒度太小,那么由于词项散布在多个细胞粒度文档中,我们就很可能错过那些重要的段落,即此时正确率高而召回率低;如果索引粒度太大,我们就很可能找到很多不相关的匹配结果,即正确率低而召回率高。索引粒度过大造成的问题可以通过采用显示或隐式的邻近搜索方法来缓解。

一个信息检索系统应该能够提供不同粒度索引的选项,在具体实施时如果要达到合理选择的目的,就必须要对文档集、用户及其可能的需求和使用模式等信息有一个非常深刻的理解。

在后面的讨论中,假设已经选择了合理的索引粒度。

2.2 词项集合的确定

2.2.1 词条化

词条化是将给定的字符序列拆分成一系列子序列的过程,其中每个子序列称为一个词条(token)。在这个过程中会去掉一些特殊字符,如标点符号等。例如:

输入:Friends, Romans, Countrymen, lend me your ears;

输出:

区分词条&词项:两者密切相关,但词项集合和词条集合可以完全不同。词项是通过对原始词条进行归一化得到的。

词条化的主要任务是确定哪些才是正确的词条。不管是输入布尔查询或者自由文本查询,为确保对文档和查询的同一字符串序列的处理结果一致,往往采用相同的词条化工具。

词条化处理必须知道文档的语言种类。由于大多数语言都有自己独特的特征模式,所以一种非常有效的语言种类识别方法(language identification)是利用短字符序列作为特征来分类(例子见书P18-19)。

2.2.2 去除停用词

一个常用的生成停用词表的方法是将词项按照文档集频率从高到底排列,然后手工选择那些语义内容与文档主题关系不大的高频词作为停用词。停用词表中的每个词将在索引过程中被忽略,可以大大减小系统所需存储的倒排记录表的数目。但是,对于短语查询,停用词表的使用可能增大搜索难度,比如歌名或者著名诗歌片段全由常用的停用词组成(如To be or not to be, Let it Be等)。

在信息检索系统不断发展的历程中,有从大停用词表(200-300个词)到小停用词表(7-12个词)最后到不用停用词的趋势。Web搜索引擎通常不用停用词表。一些现代IR系统更关注如何利用语言的统计特性来更好地处理常见词问题,因此不论是对索引大小还是查询处理的时间而言,不去除停用词所增加的开销并没有那么大。

2.2.3 词项归一化

词条归一化(token normalization)是将看起来不完全一致的多个词条归纳成一个等价类。最常规的做法是隐式地建立等价类,每类可以用其中的某个元素来命名(如将anti-discriminatory和antidiscriminatory映射成词项antidiscriminatory)。

另一种建立等价类的方法是维持多个非归一化词条之间的关联关系(如car和automobile),该方法可以扩展成手工建立同义词词表。这些词项之间的关系可以通过两种方式来实现。常用的方式是采用非归一化的词条进行索引,并为某个查询项维护一张包含多个词的查询扩展词表。当输入一个查询词项时,则根据扩展词表行扩展并将扩展后得到的多个词所对应的倒排记录表合在一起。另一种方式是在索引构建时就对词进行扩展。这两种方式虽然相对隐式建立等价类来说效率低,但是更具灵活性。

一些在实际中会遇到的词条归一化问题及其对策:

1. 重音及变音符号问题

2. 大小写转换问题

一般策略是将所有的字母转换成小写,但有些专有名词由普通名词构成,因此大小写不同则意义不同,并且这种意义不同只能通过大小写来区别。

对英语来说,大小写处理的另一种做法是只将部分词条转换成小写形式。最简单的启发式处理方法是将句首词或标题中大写词转换成小写形式,句中的大写词仍保留原来的形式。对于上述工作,也可以采用机器学习序列模型,基于多种特征实现更精确的大小写决策。

然而实际中,用户常常忽略大小写而使用小写方式输入查询,因此通常采用全部转换成小写的做法。

3. 英语中的其他问题

英语中还存在一些独特的归一化做法。如英式英语和美式英语拼写的统一,日期、时间等多种形式的表达等给归一化造成了额外的负担。

4.其他语言的问题

待索引的文档集可以同时包括来自不同语言的文档,单篇文档中也可能同时出现不同语言的文本。一个普遍的做法是,先判定语言种类,然后采用该语言的词条化和归一化规则在预定的粒度(如整篇文档或者每个段落)水平上进行处理。

当文档集包含多个语言时,单个索引中可能要包含来自不同语言的词项,一种做法是在文档上运行一个语言识别器,然后将每个词项的语言种类标记在词项词典中。

当处理外来词或者复合词时,拼写不明确或者在不同的音译标准下会产生不同拼写结果。处理此类情况的一种做法是采用启发式方法建立等价类,或者根据发音相同来进行词项扩展。

2.2.4 词干还原和词形归并

出于语法要求,文档中常出现词的不同形态,语言中也存在大量意义相近的同源词。在很多情况下,希望输入其中一个词能返回包含其同源词的文档。

词干还原和词形归并的目的都是减少词的屈折变化形式,并且有时会将派生词转化为基本形式,如am, are, is → be等。

区分词干还原(stemming)&词形归并(lemmatization):前者通常指一个很粗略的去除单词两端词缀的启发式过程,通常也包括去除派生词缀;而后者通常指利用词汇表和词形分析来去除屈折词缀,从而返回词的原形或词典中的词的过程,返回的结果称为词元(lemma)。这两个过程的区别还在于:词干还原在一般情况下会将多个派生相关词合并在一起,而词形归并通常只将同一词元的不同屈折形式进行合并。二者常通过在索引过程中增加插件程序的方式实现。

2.3 基于跳表的倒排记录表快速合并算法

回顾1.3节的倒排记录表的基本合并算法:同时在两个表中遍历,并且最后算法的时间复杂度为记录表大小的线性函数。能否在亚线性时间内完成合并过程?如果索引变化不是太快的话,答案是肯定的。

一种实现的方法是采用跳表(skip list),在构建索引的同时在倒排记录表上建立跳表。跳表指针能够提供捷径来跳过那些不可能出现在检索结果中的记录项。构建跳表的两个主要问题是:在什么位置设置跳表指针?如何利用跳表指针进行倒排记录表的快速合并?

当跳表指针目标项仍然小于另一个表的当前比较项时可以采用跳表指针直接跳转。注意:跳表指针只对AND类型的查询有用,对OR类型的查询不起作用。

在什么位置放置跳表指针?这里存在一个指针个数和比较次数的折中问题。放置跳表指针的一个简单的启发式策略是,在每隔 $\sqrt{P}$ 处均匀放置跳表指针,其中 $P$ 是倒排记录表的长度。这个策略在实际中效果不错,但仍有提高的余地,因为它没有考虑查询词项的任何分布细节。

基于跳表指针的倒排记录表合并算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
INTERSECTWITHSKIPS(p1, p2)
answer ← <>
while p1 ≠ NIL and p2 ≠ NIL
if docID(p1) = docID(p2)
then ADD(answer, docID(p1))
p1 ← next(p1)
p2 ← next(p2)
else if docID(p1) < docID(p2)
then if hasSkip(p1) and (docID(skip(p1)) ≤ docID(p2))
then while hasSkip(p1) and (docID(skip(p1)) ≤ docID(p2))
p1 ← skip(p1)
else p1 ← next(p1)
else
if hasSkip(p2) and (docID(skip(p2)) ≤ docID(p1))
then while hasSkip(p2) and (docID(skip(p2)) ≤ docID(p1))
p2 ← skip(p2)
else p2 ← next(p2)
return answer

如果索引相对固定的话,建立有效的跳表指针比较容易。但是如果倒排记录表由于经常更新而变化,那么跳表指针的建立就比较困难。恶意的删除策略可能会使跳表完全失效。

2.4 含位置信息的倒排记录表及短语查询

大部分搜索引擎都提供双引号语法(如”Stanford University“)来支持短语查询。大概有10%的Web查询是短语查询,有更多的查询虽然输入时没有加双引号,但实际上是隐式的短语查询(如人名)。要支持短语查询,只列出词项所在的文档列表的倒排记录表已不足以满足要求。

2.4.1 二元词索引

处理短语查询的一个办法就是将文档中每个接续词对看成一个短语。如文本Friends, Romans, Countrymen会产生如下的二元接续词对(biword):friends romans、romans countrymen。这种方法将每个接续词对看成词项,更长的查询可以分成多个短查询来处理。

用名词和名词短语来表述用户所查询的概念具有相当特殊的地位,但是相关的名词往往被各种虚词分开。这时可以采用如下方法建立二元词索引:首先对文本进行词条化,然后进行词形标注,这样就可以把每个词项归成名词(N,也包括专有名词)、虚词(X,冠词和介词)等。然后将形式为NX*N非词项序列看成一个扩展的二元词,每个这样的扩展二元词对应一个词项。要利用这样的扩展二元词索引处理查询,也需要将查询分析称N和X,然后将查询划分成扩展的二元词,最后在索引中进行查找。

当将长查询分析称布尔查询时,上述算法在直观上并不总是最好。

二元词索引的概念可以扩展到更长的词序列,如果索引中包含变长的词序列,通常就称为短语索引(phrase index)。实际上,在长度为3或者更长的索引短语上发生匹配错误的可能性小于二元词索引。但另一方面,存储更长的短语很可能会大大增加词汇表的大小。如何在一个混合索引机制下有效地使用部分短语索引呢?

2.4.2 位置信息索引

实际中更常用的短语查询的方式是位置信息索引(positional index,简称位置索引)。在这种索引中,对每个词项,以如下方式存储倒排记录:文档ID:<位置1,位置2,…>。在每条倒排记录中往往会保存当前词项在文档集中出现的频率,如:

1
2
3
4
5
to,993427:
<1,6:<7,18,33,72,86,231>;
2,5:<1,17,74,222,255>;
...>
//位置索引的一个例子。单词to的文档频率是993427,在文档1中出现6次,位置分别是7、18、33等。

为处理短语查询,仍然需要访问各个词项的倒排记录表。这里的倒排记录表合并操作仍然可以采用最小文档频率优先的策略,从而限制后续合并的候选文档的数目。但是这里不只是简单地判断两个词项是否出现在同一文档中,而且还要检查它们的出现位置关系与查询当中是否保持一致,这就需要计算出词之间的偏移距离。

类似的方法可以用于k词近邻搜索当中,如:employment /3 place。这里,/k意味着“从左边或右边相距k个词之内”。显然,位置索引能用于邻近搜索而二元词索引不能。

用于k词近邻搜索的算法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
POSITIONAL INTERSECT(p1, p2, k)
answer ← <>
while p1 ≠ NIL and p2 ≠ NIL
if docID(p1) = docID(p2)
then l ← <>
pp1 ← positions(p1)
pp2 ← positions(p2)
while pp1 ≠ NIL
while pp2 ≠ NIL
if |pos(pp1)-pos(pp2)| ≤ k
then ADD(l, pos(pp2))
else if pos(pp2) > pos(pp1)
then break
pp2 ← next(pp2)
while l ≠ <> and |l[0]-pos(pp1)>k| //(*)
DELETE(l[0]) //(*)
for each ps ∈ l
ADD(answer, <docID(p1),pos(pp1),ps>)
pp1 ← next(pp1)
//l ← <>可以替换(*)部分
p1 ← next(p1)
p2 ← next(p2)
else if docID(p1) < docID(p2)
then p1 ← next(p1)
p2 ← next(p2)
return answer
// 邻近搜索中两个倒排记录表p1和p2的合并算法,算法寻找两个词项在k个词之内出现的情形,返回一个三元组
// <文档ID,词项在p1中的位置,词项在p2中的位置>的列表。

位置索引的大小

采用位置索引会大大增加倒排记录表的存储空间,即使对位置值或偏移值采用压缩方法也无济于事。实际上,采用位置索引会提高倒排记录表合并操作的渐进复杂性,这是因为需要检查的项的个数不再受限于文档数目而是文档集中出现的所有的词条的个数 $T$ ,即布尔查询的复杂度是 $O(T)$ 而不是 $O(N)$ 。但是由于用户往往期望能够进行短语搜索和邻近搜索,所以实际中的大部分应用不得不采用这种做法。

位置索引的空间消耗。位置索引需要对词项的每次出现保留一个条目,因此索引的大小取决于文档的平均长度。大文件条件下会造成索引存储空间大小的两个数量级规模的增长。利用一些粗略的经验法则可以预期位置索引大概是非位置索引大小的2~4倍,而压缩后的位置索引大概为原始未压缩文档文本(去除标记信息)的1/3~1/2。

2.4.3 混合索引机制

二元词索引和位置索引可以进行有效的合并。假如用户通常只查询特定的短语,那么基于位置索引的倒排记录表合并方式效率很低。一个混合策略是:对某些查询使用短语索引或只使用二元词索引,而对其他短语查询采用位置索引。短语索引所收录的那些较好的查询可以根据用户最近的访问行为日志统计得到。

当然,以上不是唯一的准则。处理开销最大的短语查询往往是这样一些短语,它们中的每个词都很常见,但是组合起来却相对少见,如将The Who加入短语索引会对这个查询有1000倍的加速效果。尽管这些短语出现得不够频繁,但是通过短语索引后的处理效率会有大的提高,所以也常把这类短语加入短语索引中。

William等人评估了一个更复杂的混合索引机制,其中除了包含上面两种形式的索引外,还在它们之间引入了一个部分后续词索引(next word index),即对每个词项,有个后续词索引记录了它在文档中的下一个词项。论文的结论是:虽然比位置索引增加了26%的空间,但是面对典型的Web短语混合查询,其完成时间大概是只使用位置索引的1/4。

小结

第2章主要介绍了构建倒排索引中的收集索引文档、对文档词条化及对词条归一化等语言学预处理得到词项的步骤,以及一些在词条化和归一化的过程中遇到的语言学相关的问题及解决方法,后两节介绍了倒排记录表数据结构的其它扩展形式,利用跳表提高倒排记录表的使用效率,最后介绍了适合于处理短语查询和邻近查询的索引结构,这些查询在支持扩展布尔操作的检索系统和Web搜索系统中使用的十分普遍。

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