倒排索引是什么？

　　在信息大爆炸的今天，有了搜索引擎的帮助，我们能够快速、便捷的找到所求。可以毫不夸张的说，倒排索引是搜索引擎的基石。今天的内容就来学习倒排索引，有需要的朋友可以参考学习。
　　倒排索引是目前搜索引擎公司最对搜索引擎最常用的存储方式，也是搜索引擎的核心内容。在搜索引擎实际的引用之中，有时需要按照关键字的某些值查找记录，为什么？效率问题，全文搜索跟只挑几个词搜索，自己想想都知道。那么我们按照关键字创立的索引，就称之为：倒排索引，而带有倒排索引的文件我们有称之为：倒排索引文件也可以叫它为：倒排文件来实现快速的检索与高速的效率。
　　我们可以先来了解倒排索引一些基本概念
　　文档(Document)：一般搜索引擎的处理对象是互联网网页，而文档这个概念要更宽泛些，代表以文本形式存在的存储对象，相比网页来说，涵盖更多种形式，比如word，PDF，html，XML等不同格式的文件都可以称之为文档。再比如一封邮件，一条短信，一条微博也可以称之为文档。在本书后续内容，很多情况下会使用文档来表征文本信息。
　　文档集合(Document Collection)：由若干文档构成的集合称之为文档集合。比如海量的互联网网页或者说大量的电子邮件都是文档集合的具体例子。
　　文档编号(Document ID)：在搜索引擎内部，会将文档集合内每个文档赋予一个唯一的内部编号，以此编号来作为这个文档的唯一标识，这样方便内部处理，每个文档的内部编号即称之为“文档编号”，后文有时会用DocID来便捷地代表文档编号。
　　单词编号(Word ID)：与文档编号类似，搜索引擎内部以唯一的编号来表征某个单词，单词编号可以作为某个单词的唯一表征。
　　倒排索引(Inverted Index)：倒排索引是实现“单词-文档矩阵”的一种具体存储形式，通过倒排索引，可以根据单词快速获取包含这个单词的文档列表。倒排索引主要由两个部分组成：“单词词典”和“倒排文件”。
　　单词词典(Lexicon)：搜索引擎的通常索引单位是单词，单词词典是由文档集合中出现过的所有单词构成的字符串集合，单词词典内每条索引项记载单词本身的一些信息以及指向“倒排列表”的指针。
　　倒排列表(PostingList)：倒排列表记载了出现过某个单词的所有文档的文档列表及单词在该文档中出现的位置信息，每条记录称为一个倒排项(Posting)。根据倒排列表，即可获知哪些文档包含某个单词。
　　倒排文件(Inverted File)：所有单词的倒排列表往往顺序地存储在磁盘的某个文件里，这个文件即被称之为倒排文件，倒排文件是存储倒排索引的物理文件。
　　关于这些概念之间的关系，通过下图可以比较清晰的看出来。
　　
　　排索引是一种索引结构，它存储了单词与单词自身在一个或多个文档中所在位置之间的映射。
　　倒排索引通常利用关联数组实现。它拥有两种表现形式：
　　inverted file index，其表现形式为 {词项，词项所在文档的ID}
　　full inverted index，其表现形式为 {词项，（词项所在文档的ID，在具体文档中的位置）}
　　具体实例，假设有三个文档：
　　D0 = “it is what it is”
　　D1 = “what is it”
　　D2 = “it is a banana”
　　那么，采用inverted file index方式，结果是：
　　”a”: {2}
　　”banana”: {2}
　　”is”: {0, 1, 2}
　　”it”: {0, 1, 2}
　　”what”: {0, 1}
　　采用full inverted index方式，结果是：
　　”a”: {(2, 2)}
　　”banana”: {(2, 3)}
　　”is”: {(0, 1), (0, 4), (1, 1), (2, 1)}
　　”it”: {(0, 0), (0, 3), (1, 2), (2, 0)}
　　”what”: {(0, 2), (1, 0)}
　　这就是所谓的倒排索引，你看懂了吗？如果喜欢我们的分享，那就关注课课家吧！