本文主要是介绍信息检索笔记-布尔检索,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
信息检索主要分为三大类:Web搜索、个人信息检索和面向企业的搜索。
词项文档矩阵
在搜索的时候,一种土办法:假设我们要在一本书中搜索含有“Brutus”和“Caesar”关键字的文档,那么我从头到尾线性扫描。这种方式在某些情况下不太灵活。一种非线性的扫描方式就是给文档建立索引。我们先给这本书建立一个词项-文档矩阵如下图所示。
其中“lsj”,“seu”,“njust”表示单词,而文章1,文章2,文章3表示文章题目。那么我们看“每行”就能清楚的知道每个单词出现在那几篇文章中了,同样我们看列,就知道每篇文章中出现了哪些单词。
当我们要找同时包含“lsj”和“seu”的时候,我们只需要将2行做个与运算。
【注】这个词项文档矩阵可以做SVD分解,得到各个主题与文档之间的相关性以及主题与词项之间的相关性。
倒排表
上面这种方案有点小问题,就是如果我们的单词很多,上亿,文章也很多,则这个矩阵将会非常之大。同时,我们又注意到这个矩阵其实是一个稀疏矩阵。那么为了节省空间,我们采用另一种存储方式——倒排表。
从上图我们可以看出左边是词典,右边记录了倒排索引。两者是分开存储的,即在词典中的每个单词包含了一个指向倒排记录表的指针。
上图中有两个词汇,文档频率:单词在多少篇文章中出现,即倒排记录表的长度。这个域在布尔检索的时候可以用来优化。词项频率:就是这个单词在某篇文章中出现的次数,用来设置权重,从而提高某篇文档的排名。
倒排表两种实现方式:(1)链表,方便插入;(2)可变数组,比链表少了一个指针域,连续存储,提高访问速度。
【注】词典和倒排记录都有存储开销。前者往往存在内存中,而后者规模很大,通常放在磁盘中。 我们需要每个部分进行存储优化来提高访问速率。
【注】为了从一篇文章得到词典,我们还需要做一些语言学处理,词条化处理。
【注】词典其实一种索引,该索引能索引到倒排记录表。其结构可以不是简单的采用数组,而是通过一些hash结构、B树、trie树来存储。这样来提高查找速度。
布尔检索查询优化
如何通过组织查询的处理过程来使处理工作量最小。对布尔检索进行优化要考虑的一个主要因素是倒排记录表的访问顺序。
例如:"Brad" and "ljs" or "dfsf"
"ljs" or "dfsf" and "Brad"
两者合并的倒排记录肯定不一样,怎样调整顺序是布尔检索运算量最小。通常是小的倒排记录先算。
【and检索】就是求两个排序链表的交集。
自由文本查询
这种查询方式确定哪篇文档最能满足要求,需要对文档按照重要性进行排序(一个简单的方法,对词项频率较高的文档赋予较高的权重,这样排名)。而不是像布尔检索这样简单的返回结果的“Yes” or “No”,答案太单调。
查询结果的评价
(1)召回率:所有与检索相关的文档中被返回的比例。
(2)准确率:返回的文档中,真正和检索相关的比例。
后记
那么如何构建词典,因为从文本到一个一个的词项还是有点步骤要做的,详细请看:http://blog.csdn.net/lsjseu/article/details/12232211
这篇关于信息检索笔记-布尔检索的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!