《从零开始学习自然语言处理(NLP)》-倒排索引(1)

刘才权

写在最前面

在这个日新月异的信息时代，海量数据的积累，计算能力的不断提升，机器学习尤其是深度学习的蓬勃发展，使得人工智能技术在不同领域焕发出蓬勃的活力。自己经历了嵌入式开发，移动互联网开发，目前从事自然语言处理算法开发工作。从工程软件开发到自然语言处理算法开发，希望通过这个系列的文章，能够由浅入深，通俗易懂的介绍自然语言处理的领域知识，分享自己的成长，同大家一起进步。

问题描述

倒排索引是搜索引擎的基础算法，在本文中我们以一个简单的例子来详细介绍倒排索引的思想和实现。
假设用户有个搜索query：“林俊杰2019演唱会行程”。百度的搜索结果如下：

如果要求你来设计一个搜索引擎，来解决这个问题，你会如何着手呢？

问题简化

现在我们把这个问题具体化。我们除了有要查询的query：“林俊杰2019演唱会行程”。还有被查询的网页数据库。这里我们做个简化，假设我们的网页数据库内容只有如下4条：
网页1：

2019年，JJ林俊杰全球演唱会在北京首场演出，行程如下xxxxxxx；

网页2：

林俊杰，吴亦凡终于同框合影 ，惹粉丝们尖叫连连，xxxxx；

网页3：

蔡依林2019世界演唱会行程全曝光，xxxxx；

网页4：

告别2018，迎接崭新的2019，xxxxxx；

简单来说，就是从网页1~4中选取最理想的查询结果。你会怎么做呢？

关键词匹配

最容易想到的方法就是关键词匹配了，简单的来说，就是网页中包含查询的关键词越多，网页和查询query的相关度也就越大。
在做关键词查询前，一般文本会先进行预处理。这里的预处理主要包括去停用词和分词。
去停用词
去除和查询不相关的内容，比如本例子中的标点符号。在其他场景中，除了标点符号也会去除一些特别的字或词。
分词
分词主要目的是将句子切长短语或关键字，这样才利于查询匹配。比如“林俊杰2019演唱会行程”可以分词成，

林俊杰/2019/演唱会/行程

当然网页也需要这样进行分词：
网页1：

2019/年/JJ/林俊杰/全球/演唱会/在/北京/首场/演出/行程/如下/xxxxxxx

网页2：

林俊杰/吴亦凡/终于/同框/合影 /惹/粉丝们/尖叫/连连/xxxxx

网页3：

蔡依林/2019/世界/演唱会/行程/全曝光/xxxxx

网页4：

告别/2018/迎接/崭新/的/2019/xxxxxx；

分词是一项专门的技术，在实际工程中可以至今借助工具来完成，比如jieba分词。
分词处理后，我们用查询query中的关键词在网页数据库中进行关键词匹配，并统计匹配数目：

从“匹配个数”中很容易确定，网页1就是和查询query最匹配的网页。

倒排索引

讲到这里大家可能会疑问，这和倒排索引有什么关系？实际上，如果仔细考虑上面的关键词查询过程，会发现这种方法有个很大的效率问题：我们的例子中只有4个待查询的网页，而实际的互联网世界的网页数目是非常巨大的。假设互联网世界的网页数据为N，那么使用关键词查询的时间复杂度就是O(N)，显然，这样的时间复杂度还是太大了，而倒排索引就很好的优化了这个问题。
从倒排索引这个名字很容易联想出它的实现，关键就是“倒排”的“索引”。在前面的讲解中，我们的索引(key)是网页，内容(value)是关键字。倒排索引就是反过来：内容关键字作为索引(key)，所在网页作为内容(value)。前面的表格就可以改写成，

通过上面的表格，很明显网页1是包含最多关键词的网页，也是和查询query相关度最高的网页。采用倒排索引的方法，搜索的时间复杂度得到了明显的降低。

搜索引擎框架

有了倒排索引的知识，我们就可以搭建简单的搜索引擎了，

具体步骤包括：
网页抓取
主要是借助网络爬虫，来抓取网络世界的所有网页，并进行存储。网络爬虫是一项专门的技术，目前工程上也有很多现成的开源工具。
倒排索引生成
将抓取后的网页经过预处理后，整理生成倒排索引。
用户在线查询
借助倒排索引，搜索引擎能够满足用户的实时在线查询。
前两个步骤是不用考虑实时性的，可以离线进行，而用户的在线查询则需要保证实时性。

小结

本文通过一个搜索查询的例子，引出关键词查询的方案，及遇到的问题。进而介绍了倒排索引的原理，和搜索引擎的整体框架。现代搜索引擎是一个非常庞大和复杂的系统工程，这里的例子只是为了方便大家理解做了特别的简化。文中提到的分词和网络爬虫也是专门的文本处理技术，在后续的文章后，会根据需要专门展开。