1.3 倒排索引

索引是构成搜索引擎的核心技术之一，索引在日常生活中其实也是非常常见的，比如当我们看一本书的时候，我们首先会看书的目录，通过目录可以快速定位到某一章节的页码，加快对内容的查询速度。

文档通常保存在各种数据库管理系统之中，比如Oracle、MySQL等。但是搜索引擎中的数据不能保存到数据库中，主要是因为数据库不能满足搜索引擎的需求，原因有二：一是搜索引擎中的数据量非常庞大，大型商业搜索引擎需要处理数以亿计的网页，面对海量数据使用关系型数据库很难管理；二是搜索引擎使用的数据操作非常简单，一般只需增删改查这几个基本功能，一般的数据库系统则支持大而全的功能，损失了速度和空间，大量用户检索则要求搜索引擎响应时间必须很快，检索效率要非常高，数据库系统在检索响应时间和检索并发度方面都不能满足需求。而数据库中的索引就是为了提高表的搜索效率而对某些字段中的值建立的目录，在搜索引擎中使用倒排索引这种数据结构来存储网页信息。

倒排索引（Inverted index），也常被称为反向索引，是一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射，它是文档检索系统中最常用的数据结构。

下面以简单通俗的例子来理解倒排索引，假设现在有两个文档doc1和doc2, doc1包含3个关键词：中国、美国、韩国，doc2中包含4个关键词：中国、美国、德国、英国，文档和词语的包含关系（也就是正排索引），见表1-2。

表1-2 文档-单词对照表

那么词语所属的文档关系，也就是倒排索引，见表1-3。

表1-3 单词-文档对照表

如果想查找包含关键词“美国”的文档，那么结果就是doc1和doc2。这样从文档包含单词到单词所属文档的转换，就是倒排的由来。我们在搜索引擎中输入关键词进行查询，就是一次查找哪些文档包含查询关键词的过程。

下面我们通过具体实例深入理解倒排索引，通过简单文档以小见大，体验倒排索引的构建过程。如表1-4所示，在互联网上找了4条科技新闻作为一个文档集合，我们以新闻标题作为文档内容，给每个文档设置一个连续的整数编号作为文档ID。

表1-4 构建倒排索引文档集合

对于文档内容，先要经过词条化处理。和英文不同的是，英文通过空格分隔单词，中文的词与词之间没有明确的分隔符号，经过分词系统进行中文分词以后把矩阵切分成一个个的词条，文档4会被分成“谷歌”“开源”“机器”“学习”“工具”5个词项。“谷歌”这个词在文档2和文档4中各出现一次，文档频率为2，倒排记录表记作2→4，文档频率也是倒排记录表的长度。依次统计各个词项的文档频率和倒排记录表，构建倒排索引过程如表1-5所示。

表1-5 倒排索引构建过程