Search Engines: Information Retrieval in Practice – 第5章

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的挑战是如何面对“脏数据”即更新的数据。

本章完毕。

 

 

Leave a Reply

Your email address will not be published. Required fields are marked *