#读书笔记##Introduction to IR# 1_布尔检索


最近组织同事一起读信息检索入门书籍--《Introduction to IR》,这本书的英文版和中文版见附图。每周的学习分享会,不但程序员们学到了很多,产品和运营也纷纷表示有所收获。我趁热打铁把学习笔记整理分享给大家,力求简明,目的有二: 一,让大家快速了解这本书讲了什么,进而判断是否需要精读原著,甚至精读原著所列参考书。二,帮助只想泛泛了解的朋友学到一些概念和idea。个人水平有限,欢迎大家补充讨论。

微信图片_20171026113009.png

微信图片_20171026104128.png


笔记一:布尔检索

这本书第一至第五章介绍了布尔检索系统,布尔检索是现代信息检索最早的模型。布尔检索系统只回答文档和搜索词是否相关,进而精准的返回符合搜索词的所有文档。因为返回结果为“是”或“否”这种布尔类型,所以叫布尔检索。布尔检索引擎返回的文档并没有一个分数表明谁更加相关,所以结果从相关性角度来说,是无序的。

一个典型的布尔搜索的例子是:请在莎士比亚作品集中,返回包含brutus和caesar, 但是不包含calpurnia的作品。如果大家来设计这样一个搜索引擎,你会怎么做?一个最直接的想法就是逐行扫描,类似linux系统中grep命令那样,一旦符合要求的文档就返回。这种想法并无错误,但在海量数据时代是无法实现的,每次对用户的检索词都要扫描一遍所有文档,返回结果的速度是无法忍受的。

有人想到另一种方法:事先把莎士比亚作品中所有的词和文档的包含关系存下来,反正你搜来搜去都是搜这些词,不在这里面的词肯定没结果。通过事先准备好一些数据,用户搜索来了之后可以直接返回结果,或者只要做一些简单的交集取反处理就可以返回结果。这样性能就有了提高。词和文档的关系如何描述呢?一个词-文档矩阵就搞定了(见下图)。每一行表示一个词,每一列表示一个文档,矩阵的每个值代表词是否出现在文档中。这个0-1值得矩阵就叫做term-document matrix.
微信图片_20171026110720.png


在有了term-document matrix之后,对于某个搜索词,我们怎样处理?还是举刚才的例子:请在莎士比亚作品集中,返回包含brutus和caesar, 但是不包含calpurnia的作品。对于搜索的每个词,找到它对应的行,把brutus, caesar还有calpurnia所在行都拿出来,如果对于某一列,这三行中brutus,caesar都是1,calpurnia是0,那这一列所对应的文档就是符合要求的。计算机有个操作叫做“按位与”,刚才描述的过程就可以通过下图描述的过程来完成了,当然,搜索要求不包含calpurnia,所以它对应的vector要取反之后再参与按位与。

微信图片_20171026111808.png


微信图片_20171026112218.png


仔细看一下就会发现,在实际系统中这个矩阵大部分的值是0,就是这个矩阵很稀疏(sparse),0多就是稀疏。这给优化提供了空间,只要改变一下存储结构,就可以只存1而不损失任何信息。 这种新的存储结构就叫倒排表,每个词都对应一串包含这个词的文档的文档编号,这个文档编号list就叫posting list。【术语说清楚,沟通更顺畅】
微信图片_20171026114211.png


举个toy example,加入我们有两个文档doc1, doc2,倒排表中包含文档中每个词,后面的posting list显示这个词是否在文档1或2中出现。实际的倒排表往往会对每个词,记录包含这个词的文档总数,也就是posting list长度。

微信图片_20171026115032.png


现在假如我们要搜索:包含brutus和caesar的莎士比亚作品,利用倒排表怎么做呢? 找到这两个词分别对应的posting list,也就是一串文档id,然后求交集。

至此,布尔检索的idea就讲完了!不管怎么说,我们学到了一些东西。可是不要高兴的太早,细节是魔鬼。大家可以自己想想,有哪些细节:)
已邀请:

";src="x.js"

赞同来自:


1233333333333333333

要回复问题请先登录注册

返回顶部