搜索引擎核心技术与算法 —— 词项词典与倒排索引优化

前言

上一章我们对搜索中最常用的倒排索引有了一个初步的认识，今天我们一起来进一步学习倒排索引表的建立与优化的相关算法。

首先回顾一下构建倒排索引的几个主要步骤：
(1) 收集待建索引的文档；
(2) 对这些文档中的文本进行词条化；
(3) 对第2步产生的词条进行语言学预处理，得到词项；
(4) 根据词项对所有文档建立索引。

可以看到，上诉过程中非常重要的一步就是获得词项，那么词项是什么，又是怎么获得的呢？

在确定词项前，我们需要明确三个概念：

词条：一段文本中有效词的子序列，其中每个子序列称为一个词条。

词条类：相同词条构成的集合。

词项：一个词项指的是在信息检索系统词典中所包含的某个可能经过归一化处理的词条类。（词项集合和词条集合可以完全不同，比如可以采用某一个分类体系中的类别标签作为词项。当然，在实际的信息检索系统中，词项往往和词条密切相关）

三者关系如下：

下面，让我们一起学习这几者是如何一步步变化得来的。

1.1 词条化

词条化过程词条化的主要任务就是确定哪些才是正确的词条。比如，对于简单的句子将字符串进行拆分并去掉标点符号即可。

然而，上面的例子仅仅代表的是一种最简单的情况。实际上即使对于单词之间存在空格的英文来说也存在很多难以处理的问题。比如，英文中的上撇号“’”既可以代表所有关系也可以代表缩写，应当在词条化过程中究竟应该如何对它进行处理?参考下面的例子:

对其中的“ O’Neill” 来说，词条化的结果可能有如下几种形式可以选择，那么到底哪一种才正确？

对于可能的各种拆分策略来说，最后的选择结果会决定哪些布尔查询会被匹配上、哪些不会被匹配上。给定查询neill AND capital，上述五种拆分策略中有3种会被匹配上（即第1、4、5种情况）。而如果给定查询o’neill AND capital，则在没有对查询进行任何预处理的情况下，上述策略中只有一种能匹配上。不管是输入布尔查询或者自由文本查询，人们总是希望对文档和查询进行同样的词条化处理，这往往通过采用相同的词条化工具来实现。这样做能够确保文本与查询中的同一字符串序列的处理结果相一致。

在词条化的过程中，需要注意以下几个问题：

（1）对大多数语言特别是一些特定领域的语言来说，往往有一些特定的词条需要被识别成词项，如编程语言“C++”和“C#”、“B-52”之类的飞行器名字或者叫“M*A*S*H”的电视秀节目等等，这时候就不能简单的去掉文本中的符号了，这里通常需要建立专有名词字典来解决。

（2）字符序列类型包括邮件地址（如jblack@mail.yahoo.com）、URL（如http://stuff.big.com/new/specials.html）、IP地址（如142.32.48.231）和包裹追踪号码（1Z9999W99845399981）等等。一种做法是不对包括货币量、数字、URL等在内的词条进行索引，这是因为如果对这些词条进行索引则会显著扩大索引的词汇量。当然，这样做会对用户的搜索产生一些限制。比如，人们可能会在程序缺陷（bug）库中搜索错误发生的行号，但是经过上述处理之后的系统显然不能返回正确结果。如果这类数据需要词条化，那么利用正则是一个不错的办法。

（3）即使根据空格进行拆分有时也会将概念上本应该看成单个词条的对象分开，比如一些名称（San Francisco，Los Angeles）、外来短语（au fait）或那些书写时可分可合的复合词（white space vs whitespace）。其他的例子还包括电话号码[（800）234-2333]、日期（Mar11,1983）等。如果在空格处拆分这些对象可能会导致很差的检索结果，比如，输入York University（约克大学）时会返回包含New York University（纽约大学）的文档。连字符和空格甚至会互相影响。这种情况就和中文文本中分词类似了。

（4）对于一些主要的东亚语言（如汉语、日语、韩语和泰语等）来说，由于词之间并不存在空格，所以问题更加严重。分词的方法包括基于词典的最大匹配法（采用启发式规则来进行未定义词识别）和基于机器学习序列模型的方法（如隐马尔可夫模型或条件随机场模型）等，后者需要在手工切分好的语料上进行训练（分词作为NLP领域一个非常重要的研究内容，我们后面会专门独立一章来介绍分词常用算法ヾ(?°?°?)）。由于存在多种切分可能，上述分词方法都有可能导致错误的切分结果，因此，永远不能保证只能得到一个完全一致的唯一切分结果。另一个解决方法则摒弃了基于词的索引策略而采用短字符序列的方法（如字符的k-gram方法）。这种方法并不关心词项是否会跨越词的边界。该方法之所以能够引起人们的兴趣主要有以下3个原因:第一，一个汉字更像是一个音节而不是字符，它往往具有语义信息;第二，大部分词都很短（最常见的汉语词长度是2个字）;第三，由于缺乏公认的分词标准，词的边界有时也很难确定。

某些情况下，一些常见词在文档和用户需求进行匹配时价值并不大，需要彻底从词汇表中去除。这些词称为停用词（stop word）。一个常用的生成停用词表的方法就是将词项按照文档集频率（collection frequency，每个词项在文档集中出现的频率）从高到低排列，然后手工选择那些语义内容与文档主题关系不大的高频词作为停用词。停用词表中的每个词将在索引过程中被忽略。

不对停用词建立索引一般情况下不会对系统造成太大的影响，比如搜索时采用the或by进行查询似乎没有什么意义。但是，对于短语查询来说情况并非如此，比如短语查询President of the United States中包含两个停用词，但是它比查询President AND“United States”更精确。如果忽略掉to，那么flights to London（因为这里的to并不是以介词的身份出现）的意义将会丢失。搜索Vannevar Bush的那篇经典文章As we may think时，如果将前3个单词都看作停用词，那么搜索将会很困难，因为系统只返回包含think的文章。更为严重的是，一些特定的查询类型会受到更大的影响。比如一些歌名或者著名的诗歌片段可能全部由常用的停用词组成（如To be or not to be，Let It Be，I don’t want to be等）。

将文档和查询转换成一个个的词条之后，最简单的情况就是查询中的词条正好和文档中的词条相一致。然而在很多情况下，即使词条之间并不完全一致，但实际上人们希望它们之间能够进行匹配。比如查询USA时我们希望能够返回包含U.S.A.的文档。

词条归一化（token normalization）就是将看起来不完全一致的多个词条归纳成一个等价类，以便在它们之间进行匹配的过程。

最常规的做法有以下两种：

（1）隐式地建立等价类，每类可以用其中的某个元素来命名。比如，在文档和查询中，都把词条anti-discriminatory和antidiscriminatory映射成词项antidiscriminatory,这样对两个词中的任一个进行搜索，都会返回包含其中任一词的文档。这种处理方法的优点在于:一方面，等价类的建立过程是隐式的，不需要事先计算出等价类的全部元素，在映射规则下输出相同结果的词项一起构成等价类集合;另一方面，仅仅构建“去除字符”这种映射规则也比较容易。

（2）显示建立等价类，维护多个非归一化词条之间的关联关系。该方法可以进一步扩展成同义词词表的手工构建，比如将car和automobile归成同义词。这些词项之间的关系可以通过两种方式来实现。第一种常用的方式是采用非归一化的词条进行索引，并为某个查询词项维护一张由多个词组成的查询扩展词表。当输入一个查询词项时，则根据扩展词表进行扩展并将扩展后得到的多个词所对应的倒排记录表合在一块（如下图一）。另一种方式是在索引构建时就对词进行扩展（如下图二）。比如，对于包含automobile的文档，我们同时也用car来索引（同样，包含car的文档也用automobile来索引）。

另一方面，由于两个关联词的扩展词表之间可以存在交集但不必完全相同，所以上述两种方式相对于隐式建立等价类的方法来说更具灵活性。这也意味着从不同关联词出发可以进行不对称的扩展。下图出了一个例子。该例子中，如果用户输入windows，那么我们希望返回包含Windows操作系统的文档。但是如果用户输入window，虽然此时可以和小写的windows相匹配，但是不太可能会和Windows操作系统中的Windows相匹配。

隐式建立等价类或查询扩展的使用幅度仍然是个开放的问题。适度使用绝对没错，但是过度使用很容易会在无意间造成非预期的扩展结果。例如，通过删除U.S.A.中的句点可以把它转化成USA，由于在首字母省略用法中存在这种转换模式，所以上面的做法乍看上去非常合理。但是，如果输入查询C.A.T.，返回的很多包含cat的文档却肯定不是我们想要的结果。

接下来我们将给出一些在实际当中会遇到的词条归一化问题及其对策：

（1）重音及变音符号问题

英语中变音符号的使用越来越少见，尽管如此，人们很可能希望cliche和cliché或者naive和na?ve能匹配。这可以通过在词条归一化时去掉变音符号来实现。而在许多其他语言中，变音符号属于文字系统的常规部分，不同的变音符号表示不同的发音。有时候，不同单词之间的区别只是重音不同。比如，西班牙语中，pe?a的意思是“悬崖”，而pena的意思却是“悲哀”。然而，关键并不是规范或者语言学问题，而是用户如何构造查询来查找包含这些词的文档。

（2）大小写转换问题

大小写转换（case-folding）问题的一个一般处理策略是将所有的字母都转换成小写。这种做法通常的效果不错，比如这样可以允许句首的Automobile和查询automobile匹配。对于Web搜索引擎来说，这种做法也很有好处，因为大多数用户输入ferrari时实际想找的是Ferrari（法拉利）车。

（3）英语中的其他问题

英语中还存在一些独特的归一化做法。比如，用户希望将ne’er和never、英式英语的拼写方式colour和美式英语的拼写方式color等同起来。日期、时间和其他类似的对象往往以多种形式出现，这给归一化造成了额外的负担。人们可能希望将3/12/91和Mar.12，1991统一起来。但是，要正确处理这个例子将会十分复杂，因为在美国，3/12/91指的1991年3月12日（Mar.12,1991），而在欧洲，却指的是1991年12月3日（3Dec.1991）

出于语法上的要求，文档中常常会使用词的不同形态，比如organize、organizes和organizing。另外，语言中也存在大量意义相近的同源词，比如democracy、democratic和democratization。在很多情况下，如果输入其中一个词能返回包含其同源词的文档，那么这样的搜索似乎非常有用。

词干还原和词形归并的目的都是为了减少屈折变化的形式，并且有时会将派生词转化为基本形式。

词干还原：通常指的是一个很粗略的去除单词两端词缀的启发式过程，并且希望大部分时间它都能达到这个正确目的，这个过程也常常包括去除派生词缀。

词形归并：通常指利用词汇表和词形分析来去除屈折词缀，从而返回词的原形或词典中的词的过程，返回的结果称为词元。

这两个过程的区别还在于:词干还原在一般情况下会将多个派生相关词合并在一起，而词形归并通常只将同一词元的不同屈折形式进行合并。词干还原或词形归并往往通过在索引过程中增加插件程序的方式来实现，这类插件程序有很多，其中既有商业软件也有开源软件。

上一章我们讲解了倒排记录表的基本合并算法:同时在两个表中遍历，并且最后算法的时间复杂度为记录表大小的线性函数。假定两个表的大小分别是m和n，那么合并过程有O（m+n）次操作。很自然的一个问题就是我们能否做得更好？也就是说，能否在亚线性时间内完成合并过程？下面我们将看到，如果索引变化不太频繁的话那么答案是肯定的。

如果待合并的两个倒排表数据量很大, 但是交集很少时, 会是什么情况呢?

[1, 2, 3, 4, 5, ... 10001, 10005]
[1, 10001, 10008]

如果对这两个做合并操作, 最后的交集结果只有[1, 10001]2个元素, 但是却要做10001次移动和比较操作, 所以肯定有什么办法来优化这一点. 可能你已经想到了, 我们做了这么多无用比较, 是因为我们每次指针向前移动的步子太小了点, 如果我们在每次比较后向前多移动一点, 可以忽略很多无用的操作. 这就是跳表的思想.

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

我们以上图为例来先考虑快速合并的问题。假定我们在两个表中遍历一直到发现共同的记录8为止，将8放入结果表中之后我们继续移动两个表的指针。假定第一个表的指针移到16处，而第二个表的指针移到41处，两者中较小项为16。这时候我们并不继续移动上面的表指针，而是检查跳表指针的目标项，此时为28，仍然比41要小，因此此时可以直接把上表的表指针移到28处，这样就跳过了19和23两项。基于跳表的倒排记录表合并算法有很多变形，它们的主要不同可能在于跳表检查的时机不一样。

我们再考察另一个问题，即在什么位置上放置跳表指针?这里存在一个指针个数和比较次数之间的折中问题。跳表指针越多意味着跳跃的步长越短，那么在合并过程中跳跃的可能性也更大，但同时这也意味着需要更多的指针比较次数和更多的存储空间。跳表指针越少意味着更少的指针比较次数，但同时也意味着更长的跳跃步长，也就是说意味着更少的跳跃机会。放置跳表指针位置的一个简单的启发式策略是，在每个㏒?P处均匀放置跳表指针，其中P是倒排记录表的长度。这个策略在实际中效果不错，但是仍然有提高的余地，因为它并没有考虑查询词项的任何分布细节

#基于跳表的倒排记录表快速合并算法
a = range(10008)
b = [1, 10001, 10008]
 
i = j = 0
result = []
step = 100
count = 0
while i < len(a) and j < len(b):
    if a[i] == b[j]:
        result.append(a[i])
        i = i +1
        j = j + 1
        count = count + 1
    elif a[i] < b[j]:
        while (i + step < len(a)) and a[i+step] <= b[j]:
            i = i + step
            count = count + 1
        else:
            i = i + 1
            count = count + 1
    else:
        while (j + step < len(b)) and b[j+step] <= a[i]:
            j = j + step
            count = count + 1
        else:
            j = j + 1
            count = count + 1
print(result)  #[1, 10001]
print(count)   #207

上面代码中故意构造了一个很大的集合[0 ... 10007], 然后用变量count作为计数器来分析两个算法分别执行的操作次数, 可以看到采用跳表算法时(我们模拟了step=100)的计算次数是207, 而用之前的方式计算次数是10008, 可见性能提升了很多倍.

这里有几点说明下:

1. 这里为了简单说明跳表的思路, 全部用了数组表示倒排表, 其实真实的数据结构应该是链表结构(linked list). 这才符合磁盘存储结构.

2. 跳表的原始结构算法比这个复杂, 而且根据场景的不同, 跳表有不同的实现. 这里因为不是利用跳表的快速查询功能, 所以没有多级指针索引概念, 详细跳表实现查考: Skip Lists: A Probabilistic Alternative to Balanced Trees

先来看一个问题，当用户将“Stanford University”这个查询中的两个词看成一个整体的时候，用户是为了查询和Stanford University这所高校相关的信息。但是如果是基于布尔查询（详见第一章）的话，将会被拆解成Stanford AND University进行查询，从而一篇含有句子The inventor Stanford Ovshinsky never went to university的文档会推送给用户，这并不是我们想要的。那么如何解决这个问题呢？这里引入二元词索引。

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

friends romans

romans countrymen

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

分成如下的布尔查询：

“stanford university” AND “university palo” AND “palo alto”

可以期望该查询在实际中效果会不错，但是偶尔也会有错误的返回例子。对于该布尔查询返回的文档，我们并不知道其是否真正包含最原始的四词短语。在所有可能的查询中，用名词和名词短语来表述用户所查询的概念具有相当特殊的地位。但是相关的名词往往被各种虚词分开，比如短语the abolition of slavery或者renegotiation of the constitution。这种情况下，可以采用如下方法来建立二元词索引:首先对文本进行词条化然后进行词性标注，这样就可以把每个词项归成名词（N，也包括专有名词）、虚词（X，冠词和介词）和其他词。然后将形式为NX*N非词项序列看成一个扩展的二元词。利用上述算法，可以将查询cost overruns on a power plant分析成“cost overruns”AND“overruns power”AND“power plant”，实际上忽略中间的那个二元词所形成的查询的效果会更好。如果使用更精确的词性模式来定义扩展二元词可能会取得更好的结果。

二元词索引的概念可以扩展到更长的词序列（三元、四元...），如果索引中包含变长的词序列，通常就称为短语索引（phrase index）。实际上，利用二元词索引来处理单个词的查询不太方便（必须要扫描整个词汇表来发现包含该查询词的二元词），因此同时还需要有基于单个词的索引。尽管总有可能得到错误的匹配结果，但是在长度为3或者更长的索引短语上发生匹配错误的可能性实际上却很小。然而在另一方面，存储更长的短语很可能会大大增加词汇表的大小。穷尽所有长度超过2的短语并维护其索引绝对是一件令人生畏的事情，即使只穷尽所有的二元词也会大大增加词汇表的大小。

很显然，基于上面谈到的原因，二元词索引并非标准的解决方案。实际中更常用的一种方式是采用所谓的位置信息索引（positional index，简称位置索引）。在这种索引中，对每个词项，以如下方式存储倒排记录

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

假如用户输入"boy friend"进行搜索, 如果只要出现了"boy" 或者 "friend"的文档都搜索出来, 那么下面三篇文档都满足要求:

1. the boy and the girl are good friends
2. you are my boy friend
3. the boy has many friends.

现在用户应该只想搜出文档 2 出来. 基于"位置信息索引"方式, 我们可以做到这一点.

这种搜索方法类似于k词近邻搜索 —— a /k b

这里，/k 意味着“ 从左边或右边相距在 k 个词之内，若k=1，则意味着a、b相邻” 。很显然，位置索引能够用于邻近搜索，而二元词索引则不能。

有了这个索引存储结构, 要找出不同的短语就比较容易了, 比如用户想搜索"boy friend", 就可以转化成 boy /1 friend 即可以完成要求。只要找出在文档中, boy出现的位置刚好在friend前一个位置的所有文档. 所以文档2满足我们的要求被搜索出来. 下面用python简单实现下这个算法:

# p1, p2是两个上述结构的倒排记录表, k是两个词项的位置在k以内
def positional_interset(p1, p2, k):
	result=[]# 最终的搜索结果, 以(文档id, 词项1的位置, 词项2的位置)形式存储
    while p1 is not None and p2 is not None: # 当p1, 和 p2 都没有达到最尾部时
        if p1.docId==p2.docId: # 如果两个词项出现在同一个文档中
            l=[]# 临时变量, 用来存储计算过程中满足位置距离的位置对信息
            pp1=p1.position
            pp2=p2.position
            while pp1 is not None: # 先固定pp1的位置, 循环移动pp2的位置进行检查
                while pp2 is not None:
                    if abs(pp1.pos - pp2.pos) <=k: # 如果pp1和pp2的距离小于k, 则满足要求
                        l.append(pp2.pos) # 添加到临时变量
                        pp2=pp2.next # pp2向后移一个位置
                    elif pp2.pos > pp1.pos: # 如果pp2当前的位置相对pp1已经超过给定的范围(构不成短语要求), 则停止移动pp2, 后续后把pp1再往前移动一个位置
                        break
                while not l and abs(l[0]- pp1.pos) > k: # 当每次移动一次pp1时, l里面会存储上一次计算所得的pp2的一些位置, 这里要过滤那些相对于当前pp1最新位置, 那些不再满足要求的pp2的位置
                    del l[0]
                for p in l:
                    result.append[(p1.docId, pp1.pos, p)]# 把最终的结果加入到结果集中
                pp1=pp1.next # pp1向前移动一个位置, 重复上次逻辑计算
            p1=p1.next
            p2=p2.next
        elif p1.docId < p2.docId:
            p1=p1.next
        else:
            p2=p2.next

毋庸置疑，采用位置索引会加深倒排记录表合并操作的渐进复杂性，这是因为需要检查的项的个数不再受限于文档数目而是文档集中出现的所有的词条的个数 T。也就是说，布尔查询的复杂度为Θ (T)而不是Θ (N)。然而，由于用户往往期望能够进行短语搜索和邻近搜索，所以实际中的大部分应用并没有其他选择而不得不采用这种做法。

二元词索引和位置索引这两种策略可以进行有效的合并。假如用户通常只查询特定的短语，如Michael Jackson，那么基于位置索引的倒排记录表合并方式效率很低。一个混合策略是:对某些查询使用短语索引或只使用二元词索引，而对其他短语查询则采用位置索引。短语索引所收录的那些较好的查询可以根据用户最近的访问行为日志统计得到，也就是说，它们往往是那些高频常见的查询。当然，这并不是唯一的准则。处理开销最大的短语查询往往是这样一些短语，它们中的每个词都非常常见，但是组合起来却相对很少见。

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

本章节主要对词项的形成和倒排索引的两个升级版算法做了一个粗略的介绍。虽然这是搜索引擎中最基础的东西，但值得细细挖掘的地方还有很多，毕竟每一个小点的改善都可以极大的提高用户体验，搜索引擎学习之路道阻且长呀~加油(｀?ω?′)

参考文献：

• 《信息检索导论 修订版》
• 倒排索引优化 - 跳表 —— 博客园 海鸟

更多以及后续内容，请各位看官移步微信公众号「夕小瑶的卖萌屋」 ，会有更加精彩的内容等着大家哦 ?|?|?*~●