Week 1

C1

Boolean model 是老师引入信息检索的例子。这个就是使用 NOT/AND/OR 等 boolean 操作符搜索符合条件的文档。 例子：

• 文档中包含有 Anony这个词

一个最简单的想法就是将所有的要检索的词（terms）和所有文档做一个矩阵，0无1有。然后按行得出一个 vector ，之后用 boolean 操作符计算就好了。 问题就是当文档量上来之后就出现了问题： terms 和文档构成的矩阵的数据将远大于可能含有的 “1” 的数量形成一个稀疏矩阵浪费空间。 介绍！ Inverted Indexing！
将文档数据整理为一个更方便的数据结构的过程就叫 Indexing。 在这里使用的是一个 有序 list 结构，将文档序号 list 附带到 terms 后。 ![[信息检索1.png]]

Index 步骤：

1. 将输入的文档转化为 Token 序列
2. 将得出的 terms 按字母顺序排序
3. 根据排序出的构成一个字典
4. 然后将构建文档的序号 list 有序的排列到 字典对应的 terms 后面，构成一个有序 list ，这个过程叫做posting

AND 检索算法：O(X+Y)

两个 list 索引a/b从头开始, 一个空列表 answer：
if a < b -> a++ if b < a -> b++ if a == b -> 对应序号加入answer，ab++

C2

Query 优化 通过排序 OR 和 AND 操作，可以优化操作： AND 在较短的list之后可以直接完结，而不用走完整个较长的list。

Skip Pointer： 通过在某些节点加入指针指向后面的节点可以节省检索过程。

Tokenization 对于每一个对文档动的操作，应该也对 query 做。

之后是一对在 Normalization 和 Tokenization 过程中的难点