您好、欢迎来到现金彩票网!
当前位置:八马彩票 > 概念检索 >

搜索引擎概述之布尔检索

发布时间:2019-05-15 13:43 来源:未知 编辑:admin

  阅读本篇文章首先要对“词汇文档矩阵”和“倒排索引”有个基本的认识,要了解相关的知识可以阅读上一篇文章:搜索引擎概述之倒排索引。

  布尔检索是最基础,也是使用最广泛的信息检索模型了。所谓布尔查询就是通过AND、OR、NOT等逻辑操作符将检索词连接起来的查询。比如:

  那么,布尔检索时如何利用倒排索引进行查询的呢?我们还是先从词汇文档矩阵说起吧~

  当我进行布尔查询的时候,其实本质就是在为文档矩阵中的每行1和0组成的二进制数做布尔逻辑运算。

  AND操作就是,相同的位同时为1,则结果为1,否则为0。李白 AND 杜甫最终得出的结果就是文档1和文档2。

  OR操作就是,相同的位有一个位1,则结果为1,都为0结果才是0。杜甫 OR 白居易最终得出的结果就是所有的文档。

  NOT操作就是先将NOT之后的内容取反,再进行AND操作。李白 NOT 苏轼最终得出的结果就是文档1和文档6。

  我们可以发现使用词汇文档矩阵的话,进行布尔检索十分简单。但是我们在“搜索引擎概述之倒排索引”(回复“倒排索引”查看)中说过,词汇文档矩阵是稀疏的,极其浪费空间资源,使用这种结构存储大量的数据是不现实的。因此,我们要使用的是倒排索引。

  那么在倒排索引中我们如何进行布尔查询呢?首先我们先将上边的词汇文档矩阵转换为倒排索引:

  同理,OR查询就是取并集,NOT查询就是从从第一个倒排记录中排除第二个倒排记录的内容。为了高效的完成交集,并集和排除操作,一般我们会要求倒排记录中的文档id是有序的。

  下面我们以三种操作中比较复杂的求交集为例,来说一下布尔查询的算法实现。一种比较常见的倒排记录求交集的算法如下面伪代码所示:

  我们的倒排记录是有序的。我们依次比对两个倒排记录中文档id的值。如果,如果两者id一样则输出该id,然后同时比对下一个文档id。如果两者id不一样,则较大的那个不变,之后去和较小的id的下一个id去做比对。这个算法的时间复杂度是O(x+y),也就是O(N),要远优于无序列表依次作比对的O(N²)。

  当我们去查询一种多个AND组成的查询时,其实本质上就是依次取交集。而且我们很容易知道,对于上边所述的算法来说,如果其中一个集合越短,那么计算可能就越快。因此一个启发式的优化方法就是,在取多个交集的时候,不是去依次的计算,而是先将倒排记录表按照长度从小到大排列,我们先合并最短的两个倒排记录表。这样所有的中间结果的大小都不会超过最短的倒排记录表。因为多个集合的交集元素个数,一定不会大于其中任何一个集合的元素个数。

  如果两个倒排记录表的元素个数差距极大的时候(比如比较极端的:1和10000),我们就没必要依次去比较它们的元素了。采用对短列表中的全部元素分别在长列表中做二分查找的方式,可能会更快。

  另外,使用跳表的方式去实现倒排记录表,也可以加快倒排记录表求交集的速度。但是,由于跳表是一种用空间换时间的数据结构,因此会占用更大的空间。同时,虽然现代计算机的cpu运算速度很快,但是磁盘的访问速度依旧很慢。在这样的前提下,如果是一个将所有索引数据都存在内存中的搜索引擎,使用跳表会加快速度;但如果是将索引数据存储在硬盘上的搜索引擎,反而可能会大大的降低速度。由于篇幅有限,我无法在这里详细的介绍跳表这种数据结构的实现。在未来的文章中我会单独介绍这种数据结构,到时候会再次深入的讨论这个问题。

  布尔查询的本质只是查询了某些词汇在文档中的有无,但是却无法告诉用户哪些是更相关的,哪些是不那么相关的。也就是说,布尔查询本身无法按照相关度进行排序。

  比如说如果每次查询,我都将所有的文档返回,召回率必然是100%(所有的文档中必然包含所有的相关文档),但是正确率就会很低很低(100万文档中只有1万文档真的和需求相关)。而如果我每次只返回一条数据,而且保证这条数据百分之百和用户需求相关,那么正确率就是百分之百(共返回1篇文档,有1篇和用户信息相关,因此是百分之百) ,但召回率很低(1万篇相关文档之返回1篇)。

  如果我要查一篇名字为“Semantic information retrieval research based on co-occurrence analysis”的文章,如果我将所有的空格都识别为AND,这时就只会返回标题为这篇文章的文档,用户无法获得任何其他相关信息。此时正确率很高,但召回率很低。同样,如果我将所有的空格都识别为OR,这时我虽然会获得相关信息了,但是很可能很多相关信息只和information有关,但这并不是我想要的。因此此时虽然召回率很高,但是正确率很低。布尔检索在召回率的问题上很容易走两个极端,很难达到理想的均衡状态。

  然而在检索引擎几十年的发展中,已经有很多方案在完善这些问题,或者说在增强布尔查询的能力。而另一方面,也有了一些新的检索模型或技术(如,自由文本查询)来解决这些问题。这些我都将在未来的文章中,慢慢的介绍给大家。返回搜狐,查看更多

http://essexappliance.net/gainianjiansuo/234.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有