本文主要介绍了搜索引擎技术中的倒排索引技术，并对索引数据结构，索引建立方法进行了研究。文章可分为四个部分：（1）索引基础，该部分介绍了我文档矩阵与倒排索引基本概念；（2）单词词典，该部分介绍倒排索引词典部分的数据结构：哈希加链表法、树形结构；（3）倒排列表，该部分介绍了倒排项与倒排列表的概念；（4）建立索引，该部分介绍了构建倒排索引的三种方法：两遍文档遍历法、排序法、归并法。
关键词：倒排索引、哈希加链表法、排序法、归并法
This article mainly introduces the inverted index technology in search engine technology, and studies the index data structure and index establishment method. The article can be divided into four parts: (1) the basis of index, which introduces the basic concepts of my document matrix and inverted index; (2) word dictionary, which introduces the data structure of inverted index dictionary part: hash table method and tree structure; (3) inverted list, which introduces the concept of inverted list and inverted list; (4) indexing, this section describes three ways to build inverted index: two-pass document traversal method, sorting method, merger method.
Keywords：inverted index, hash table method, sorting method, merger method
索引在生活中十分常见，如图书的目录就是一种索引的方式，人们通过图书的目录可以很快找到对应的文章内容。类似的还有，百度旗下的hao123导航网站本质上也是一种索引结构，它建立于互联网为使用者提供快速查找网站的方法。索引的根本目的是加快查找速度。数据库中，常常利用索引的方式来加快搜索的速度。
倒排索引是搜索引擎中核心的技术，它来自实际应用中需要根据属性的值来查找记录。这种索引表中的每一项都包括一个属性值和具有该属性值的各记录的地址。又因为不是根据记录来确定属性的值，而是根据属性的值来确定记录的位置，所以被称为倒排索引。
搜索引擎中，查询词常常会被分成若干个单词，所以对于搜索引擎来说，倒排索引对应的属性就是单词，而其中对应的记录就是网页。所以，搜索引擎中的倒排索引其实是实现“单词-文档矩阵”的一种具体存储形式。通过倒排索引，我们可以根据属性快速获得包含这个属性的文档的列表。倒排索引由两个部分组成：单词词典、倒排文件。
1.1文档矩阵
单词-文档矩阵是表达单词与文档之间的包含关系的概念，图1.1展示了它的含义。图1.1的每列代表一个文档，每行代表一个单词，打对钩的位置代表包含关系。
图1.1单词-文档矩阵
从纵向，即文档这个维度来看，每列代表文档包含了哪些单词，如文档1中包含了词汇1、词汇4，却不包括词汇2，词汇3。从横向，即单词这个维度来看，每行代表了哪些文档包含了某个单词。比如对于词汇1来说，文档1和文档4中出现过词汇1，而其他文档不包含词汇1。矩阵中其他的行列也可做此种解读。搜索引擎的索引从本质上来说就是实现单词-文档矩阵的一种数据结构。这里可以有不同的方式来实现上面所说的概念模型，比如倒排索引、签名文件、后缀树等方式。但是经过实践表明，倒排索引方式是单词-文档关系映射的最好的实现方式之一。
1.2倒排索引基本概念
倒排索引中常常会用到一些术语，这些术语有助于了解倒排索引。如表1.1所示，同时可以用图1.2更直观的表达。
表1.1倒排索引术语
| 名词 |
含义解释 |
|
| 文档 |
一般搜索引擎的处理对象是互联网网页，而文档这个概念要更广泛一些，代表以文本形式存在的存储对象。相比网页来说，涵盖更多形式，比如Word、PDF、html、XML等不同格式的文件都可以称为文档，再比如一封邮件、一条短信、一条微博也可以称为文档。 |
|
| 文档集合 |
由一些文档构成的集合称为文档集合。比如海量的互联网网页或者说大量的电子邮件，都是文档集合的具体例子。 |
|
| 文档编号 |
在搜索引擎内部，会为文档集合内每个文档赋予一个唯一的内部编号，以此编号来作为这个文档的唯一标识，这样方便内部处理。每个文档的内部编号即称为文档编号，后文有时会用DocID来便捷地代表文档编号。 |
|
| 单词编号 |
与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。 |
|
| 倒排索引 |
倒排索引是实现单词-文档矩阵的具体存储形式。通过倒排索引，我们可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：单词词典和倒排文件。 |
|
| 单词词典 |
搜索引擎通常的索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息及指向倒排列表的指针。 |
|
| 倒排列表 |
倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项（Posting）。根据倒排列表，即可获知哪些文档包含某个单词。 |
图1.2倒排索引基本概念示意图
二、单词词典
单词词典是倒排索引中很重要的组成部分，它维护了文档集合中出现过的所有单词的相关信息，同时记载了某单词对应的倒排列表在倒排文件中的位置信息。在支持搜索时，根据用户的查询词，去单词词典里查询，就能够获得相应的倒排列表，并以此作为后续排序的基础。对于一个很大的文档集合来说，很可能有成千上网的文档数目，这时候索引的速度就很重要了，而索引的数据结构是决定索引速度的关键。常用的数据结构有：哈希加链表结构、树形词典结构。
2.1哈希加链表
哈希加链表法主要有两个部分构成，分别是哈希表和冲突表。其中，哈希表中每个表项保存一个指针，指针指向冲突链表，在冲突表中，具有相同哈希值的单词形成链表结构。这里，哈希表之索引存在是因为，两个不同的单词有可能会有相同的哈希值。我们将冲突的单词存放在链表中，便于查找。如图2.1是哈希加链表的词典结构。
2.1哈希加链表词典结构
2.2树形结构
B树是一种查询效率很高的结构，如图2.2所示。使用B树方式构建索引，需要字典项可以比较大小，而哈希加链表的方法不需要字典项有这样的性质。B树形成层级的查找结构，中间节点用于指出一定顺序范围的词典项目存储在哪个子树中，起到根据词典项比较大小进行导航的作用，最底层的叶子节点存储单词的地址信息，根据这个地址就可以提取出单词字符串。
图2.2B树查找结构
三、倒排列表
倒排列表记录了每个文档中包含哪些单词。一般来说，每个文档都会包含很多单词，文档需要记录文档编号，单词出现的次数，单词出现的位置等信息，这样的一条文档信息成为倒排索引项，多个有该单词的倒排索引项构成了倒排列表，如图3.1所示。
图3.1倒排列表示意图
在实际应用中，倒排文档中存储的并不是文档编号，而是车次文档编号的差值。文档编号差值是倒排列表中相邻的两个倒排索引项文档编号的差值，一般在索引构建过程中，可以保证倒排列表中后面出现的文档编号大于之前出现的文档编号，所以文档编号差值总是大于0的整数。之所以要对文档编号进行差值计算，主要原因是为了更好地对数据进行压缩，原始文档编号一般都是大数值，通过差值计算，就有效地将大数值转换为了小数值，而这有助于增加数据的压缩率。
四、建立索引
建立索引有很多种方式，这里介绍三种比较实用的方法。
4.1两遍文档遍历法
两遍文档遍历法需要对文档集进行两次遍历，该方法全部是在内存中创建索引。具体步骤，如图4.1所示。该方法在建立索引的过程中，对内存的消耗要求很高，不同文档集合包含文档数量大小不同，所需要的内存大小是不确定的。当文档很大的时候，有可能因为内存不足而无法建立索引。下面将详细讲解两次文档遍历的工作。
图4.1两遍文档遍历法
4.1.1第一次文档遍历
第一次文档遍历主要是为了统计一些全局的统计信息。其中，全局信息包括：文档集合中的文档个数，文档集合内所包含的不同单词个数，每个单词在多少个文档中出现过。通过这些信息，我们可以知道建立索引所需要的内存大小是多少。在建立索引时，需要根据以上信息分配内存大小，用来存储倒排索引内容。这样可以在内存中开辟连续存储区域，因为第一次文档遍历已经获得了每个单词在多少文档中出现的信息，将连续的存储区域划分为不同的大小片段，词典内某个单词根据自己对应的信息，可以通过指针，指向属于自己的内存片段的起始位置和终止位置，将来在第二遍扫描时，这个单词对应的倒排列表信息会被填充进这个片段中。
4.1.2第二遍文档遍历
第二次文档遍历才真正开始为每个单词建立倒排列表信息，即对一个单词来说，知道包含该单词的文档的ID，以及该单词在该文档中出现的信息：如位置，次数等，就可以填充第一次便利文档时在内存中所划分的空间。当第二遍文档完成时，第一次遍历所分配的内存空间全部并填充，并且每个单词指针所指向的片段的起始位置与终止位置之间的数据就是这个单词对应的倒排列表。经过两遍扫描完成索引建立后，即可将内存的倒排列表和词典信息写入磁盘，以上就是建立索引的整个过程。从上述流程可以看出，索引的构建完全是在内存中完成的，这对电脑内存提出了很大的需求，如果文档集合太大，内存可能不能提供足够的空间，索引构建就会失败。
4.2排序法
排序法在建立索引的过程中，始终在内存中分配固定大小的空间，来存放词典信息和索引的中间结果，当分配的空间被消耗光是，把中间结果写入磁盘，清空内存里中间结果所占空间，以用做下一轮存放索引中间结果的存储区。这种方法由于只需要固定大小的内存，所以可以对任意大小的文档集合建立索引。如图4.2所示。其中，排序法的具体策略为：
1.读入文档后，对文档进行编号，每个文档拥有一个可以唯一标识该文档的ID。
2.对于文档中出现的单词，在词典中进行查找
3.如果查到该单词将其转换为单词ID，如果没有查到该单词，则对该单词进行编号，每个单词拥有一个可以唯一标识该单词的ID。
4．将该文档内每个单词建立一个三元组：单词ID，文档ID，单词频率，这个三元组就倒排列表项。
5.读入下一个文档，执行步骤1.
图4.2排序法
随着索引建立过程的推进，三元组占用的中间结果内存越来越大，词典中的单词越来越多，当分配的内存占满之后，系统会将三元组写到磁盘上，在写到磁盘之前会对三元组进行排序。这里需要注意的是：在建立索引的过程中，当分配的内存占满之后，系统会将三元组写到磁盘上，在写到磁盘之前会对三元组进行排序。随着处理文档的增加，词典占用的内存会逐渐增加，由于分配内存是固定大小，而词典占用内存越来越大，也就是说，越往后，可用来存储三元组的空间是越来越少的。
在所有文件都经过排序法建立索引后，需要对所有的中间结果进行合并。在生成中介结果缓冲文件时，我们已经进行了排序。合并时，需要将不同缓冲区中同一个单词的三元组级进行合并，若该单词的所有三元组全部合并完成，将其写入最终索引中，清空缓冲区中关于这个单词ID的内容。如图4.3所示。
图4.3中间结果合并
4.3归并法
在排序法中，可以分配固定的内存来建立索引，但是随着索引建立过程的进行，词典越来越大，而词典恰恰是存储在内存中的，这样后期中间结果可用的内存越来越少。归并法对此进做出了改进，即每次将内存中数据写入磁盘时，包括词典在内的所有中间结果信息都被写入磁盘，这样内存所有内容都可以被清空，后续建立索引可以使用全部的定额内存。其中，归并法的算法过程如图4.4所示，首先在内存中维护中间结果，在内存占满后将数据写入临时文件，然后在所有文档都生成中间结果后，对中间结果进行合并。
图4.4归并法
归并法与排序法看起来很相似，但是实际上有很大的不同，它们的不同主要体现在以下三个方面：
1.排序法在内存中存放的是词典信息和三元组数据，而归并法则是在内存中建立一个完整的内存索引结构。
2.归并法会将整个内存的倒排索引写入临时文件，排序法只是将三元组数据排序后写入磁盘临时文件，词典作为一个映射表一直存储在内存中。
3.排序法在合并时是对同一单词的三元组依次进行合并，归并法在合并时针对每个单词的倒排列表进行合并，形成这个单词的最终倒排列表。另外，归并法在最后的合并过程中形成最终的词典信息。
参考文献
[1] Heinz S, Zobel J. Efficient single-pass index construction for text databases (p 713-729)[J]. Journal of the American Society for Information Science & Technology, 2010, 54(8):713-729.
[2] Zobel, J., Heinz， S. and Williams, H. E. (2001). In-memory hash tables for accumulating text vocabularies. Information Processing Letters 80, 271.
[3] Brown, E.W., Callan, J.P., and Croft, W. B. (1994). Fast incremental indexing for full-text information retrieval. In Proceedings of the International Conference on Very Large Databases, Santiago . Morgan Kaufmann, 192-202.
[4] Buttcher, S. and Clarke, C. L. (2005). Indexing time vs. query time trade-offs in dynamicnformation retrieval systems. In Proceedings of the International Conference on Information and Knowledge Management, Bremen, Germany, ACM Press, 317-318.
[5] Cutting, D. and Pedersen, J. (1990). Optiminisationsfor dyamic invert index maintenance. In Proceedings of the ACM-SIGIR International Conference on Research and Development in Information Retrieval Brussels, Belgi山n,J.-L. Vidick, Ed. ACM Press, 405-411.
[6] Lester，N，Zoble,J., and Williams, H. E. (2006). Efficient ooline index maintenance fortext retrieval systems. Informationof Processingand Management.
[7] Williams, H. E., Zobel, J.，and Bahle，D.(2004). Fast phrase queying with combined indexes. ACM Trans on Information System.22, 4, 573-594.
[8] Lester，N，ZobeJ., and Williams, H. E. (2004). In-Place versus Re-Build Jdversus Re-Merge: Indexes Maintenance Strategies for TextRetrieval Systems. In Proceedings of the 27th Conference on Australasian Computer Scienc哩，Darlingh町st,Aus位alia.
[9]Moffat A.,Zobel, J., (Oct. 1996). Self-indexing inverted list for fast text retrieval. ACM Transactions on Information Systems 14
