第2章 词项词汇和倒排记录表

回顾建立倒排索引的主要步骤：
1.收集要索引的文档。
2.词条化文本。
3.对词条进行语言预处理，生成标准化词条。
4.建立倒排索引，索引每个词项出现的文档。

2.1文档描述和字符序列解码

1.在文档中获取字符序列

文档处理第一步：将文档中的字节序列转换成字符的线性序列
（1）确定编码方案（可看作机器学习分类的问题，但通常通过启发式方法、用户选择或使用提供的文档元数据处理）
（2）确定文档格式（通常通过授权一个处理解码文档格式和字符编码的软件库解决）

*文本本质上是线性结构，字符的概念上的线性顺序并不一定是在页面上看到的顺序，使用现代的Unicode表示概念，文件中的字符顺序与概念顺序相匹配，而显示字符的反转是由呈现系统处理。

2.选择文档单位

索引粒度：假设文档是用于索引的固定单位，有时可能想要将文件所包含的每个文件作为单独的文档进行处理（Unix中），有时可能想要将多个文件合并到单个文档中（Web中),由此引出索引粒度问题。
精度/返回的权衡：如果单位太小，很可能会错过重要的段落，因为词项是在几个小文档上分布的；如果单位太大，倾向于得到虚假的匹配，相关信息很难被发现

*大型文档单位的问题可以通过使用显式或隐式近距离搜索来缓解。

2.2决定词项的词汇

1.词条化

·词条化：给定一个字符序列和一个已定义的文档单位，词条化是将其分割成子序列的过程，这些子序列称为词条，可能同时会丢弃某些字符，比如标点符号。
·词条：是某些特定文档中一系列字符的一个实例，这些字符被分组以作为一个有用的语义单元进行处理。
·类型：是包含相同字符序列的所有词条词项的类。
·词项：是一个（可能是规范化的）类型，它包含在IR系统的字典中。

简单的策略是在所有非字母数字字符上进行分割，而实际的词条化处理时复杂的：
（1）词条化的问题是特定于语言的，大多数语言都有独特的标记模式，如编程语言c++和c#等。
（2）连字符(hyphenation)，如co-education和hold-him-back-and-drag-him-away,自动处理连字符可能是复杂的，既可以作为分类问题处理，也可以通过一些启发式规则处理。
（3）空白区域上的分割，如York University 的搜索会返回包含New York Universty的文档，即在空格上分割词条化导致糟糕的检索结果。
（4）不同种语言问题，如法语中撇号的不同用法、德语在没有空格的情况下写复合名词等。

*对于布尔或*文本查询，希望对文档和查询词进行完全相同的词条化，通常通过使用相同的记号赋予器处理查询，保证文本中的字符序列总是与在查询中输入的相同序列匹配。
*东亚语言，如汉语、日语、韩语和泰语中文字没有任何空格。一个方法是将单词分割作为先前的语言处理。另一种方法是放弃基于文字的索引，并通过字符的短子序列完成所有的索引。

2.删除常用词项：停用词

·停止词：一些非常常见的在帮助选择匹配用户需求的文档时显得毫无价值，完全被排除在词汇表之外的词。

√ 决定停用词表的普遍策略：通过“收集频率”(每个词项出现在文档集合中的总次数)排序词汇,取最常见的词项,经常手动过滤域与被索引文档相关的语义内容。
√ 优点：使用停用词表可显著减少系统必须存储的倒排记录表数量
√ 缺点：短语搜索中可能不正确，如“President of the United States”包含两个停止词，比President AND “United States”更精确

√ 在路透社-rcv1中常见的25个语义非选择性词的停用词表：

√ 现代IR系统总体趋向于不去掉停用词原因：
良好的压缩技术大大降低了存储普通单词倒排记录表的成本。
标准的词项权重如何导致非常普通的词对文档排名影响不大。
一个带有影响排序的索引的IR系统可以在权重变小的时候终止对倒排记录表的扫描，即使停止词列表很长，普通的单词也不会引起平均查询中产生大量额外的处理成本。

3.词条归一化（词项的等价分类）

·词条归一化：将不完全一致的词条规范为一个等价类的过程，即使在词条的字符序列中存在表面差异，也会发生匹配。

（1）最规范化的标准方法：隐式地创建等价类，使用映射规则来删除句点、连字符（“anti-discriminatory"和"antidiscriminatory"映射到词项"antidiscriminatory”）
（2）创建等价类的另一种方法：维持非归一化词条之间的关联关系，这个方法可以扩展到手工构建的同义词列表，比如car和automoble。

√两种方式实现：
①通常的方法：索引非归一化的词条，并维护多个词汇表条目的查询扩展列表，以考虑特定的查询词项。查询car时，合并car和automobile的倒排索引。
②另一种方法：在索引结构中执行扩展。当文档包含automobile时，也将它在car下进行索引。
√优缺点：这些方法中的任何一种都比等价类的效率低得多，更多的倒排记录表需要存储和合并。第一种方法添加了查询扩展字典，在查询时需要更多的处理，而第二个方法则需要更多的空间来存储帖子；由于现代存储成本，不同的倒排记录表使灵活性增加。

（3）常用的归一化形式及实现：
口音和变音符号：通过规范化词条消除变音符，最好将所有的单词与一种没有变音符的形式等同起来。
样例折叠：通过将所有字母减少到小写字母来进行样例折叠

*被索引的文档集合可以包括来自许多不同语言的文档：最常见的情况是，语言被检测到，语言特定的词条化和规范化规则应用于预先确定的粒度。当文档集合包含多种语言时，单个索引可能必须包含几种语言的词项。一种选择是在文档上运行语言识别分类器，然后在词汇表中为其语言词条化词项。
*处理外来词或复杂词汇时，拼写可能不清楚，可能有不同的音译标准，一种解决方法是使用启发式到等价类，或者用语音对等物扩展词项。传统和最著名的算法是Soundex算法。

4.词干还原（stemming）和 词形归并（lemmatization）

词干还原和词形归并的目标：减少屈折形式,有时将一个词的相关派生形式转变为基本形式。例如：am,are,is ->be ; car,cars,car’s,cars’ -> car

·词干还原（stemming）：通常指的是一种粗糙的启发式过程，它可以将单词的末端切掉，希望大多数时候都正确地实现这个目标，并且常常包括取消派生的词缀。如果遇到词条saw，可能会返回s。
·词形归并（lemmatization）：通常指的是用词汇和词汇的形态分析处理，通常目的是去除曲折的结尾，并返回一个词的基本或字典形式。遇到词条saw，词形归并会尝试返回see或saw（取决于词条的使用是作为一个动词还是一个名词）

（1）不同点：词干还原在一般情况下会将多个派生相关词合并在一起，而词形归并通常只将同一词元的不同屈折形式进行合并。Stemmers使用特定于语言的规则，但它们需要的知识比一个lemmatizer需要更少的知识，它需要一个完整的词汇表和形态分析来精确地使单词化。
（2）对词干还原和词形归并的语言处理通常是由一个附加的插件组件到索引过程来完成的，有许多这样的组件存在，包括商业和开放源码。
（3）常见的词干还原算法：Porter stemmer、Lovins stemmer、Paice stemmer

2.3 快速倒排记录表合并，通过跳表指针

回顾基本倒排记录表的交集操作：同时遍历两个倒排记录表，如果列表长度是m和n，那么交集时间线性，O（m+n）。

·跳跃表：倒排记录表合并算法的优化，通过使用跳跃指针（在索引时）增加倒排记录表

（1）高效合并：以图2.1为例。假设在每个列表上匹配了【8】，并将其移动到结果列表中，推进指针，上面的列表给出【16】，下一个列表有【41】。最小的项是顶部列表中的元素【16】。首先应检查跳跃表指针，并注意到【28】也小于【41】，而不是简单地推进上面的指针。因此，我们可以遵循跳跃表指针，然后将上指针推进到【28】。避免了上一列表的【19】和【23】。
（2）放置跳跃：是一个权衡。跳表指针越多意味着跳跃时间越短。但它也意味着大量的比较和大量的空间存储跳过指针。跳表指针越少意味着很少的指针比较，但是跳跃时间变长，这意味着跳越的机会将会减少。
√ 简单的放置跳跃的启发式方法：对于一个长度为P的倒排记录表，使用间隔的跳跃指针。这种启发式可以改进;它忽略了查询词项分布细节。
√ 如果索引是相对静态的，那么构建有效的跳跃指针是很容易的;如果一个倒排记录表因为更新而不断变化，构建会较难。恶意删除策略可能使跳跃表无效。

图2.1 有跳跃指针的倒排记录表

图2.2 带跳跃指针的倒排记录表的合并算法

2.4 位置信息和短语查询

大多数搜索引擎支持双引号语法用于短语查询，多达10%的web查询是短语查询，更多的是隐式短语查询（如人名），不使用双引号。为了能够支持这样的查询，对于倒排记录表来说，仅仅是包含单个词项的文档列表是不足够的。

1.双词索引（Biword indexes）

（1）双词索引（Biword indexes）

√ 处理短语的一种方法：将文档中的每一对连续的词项看作一个短语。
例如， Friends，Romans，Countrymen会产生二元接续词对:
friends romans，romans countrymen

√ 将每个词对看成一个词项，更长的短语可以通过分解来处理。
例如，查询 stanford university palo alto分成如下的布尔查询：
“stanford university” AND “university palo” AND “palo alto”

（2）扩展的双词（Extended Biword）

√ 首先对文本进行词条化，并执行词性标注。然后将词项分组到名词中，包括专有名词（N）和函数词，包括文章和介词（X），以及其他类。现在，我们认为任何形式的NX*N的形式都是一个扩展的双词。每一个这样的扩展双词都在词汇表中被定义为一个词项。
√ 要使用一个扩展的双词索引来处理查询，我们还需要将其解析为Ns和Xs，然后将查询分割成扩展的双词，在索引中查找。
√ 存在的问题：
在不检查文档的情况下，我们不能验证与布尔查询匹配的文档是否真正包含了最初的单词短语。
在将较长的查询解析成布尔查询时，这种算法并不总是以直观的方式工作。

·短语索引（phrase index）：双词索引的概念可以扩展到更长的单词序列，如果索引包含可变长度的单词序列，那么它通常被称为短语索引。

2.位置索引(Positional indexes)

·位置索引：对于索引词汇表中的每一项，都储存文档的位置(position1,position2,…)，每个位置都是文档中的词条索引。如：

图 2.3 to 和be的位置索引

√要处理短语查询，仍需要为每个单独的词项访问倒排索引。在合并操作中，使用与以前相同的通用技术，但不是简单地检查两个词项是否都在一个文档中，还需要检查它们在文档中的位置是否与查询短语一致。这需要计算单词之间的偏移距离。
√同样的通用方法也适用于k字近距离搜索：
在这里，/k表示在k个单词（在任何一边）。显然位置索引可以处理邻近式查询，而双词索引不能。

图2.4一种用于k个词近距离搜索的算法，该算法找到两个词项在k个单词中出现的位置，并返回一个三元组列表，给出p1和p2的词项位置。

√ 位置索引的大小。采用位置索引可以显著地扩展所需的倒排记录表存储，事实上，移动到位置索引也会改变一个倒排记录表交集操作的渐近复杂度，因为要检查的项目的数量不是由文档数量限制的，而是由文档集合t中的词条总数限制的。也就是说，布尔查询的复杂性是O（T）而不是O（N）。然而，大多数应用程序都别无选择，只能接受这一点，因为大多数用户现在期望拥有短语和近距离搜索的功能。

3.组合方案（Combination schemes）

√ 如果用户经常查询特定的短语，如Michael Jackson，那么合并位置索引的倒排记录表是低效的。
√ 组合策略：用于某些查询使用短语索引或者仅使用双词索引，其他短语查询使用位置索引。√ 在短语索引中包含的好的查询可以基于最近的查询行为统计。但这并不是唯一的标准：成本高的短语查询是那些常见的单个单词，但组合起来却相对少见的短语。
添加Britney Spears作为短语索引条目，可能只会给查询加速3倍，因为大多数提到这两个单词的文档都是有效的文档，而添加The Who作为短语索引可能会使查询速度提高1 000倍。因此后者更可取，即使它是相对不那么常见的。
√ Williams等人（2004）评估了一种更复杂的方案，它使用这两种方法的索引，以及部分下一个词索引。对于每一项，下一个单词索引记录了在文档中下一个词项。他们的结论是，这样的策略允许在使用位置索引的1/4的时间内完成web短语组合查询，而单独使用位置索引的空间则要多出26%。