何为信息检索？
从大规模非结构化数据(通常是文本)的集合(通常保存在计算机上)中找出满足用户信息需求的资料(通常是文档)的过程。文本数据往往被认为是典型的非结构化数据。
非结构化 v.s 无结构？
没有数据是完全无结构的，比如网页就是一种半结构化数据
<title>李甲主页</title>
<body>…</body> …
一般是如何实现文档分类的？
通常做法是，先手工标注一些文档，然后借助这些已标注文档来自动判断其他文档的类别。
补充几个知识点？
词项不一定是词！
比如I-9、Hong Kong都是词项，但是它们并不是词。
ad hoc检索
通过一次性的、由用户提交的查询传递给系统，系统从文档集中返回与之相关的文档。
语料库
所有文档组成的文档集。
正确率
返回的结果中真正和信息需求相关的文档所占的比例。
召回率
所有和信息需要真正相关的文档和被检索系统返回的百分比。
词项-文档关联矩阵？
为了响应Brutus AND Caesar BUT NOT Calpurnia，我们分别取出Brutus、Caesar及Calpurnia对应的行向量，并对Calpurnia对应的向量求反，然后进行基于位的与操作，得到：
110100 AND 110111 AND 101111 = 100100.
结果向量中的第1和第4个元素为1，这表明该查询对应的剧本是Antony and Cleopatra和Hamlet。
词项-文档矩阵的缺点？
庞大的矩阵实际上具有高度的稀疏性，即大部分元素都是0。
实际情况是99.8%左右的元素都为0。
为解决以上缺点，引入倒排索引？
何为倒排索引？
被用来存储在全文搜索下某个词项在一个文档或者一组文档中的存储位置的映射。也就是一个词项后面跟着一个记录表，用来记录该词项在哪些文档中出现过。
一般左边的词典存放在内存中；右边的倒排记录存在磁盘中。
倒排记录到底如何存储？
单链表法
便于文档插入和更新，便于更高级的索引策略（如，跳表）的实现。
变长数组法
节省指针消耗的空间，内存连续存放，利用计算机缓存技术可以提高访问速度。
倒排索引是如何构建的？
如何布尔查询？
将倒排记录表进行交集（∩）操作，该操作也称为合并操作——执行逻辑“与”操作。
假定表长分别为x 和y, 那么上述合并算法的复杂度为 O(x+y)。
关键原因: 倒排记录表按照docID排序。
优化布尔查询？
AND
每次将倒排记录最短的两个进行合并。
OR
(保守)通过将词项的倒排记录相加，估计每个OR表达式对应的倒排记录表的大小。
按照上述估计从小到大依次处理每个OR表达式。
布尔检索的缺点？
表达式相当复杂，构造困难！
不严格的话结果过多，而且很多不相关；非常严格的话结果会很少，漏掉很多结果。
布尔查询构建复杂，不适合普通用户。构建不当，检索结果过多或者过少。
没有充分利用词项的频率信息
1 vs. 0 次出现
2 vs. 1次出现
3 vs. 2次出现, …
通常出现的越多越好，需要利用词项在文档中的词项频率(term frequency, tf)信息。
不能对检索结果进行排序。
References:
[1] Christopher D.Manning, Hinrich Schütze, Prabhakar Raghavan, 王斌[译]. 信息检索导论[M]. 北京:人民邮电出版社, 2016.
[2] 王斌,信息检索导论讲义,lecture1-booleanretrieval,2017
@qingdujun
2017-12-9 北京 怀柔