术语介绍
信息检索（Information Retrieval）：信息检索是从大规模非结构化数据（通常是文本）的集合（通常保存在计算机上）中找出满足用户信息需求的资料（通常是文档）的过程。
非结构化数据：计算机不易处理的那种。
结构化数据：懂得都懂，DB。
聚类（clustering）是根据文档内容让文档自动聚团， 分类（classification）是基于某种信息需求，将文档分到一个或多个类别的任务。
按所处理的数据规模：
Web搜索：大规模，需要处理在数百万台计算机上的数十亿文档。
个人信息检索：小规模，例如个人计算机上各种格式的文档等等。
面向企业、机构和特定领域的搜索：介于上述两种之间的规模，例如公司内部文档、专利库或生物医学文献的搜索。
1.1 一个信息检索的例子
比如搜索含有‘Brutus’和‘Caesar’但不包含‘Calpurnia’的文档，一种方法是grep，来自于Linux的grep命令，就是从头到尾线性扫描所有文档，找出符合这个条件的文档。
1）grep无法完成在大规模文档集条件下的快速查找。
2）有时可能需要更灵活的匹配方式。比如我们需要找到某两个关键词之间距离不超过两行的文档。
3）需要对结果进行排序。
词（term）是索引的单位，它通常可以用词来表示，词不一定是词，比如I-9，Hong Kong可以是term但它们不是词。
布尔检索模型：接受布尔表达式查询，即通过AND、OR及NOT等逻辑操作符将term连接起来的查询。每篇doc只被看成是一系列词的集合。
ad hoc检索任务：任意用户的信息需求通过一次性的用户提交的query传递给系统，系统从文档集中返回与之相关的文档。
文档（doc）指的是检索系统的检索对象，它们可以是一条条单独的记录或者是一本书的各章。
正确率（precision）：返回结果中真正的信息需求相关的文档所占的百分比。
召回率（recall）：所有和信息需求真正相关的文档中被检索系统返回的百分比。
倒排索引（inverted index）:从词项反向映射到文档。其实‘倒排’两字有些多余。
词项词典（dictionary）:倒排索引中记录的term。
每个词项对应的整个表称为倒排记录表（posting list）或倒排表（inverted list），倒排表记录的是包含这个term的所有文档，往往还会包含term在文档中出现的位置。
1 dictionary posting list 2 3 Mike 2->5->10->15 4 have 1->2->4->5->6->16->57->132 5 Caesar 2->31->54->101
倒排索引两个部分，词典和倒排表，词典中记录了数据集中所有的term，词典中的term按照字母序排序、倒排记录表中按docID进行排序。
1.2 构建倒排索引
（1）收集需要建立索引的文档。
（2）将每篇文档转换成一个个词条（token）的列表，这个过程通常被称为词条化（tokenization），或者分词。
（3）进行语言学预处理，产生归一化的词条来作为term，比如friends -> friend，Romans->roman等，做一些处理。
（4）对所有文档按照其中出现的term来构建倒排索引，索引包含一部词典和一个全体倒排记录表。
词典和倒排记录都有存储开销。词典往往放在内存中，倒排记录因为规模大得多，通常放在磁盘上。也会有相应的一些方法来优化存储结构，一般来说存倒排记录可以使用单链表或者变长数组。
建立倒排索引的过程；词项加上docID通过按照字母顺序排序。通过词项进行合并，词项存储在词典中，每个词项有一个指针指向倒排记录表。
上述操作执行完之后，对每篇doc建立索引时的输入就是一个归一化的词条表，也可以看成二元组（term，doc ID）一个term在同一个doc中的多次出像会被合并，最后整个结果分成词典和倒排记录表两部分。
同时也可以记录一些统计信息，比如出现某个term的doc的数目，即doc frequency。
1.3 布尔查询的处理
对于一个query： Brutus AND Calpurnia，
（1）定位Brutus和Calpurnia在词典中的位置，并获取到它们的倒排表。
（2）对两个倒排表求交集（merge结果）
// 因为倒排表按docID排序了
while(p1 != nullptr && p2 != nullptr) {
if(p1->docid == p2->docid) {
result.push_back(p1->docid);
p1 ++;
p2 ++;
}
else {
if(p1->docid > p2->docid) p2++;
if(p2->docid > p1->docid) p1++;
}
}
这个merge操作需要O(x+y)的时间，x和y分别是两个倒排表的长度。
查询优化：一般可以先获取较短的倒排表再进行合并，或者对于一个长倒排表和一个很短的已经经过几次合并计算的中间结果的合并，可以在长的倒排表上通过二分查找等手段快速实现合并。
1.4 对基本布尔操作的扩展及有序检索
与布尔检索模型相对的是有序检索模型，布尔检索最后得到的结果集是无序的，往往不能满足用户的需求。
我理解有序检索模型就是加入了算分排序的检索模型，通过指定一些指标，来衡量结果与查询的相关程度；例如加入term proximity来衡量两个词在文档中的靠近程度（词的紧密度）。
总之，布尔模型的无序结果不能完全满足需求，需要对结果集进行排序（算分排序也是现代搜索引擎中几乎是最重要的部分）。
1.5 参考文献及补充读物
布尔查询的OR和AND会导致检索结果的precision和recall分别走向两个极端，不能达成很好的均衡，之后还会介绍存储结构，正则表达式等知识。