Book Note 1: An Introduction to Information Retrieval 读书笔记（一）

An Introduction to Information Retrieval 读书笔记（一）
这本书是 Yahoo! Labs 老大 Dr. P 合著的，近日决定泛读一下.

IR 所谓“方法”其实也就 inverted index 搞来搞去，新的东西不多，都是从别的地方借用过来的感觉。这部分我们整理第一章到第五章的内容，这是关于建立 boolean retrieval 的基本知识。大概的分块如下：

• boolean retrieval，第 1-5 章
• vector space model 和 evaluation，第 6-8 章
• relevence 和几个 specific 的 retrieval 问题，第 9-12 章
• machine learning 方法，第 13-18 章
• web search 和 link analysis， 第 19-21 章

boolean retrieval 要解决的就是一堆“（不）含有 xxx”通过和、或连接起来的 bool 表达式下的 retrieval 问题，这最常用的 inverted index 是相对 forward index 而言：所谓前向索引就是文档编号到所包含内容（如 bag of words 表达）的关系，而倒排索引是 word 对应到哪些文档的关系。对一个较大的语料建立 inverted index 可以用一次 Map/Reduce 实现：

• mapper 输入为 doc ID 和内容，输出为 word, doc ID 的 key/value 对；
• reducer 拿到的是同一个 word 对应的 doc ID 序列，一般我们将其顺序存储到一个链表结构里面；

为了从 query 关联到对应的链表，我们可以用 hash table 或者 trie。剩下的就是处理两个 list 的交、并实现 and/or 的逻辑，事实上使用按照 doc ID 排序后的链表取交可以使用类似 merge sort 中 merge 的策略，类似的实现并也可如此。那么如果要实现“非”，也可以类似处理，只是判断是否出现在取非的部分。

有了这么一个概念，剩下的就是细化里面的一些步骤，比如抽取单词，这部分我们一般需要一些 NLP 的工具做 tokenize 获得一个一个的 token，然后根据语言做 stemming/lemmatization 这样一些 normalization 的步骤（如大小写转换）。对某些特定的问题，我们知道 stop words 可以在这个过程中去掉避免产生的 posting list 过长。为了加速 posting list 的遍历，往往加入所谓 skip pointers，将 list 分段，如每隔长度的算术平方根个 doc 加一个跳转。那么比较精细的做法往往会存下该词出现在某个文档中的频率甚至位置列表。加入这些东西以后可以做 proximity search（指定单词之间的距离不能超过多少）。

我们可以为某些 search 提供一个字典方便加入对含有 wildcard 类型 query 的支持，这一般会使用 search tree（通过前缀获得）。另一方面我们也会引入 edit distance（也叫 Levenshtein 距离）对输入有误的 query 进行修正。

建立好一个 index 需要动态的维护是一个相对较复杂的问题。增加我们可以继续前面类似的操作；删除一般需要维护一个删除列表，在合适的时候移除（lazy delete 策略）；头疼的是更新 =.=

存放的 dictionary、index 均可以用某种方式进行压缩，因此有必要研究各种分布。通常认为语料的大小  与字典的大小  满足 heap’s law，即 ；各个文档中间依照词频排序后对应的比例关系满足 Zipf’s 

law，即 。编码方式往往可以利用前缀性质和变长编码。

开源的 lucene为我们提供了一
套建立 boolean retrieval 的机制。我们可以使用 lucene 提供的简单的命令行为一个目录下面的文件建立 index，

java org.apache.lucene.demo.IndexFiles -docs your-docs-dir
java org.apache.lucene.demo.SearchFiles

进行搜索，如果希望修改已有的建立索引、搜索的流程，可以看看对应文件的源代码。

Please read full article from An Introduction to Information Retrieval 读书笔记（一）