倒排索引原理简析

  倒排索引是一种源于搜索引擎中根据关键字对文档进行搜索的技术，lucene就是基于倒排索引实现的。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。由于不是由记录来确定属性值，而是由属性值来确定记录的位置，因而称为倒排索引(inverted index)。带有倒排索引的文件我们称为倒排索引文件，简称倒排文件(inverted file)。
   倒排索引一般表示为一个关键词，然后是它的频度（出现的次数），位置（出现在哪一篇文章或网页中，及有关的日期，作者等信息），它相当于为互联网上几千亿页网页做了一个索引，好比一本书的目录、标签一般。读者想看哪一个主题相关的章节，直接根据目录即可找到相关的页面。不必再从书的第一页到最后一页，一页一页的查找。

倒排索引.jpg

倒排索引组成

   倒排索引主要有由两个部分组成：单词词典和倒排文件。

单词词典

   单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
   单词词典是倒排索引中非常重要的组成部分，它是用来维护文档集合中所有单词的相关信息，同时用来记载某个单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表。
   对于一个规模很大的文档集合来说，可能包含了几十万甚至上百万的不同单词，快速定位某个单词直接决定搜索的响应速度，所以我们需要很高效的数据结构对单词词典进行构建和查找。常用的数据结构包含哈希加链表和树形词典结构。

倒排文件

  所有单词的倒排列表顺序的存储在磁盘的某个文件里，这个文件即被称为倒排文件，倒排文件是存储倒排索引的物理文件。

倒排索引生成算法

假设现在有两篇文章：
设有两篇文章1和2：
文章1的内容为：Tom lives in Guangzhou,I live in Guangzhou too.　
文章2的内容为：He once lived in Shanghai.

1.取得关键字

  a.我们现在有的是文章内容，即一个字符串，我们先要找出字符串中的所有单词，即分词。英文单词由于用空格分隔，比较好处理。中文单词间是连在一起的需要特殊的分词处理。
  b.文章中的”in”, “once” “too”等词没有什么实际意义，中文中的“的”“是”等字通常也无具体含义，这些不代表概念的词可以过滤掉。
  c.用户通常希望查“He”时能把含“he”，“HE”的文章也找出来，所以所有单词需要统一大小写。
  d.用户通常希望查“live”时能把含“lives”，“lived”的文章也找出来，所以需要把“lives”，“lived”还原成“live” 。
  e.文章中的标点符号通常不表示某种概念，也可以过滤掉。
  经过上面处理后，文章1的所有关键词为：
[tom] [live] [guangzhou] [i] [live] [guangzhou]
  文章2的所有关键词为：
[he] [live] [shanghai]

2.建立倒排索引

  有了关键词后，我们就可以建立倒排索引了。上面的对应关系是：“文章号”对“文章中所有关键词”。倒排索引把这个关系倒过来，变成: “关键词”对“拥有该关键词的所有文章号”。文章1，2经过倒排后变成:

关键词          文章号 　　
guangzhou        1 　　
he               2 　　
i                1 　　
live             1,2 　　
shanghai         2 　　
tom              1 　

  通常仅知道关键词在哪些文章中出现还不够，我们还需要知道关键词在文章中出现次数和出现的位置，通常有两种位置：
 a.字符位置，即记录该词是文章中第几个字符（优点是关键词亮显时定位快）；
 b.关键词位置，即记录该词是文章中第几个关键词（优点是节约索引空间、词组（phase）查询快），lucene中记录的就是这种位置。 　　
 加上“出现频率”和“出现位置”信息后，我们的索引结构变为：

关键词            文章号[出现频率]              出现位置 　　
guangzhou           1[2]                      3，6 　　
he                  2[1]                      1 　　
i                   1[1]                      4 　　
live                1[2]                      2，5,
                    2[1]                      2 　　
shanghai            2[1]                      3 　　
tom                 1[1]                      1

3.实现

  将上面三列分别作为词典文件（Term Dictionary）、频率文件(frequencies)、位置文件 (positions)保存。其中词典文件不仅保存有每个关键词，还保留了指向频率文件和位置文件的指针，通过指针可以找到该关键字的频率信息和位置信息。

更新策略

  倒排索引的更新策略有四种：完全重建、再合并策略、原地更新策略以及混合策略。

1. 完全重建策略：当新增文档到达一定数量，将新增文档和原先的老文档整合，然后利用静态索引创建方法对所有文档重建索引，新索引建立完成后老索引会被遗弃。此法代价高，但是主流商业搜索引擎一般是采用此方式来维护索引的更新（这句话是书中原话）
2. 再合并策略：当新增文档进入系统，解析文档，之后更新内存中维护的临时索引，文档中出现的每个单词，在其倒排表列表末尾追加倒排表列表项；一旦临时索引将指定内存消耗光，即进行一次索引合并，这里需要倒排文件里的倒排列表存放顺序已经按照索引单词字典顺序由低到高排序，这样直接顺序扫描合并即可。其缺点是：因为要生成新的倒排索引文件，所以对老索引中的很多单词，尽管其在倒排列表并未发生任何变化，也需要将其从老索引中取出来并写入新索引中，这样对磁盘消耗是没必要的。
3. 原地更新策略：试图改进再合并策略，在原地合并倒排表，这需要提前分配一定的空间给未来插入，如果提前分配的空间不够了需要迁移。实际显示，其索引更新的效率比再合并策略要低。
4. 混合策略：出发点是能够结合不同索引更新策略的长处，将不同索引更新策略混合，以形成更高效的方法。

参考：
1.https://yq.aliyun.com/articles/38228
2.https://baike.baidu.com/item/倒排索引/11001569?fr=aladdin