Information retrieval (IR class1)

1. 什么是IR？ IR与数据库的区别？

答：数据库是检索结构化的数据，例如关系数据库；而信息检索是检索非结构化/半结构化的数据，例如：一系列的文本。信息检索是属于NLP（自然语言处理）里面最实用的一个场景，应用之一。

2. 什么是term-document incidence matrix？

答：文档中，出现了某个词记做1，未出现记做0的矩阵。 e.g, 单词集合 W={w1, w2, w3, w4}，文章集合 D={d1, d2, d3, d4, d5}。 term-document incidence matrix 如下所示：

查询语句：w1 ∩ w2 ∩ w3 ∩ w4 (意思是：查找一篇文档，要求文档中出现了单词w1, w2, w3, w4)

答：做字节与运算：

　　　　　　　　01111

　　　　　　　 + 11011

　　　　　　　 + 101111

　　　　　　　 + 00001

--------

　　　　　　　 00001

　结果表示，只有文档d5符合条件。也就是只有d5中同时出现了w1～w4这四个单词。

3. 什么是 “inverted index” ？

由2可知，我们得到了term与documents的相关矩阵。但是存在的问题是： 1. 费空间 2. 稀疏矩阵 sparse matrix。

所以，我们需要用到inverted index。也就是以链表的形式，表示文档。

例如：

仍然用2中的例子：可以表示如下：

w1 ： 2 -〉3 -〉4 -〉5

w2: 1-〉2-〉4-〉5

w3： 1-〉3-〉4-〉5

w4： 5

可以使用链表linked list，也可以使用连续的list，continuous list. 前者访问快，后者省空间。具体权衡视情况而定。

此时，w_1 - w_n 称为“字典部分”（dictionary），而后面的索引的数字称为“posting”。每一个word都有一个“posting list”

4. 如何使用“inverted index”求 AND OR NOT运算

　答： w1 的inverted index 是：w1_postingList={ 1,2,3,4,10}

　　　　同理，　　　　　　　　 w2_postingList={1,2,5,6,8}

　　　　　　　　　　　　　　　w3_postingList={7,8}

　　w1 AND w2 OR w3 = w1_PL ∩ w2_PL ∪ w3_PL = {1,2,7,8}

5. inverted index 的构造流程

6. query optimization

1⃣️ 对于一个包含n的term的query， query q ： A AND B AND C

　　最优的策略是：按照升序的顺序

2⃣️ 同理，对于query q ： A OR B OR C

　　最有的策略是：按照升序的顺序

巴特西