信息检索

信息检索导论第一章－－布尔检索

信息检索导论第一章–布尔检索

一、信息检索概述

信息检索
信息检索是从大规模非结构化数据（通常是文本）的集合（通常保存在计算机上）中找出满足用户信息需求的资料（通常是文档）的过程。

数据的类型

  • 结构化数据：指具有固定格式或有限长度的数据,如数据库,元数据等。
  • 非结构化数据(全文数据)：指不定长或无固定格式的数据,如邮件,word 文档等自有文本。
  • 半结构化数据：如 XML,HTML 等,当根据需要可按结构化 数据来处理,也可抽取出纯文本按非结构化数据来处理。

传统信息检索与现代信息检索
传统信息检索主要关注非结构化、半结构化数据。
现代信息检索关注非结构和半结构化数据的同时也处理结构化数据。

二、倒排索引

顺序扫描：这种现行扫描是一种最简单的计算机文档检索方式。这个过程通常称为 grepping，它来自于Unix下的一个文本扫描命令grep。
顺序扫描的不足：

  • 速度慢(特别是大型文档集)
  • 有时我们需要更灵活的匹配方式。比如，在 grep 命令下不能支持诸如 Romans NEAR countrymen之类的查询，这里的 NEAR操作符的定义可能为“5个词之内” 或者“同一句子中”。
  • 不支持检索结果的排序(即只返回较好的结果)

词项－文档关联矩阵

词项—文档关联矩阵，其中每行表示一个词，每列表示一个剧本。当词t在剧本d中存在时，矩阵元素（t，d）的值为 1，否则为 0

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

词项－文档关联矩阵是一种高度稀疏的矩阵，因此仅仅保存其非零位置更好。因此引入
倒排索引的概念。

1、倒排索引的构建

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

三、布尔查询处理

1、AND查询

考虑查询Brutus AND Caesar：

  • 在词典中定位 Brutus
    • 返回对应倒排记录表(对应的docID)
  • 在词典中定位Caesar
    • 再返回对应倒排记录表
  • 合并(Merge)两个倒排记录表，即求交集

    合并过程：
    每个倒排记录表都有一个定位指针，两个指针同时从前往后扫描, 每次比较当前指针对应倒排记录，然后移动某个或两个指针。合并时间为两个表长之和的线性时间
    假定表长分别为x 和y, 那么上述合并算法的复杂度为 O(x+y)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
if(operator.equals("AND")){
	if(tokenList1.size() == 0 || tokenList2.size() == 0){
		System.out.println("There is no Document both contain " + token1 +" and " + token2);
	}else{
		while(i < tokenList1.size() && j < tokenList2.size()){
		if(tokenList1.get(i) == tokenList2.get(j)){
			result.add(tokenList1.get(i));
			i ++;
			j ++;
		}else if(tokenList1.get(i) < tokenList2.get(j)){
			i ++;
		}else if(tokenList1.get(i) > tokenList2.get(j)){
			j ++;
		}
	}
	System.out.print("The Document both contain " + token1 + " and " + token2 +": ");
}

2、OR查询

考虑查询Brutus OR Caesar：

  • 在词典中定位 Brutus
    • 返回对应倒排记录表(对应的docID)
  • 在词典中定位Caesar
    • 再返回对应倒排记录表
  • 对两个倒排记录表求并集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
else if(operator.equals("OR")){
	if((tokenList1.size() == 0 ) && (tokenList2.size() == 0)){
		System.out.println("There is no Document contain " + token1 + " or " + token2);
	}else if((tokenList1.size() == 0) &&(tokenList2.size() != 0)){
		result.addAll(tokenList2);
		System.out.println("The Document contain " + token1 + " or " + token2 + ": ");
	}else if((tokenList1.size() != 0) &&(tokenList2.size() == 0)){
		result.addAll(tokenList1);
		System.out.println("The Document contain " + token1 + " or " + token2 + ": ");
	}else if((tokenList1.size() != 0) &&(tokenList2.size() != 0)){
		while(i < tokenList1.get(i) && j < tokenList2.size()){
		    if(tokenList1.get(i) == tokenList2.get(j)){
				result.add(tokenList1.get(i));
				i ++;
				j ++;
			}else if(tokenList1.get(i) < tokenList2.get(j)){
				result.add(tokenList1.get(i));
				i ++;
			}else if(tokenList1.get(i) > tokenList2.get(j)){
				result.add(tokenList1.get(j));
				j ++;
			}
		}
		System.out.println("The Document contain " + token1 + " or " + token2 + ": ");
	}
}

3、NOT查询

考虑查询NOT Brutus：

  • 在词典中定位 Brutus
    • 返回所有不包含Brutus的倒排记录表(对应的docID)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
else if(operator.equals("NOT")){
	if((tokenList1.size() == 0 ) && (tokenList2.size() == 0)){
		System.out.println("There is no Document contain " + token1 + " not " + token2);
	}else if((tokenList1.size() == 0) &&(tokenList2.size() != 0)){
		System.out.println("There is no Document contain " + token1 + " not " + token2);
	}else if((tokenList1.size() != 0) &&(tokenList2.size() == 0)){
		result.addAll(tokenList1);
		System.out.println("The Document contain " + token1 + " not " + token2 + ": ");
	}else if((tokenList1.size() != 0) &&(tokenList2.size() != 0)){
		while(i < tokenList1.get(i) && j < tokenList2.size()){
			if(tokenList1.get(i) == tokenList2.get(j)){
				i ++;
				j ++;
		    }else if(tokenList1.get(i) < tokenList2.get(j)){
				result.add(tokenList1.get(i));
				i ++;
			}else if(tokenList1.get(i) > tokenList2.get(j)){
				j ++;
			}
		}
		System.out.println("The Document contain " + token1 + " not " + token2 + ": ");
	}
}

4、布尔检索的优缺点

优点：构建简单、常用

缺点：

  1. 布尔查询构建复杂，不适合普通用户。构建不当，检索结果过多或者过少
  2. 没有充分利用词项在文档中的词项频率(term frequency, tf)信息
  3. 不能对检索结果进行排序

5、通用的查询优化策略

每个布尔表达式都能转换成下述形式(合取范式)

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

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

  • 获得每个词项的df
  • (保守)通过将词项的df相加，估计每个OR表达式对应的倒排记录表的大小
  • 按照上述估计从小到大依次处理每个OR表达式

反例：[1,2,3,4] and [1,2,3,4] and [5,6,7,8,9] 4+4>4