『IR 信息检索入门必看』#8 倒排索引模型（简明）

文件组织架构，也称 index (索引)，常用于提升一个检索系统的性能。

回顾向量空间模型，我们知道在查询时，命中的 doc 应该是与 query 最为相近的几个向量。当查询时，若只在所有 可能相似的文档 （至少含有一个 query 中的关键词）中查找，可以大大减少资源浪费。

那么就需要先得到 query 中各个 term 出现过的文档，再取 并集 ，最后在并集中进行相似度的计算——「 过滤 」思想。

此时用特殊的索引方式，就可以更快地实现文档的过滤。有人提出 Hash 的设想，但是 Hash 的缺点在于不能模糊匹配，当用户的 Query 和词典中的 term 略有差距时，可能在 hash table 中会相距十分遥远。

我们通过一组对比，引入「 倒排 」的概念：

由此我们可以得到倒排文件组织架构的 构成 ：

有了上述的架构，当用户输入 query 时，我们可以提取出 term，直接访问对应的 Index file，再根据链接来到 Posting file。对于多个 term，可以先完成交、并等逻辑运算，得到结果后，再去访问过滤后的文档集。

由此，我们可以知道当爬取到新的文档时，构建索引的步骤：

接下来介绍搜索引擎如何解析一个新爬取到的文档，这个过程往往是离线进行的（在线进行的是用户查询过程）。

而由于文档的多样性，往往解析过程中会面临各式各样的问题：文件格式、各国语言、字符编码、停用词等。这些问题往往用 启发式 （heuristically）的方法解决。

Token 来自文档的原始字符串，是根据空格划分提取出的原始单词。在实际中，要考虑：是否保留 's 、是否保留连字符、专有名词是否拆开、数字嵌入等子问题。

而针对不同语言，也有更多新的问题：法语中大量的 ' 使用、德语中名词复合现象、中文日文不适用空格分词、日语的平假片假、阿拉伯语的书写次序等。

在文本中，往往还需要把最频繁出现的无意义词停用。在文档解析中，如何利用停用词进行压缩空间？在查询优化中，如何判别停用词？当停用词有意义时，如何识别？这些都是需要考虑的问题。

在英语中，通常时以定义「 等价集 」（equivalence classing）来归并词项。通常将单词归并到其原型，而对于特殊的单词有特殊的规则，例如规定 “U.S.A.” 归并于 “USA”，规定 “anti-discriminatory” 归并于 “antidiscriminatory”。

对于有的单词，不同形式可能含有不同语义，例如 window/windows/Windows。此时在查询时可以先做 不对称展开 （asymmetric expansion），对展开项搜索后取并集。

主要针对 Synonyms (同义词)、Homonyms (同形同音异义词)，这种情况下也可以利用等价集和不对称展开解决。

此外，当用户查询中有英文拼写错误时，常用的方法是 Soundex (探测法)，返回同音字串。Soundex 是基于语音启发式方法生成的 语音等价集 。这种方法在汉语拼音中同样有很大应用。

将单词的名词、动词、形容词等形式统一归并到 词根 ，将单复数、人称所有格、时态等统一归并到 原型 。

解析完文档后，我们可以将新的文档直接存入文档集，也可以利用 摘要生成 技术生成 Surrogates (文档替代品)，减少存储空间。

此外，当我们搜索到页面文档时，其文件格式可能各不相同，如 HTML、XML 等，故检索到网页后还需要进行 Page Purifing (文档净化)，从而获得便于识别的文本文档和内部链接。

之前的文章介绍过，用于连接 term 和 doc 的词典表往往是个稀疏矩阵。而倒排文件用 链表 的形式存储每一行的内容，即包含此 term 的所有 doc 及其基本信息，串接而成。链表中的每个元素称为一个 posting (记录)。

其中，基本信息可以包含：Document ID (文档的唯一标识)、Location Pointer (该文档在 Doc file 中的位置)、原始的权重因子。

存储原始的权重因子，是为了在查找的时候更方便的计算词项权重。可以包括 df、tf、最大频度、总文档数等等。

此外，链表中的元素以 Doc ID 排序，这样存储有利于多页倒排表的 合并 匹配。

索引文件通常以词典的形式存储 term ID、含有该 term 的文档数以及该 term 在记录文件中的位置（指针）。

以下列出几种常用的索引文件组织形式：

前文提到，在解析一篇文档获得索引时，最简单的方法就是先提取 token，再获得 term 作为索引。而在真正高效的索引模型（Index Model）中，往往要先对文档进行 特征选取 ，从而构成索引。

而特征选择问题，可以转化为词项权重（term weighting）计算，一篇文档中权重较大的 term 往往更能表示这篇文档。

在前面的文章中有提到，tf 及其衍生的权重计算方法，是 IR 模型中最常用的权重计算方法。这里就不再重复介绍，仅提及一个有趣的定理 Zipf's Law 。

该定理描述了如下现象：在一个大的文档集中，统计出各个词项的 tf 排名后，记排名为 r ，频率为 f ，则有

而在实际中，排名最高的词项通常都是停用词，最「 重要 」的词往往词频不是很高，而最罕见的词往往没有普遍价值。这也与 tf·idf 的思想契合，下图说明了这一点。

在倒排文档中，移除停用词和罕见词、保留重要词，可以节约大量的记录空间。

对于一个确定大小的文档集，需要多少词项才能很好的索引全部文档呢？这便是根据文档集大小确定词典大小（Lexicon Size）的问题。 Heap's Law 对此进行了估算：

其中， K 通常取 10 到 100 间的整数， 通常取 0.4 到 0.6 之间的小数。绘制出的图如下：

在一个向量空间中，文档由 基向量 加权构成的向量表示。

我们可以计算文档之间的相似度，相似度越高，代表空间越紧凑，反之则越松散。计算文档集两两之间的相似度需要 的复杂度。

当然，如果先计算出一个「 平均文档 」，再计算其他文档与其的相似度，则只需要 的复杂度。

词项判别模型则是通过 引入 一个新的 term 作为基向量，观察相似度的变化分析该 term 的重要性。大致的思想是：