Ranking with Indexes

本章内容：索引结构

1、每个系统都需要对应的数据结构(data structures)。信息检索中最常用的数据结构是：倒排索引(inverted index)。

2、本章的另外一个主题是：查询处理(Query processing)，即如何让查询使用索引的数据。

3、抽象检索模型：
(1)一篇文档被转化为对应的词项(index terms)，形成不同的特征(features)
(2)主题特征(topical features)：比如在Query中出现的词，得分高。
(3)非主题特征/质量特征(quality features)：比如链入(inlink)数量、网页最近更新事件(Last Update)等。
(4)各种特征(features)综合起来，形成一个特征函数(feature function)，用于打分和排序。

4、特征函数(feature function)一般综合文档、查询两个部分的得分。如果文档得到了高分，说明它与Query很相关，应该靠前返回。

5、更具体的来举例：R(Q, D) = Sum(gi(Q)fi(D))，其中i是每一个feature，如每个词、每个文档质量得分；f是对文档计算的得分，g是对查询计算的得分。

6、其实查询也可以包含文档质量因素：如"today's weather"这个Query，则今天的天气网页的g得分会更高。

7、信息检索中，最常用的结构是：倒排索引。早期也有signature file，把一段文字按照hash后存储为bit的方式放置，不过缺点很多，就慢慢不用了。

8、倒排索引表是通过词项(index term)阻止的。每一个词项(entry)跟着倒排链(posting)，posting指明了这个term在哪些个文档中出现过。

9、倒排索引的优势之一：可以仅检查少量倒排链，就能完成整个查询过程。

10、另一种存储数据结构是k-d树。

11、但常用的还是倒排索引，一般来说，打分函数(ranking function)越复杂，所需要的信息就越多，也就又越多的信息需要存储在倒排索引里面。

12、最基本的倒排索引：词表+倒排链。
例如：
fish 1 2 3
money 2  4

表示词fish在文档1、2和3中出现过。这种倒排索引甚至不记录词在文档中出现的频率，只记录是否出现。

当两个词查询fish money时，实际就是在对链fish和money进行交操作。传统归并算法是O(max(m,n))的事件复杂度，使用跳表，可以将它缩减到O(min(m,n))

13、加入了counts的倒排索引：在posting每一项中，同时记录它在x文档中出现了y次。实际就是tf啦，tf是非常有利的工具。出现的tf越多，则越相关。

如：

are 3:1 4:1
fish 1:2 2:3 3:2 4:2

:之前是哪篇文档，之后是在这个文档中出现了几次。

14、加入了位置信息的倒排索引，除了count外，还记录每一次都出现在什么位置。位置信息对于phrase检索(短语检索)非常有用。其他一些模型也会利用位置信息。

由于需要记录每次出现的位置，就没必要单独记录counts了。

例如：

fish 1,2 1,4 2,7 2,18 2,23

表示在第1篇文档出现两次，分别位于2和4，第2篇文档出现3次，分别是位置7、18和23。
关于怎么用位置信息搜短语，看书吧，不复杂，就不说了

15、在真正的信息检索中，都是有多个域的，而且很多域有同等重要的地位。

16、对于多个域的检索，简单的方法是，给每个倒排链附加一个bit-map，bit-map长N，假设有N个域。在title出现，则第一位为1，content没出现，则第2位为0。

17、上面这种方法，对于一个域出现了多次就不好处理了，例如有三个作者！张三、李四、王五。（假设按照字分词）我们搜李五，是可以搜到的。这显然不太合适。

18、为此，提出了域范围列表(extent list)这个形式。除了传统倒排索引外，附加N个域名范围(extent list)列表。每个extent list里面，记录了每个域在每篇文档中出现的M次的位置和长度。

具体看书138页吧。

19、理论上，是可以把算好的得分直接写到索引，而不存基础信息的，这有好有坏。
(1)好：让很多超复杂打分公式的应用成为可能，计算一次即可，Query会很快。
(2)不好：不灵活，一旦更改打分函数，就会很麻烦。另外会丢掉一些原始信息。

20、到目前为止，我们一直假设posting是按照docid升序/降序排列的。但这不是必须的、更不是唯一的。还可以按照分数等排序。

21、压缩是索引中非常重要的一部分。

22、在现在计算机的存储结构中，内存是较快的，但很小不足以放下全部索引。而硬盘的空间足够大，速度却很慢。因此，检索的性能主要取决于如何利用好内存。

23、压缩的两个目的：
(1) 存同样的索引，使用更少的硬盘空间。
(2) 内存不变的前提下，能让更多的索引加载到内存中。

24、压缩同样有缺点：需要耗费CPU解压缩。关于如何定义有效的压缩，书上给出了比较麻烦的定义。简而言之，解压缩所增加的时间要小于减少的磁盘I/O时间，就是可以的。

25、索引压缩，一般都是无损压缩，对于小波变换等图像、信号领域常见的有损压缩，不予讨论。

26、一般对于文档ID、TF、Position等信息的压缩非常有效。

27、压缩技术的原理是概率论（信息熵）。最基本的思路：赋予常出现的字符较短的编码，很少出现的给它长编码。一个经典方案就是霍夫曼编码。

28、可以证明，任何一种压缩算法都不能保证对每个字符都减小(对应的编码长度)。

29、一个假设：小的数值比大的更容易出现。对于词频，这是显然的（一篇文档里大多数词都只出现1~2次）。而对于docID这种就不可能了，但我们可以用delta(两个文档之差)来表示docID。比如文档：

1, 5, 9, 18, 23, 24, 30, 44, 45, 48

用Delta编码后就变成了：

1, 4, 4, 9, 5, 1, 6, 14, 1, 3

这样，就把很大的docID变成了很小的数值。而且docID一般是一个一个的取，这样计算起来也不会很麻烦。

将大数转化为小数本身不能压缩，但它方便了其他压缩算法，进一步节省空间。

30、基于比特对齐(Bit-Aligned Codecs)的编码：最简单的Unary code，稍微复杂些的Elias gamma、Ealias 嘎码。

31、Unary Code：表示N，N个1加一个0。如3 -> 1110。对于0和1这样小的数字，这种表示方法非常经济（只耗费1个比特，而即使用byte也要1个字节）。但对于大的数字就不划算了，比如1023, 要耗费1024比特，而传统编码2字节=16比特就能搞定！

32、Elias gamma编码也是一种比特编码的压缩方式。数字k表示为kd和kr两部分。
kd = [log2k] (向下取整)，用Unary Code表示
kr = k - 2^[log2k]

更直观的计算方法：kd是k表示为2进制之后要写的位数（位长度-1个1和1个0），kr是k表示为2进制后，去掉最左边的1，剩下的部分。

例如1023, 2进制为1111111111，共10位，所以kd=10-1 = 9，用Unary Code表示为1111111110，去掉最左边第一个1后，剩下的为11111111。

33、Ealias 嘎码更进了一步，对kd再次进行一次log2取整。

34、尽管比特压缩的方法看起来很美好，但实际上(计算)性能并不好。因为大多数CPU都是以字节为基础单位处理的。

35、v-byte的思路非常简单：对于数K，用若干字节表示，每个字节的最高位0或者1，1表示是最后一个字节，0表示不是最后一个字节。每个字节剩余的7个位表示数值。

例如表示127，则1 1111111，第一个1表示是最后一个字节，剩下7个1是127。

再比如20000，先表示为2进制，100111000100000，然后从又到左，7个一组，最高位补上0/1，最终结果为0 0000001 0 0011100 1 0100000

v-byte编码在实际的解压、压缩速度上，都比基于比特编码的要好。

36、压缩算法在实际中的应用：我们现在有了很多压缩算法，如何实际用于倒排索引中呢？考虑下面的一条倒排链：
(1, 1) (1, 7) (2, 6) (2, 17) (2, 197) (3, 1)
每一组括号中：第一个数字是文档ID，第二个数字是词的位置。

策略：对于第一部分文档ID，是递增的，我们可以用Delta编码，再V-Byte。

第二部分的position却不是递增的！我们可以把同一个文档ID的，放在一起，如下：

(1, 2, [1, 7]) (2, 3, [6, 17, 197]) (1, 1, [1])

然后可以用VByte编码搞定。

37、现在，压缩优化的思路集中于：硬件加速，让压缩算法更符合CPU的胃口（如分支预测等），以进一步提高效率。

38、跳表，如果查询两个词，且两个倒排链非常长，那么比较它们的AND/OR操作活非常慢。例如"galago AND animal"，animal可能又4kw个，galago只有100w个，时间复杂度最差是O(M+N)，

跳表可以优化这种情况。即在传统的合并排序类似的算法基础上，如果d[a] < d[b]，a链跳过k个，如果d[a+k] < d[b]，继续跳过，知道d[a+mk]>=d[b]为止。

特别说明的是，跳表对于delta等压缩编码依然有效，书上153下面有一个结合delta编码的跳表例子，可以看看。

39、其他数据结构：除了倒排表，还有其他的数据结构，用于检索。如词表。(dictionary/lexicon)

40、词表一般设计的比较小，让它能够完全装入内存。然后词表包含单词(apple)和apple倒排链在倒排文件中的偏移量。

41、对于很多检索模型，都需要词的df，这个信息可以存在倒排链的头上，减少磁盘I/O的开销。

42、搜索引擎除了找到对应的docID外，还要返回其他信息，如snippet摘要、标题title、url等。一般来说，会使用单独的文档服务器存储这些元信息，供前台调用。

43、建索引的流程并不复杂，但是随着数据规模海量的增加，需要一些额外的技巧。

44、基础的建索引算法见157页，很简单，但缺点是：
(1)所有倒排链都存储在内存中，当文档很多时候，会爆掉。
(2)算法是顺序执行的，没法并行化。

45、解决内存的简单方法是：合并(merge)。
(1)按照基础算法建索引，直到内存用尽，然后将它们写入磁盘上。
(2)如上建立索引I1、I2。。。
(3)最后用磁盘归并类似的算法，合并成一个大的索引。

上述合并的例子可以见158页的图。

46、目前的并行化趋势是：利用廉价PC机组成集群，然后使用软件让系统协同工作，优点有两个：
(1)可以承载海量数据
(2)经济实惠
也有缺点：
(1)故障概率大
(2)编程复杂

47、书里主要介绍了Map/Reduce框架建索引：
建索引算法Map阶段：

procedure MapDocumentsToPostings(input)
    while not input.done() do
        document <- input.next()
        docid <- document.docid
        position <- 0
        tokens <- Parse(document)
        for each word w in tokens do
            Emit(w, docid&&position)
            position+=1
        end for
    end while
end procedure

如上产生的key/value对：
key是word
value是docid和position

合并并产生postings的过程在reduce完成：

proceduce ReducePostingsToLists(leys, values)
    word <- key
    WriteWord(word)
    while values.hasnext() do
        encodingPostings(values.next()
    end while
end procedure

这里需要说明的是，对于map/reduce，在shuffle过程中会自动排序，因此每个key(word)对应的values(docid和poisition)都已经是有序的了。

48、当索引需要更新的时候怎么办，有两种基本方法：
(1)索引合并：对Update的部分新建小索引I2，然后和原索引I1合并。当Update大批量且不频繁时，这种策略比较合适。
(2)结果合并：对于删除索引，或者更新非常频繁的场景，在内存中建立一个小的，新的索引，在检索结果返回时合并。不宜使用过多数量的索引，可以让索引规模呈几何级数增长。

49、索引建好以后，如何让检索程序使用它们产生服务于用户的结果呢？有两种传统方法：
(1)Document-at-a-time：
(a)假设Query中有N个term，则一次取N个倒排链
(b)对N个倒排链取交
(c)依次计算doc1/doc2/doc...的分数

它的优点是省内寸

(2)Term-at-a-time
也是先取出N个倒排链接。
但是对链的每个文档都计算一下分，然后取topK

50、在实际工程中，一般会采取一些优化技术：要么减少从索引中读取的数据量，要么能处理更少的文档。

51、跳表(skip pointers)：假设倒排链长为n字节，我们每隔c字节添加一个跳表指针，每个指针k字节长。假设c=100，k=4，则如果读到链尾部，实际只读了2.5%的数据。

c不是越大越好，读取的总长度是：

kn/c+pc/2，由此可见。

51、连接处理(conjunctive processing)：原理很简单，每个返回给用户的文档必须包含所有的query词。实际就是如果在doc在链1中出现但是链2没出现，就剪支。

52、最小分值(Threshold method)：为返回结果设置一个下限的最小score，如果计算过程中小于它，则被丢弃。

53、有的时候，对postings排序也有效果。

54、分布式检索(DIR)：通过分发结点(director machine)将请求发送到多个索引(indexer)上，然后将返回的结果合并。

55、最简单的策略是文档分布，即每个索引上有一小部分，它们都返回top K，然后由发起结点合并成最终的topK。缺点是它默认了每个索引上的统计信息一致，这样和传统的单机检索会有差距。

56、另一种策略是词项分布，apple的postings在机器A，google的postings在机器B。缺点是不好扩展。而且现在研究表明，这样没必要。

57、对检索结果进行Cache很重要，可以Cache倒排链，也可以Cache检索结果。

58、Cache的挑战是如何面对“脏数据”即更新的数据。

本章完毕。