第15讲 信息检索之倒排索引在线视频

欢迎来到

互联网大规模数据分析技术

的课堂

我是今天的主讲教师李琳

来自武汉理工大学

今天我们开始第十五讲

信息检索之倒排索引的学习

我们首先回顾一下

上节课我们所学习的

信息检索的概念

信息检索是找到相关的文档

从一些自由文本当中

满足用户的查询需求

那么这是一种检索和查询服务

Web上最典型的应用

就是我们的搜索引擎

当然

你也可以进行Email的搜索

和你的个人电脑当中的文档搜索

这些是我们在上一节课

跟大家做的一个信息检索的概述

今天

我们将从以下四个方面

来学习一下信息检索当中的

关键数据结构倒排索引

它们是怎么帮助信息检索系统

快速的响应用户的查询需求呢

我们逐一来进行学习

首先我们看一下

这样一个问题

Which plays of Shakespeare

contain the words Brutus AND

Caesar but NOT Calpurnia

这是什么意思呢

莎士比亚的哪一个作品当中包含

这两个词

但是不包含这一个词

想找到这样的一部

莎士比亚的作品

传统的方式

那就是我把莎士比亚的

每一部作品都逐一的

去做字符串匹配

看哪个作品当中

既有这个词就有这个词

但是如果某一个作品包含这个词

我就把这个作品

从list当中去掉显然

这样一种方式呢

会比较慢

每有一个查询词

你就要把所有的文档遍历

和对比一遍

这个非常麻烦

二要找到哪一个文档

不包含这个词

你怎么知道它不包含呢

你就必须把这个文档

全部去比较一遍

不管这个文档有多长

所以这样的方式

使得实时的查询要求

没办法得到快速的响应

怎么办呢

我们的研究者很聪明

提出了一种解决方案

我们首先来看

它的一个基本的思想

我们把它叫做Term-document

incidence matrices

也就是

词、文档

这样一个出现的矩阵

在这个里面

我们的列

代表每一个莎士比亚的作品

大家看到了哈姆雷特

我们的行代表

所有的作品当中的每一个单词

大家记不记得

在MapReduce当中

我们学会了如何统计每一个单词

在每一个文档当中出现的次数

我们知道这个单词

在这个文档当中出现的次数

今天我们先把这个问题简化一下

有，我就记为“1”

没有出现，我就记为“0”

1 if play contains word

0 otherwise

就是这个意思

那么我们把问题简化成

“1”代表有

“0”代表无的形式

这样的表达方式

我们有什么好处呢

我们来看一下

如果我们想回答

哪一个莎士比亚的作品

含这两个单词

不含第三个单词呢

我们把每一个单词对应的1、0

把它取出来

比如说第一个单词Brutus

它对应的就是110100

那么我们的Caesar对应的就是110111

“含”这两个单词

你有我有，表示都有

你有我无，那肯定不行

所以，“1”、“0”

我可以做一个“与”的运算

“不含”是什么意思呢

“不含”

我就把

这一行去取反

“1”的位置变“0”

“0”的位置变“1”

我就得到了“10111”

然后这三者去做一个

“与”的运算

我得到“与”的结果

全为“1”就是“1”

全为“0”也是“0”

有一个为“0”

它肯定也是“0”

所以我们得到这样一组向量

这样一个向量

“100100”代表什么意思呢

也就是说

第一列的文档和第四列的文档

同时含这两个单词

又不含第三个单词

所以这样

我们通过位与运算

学过计算机基础的同学会知道

位与运算是非常快的一种运算

我们能够直接得出哪个作品含

符合我们的查询要求

我们得到的两个作品

一个是哈姆雷特

一个是Antony这样一个作品

我们看一下

刚才的那个单词文档出现矩阵

能够满足我们在莎士比亚的

这样一个查询过程当中的需求

面对更大的文档集合

它能不能够胜任呢

我们来看一下这样一个例子

当有100万个文档

每个文档大概有1000个单词

如果每一个单词

需要6个字节来存放

包含标点符号和空格的话

我们大概需要6GB的容量

来存放这样一个矩阵

我们通过计算分析发现

我们有500k的单词

在这样一个矩阵当中

这样一个矩阵

就是500k行

乘以100万列

而且这样一个列当中

有很多“0”和“1”来组成

而且我们发现，“1”的个数偏少

“0”的个数偏多

也就是这样一个矩阵

是一个非常稀疏的矩阵

extremely sparse

非常稀疏

存了大量的“0”

学过数据结构的同学就会知道

对于这样的矩阵我们可以采用

稀疏矩阵的存储方式

只存“1”不存“0”

“没有”就是不出现

所以这样可以

带部分解决我们查询问题

但是

我们的大规模的

海量的数据分析

用矩阵的方式来存放合不合理呢

因为我们在现实生活当中

实际上是没有办法把所有的数据

这样一个矩阵放到内存里面的

它存不下的

刚才我看到100万个的网页

它就需要6GB

所以那么我们怎么来办呢

在我们的信息检索当中呢

我们提出了一个

非常有名的结构叫做

Inverted index

“Inverted”什么意思呢

倒排

“index”索引

也就是我们这一讲的标题

倒排索引

那么倒排索引是怎么来做的呢

我们在这里看一下

这还是我们的单词

这个单词有一个指针

指向一个列表

这个列表当中存放的是什么呢

Document ID

1号文档有这个单词

2号文档有这个单词

4号文档有这个单词

我们不用矩阵

我们用这样一个倒排索引的方式

可以将文档的这样一个列表

因为它过大

存到硬盘里面

可以考虑把单词

因为大家都知道

单词的个数相对来说是固定的

可以存到内存里面

然后有一个指针

指向文档所存放的位置

这样来解决我们的存放

当然同学们注意到了一个问题

我们这个Document ID

是按顺序从小到大排列的

后面我们有个例子会给大家讲解

当你有新的文档进来的时候呢

我们就要在相应的位置

进行插入的操作

来实现文档列表的更新

所以我们实际上是需要一个

变长的列表

也就说这个列表

究竟有多少个文档我不知道

因为我还可能会加

我还可能会加

我还可能会加

而且我还有可能会减

因为这个网页不存在了

我还要把它减掉

所以大家可以看到

在我们的硬盘当中

如果要存放的话

我们是在连续的空间当中

去存放它

当然一般的情况下

是放不到内存里面去的

所以我们把这样一个文档的集合

叫做posting

把这样一个文档的列表叫做

posting list

多个叫posting

我们把这个单词

一个个单词组成的集合

我们把它叫做dictionary

叫做字典

刚才我们看到了

倒排索引的这样一个结构

怎么建立这样一个倒排索引呢

实际上这里面涉及到了一些

自然语言处理的技术

在这门课当中

我们并不跟大家介绍

自然语言的原理

大家都感兴趣的话

可以去参考相关的书籍

我们在这里

只对它的流程做一个简要的介绍

比如说我们有了很多文档

Friends、Countrymen

这样一些文档

有逗号有句号

有冒号有分号

有各种各样的形式的英文文档

当然中文的处理会更复杂

所以这里面我们就不再介绍

还是以英文为例

大家看一下

那我怎么办呢

我首先要得到一个个单词

我把这些

逗号、逗号、句号、冒号、分号

全部去掉

得到一个个单词

我们把这个叫做Tokenizer

然后怎么办呢

我们要采用一些模型

把Friends变成friend

把Romans变成roman

Countrymen变成countryman

大家看看这需要语言模型

而且大家会看到

我大小写也进行了转换

因为你不能说

我输一个大写的Friend

你说小写的friend

不符合我的要求吗

从语义上来说它是符合的

然后我们得到了一个一个单词

我们再把

这个单词出现的文档的集合

形成这样一个postings list

这样就得到了

我们的Inverted index

而实际上

前面的这三步

都需要用我们

自然语言处理的技术，这些呢

不同的语言采用的方式不一样

英语、中文、法语、德语

还有阿拉伯语言

它们各自有各自的语言模型

这个需要大家能做

另一方面的扩展知识的阅读

所以当我们对这样一些文档

进行处理之后

我们就构建了这样一个Inverted index

而且我们这个Inverted index

它非常容易用我们的

MapReduce的编程来实现

大家还记不记得上一节课

我们讲过的MapReduce

遇到一个单词逗号1

遇到一个单词逗号1

归并之后形成单词在文档当中

出现的次数

同时我还可以得到文档的标号

那么我们最终形成了这样一个

倒排索引的列表当中

我们可以包含一些信息

比如前面我们在学习当中

所涉及到的词频和文档频率的

这样一些信息

都可以很容易的包含在

这样一个键值对的结构当中

比如说大家在这里可以看到

这个单词

1代表什么意思呢

我出现在一个文档中

比如说这个capitol 1

也就是一个文档

Caesar 2什么意思呢

我出现在两个文档中

那么这样的一种方式

我们一般来说

会把这样一个词典存在内存里面

把postings list

也就是它所在的文档的集合

存在硬盘里面

当用户提出查询要求的时候呢

我们很容易快速的

从内存当中找到我这个单词

所对应的文档集合的指针

从而将文档返回给用户

当然

也可以把我们其它的一些信息

包含在这样一些列表

或者是文档当中

根据大家的需求来完成

这就是我们对整个的存储

进行一个分析

我们会看见我们要存单词

我们要存单词在文档当中的

文档的频率

我们还要存什么呢

每个单词

所指向文档列表存放位置的指针

我们还要存什么呢

list和document id

也就是文档列表

List of docIDs

这一些呢

我们IR系统呢信息检索系统

都会帮助大家来进行建立

我们有一个开源的

信息检索系统的平台

后面我们会做一个介绍

它能帮助我们

有效地建立索引来进行这个存储

就像我们刚才提到的一样

字典存放在memory当中

posting list存在硬盘里面

那么我们如果

从数据结构的角度考虑

这样一个列表

它是动态变化的话

我们该用什么样的数据结构

来存放呢

因为它变化

所以用fix的矩阵

数组，显然浪费

我们可以用链表的形式

或者是变长数组的形式

来进行存放

从而达到这样一个

节约存储空间的目的

好

那我们现在要做的一个问题是

我们已经有了索引结构

那么对一个单词的查询

我们该怎么来做呢

我们看看刚才那样一个例子

我输入这两个单词

也就是说请告诉我

包含这两个单词的文档有哪些

所以我做的第一步

大家看

找到Brutus

从内存当中找到布鲁特斯

所在的位置

比如说是这个地方

找到Caesar在字典中的位置

比如说这个地方

那么我得到两个列表

大家想一想

这包含这两个词的列表的

有哪些呢

或者说文档有哪些呢

显然是这两个集合的什么啊

交集

所以在这个里面就找

Intersect document set

这两个文档的交集就变成了

我的最终的结果

由于这里面我只存储出现的文档

不像刚才的单词文档出现矩阵

我把没有出现的标记为了“0”

所以我们用位与运算

很容易的解决

但是在这里

我们就如果采用稀疏矩阵或者是

倒排索引的方式

你就需要去求交集

那么求交集该怎么来完成呢

大家如果有一定的编程基础

都知道

我可以用外循环

和内循环结合的方式

外循环遍历第一个单词

所在的列表

内循环变量第二个单词

所在的列表

遇到相同的document id

我就把存起来

遇到相同的我就存起来

遇到相同的我就存起来

大家都知道两层循环

它的时间复杂度是o(n^2)

作为大规模的数据处理

我们就考虑了

我们能不能在线性的时间内

获得两个列表的交集呢

在这里我们是有办法的

而且我们这个办法的关键就在于

文档集合列表是按照顺序

document id的顺序

由小到大排列的

如果你事先把它排好了

你是可以在线性时间内完成的

那么在这里我把这个伪代码

放在ppt上面供大家学习

大家可以课后去思考一下

对代码的详细内容

我在这里不做解释了

它的关键点位已经跟大家讲过了

是按照document id去排好序了

所以在这个里面

我们很容易地进行一些循环判断

来达到线性的时间

这个大家去自己分析一下

好，最后我们

可以看一下信息检索

和数据库当中的查询的一些区别

我们简单对比一下

在数据库当中

你肯定有这样一种表

那么在数据库的查询当中

你肯定要符合

某种SQL查询语句的语法要求

比如说你这样的查询要求

你就要写成我们SQL的语法

然后你有这个Salary字段

我才能用Salary进行查询

你有这个Manager字段

我才能用Manager来进行查询

但是在非结构化文本的查询当中

我可能是没有这些信息的

没有这些信息我们只能说

用简单的这样一种

keyword字符串的形式来完成

当然我们的网页实际上

HTML的语言

是带有一定的标签的

我们把HTML的这种网页呢

也可以叫做半结构化

但是这种半结构化的查询

实际上我们仍然是

把文档提取出来之后

按照free text非结构化的

这种语言来完成

所以整个的这样一个过程

也就说在Web上

我们虽然面临的HTML语言

是具有半结构化的数据

但是我们仍然按照

非结构化的方式来进行查询

所以这个还是要用到

我们传统的检索模型

好

那么这是我们今天上课

跟大家讲的主要内容

谢谢大家的观看