《信息检索导论》 Christopher D.Manning 等著
1. 信息检索：信息检索是从大规模非结构化数据（通常是文本）的集合（通常保存在计算机上）中找出满足用户信息需求的资料（通常是文档）的过程。
2. 检索方式：
1）线性扫描：在文档或者文档集中从头到尾地查找所需信息，扫描过程中可以通过使用正则表达式来支持通配符查找，使用于小规模的文档集。
2）非线性扫描：一种方法是事先给文档建立索引（index）。对每篇文档都事先记录它是否包含词表中的某个词，得到一个布尔值构成的词项-文档关联矩阵（incidence matrix）。
词项（term）是索引的单位，它通常可以用词来表示。在矩阵中，行向量表示每个词项对应的文档向量，即词项在哪些文档中出现或不出现；列向量表示每个文档对应的词项向量，
即文档中哪些词项出现或不出现。可以进行行向量的位与操作来获得查询结果文档集。
3. 布尔检索模型：布尔检索模型接受布尔表达式查询，即通过AND、OR及NOT等逻辑操作符将词项连接起来的查询。在该模型下，每篇文档只被看成是一系列词的集合。
4. ad hoc检索任务：任一用户的信息需求（information need）通过一次性的、由用户提交的查询（query）传递给系统，系统从文档集中返回与之相关的文档。
5. 倒排索引（inverted index）：倒排索引由词项词典（dictionary）和全体倒排记录表（postings）构成。每个词项都有一个记录出现该词项的所有文档的列表，该表中的每个元素记录
的是词项在某文档中的一次出现信息（posting）。每个词项对应的整个表称为倒排记录表（posting list/inverted list）。
在最终得到的倒排索引中，词典和倒排记录表都有存储开销。前者往往放在内存中，而后者由于规模大得多，通常放在磁盘上，我们还可以对每个部分进行存储优化来提高访问效率。
6. 倒排记录表的数据结构：
1）单链表：便于文档的插入与更新，因此通过增加指针的方式可以很自然地扩展到更高级的索引策略。
2）可变长数组：既可以节省指针消耗的空间，也可以采用连续的内存存储，可以充分利用现代计算机的缓存技术来提高访问速度。如果索引更新不是很频繁的话，变长数组的存储方式在空 间上更紧凑，遍历也更快。
原文：http://www.cnblogs.com/summerkiki/p/5129943.html