【大数据管理】数据组织与存储（五）_轮排索引

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

•很多复杂的或技术性的概念、机构名和产品名等都是由多个词语组成的复合词或短语。用户希望能够将类似Stanford University 的查询中的两个词看成一个整体.

•大部分搜索引擎都提供了双引号语法（如“ Stanford University” ）来支持短语查询，这种语法很容易理解并被用户成功使用.

•大概有10%的Web 查询是短语查询，有更多的查询虽然输入时没有加双引号，但实际上是隐式的短语查询（如人名）。

•要支持短语查询，只列出词项所在的文档列表的倒排记录表已不足以满足要求.

•将考虑两种支持短语查询的方式及它们的交叉使用.

 

二元索引

•处理短语查询的一个办法就是将文档中每个接续词对看成一个短语。例如，文本Friends, Romans, Countrymen 会产生如下的二元接续词对（biword）：

friends romans

romans countrymen

•这种方法将每个接续词对看成词项，这样马上就能处理两个词构成的短语查询，更长的查询可以分成多个短查询来处理。比如，按照上面的方法可以将查询stanford university palo alt可分成如下的布尔查询：“stanford university” AND “university palo” AND “palo alto”

•但是相关的名词往往被各种虚词分开，比如短语the abolition of slavery或者renegotiation of the constitution。

•这种情况下，可以采用如下方法来建立二元词索引：

（1）首先对文本进行词条化然后进行词性标注，这样就可以把每个词项归成名词（N，也包括专有名词）、虚词（X，冠词和介词）和其他词。

（2）然后将形式为NX*N非词项序列看成一个扩展的二元词。每个这样的扩展二元词对应一个词项。例如：

 

renegotiation of the constitution

N                    X  X      N

•要利用这样的扩展二元词索引处理查询，也需要将查询分析成N 和X，然后将查询划分成扩展的二元词，最后在索引中进行查找。

•二元词索引的概念可以扩展到更长的词序列，如果索引中包含变长的词序列，通常就称为短语索引（phrase index）.

•实际上，利用二元词索引来处理单个词的查询不太方便（必须要扫描整个词汇表来发现包含该查询词的二元词），因此同时还需要有基于单个词的索引。

•尽管总有可能得到错误的匹配结果，但是在长度为3 或者更长的索引短语上发生匹配错误的可能性实际上却很小。

•然而在另一方面，存储更长的短语很可能会大大增加词汇表的大小。穷尽所有长度超过2的短语并维护其索引绝对是一件令人生畏的事情，即使只穷尽所有的二元词也会大大增加词汇表的大小。

 

位置信息索引

•很显然，基于上面谈到的原因，二元词索引并非标准的解决方案。

•实际中更常用的一种方式是采用所谓的位置信息索引（positional index，简称位置索引）。在这种索引中，对每个词项，以如下方式存储倒排记录（见图2-11）

 文档ID：（位置1，位置2，…）

•为处理短语查询，仍然需要访问各个词项的倒排记录表。像以往一样，这里可以采用最小文档频率优先的策略，从而可以限制后续合并的候选词项的数目。

•在合并操作中，同样可以采用前面提到的各种技术来实现，但是这里不只是简单地判断两个词项是否出现在同一文档中，而且还需要检查它们出现的位置关系和查询短语的一致性。这就需要计算出词之间的偏移距离。

•例 2-1 短语查询请求的应答处理。假定to和be的倒排记录表如2-11 所示，某个查询为to be or not to be。

•需要访问如下词的倒排记录表：to、be、or和not。考虑to和be的倒排记录表的合并：

•首先，查找同时包含这两个词项的文档；然后，检查表中的位置看看是否有某个be的前面一个词条位置上正好出现to。图2-11 中给出的倒排记录表中，可能存在的一个匹配为：

 to: 〈. . . ; 4: 〈. . . ,429,433〉; . . .〉

be: 〈. . . ; 4: 〈 . . ,430,434〉; . . . 〉

•位置索引的大小。采用位置索引会大大增加倒排记录表的存储空间。

•实际上，采用位置索引会加深倒排记录表合并操作的渐进复杂性，这是因为需要检查的项的个数不再受限于文档数目而是文档集中出现的所有的词条的个数T。

•也就是说，布尔查询的复杂度为Θ (T)而不是Θ (N)。然而，由于用户往往期望能够进行短语搜索和邻近搜索，所以实际中的大部分应用并没有其他选择而不得不采用这种做法。

•回头再看看采用位置索引的空间消耗。位置索引需要对词项的每次出现保留一个条目，因此索引的大小取决于文档的平均长度。

•网页的平均长度往往不到1 000 个词项，而诸如证管会（SEC）股票文件、书籍甚至一些英雄史诗等文档的长度则很容易就能达到100 000 个词项。

•考虑在平均1 000 个词项中每个词项的频率都是1，最后的结果就是：大文件条件下会造成索引存储空间大小的两个数量级规模的增长，如下所示。

•尽管确切的数字要视文档及其语言的具体类型而定，但是利用一些粗略的经验法则可以预期位置索引大概是非位置索引大小的2～4 倍.

 

 

混合索引机制

 •二元词索引和位置索引这两种策略可以进行有效的合并.

•假如用户通常只查询特定的短语，如Michael Jackson，那么基于位置索引的倒排记录表合并方式效率很低。

•一个混合策略是：对某些查询使用短语索引或只使用二元词索引，而对其他短语查询则采用位置索引.

•短语索引所收录的那些较好的查询可以根据用户最近的访问行为日志统计得到，也就是说，它们往往是那些高频常见的查询。

 

 

词典及容错式检索

词典搜索的数据结构

•假设给定倒排索引及查询，那么首要任务是确定每个查询词项是否在词汇表中，如果在，则返回该词项对应的倒排记录表的指针.

•词汇表的查找操作往往采用一种称为词典（dictionary）的经典数据结构，并且主要有两大类解决方案:

 (1)哈希表方式

 (2)搜索树方式

•在数据结构相关的文献中，词汇表中的每个条目（这里是词项）常常称为关键字或键（key）.

•选择具体解决方案（不论是哈希表方式和搜索树方式）时，通常要考虑如下问题：
 (1) 关键字的数目有多少？

(2) 关键字的数目是固定的还是经常变化？在变化的情况下，是只插入新关键字，还是同时要删除某些旧关键字？

(3) 不同关键字的相对访问频率如何？

•哈希表方式已在某些搜索引擎中用于词典查找。这种方式下，每个词项通过哈希函数映射成一个整数，映射函数的目标空间需要足够大，以减少哈希结果冲突的可能性。

•当然，这种方式很难避免冲突的发生，此时需要精心维护一个辅助结构来解决冲突问题.

•查询时，对于每个查询项分别进行哈希操作，并解决存在的冲突，最后返回每个查询词项对应的倒排记录表的指针。

•由于查询词项稍有变化后哈希函数会生成截然不同的结果，哈希表方式难以处理查询词项存在轻微变形的情况（如单词resume的重音符和非重音符版本）.

•特别地，哈希表方式很难处理前缀式查询，如查找以automat开始的词项所在的文档。

•最后需要指出的是，在词汇表不断增长的环境（如Web）中，为当前需求所设计的哈希函数可能会在几年内很快失效。

•搜索树方式能够解决上面提到的大部分问题。比如，它可以支持以automat开始的前缀式查询。

•最出名的搜索树莫过于二叉树（binary tree）,其每个内部节点都有两个子节点.

•在二叉树中搜索词项要从根节点开始，而每个内部节点（包括根节点）都代表一个二值测试，测试的结果用于确定下一步应该搜索的子树.

•图3-1 给出了一个基于二叉树表示的词典的例子。

•为了减轻重新平衡化处理的开销，有一种方法允许内部节点的子树数目在某个固定区间内变化。

•词典搜索中普遍使用的B-树就是这类方法的一个实例。它每个内部节点的子节点数目在区间[a,b]内取值，其中a 和 b 都是某个合适的正整数。

•图3-2 给出了一棵B-树的例子，其中a=2，b=4

 

 

通配符查询

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

(1)用户对查询的拼写不太确定（比如，如果询S*dney）;

(2)用户知道某个查询词项可能有不同的拼写版本，并且要把包含这些版本的文档都找出来（比如color 和colour）；

(3)用户查找某个查询词项的所有变形，这些变形可能还做了词干还原，但是用户并不知道搜索引擎是否进行了词干还原（比如judicial 和judiciary，可采用通配符查询judicia* ）；

(4) 用户不确定一个外来词或者短语的正确拼写形式（如查询Universit* Stuttgart）。

•因为通配符*在查询字符串末尾仅出现一次，所以一个诸如mon* 的查询称为尾通配符）。

•基于搜索树的词典结构对于处理尾通配符查询来说非常方便，比如对于查询mon*，可以依次按照字符m、o、n 从上到下遍历搜索树，直到能列举词典中所有以mon 开头的词项集合W时为止.

•最后，在普通倒排索引中进行|W|次查找后取出W中所有词项所对应的文档。

•上述做法中存在的一个明显的问题就是，如果通配符不出现在查询尾部应该如何处理？

•在处理这种更一般的情况之前，首先对尾通配符查询做一个小小的改进；

•考虑首通配符查询（leading wildcard query）或者说*mon 形式的查询。此时可以引入词典的反向B-树（reverse B-tree）结构，在该结构中，原来B-树中的每个从根到叶子路径所代表的词项全部反过来写。

•因此，词项lemon在反向Ｂ—树中的路径就是 root-n-o-m-e-l。所以对反向B-树遍历后可以返回所有包含同一后缀的词项。

•于是，同时使用B-树和反向B-树，我们可以处理更一般的单通配符查询，比如se*mon。

•具体处理时，可以通过B-树来返回所有前缀为se且后缀非空的词项子集W，再通过反向B-树来返回所有后缀为mon且前缀非空的词项子集R。

•然后，对W和R求交集W ∩ R，之后对交集进行扫描，当前缀和后缀相同时去掉它们对应的词项（比如，查询ba*ba对应的集合R和W都包含词项ba，这种情况下应该过滤掉ba），得到结果集合。

•最后，通过普通倒排索引来获取结果集合中所有词项对应的文档。这样，就可以通过同时引入B-树和逆B-树的方式来处理只包含单个*号的查询。

 

 

一般的通配符查询

•本节中考察两种一般通配符查询的处理方法，它们都采用了同一种策略，即将给定的通配符查询qw 表示成布尔查询Q，随后在特定的倒排索引上进行处理。

•此时，Q 对应的词项集合覆盖了qw 对应的词项集合。

•然后，逐一判断Q 对应的词项集合中的每个元素，看是否满足qw 的需求，并将那些不满足其要求的词项剔除。

•最后，得到qw 对应的词项，再去查普通倒排索引即可返回相关文档。

•轮排索引：第一种专门用于一般通配符查询的索引是轮排索引（permuterm index），它是倒排索引的一种特殊形式。

•首先，在字符集中引入一个新的符号$，用于标识词项结束。

•因此，词项hello在这里表示成扩展的词项hello$。然后，构建一个轮排索引，其中对扩展词项的每个旋转结果都构造一个指针来指向原始词项。

•图3-3 给出了词项hello对应的轮排索引的例子。

•将词项旋转后得到的集合称为轮排词汇表（permuterm vocabulary）。

•那么，如何利用轮排索引来处理通配符查询呢？

•考虑通配符查询m*n，这里的关键是将查询进行旋转让*号出现在字符串末尾，即得到n$m* 。

•下一步，在轮排索引中查找该字符串（可通过搜索树方式查找），实际上等价于查找某些词项（如man 和moron）的旋转结果。

 •既然可以使用轮排索引查找到匹配通配符的原始词典中的词项，那么就可以在普通倒排索引中查找这些词项，从而检索出匹配的文档。

•这样，就能够处理所有包含单个*号的通配符查询。

•但是，如果查询中存在多个通配符（如fi*mo*er），应该如何处理？

•在这种情况下，首先返回轮排索引中er$fi*对应的词项集合，然后通过穷举法检查该集合中的每个元素，过滤掉其中不包含mo 的词项。

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

 

 

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

•尽管前面介绍的轮排索引结构尽管非常简单，但是由于要支持词项旋转，所以它会引起空间的急剧增长。对于一部英语词典来说，这种增长可能达到10 倍左右。

•为此，下面介绍另外一种称为k-gram索引的通配符查询处理技术

•一个k-gram代表由k 个字符组成的序列。对于词项castle 来说，cas、ast、stl 都是3-gram。$ca、cas、ast、stl、tle 及le$。

•在k-gram索引结构中，其词典由词汇表中所有词项的所有k-gram形式构成，而每个倒排记录表则由包含该k-gram的词项组成。

•比如，3-gram etr可能会指向包括metric和retrieval在内的这些词项。图3-4 给出了一个例子。

 

•通过一个例子来说明如何利用上述索引结构来处理通配符查询。

•考虑查询re*ve，目标是返回所有前缀是re 且后缀是ve 的词项。

•为此，构造布尔查询 $re AND ve$，这个查询可以在3-gram 索引中进行查找处理，返回诸如relive、remove 及retrieve 的词项。

•然后可以在普通倒排索引中查找这些返回的词项，从而得到与查询匹配的文档。

•然而，使用k-gram索引时往往还需要进行进一步的处理。

•考虑3-gram索引结构的情况，对于查询red*，按照上面的处理步骤就会将原始查询转换为布尔查询$re AND red，这时可能会返回诸如retired的词项，因为它同时包含$re和red。

•但这个结果显然并不满足原始的查询red*，也就是说采用k-gram索引会导致非预期的结果。

•为了解决这个问题，引入一个称为后过滤（postfiltering）的步骤，即利用原始的查询red*对上述布尔查询产生的结果进行逐一过滤。

•过滤时只需要做简单的字符串匹配操作即可。 

•和前面一样，在普通倒排索引中查找上述过滤得到的结果词项，从而得到最后的文档集合。

 

 

拼写校正

•节主要关注查询的拼写校正问题。例如，用户输入carot 时，实际上可能想返回包含词项carrot的文档。

•Google的报告（ www.google.com/jobs/ britney.html）指出，当用户输入britian spears、britney’s spears、brandy spears 或者prittany spears 时，实际上搜索引擎都会当成是britney spears的错误拼写输入来处理.

•考察解决该问题的两个步骤：

第一步基于编辑距离（edit distance），

第二步基于k-gram 重合度（k-gram overlap）

•介绍详细算法之前，首先简单介绍一下搜索引擎是如何实现拼写校正并使其成为用户体验的一部分的。

 

拼写校正的实现

•对于大多数拼写校正（spelling correction）算法而言，存在以下两个基本的原则。

(1)对于一个拼写错误的查询，在其可能的正确拼写中，选择距离“ 最近” 的一个。这就要求在查询之间有距离或者邻近度的概念.

(2) 当两个正确拼写查询邻近度相等（或相近）时，选择更常见的那个。例如，grunt 和grant都是查询grnt 的可能的正确拼写。算法将会从它们之中选择更常见的那个作为最后的拼写结果。

•最简单的情况下，“ 更常见” 可以通过统计各词项在文档集中出现的次数来获得。因此，如果grunt 在文档集中比grant 出现得更多，则选择grunt 作为校正结果。

•在很多搜索引擎中使用了另一种“ 更常见” 的概念，其基本思路是，使用所有其他用户输入的查询中出现最频繁的拼写形式作为最后的选择.

•也就是说，如果用户输入grunt 作为查询的次数相比grant 更多的话，那么用户输入grnt 更有可能是想要查询grunt。

 

拼写校正的方法

•这里主要关注两种拼写校正的方法：一种是词项独立（isolated-term）的校正，另一种是上下文敏感（context-sensitive）的校正.

•在词项独立的校正方法中，不管查询中包含多少个查询词项，其每次只考虑一个词项的校正，也就说在校正时词项之间是相互独立的。上面给出的carot 的例子就属于这一类做法.

•利用这种词项独立校正的方法，很难检测到查询flew form Heathrow 中实际上包含一个错误的词项form（正确的形式应该是from），这是因为在校正时每个词项之间是相互独立的。

•首先，介绍两种词项独立的校正方法：编辑距离方法及k-gram 重合度方法。

•然后，介绍基于上下文敏感的校正方法。

 

编辑距离

•给定两个字符串s1 及s2，两者的编辑距离（edit distance）定义为将s1 转换成s2 的最小编辑操作（edit operation）数.

•通常，这些编辑操作包括：

(i) 将一个字符插入字符串；

(ii) 从字符串中删除一个字符；

(iii) 将字符串中的一个字符替换成另外一个字符。

•对于这些操作，编辑距离。

例如，cat和dog的编辑距离是3。

•实际上，编辑距离的概念可以进一步推广，比如允许不同的编辑操作具有不同的权重.

•例如，将字符s替换成字符p的权重会比将s换成a的权重大（这是因为在键盘上a离s更近，因此花费的代价更小）.

•下面只考虑所有的编辑操作具有等权重的情况。

•众所周知，可以在O（|s1| × |s2|）的时间复杂度下计算两个字符串s1 和s2 的（带权）编辑距离，其中，|si| （i=1,2）表示字符串si 的长度。

•其主要解决思路是采用动态规划算法（如图3-5所示），其中s1 和s2 以字符数组的方式进行存放.

•整数矩阵m 的行数和列数分别是两个字符串的长度，算法在运行中不断填写矩阵元素。算法运行结束后，矩阵第i 行第j 列的元素保存的是s1 的前i 个字符构成的字符串和s2 前j 个字符构成的字符串的编辑距离。

•在图3-5 中的第8～10行描述了动态规划的核心过程，其中求最小值的3 个参数分别对应在s1 中替换一个字符、在s1中插入一个字符和在s2 中插入一个字符的操作。

 •图3-6 给出了一个采用图3-5 中算法计算编辑距离的例子。

•然而，拼写校正问题需要计算出编辑距离给定字符串集合V （对应词项词汇表）和查询字符串q.

•要从V 中寻找和q 具有最小编辑距离的字符串。

•可以把这个问题看成是解码问题，其中编码词（对应V 中的字符串）已经预先定义好.

•最直接的方法是，计算q 到V 中每个字符串的编辑距离，然后选择其中编辑距离最小的字符串。

•很显然，这种穷举的搜索方法开销很大。因此，实际当中使用了多种启发式方法来提高查找的效率。

•最简单的启发式方法是将搜索限制在与查询词具有相同首字母的字符串上，也就是说期望查询的拼写错误不会出现在第一个字符上。

 

拼写校正中的k-gram 索引

•为了进一步限制计算编辑距离后得到的词汇表大小，以下介绍如何通过使用3.2.2 节中所介绍的k-gram 索引来辅助返回与查询q 具有较小编辑距离的词项。

•一旦返回这些词项之后，利用k-gram 索引，就能从中找出与q 具有最小编辑距离的词。

•实际上，利用k-gram 索引来查找与查询具有很多公共k-gram 的词项。只要对“ 具有很多公共k-gram” 进行合理定义，认为上述查找实际上是对查询字符串q 中k-gram的倒排记录表进行单遍扫描的过程。

 •图3-7 给出的是查询bord 的2-gram 索引的一个片段，其中包含3 个2-gram 组成的倒排记录表。

本例当中，这些词项包括aboard、boardroom及border。

•这种通过线性扫描并立即合并倒排记录表的做法十分简单，只需要待匹配词项包含查询q中某个固定数目的k-gram 即可。

•但是这种做法有一个缺点，比如boardroom这种不可能是bord的正确拼写形式的词也会被返回。

•所以，需要计算词汇表中词项与查询q 之间更精细的重合度计算方法.

•比如采用雅可比系数（Jaccard coefficient）就可以对先前的线性扫描合并方法进行修正。

•这里，雅可比系数的计算公式为|A∩B|/|A∪B|，其中A、B 分别是查询q、词汇表词项中的k-gram 集合。

•扫描过程中，一旦扫描到当前的词项t，就快速计算出q 和t 的雅可比系数，然后继续扫描下一个词项。

•如果雅可比系数超过预定的阈值，则将t 输出。否则，往下继续扫描。上述过程表明，在计算雅可比系数时，需要知道q 和t 的k-gram 集合。

•由于是对q中的所有k-gram扫描倒排记录表，因此q中的k-gram集合是已知的，于是问题就变成如何求解t中的所有k-gram。

•理论上，可以穷举出t中所有的k-gram。但是这种做法不仅慢而且在实际中也难以实现。

 •为了说明这一点，重新回到图3-7 中的例子，对于查询q = bord扫描倒排记录表直到t = boardroom。这时知道有2 个2-gram已经匹配上了。

•如果倒排记录表中已经预先记录了boardroom所包含的2-gram的数目（这里是8），那么所有计算雅可比系数的信息都已知，计算公式为：2/（8+3-2）。

•其中，分子为倒排记录的命中数（值为2，分别来自bo和rd），分母为bord及boardroom中的2-gram之和减去倒排记录表的命中数。

 

上下文敏感的拼写校正

•独立的词项拼写校正方法在面对诸如 flew form Heathrow 中的输入错误时无能为力，因为这3个词单独看来拼写都没有错误。

•当输入这类查询时，搜索引擎可能会发现返回的文档非常少，随后也许会提供正确的查询建议flew from Heathrow。

•这种功能的一种简单的实现方法就是，即使每个单词拼写都是对的，仍然要对每个单词找到可能的拼写正确词（采用3.3.4 节中使用的方法），然后尝试对短语中的每个词进行替换.

•比如对于上面flew form Heathrow 的例子，可能会返回如下短语fled from Heathrow 和flew fore Heathrow。

•对每个替换后的短语，搜索引擎进行查找并确定最后的返回数目。

•如果单独的查询有多种可能的正确拼写形式，那么上述方法中穷举过程的开销会非常大，最后就会面对非常多的拼写组合。

•有一些启发式方法可以减小可能的拼写结果空间。

•上述例子中，当对flew 及from 进行扩展时，只保留文档集合或查询日志中的高频组合结果。

•比如，很可能会保留flew from 而不是fled fore 或flea form，这是因为fled fore 很可能比flew from 出现的次数少。

•接下来，仅仅根据高频双词（如flew from）来获得Heathrow的可能的正确拼写。计算双词频率的时候可以使用文档集，也可以使用用户的查询日志。

 

基于发音的校正技术

•最后一项用户容错检索技术与发音校正有关，即拼写错误的原因在于用户输入了一个和目标词项发音相似的查询。该方法尤其适用于人名的查找

•其基本的思路是：对每个词项，进行一个语音哈希操作，发音相似的词项都被映射为同一值。

•该思路最早源于国际警察部门的工作，它们自20 世纪初开始就在全球范围内寻找与犯罪嫌疑人发音相似的人名，而不管这些人名在不同国家的发音是否有所不同。上述思路主要用于专有名词的语音校正。

•这一类通过语音哈希的方法通常统称为soundex 算法。其中，一个原始的soundex 算法的构建方法如下。

（1）将所有的词项转变为四字符的简化形式。基于这些简化形式建立原始词项的倒排索引，该索引被称为soundex 索引。

（2）对查询词项进行同样的操作。

  (3) 当对查询进行soundex 匹配时，就在soundex 索引中搜索。

•soundex 算法很多，主要不同之处在于将词项转变为四字符简化形式的方法不同。

•一个普遍使用的转换方法会得到四字符的编码结果，其中第1 个字符是字母而其他3 个字符是0～9 之间的数字。转换方法如下：

（1）保留词项的首字母；

（2）将后续所有的A、E 、I、O 、U、H、W及Y 等字母转换为0。

 (3) 其他字母的转换规则如下：

 将B、F、P 和V 转换为1；将C、G、J、K、Q、S、X和Z 转换为2；将D 和T 转换为3；将L 转换为4；将M和N 转换为5；将R 转换为6。

(4) 将连续出现的两个同一字符转换为一个字符直至再没有这种现象出现。

(5) 在结果字符串中剔除0，并在结果字符串尾部补足0，然后返回前四个字符，该字符由1 个字母加上3 个数字组成。

•利用上述转换方法,就可将Herman ->H06505->H655。

•给定一个查询（比如hermen），可以计算其soundex 编码然后从soundex 索引中返回具有相同编码的词项，最后再在普通倒排索引中得到最后结果。