信息索引导论学习笔记（1）——布尔检索

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

1. 大规模文档集条件下的快速查找。
2. 更灵活的匹配方式。比如grep命令下不能支持诸如Romans NEAR countrymen之类的查询
3. 需要对结果进行排序

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

1. 取出包含字符串“Brutus”的倒排记录表
2. 取出包含字符串“Calpurnia”的倒排记录表
3. 通过合并两个倒排记录表，找出既包含“Brutus”又包含“Calpurnia”的文档

#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
• 通过将词项的df相加，估计每个OR表达式对应的倒排记录表的大小
• 按照上述估计从小到大依次处理每个OR表达式

• 双重否定律
• 德×摩根定律：非（P 且 Q） = （非P）  |  （非Q） 非（P 或 Q） = （非 P） 且 （非 Q）
• 分配律