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

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

词典及容错式检索

由于本章中介绍了倒排索引结构的多种不同版本,因此有时将第1、2章中所定义的倒排索引称为普通倒排索引(standard inverted index)。在普通倒排索引中,词汇表中的每一个词项都会对应一个由文档集中的多篇文档组成的倒排记录表。实际上,本章介绍的倒排索引对普通倒排索引中的词典部分再进行了一层索引,可以找到词项,然后通过普通倒排索引最终定位到文档。

3.1 词典搜索的数据结构

假设给定倒排索引及查询,那么我们的首要任务是确定每个查询词项是否在词汇表中。词汇表的查找操作往往采用一种称为词典(dictionary)的经典数据结构,主要有两大类解决方案:哈希表方式和搜索树方式。选择具体解决方案时,通常要考虑如下问题:

  • 词项的数目有多少?
  • 词项的数目是固定的还是经常变化?变化时是只插入新词项,还是同时要删除某些旧词项?
  • 不同词项的相对访问频率如何?

哈希表方式

这种方式下,每个词项通过哈希函数映射成一个整数,映射函数的目标空间需要足够大,以减少哈希结果冲突的可能性,但很难避免(有一种称为完美哈希函数的方法能够避免冲突的发生,但这类方法计算、实现都很复杂)。由于查询词项稍有变化后哈希函数会生成截然不同的结果,故哈希表方式难以处理查询词项存在轻微变形的情况,特别地,它很难处理前缀式查询(如查找以auto开始的词项所在的文档)。在词汇表不断增长的环境中,哈希函数很快就会失效。

搜索树方式

能够解决上面提到的大部分问题。最出名的搜索树莫过于二叉树(binary tree)。二叉树的平衡性是实现高效搜索(此时比较次数为 $O(logM)$ )的关键,即任何节点两棵子树下的词项数目要么相等要么相差1。为了在加入或者删除词项时保持树的平衡性,往往需要对树节点进行重新的平衡化处理。

为了减轻重新平衡化处理的开销,词典搜索中普遍使用的B树允许内部节点的子树数目在某个固定区间内变化。在内存空间不足以存下全部词典而要将部分词典常驻磁盘时,这种方式很有效。

注意:和哈希表方式不同,搜索树要求树中的字符集有预定义的排序方式,如英语26个字母常按照A到Z排序。

3.2 通配符查询

通配符查询适用于如下任何一种场景:

  1. 用户对查询的拼写不太确定;
  2. 用户知道某个查询词项可能有不同的拼写版本,并且要把包含这些版本的文档都找出来;
  3. 用户查找某个查询词项的所有变形;
  4. 用户不确定一个外来词或者短语的正确拼写形式。

尾通配符查询(trailing wildcard query):通配符*在查询字符串末尾仅出现一次。基于搜索树的词典结构对于处理尾通配符查询来说非常方便。

首通配符查询(leading wildcard query):此时可以引入词典的反向B树(reverse B-tree)结构,在该结构中,原来B树中的每个从根到叶子路径所代表的词项全部反过来写(如词项lemon在反向B树中的路径就是root-n-o-m-e-l),所以对反向B树遍历后可以返回所有包含同一后缀词项。

同时使用B树和反向B树,可以处理只包含单个*通配符的查询。

3.2.1 一般的通配符查询

考察两种一般通配符查询的处理方法,它们都采用了同一种策略,即将给定的通配符查询 $q_w$ 表示成布尔查询 $Q$ ,随后在特定的倒排索引上进行处理。此时, $Q$ 对应的词项集合覆盖了 $q_w$ 的。逐一判断 $Q$ 对应的词项集合中的每个元素,看是否满足需求,不满足的剔除,最后得到 $q_w$ 对应的词项,再去查普通倒排索引即可返回相关文档。

轮排索引(permuterm index)

首先,在字符集中引入新符号\$,用于标识词项结束。然后构建一个轮排索引,其中对扩展词项的每个旋转结果都构造一个指针指向原始词项。如hello对应的轮排索引:

将词项旋转后得到的集合称为轮排词汇表(permuterm vocabulary)。以查询m*n为例,关键是将查询进行旋转让*号出现在字符串末尾,即得到n\$m*。在轮排索引中查找该字符串(可通过搜索树方式查找)实际上等价于查找某些词项(如man、moron)的旋转结果。

如果查询中存在多个通配符(如fi*mo*er),首先返回轮排索引中er\$fi*对应的词项集合,然后通过穷举法检查该集合中的每个元素,过滤掉不包含mo的词项。最后再利用剩下的词项查普通倒排索引。

轮排索引的一个最大的缺点是会使得词典变得非常大,因为它保存了每个词项的所有旋转结果。

3.2.2 (支持通配符查询的)k-gram索引

一个k-gram代表由k个字符组成的序列。在k-gram索引结构中,其词典由词汇表中所有词项的所有k-gram形式构成(用特殊字符\$标识词项的开始或结束),而每个倒排记录表则由包含该k-gram的词项组成,如:

Note:k-gram索引结构的倒排记录表中存储的是所有包含该k-gram的词项。而普通倒排索引中,倒排记录表存储包含该词项的文档集合。

以查询re*ve为例,我们的目标是返回所有前缀是re且后缀是ve的词汇,构造布尔查询\$re AND ve\$,这个查询可以在3-gram索引中进行查找处理,之后在普通倒排索引中查找返回的词项,从而得到与查询匹配的文档。但采用k-gram索引会导致非预期的结果,即能保证结果的召回率,但不能保证正确率(例如对于查询red*,转换为布尔查询\$re AND red,可能返回诸如retired的词项)。

为提高k-gram索引的正确率,引入一个称为后过滤(postfiltering)的步骤,即利用原始的查询red*对上述布尔查询产生的结果进行逐一过滤。过滤时只需要做简单的字符串匹配。

搜索引擎还可以通过布尔操作符支持多个通配符查询的组合,如red* AND fe*ri,即寻找同时匹配上red*和fe*ri的词项的文档。

即便是单个通配符查询的处理也是非常耗时的。搜索引擎可以支持这些丰富的功能,但通常隐藏在一个大部分用户从不访问的界面下。

3.3 拼写校正

解决拼写校正问题的两个步骤:第一步基于编辑距离(edit distance),第二步基于k-gram重合度(k-gram overlap)

3.3.1 拼写校正的实现

对于大多数拼写校正算法,存在以下两个基本原则:

  1. 对于一个拼写错误的查询,在其可能的正确拼写中选择距离“最近”的一个,这就需要度量邻近度;
  2. 当两个正确拼写查询邻近度相等/相近时,选择“更常见”的那个。“更常见”的两个概念:词项在文档集中出现的次数更多或者其他用户输入的查询中出现最频繁的拼写形式。

3.3.2 拼写校正的方法

主要关注两种拼写校正的方法:一种是词项独立(isolated-term)的校正,即不管查询中包含多少个词项,每次只对单个查询词项进行校正;另一种是上下文敏感(context-sensitive)的校正。

首先介绍两种词项独立的校正方法:编辑距离方法和k-gram重合度方法。然后介绍基于上下文敏感的校正方法。

3.3.3 编辑距离

给定两个字符串 $s_1$ 和 $s_2$ ,两者的编辑距离(edit distance)定义为将 $s_1$ 转换成 $s_2$ 的最小编辑操作数。通常,这样的编辑操作包括:

  1. 将一个字符串插入字符串;
  2. 从字符串中删除一个字符;
  3. 将字符串中的一个字符替换成另外一个字符

编辑距离的概念可进一步推广,如允许不同的编辑操作具有不同的权重,即根据字符之间替换的可能性计算权重。

显然,可以在 $O(|s_1|*|s_2|)$ 的(带权)编辑距离,主要解决思路是采用动态规划算法,其中 $s_1$ 和 $s_2$ 以字符数组的方式进行存放。整数矩阵m的行数和列数分别是两个字符串的长度,算法在运行中不断填充矩阵元素。算法运行结束后,矩阵第 $i$ 行第 $j$ 列的元素保存的是 $s_1$ 的前 $i$ 个字符构成的字符串和 $s_2$ 前 $j$ 个字符构成的字符串的编辑距离。

然而,拼写校正问题不止要计算出编辑距离:给定字符串 $V$ (对应词项词汇表)和查询字符串 $q$ ,我们要从 $V$ 中寻找和 $q$ 具有最小编辑距离的字符串。最简单的启发方式是将搜索限制在与查询词具有相同首字母的字符串上,另一方法是利用轮排索引的某种版本,考虑查询字符串 $q$ 的所有旋转结果集合,对集合的每个旋转 $r$ ,通过遍历B树来访问轮排索引,返回以旋转 $r$ 开头的词项,但采用这种做法会是我们错过一些可能更相关的词。此时我们可以改变旋转的使用机制:对每个旋转结果,在遍历B树之前忽略其长度为$l$的后缀,这样可以保证返回词项集合R中的每个词项和 $q$ 之间都包含一段较长的公共子串。 $l$ 的值取决于 $q$ 的长度,也可以设置为常数。

小结

本章介绍当查询中存在拼写错误时的鲁棒性处理技术,并给出可能的正确拼写结果。3.1节主要介绍支持词典快速查找的多个数据结构。3.2节主要介绍通配符查询(wildcard query)。3.3节将转向介绍拼写上存在错误的查询,一开始介绍两个查询之间的邻近度概念及其高效的计算方法,之后详细介绍了一系列查询拼写的自动校正技术,其中包括针对每个查询词的独立校正技术,以及针对整个查询串的整体校正技术。最后,3.4节考察了一种在词汇表中查找与查询词发音近似的词项的方法。

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