倒排索引

倒排索引(Inverted Index)：

倒排索引从逻辑结构和基本思路上讲非常简单，下面我们通过具体实例来进行说明，使得大家能够对倒排索引有一个宏观而直接的感受。

中文和英文等语言不同，单词之间没有明确的分隔符号，所以首先要用分词系统将文档自动切分成单词序列，这样每个文档就转换为由单词序列构成的数据流。

为了系统后续处理方便，需要对每个不同的单词赋予唯一的单词编号，同时记录下哪些文档包含这个单词，在处理结束后，我们可以得到最简单的倒排索引（参考图4）。

图4中，“单词ID”一列记录了每个单词对应的编号，第2列是对应的单词，第3列即每个单词对应的倒排列表。比如：单词“谷歌”，其中单词编号为1，倒排列表为{1,2,3,4,5}，说明文档集合中每个文档都包含了这个单词。

之所以说图4的倒排索引是最简单的，是因为这个索引系统只记载了哪些文档包含某个单词。而事实上，索引系统还可以记录除此之外的更多信息。

图5是一个相对复杂些的倒排索引，与图4所示的基本索引系统相比，在单词对应的倒排列表中不仅记录了文档编号，还记载了单词频率信息，即这个单词在某个文档中出现的次数。之所以要记录这个信息，是因为词频信息在搜索结果排序时，计算查询和文档相似度是一个很重要的计算因子，所以将其记录在倒排列表中，以方便后续排序时进行分值计算。

在图5所示的例子里，单词“创始人”的单词编号为7，对应的倒排列表内容有（31），其中3代表文档编号为3的文档包含这个单词，数字1代表词频信息，即这个单词在3号文档中只出现过1次，其他单词对应的倒排列表所代表的含义与此相同。

实用的倒排索引还可以记载更多的信息，图6所示的索引系统除了记录文档编号和单词词频信息外，额外记载了两类信息——即每个单词对应的文档频率信息（图6的第3列）及单词在某个文档出现位置的信息。

文档频率信息代表了在文档集合中有多少个文档包含某个单词，之所以要记录这个信息，其原因与单词频率信息一样，这个信息在搜索结果排序计算中是一个非常重要的因子。

而单词在某个文档中出现位置的信息并非索引系统一定要记录的，在实际的索引系统里可以包含，也可以选择不包含这个信息，之所以如此，是因为这个信息对于搜索系统来说并非必要，位置信息只有在支持短语查询的时候才能够派上用场。

以单词“拉斯”为例：其单词编号为8，文档频率为2，代表整个文档集合中有两个文档包含这个单词，对应的倒排列表为{(31<4>),(51<4>)}，其含义为在文档3和文档5出现过这个单词，单词频率都为1，单词“拉斯”在这两个文档中的出现位置都是4，即文档中第4个单词是“拉斯”。

图6所示的倒排索引已经是一个非常完备的索引系统，实际搜索引擎的索引结构基本如此，区别无非是采取哪些具体的数据结构来实现上述逻辑结构。

有了这个索引系统，搜索引擎可以很方便地响应用户的查询。比如：用户输入查询词 “Facebook”，搜索系统查找倒排索引，从中可用读出包含这个单词的文档，这些文档就是提供给用户的搜索结果。

而利用单词词频信息、文档频率信息即可对这些候选搜索结果进行排序，计算文档和查询的相似性，按照相似性得分由高到低排序输出，此即为搜索系统的部分内部流程。

单词词典是倒排索引中非常重要的组成部分，它用来维护文档集合中出现过的 所有单词 的相关信息，同时用来记载某个 单词对应的倒排列表在倒排文件中的位置信息 。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。

对于一个规模很大的文档集合来说，可能包含几十万甚至上百万的不同单词，能否快速定位某个单词，这直接影响搜索时的响应速度，所以需要高效的数据结构来对单词词典进行构建和查找， 常用的数据结构包括 哈希加链表 结构和 树形 词典结构。

B树（或者B+树）是另外一种高效查找结构，图8是一个 B树结构示意图。B树与哈希方式查找不同，需要字典项能够按照大小排序（数字或者字符序），而哈希方式则无须数据满足此项要求。

B树形成了层级查找结构，中间节点用于指出一定顺序范围的词典项目存储在哪个子树中，起到根据词典项比较大小进行导航的作用，最底层的叶子节点存储单词的地址信息，根据这个地址就可以提取出单词字符串。

具体的大家可以看看[ https://blog.csdn.net/hackerose1994/article/details/50933396?locationNum=11&fps=1 )

正排索引与倒排索引

正排索引也叫正向索引(forward index)

,倒排索引也叫反向索引(inverted index)。他们都是搜广推经常用到的工具,用于记录海量 对象与特征 之间的关系

倒排索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件。建立全文索引中有两项非常重要，一个是如何对文本进行分词，一是建立索引的数据结构。分词的方法基本上是二元分词法、最大匹配法和统计方法。索引的数据结构基本上采用倒排索引的结构。

分词的好坏关系到查询的准确程度和生成的索引的大小。在中文分词发展中，早期经常使用分词方式是二元分词法，该方法的基本原理是将包含中文的句子进行二元分割，不考虑单词含义，只对二元单词进行索引。因此该方法所分出的单词数量较多，从而产生的索引数量巨大，查询中会将无用的数据检索出来，好处是算法简单不会漏掉检索的数据。之后又发展出最大匹配分词方法，该方法又分为正向最大分词和逆向最大分词。其原理和查字典类似，对常用单词生成一个词典，分析句子的过程中最大的匹配字典中的单词，从而将句子拆分为有意义的单词链。最大匹配法中正向分词方法对偏正式词语的分辨容易产生错误，比如“首饰和服装”会将“和服”作为单词分出。达梦数据库采用的是改进的逆向最大分词方法，该分词方法较正向正确率有所提高。最为复杂的是通过统计方式进行分词的方法。该方法采用隐式马尔科夫链，也就是后一个单词出现的概率依靠于前一个单词出现的概率，最后统计所有单词出现的概率的最大为分词的依据。这个方法对新名词和地名的识别要远远高于最大匹配法，准确度随着取样文本的数量的增大而提高。

二元分词方法和统计方法是不依赖于词典的，而最大匹配法分词方法是依赖于词典的，词典的内容决定分词结构的好坏。

全文检索的索引被称为倒排索引，之所以成为倒排索引，是因为将每一个单词作为索引项，根据该索引项查找包含该单词的文本。因此，索引都是单词和唯一记录文本的标示是一对多的关系。将索引单词排序，根据排序后的单词定位包含该单词的文本。

步骤1）读取一整条句子到变量str中，转到步骤2

步骤2）从句子的尾端读取1个字到变量word中，转到步骤3

步骤3）在字典查找word中保存的单词。如果存在则保存word，转到步骤4，否则转到步骤5）

步骤4）如果是字典中最大单词或者超过最大单词数（认定为新词），从句尾去掉该单词，返回步骤2

步骤5）读取前一个字到word中，构成新单词，转到步骤3）

词库的内存数据结构和词库中单词的匹配算法

内存中单词采用层次结构保存

假设字典中有如下的单词：中国 中华民国 国家 人民 民主

在内存中按照如下方式按层排列，其中每一个方块代表一个字，箭头所指向为该单词的前一个字

---