信息索引导论学习笔记(1)——布尔检索

信息检索

信息检索(Information Retrieval,简称IR):从大规模非结构化数据(通常是文本)的集合(通常保存在计算机上)中找出满足用户信息需求的资料(通常是文档)的过程

信息检索按照规模分类:
  • 以web搜索为代表的大规模级别
  • 小规模级别,典型示例为个人信息检索
  • 中等规模级别,面向企业、机构和特定领域的搜索

倒排索引

顺序扫描:这种线性扫描就是一种最简单的计算机文档检索方式。这个过程通常称为grepping,它来自于Unix下的一个文本扫描命令grep。

顺序扫描无法满足的几种情况:
  1. 大规模文档集条件下的快速查找。
  2. 更灵活的匹配方式。比如grep命令下不能支持诸如Romans NEAR countrymen之类的查询
  3. 需要对结果进行排序
词项-文档的关联矩阵



词项-文档的关联矩阵,其中每一行代表一个词,每列表示一个剧本。当词t在剧本d中存在时,矩阵元素(t, d)的值为1,否则为0

为想要查询 Brutus AND Caesar AND NOT Calpurnia,我们分别取出 Brutus,Caesar及Calpurnia对应的行向量,并对Calpurnia对应的向量求反,然后进行基于位的与操作,得到:
110100 AND 110111 AND 101111 = 100100

词项-文档(term-doc)的关联矩阵具有高度稀疏性,仅仅保存非零的位置明显更好

倒排索引的构建
  • 对每个词项t,记录所有包含t的文档,建立词条序列<词条,docID>二元组
  • 对词项、文档排序。按词项排序,然后每个词项按docID排序
  • 合并词项,并记录词项的文档频率df(对每个词项t,记录所有包含t的文档数目)



布尔查询处理

and查询处理

比如说,我们要寻找既包含字符串“Brutus”又包含字符串“Calpurnia”的文档,我们可以采用归并的方法(类似于归并排序中的merge操作),进行如下几步:
  1. 取出包含字符串“Brutus”的倒排记录表
  2. 取出包含字符串“Calpurnia”的倒排记录表
  3. 通过合并两个倒排记录表,找出既包含“Brutus”又包含“Calpurnia”的文档



利用归并的算法,可以在O(n)的时间复杂度求出交集,书上用链表,我为了方便,直接用数组了

#include <stdio.h>

int main(void)
{
	int arr1[7] = {1, 2, 4, 11, 31, 45, 173}; /*Brutus文档集合*/
	int arr2[4] = {2, 31, 54, 101}; /*Calpurnia文档集合*/
	int result[7] = {0}; /*交集集合*/
	int i, j, k, len1, len2;

	/*变量初始化*/
	len1 = sizeof(arr1) / sizeof(int);
	len2 = sizeof(arr2) / sizeof(int);

	/*归并算法*/
	for (i = j = k = 0; i < len1 && j < len2;) {
		if (arr1[i] == arr2[j]) {
			result[k] = arr1[i];
			i ++;
			j ++;
			k ++;
		} else if (arr1[i] < arr2[j]) {
			i ++;
		} else if(arr1[i] > arr2[j]) {
			j ++;
		}
	}

	/*打印输出*/
	for (i = 0; i < k; i ++) {
		printf("%d ", result[i]);
	}
	printf("\n");

	return 0;
}

通用的查询优化策略(词典中保存文档频率df的一个充分理由)

(madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)

  • 每个布尔表达式都能转换成上述形式(合取范式)
  • 获得每个词项的df
  • 通过将词项的df相加,估计每个OR表达式对应的倒排记录表的大小
  • 按照上述估计从小到大依次处理每个OR表达式

布尔逻辑转换(数学理论)

可以参考我之前写的一篇博客: http://blog.csdn.net/zinss26914/article/details/9056049

这种变换基于关于逻辑等价的规则:
  • 双重否定律
  • 德×摩根定律:非(P 且 Q) = (非P)  |  (非Q) 非(P 或 Q) = (非 P) 且 (非 Q)
  • 分配律

参考链接

相关文章
相关标签/搜索