【序】

    先介绍一下正向索引: 当用户发起查询时（假设查询为一个关键词），搜索引擎会扫描索引库中的所有文档，找出所有包含关键词的文档，这样依次从文档中去查找是否含有关键词的方法叫做正向索引。互联网上存在的网页（或称文档）不计其数，这样遍历的索引结构效率低下，无法满足用户需求。

正向索引结构如下:

    DOC-1寻找到：WORD-1的信息，WORD-2的信息…

    DOC-2寻找到：WORD-2的信息，WORD-3的信息…

    这里需要注意的是：**一般是通过key，去找value。**但是假设用户在主页上搜索关键词“苹果手机”时，假设只存在正向索引（forward index），那么就需要扫描索引库中的所有文档，找出所有包含关键词“苹果手机”的文档，再根据打分模型进行打分，排出名次后呈现给用户。因为互联网上收录在搜索引擎中的文档的数目是个天文数字，这样的索引结构根本无法满足实时返回排名结果的要求。所以，搜索引擎会将正向索引重新构建为倒排索引，即把文件ID对应到关键词的映射转换为关键词到文件ID的映射，每个关键词都对应着一系列的文件，这些文件中都出现这个关键词。 得到倒排索引的结构如下：

    WORD-1寻找到：DOC-1的信息…

    WORD-2寻找到：DOC-1的信息，DOC-2的信息…

    WORD-3寻找到：DOC-2的信息…

    这里与正向索引刚好相反，从词的关键字，去找文档。

【基本概念】

    1、文档(Document)：一般搜索引擎的处理对象是互联网网页，而文档这个概念要更宽泛些，代表以文本形式存在的存储对象，相比网页来说，涵盖更多种形式，比如Word，PDF，html，XML等不同格式的文件都可以称之为文档。再比如一封邮件，一条短信，一条微博也可以称之为文档。在本书后续内容，很多情况下会使用文档来表征文本信息。

    2、文档集合(Document Collection)：由若干文档构成的集合称之为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。

    3、文档编号(Document ID)：在搜索引擎内部，会将文档集合内每个文档赋予一个唯一的内部编号，以此编号来作为这个文档的唯一标识，这样方便内部处理，每个文档的内部编号即称之为“文档编号”，后文有时会用DocID来便捷地代表文档编号。

    4、单词编号(Word ID)：与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。

    5、倒排索引(Inverted Index)：倒排索引是实现“单词-文档矩阵”的一种具体存储形式，通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。

    6、单词词典(Lexicon)：搜索引擎的通常索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。

    7、倒排列表(PostingList)：倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项(Posting)。根据倒排列表，即可获知哪些文档包含某个单词。

    8、倒排文件(Inverted File)：所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称之为倒排文件，倒排文件是存储倒排索引的物理文件。

这些概念之间的关系如图所示：

【文档矩阵】

    单词-文档矩阵是表达两者之间所具有的一种包含关系的概念模型。

    现有以下几个文档:

        D1：Win11 新记事本速度变慢，无法粘贴大量文本，将在后续更新中改进性能

        D2：微软因区别对待 Win11 Dev 测试者被吐槽

        D3：微软 Win11 安卓手机伴侣 Phone Link 新功能曝光

        D4：微软 Office Word 网页版新增支持评论点赞功能

        D5：Win11 Dev 预览版 Build 25136 左下角出现全新搜索栏

    此时用户查询为“微软 And (win11 Or Dev)”，表示包含单词“微软”，同时还包含“win11”或“dev”的其中一个。

    则“单词-文档”矩阵为:

    该矩阵可以从两个方向进行解读:

    纵向: 表示每个单独的文档包含了哪些单词，比如D1包含了“win11这个词”，D5包含了“win11”和“Dev”。

    横向: 表示哪些文档包含了该单词，比如D2、D3、D4包含了“微软”这个词。

    搜索引擎的索引其实就是实现“单词-文档”矩阵的具体数据结构。可以有不同的方式来实现上述概念模型，比如“倒排索引”、“签名文件”、“后缀树”等方式，但是“倒排索引”是实现单词到文档映射关系的最佳实现方式。

【简单示例】

        D1：Win11 新记事本速度变慢，无法粘贴大量文本，将在后续更新中改进性能

        D2：微软因区别对待 Win11 Dev 测试者被吐槽

        D3：微软 Win11 安卓手机伴侣 Phone Link 新功能曝光

        D4：微软 Office Word 网页版新增支持评论点赞功能

        D5：Win11 Dev 预览版 Build 25136 左下角出现全新搜索栏

    这五个文档中的数字代表文档的ID，比如"Doc1"中的“1”。

通过这5个文档建立简单的倒排索引:

    首先要用分词系统将文档自动切分成单词序列，这样就让文档转换为由单词序列构成的数据流，并对每个不同的单词赋予唯一的单词编号(Word_ID)，并且每个单词都有对应的含有该单词的文档列表即倒排列表。如上表所示，第一列为单词ID，第二列为单词ID对应的单词，第三列为单词对应的倒排列表。如第一个单词ID“1”对应的单词为“微软”，单词“微软”的倒排列表为{2,3,4},即文档2、文档3、文档4都包含有单词“微软”。

这上面的列表是最简单的倒排索引，下面介绍一种更加复杂，包含信息更多的倒排索引。

TF(term frequency): 单词在文档中出现的次数。

Pos: 单词在文档中出现的位置。

    这个表格展示了更加复杂的倒排索引，前两列不变，第三列倒排索引包含的信息为(文档ID，单词频次，单词位置)，比如单词“新”对应的倒排索引里的第5项(1;2;8,31)意思是，文档1包含了“新”，并且在这个文档中出现了2次，第一个位置是8，第二个位置是31。