lecture5-indexcompression-信息检索导论-王斌-PPT-课件-第5章

IntroductiontoInformationRetrieval现代信息检索中科院研究生院2011年秋季课程《现代信息检索》更新时间：ModernInformationRetrieval授课人：王斌~wangbin*改编自”AnintroductiontoInformationretrieval”网上公开的课件，地址第5讲索引压缩Indexcompression12011/9/26提纲2❶上一讲回顾❷压缩❸词项统计量❹词典压缩❺倒排记录表压缩提纲3❶上一讲回顾❸压缩❸词项统计量❸词典压缩❸倒排记录表压缩现代信息检索4基于块的排序索引构建算法BSBI4现代信息检索5内存式单遍扫描索引构建算法SPIMI关键思想1:对每个块都产生一个独立的词典–不需要在块之间进行term-termID的映射关键思想2:对倒排记录表不排序，按照他们出现的先后顺序排列基础上述思想可以对每个块生成一个完整的倒排索引这些独立的索引最后合并一个大索引5现代信息检索现代信息检索6SPIMI-Invert算法6现代信息检索7基于MapReduce的索引构建7现代信息检索8动态索引构建：最简单的方法在磁盘上维护一个大的主索引(Mainindex)新文档放入内存中较小的辅助索引（Auxiliaryindex）中同时搜索两个索引，然后合并结果定期将辅助索引合并到主索引中8现代信息检索9本讲内容信息检索中进行压缩的动机倒排索引中词典部分如何压缩？倒排索引中倒排记录表部分如何压缩？词项统计量:词项在整个文档集中如何分布？9提纲10❶上一讲回顾❷压缩❸词项统计量❹词典压缩❺倒排记录表压缩现代信息检索现代信息检索什么是压缩？将长编码串用短编码串来代替11111111111111111118个111现代信息检索12为什么要压缩?(一般意义上而言)减少磁盘空间(节省开销)增加内存存储内容(加快速度)加快从磁盘到内存的数据传输速度(同样加快速度)[读压缩数据到内存+在内存中解压]比直接读入未压缩数据要快很多前提:解压速度很快本讲我们介绍的解压算法的速度都很快12现代信息检索13为什么在IR中需要压缩?首先，需要考虑词典的存储空间词典压缩的主要动机:使之能够尽量放入内存中其次，对于倒排记录表而言动机:减少磁盘存储空间，减少从磁盘读入内存的时间注意:大型搜索引擎将相当比例的倒排记录表都放入内存接下来，将介绍词典压缩和倒排记录表压缩的多种机制13现代信息检索14有损(Lossy)vs.无损(Lossless)压缩有损压缩:丢弃一些信息前面讲到的很多常用的预处理步骤可以看成是有损压缩:统一小写,去除停用词,Porter词干还原,去掉数字无损压缩:所有信息都保留索引压缩中通常都使用无损压缩14提纲15❶上一讲回顾❷压缩❸词项统计量❹词典压缩❺倒排记录表压缩现代信息检索现代信息检索词典压缩和倒排记录表压缩词典压缩中词典的大小即词汇表的大小是关键能否预测词典的大小？倒排记录表压缩中词项的分布情况是关键能否对词项的分布进行估计？引入词项统计量对上述进行估计，引出两个经验法则16现代信息检索17对文档集建模：ReutersRCV117NLMT文档数目每篇文档的词条数目词项数目(=词类数目)每个词条的字节数(含空格和标点)每个词条的字节数(不含空格和标点)每个词项的字节数无位置信息索引中的倒排记录数目800,000200400,00064.57.5100,000,000现代信息检索18预处理的效果18现代信息检索19第一个问题：词汇表有多大(即词项数目)?即有多少不同的单词数目?首先，能否假设这个数目存在一个上界？不能：对于长度为20的单词，有大约7020≈1037种可能的单词实际上，词汇表大小会随着文档集的大小增长而增长！Heaps定律:M=kTbM是词汇表大小,T是文档集的大小(所有词条的个数，即所有文档大小之和)参数k和b的一个经典取值是:30≤k≤100及b≈0.5.Heaps定律在对数空间下是线性的这也是在对数空间下两者之间最简单的关系经验规律19现代信息检索现代信息检索ReutersRCV1上的Heaps定律词汇表大小M是文档集规模T的一个函数图中通过最小二乘法拟合出的直线方程为：log10M=0.49∗log10T+1.64于是有：M=101.64T0.49k=101.64≈44b=0.4920现代信息检索21拟合vs.真实例子:对于前1,000,020个词条，根据Heaps定律预计将有38,323个词项:44×1,000,0200.49≈38,323实际的词项数目为38,365，和预测值非常接近经验上的观察结果表明，一般情况下拟合度还是非常高的21现代信息检索22课堂练习❶在容许拼写错误或者对拼写错误自动纠错的情况下，Heaps定律的效果如何？❷计算词汇表大小M观察一个网页集合，你会发现在前10000个词条中有3000个不同的词项，在前1000000个词条中有30000个不同的词项假定某搜索引擎索引了总共20,000,000,000(2×1010)个网页,平均每个网页包含200个词条那么按照Heaps定律，被索引的文档集的词汇表大小是多少？22现代信息检索23第二个问题：词项的分布如何？Zipf定律Heaps定律告诉我们随着文档集规模的增长词项的增长情况但是我们还需要知道在文档集中有多少高频词项vs.低频词项。在自然语言中，有一些极高频词项，有大量极低频的罕见词项Zipf定律:第i常见的词项的频率cfi和1/i成正比cfi是文档频率(collectionfrequency):词项ti在所有文档中出现的次数(不是出现该词项的文档数目df)23现代信息检索24Zipf定律Zipf定律:第i常见的词项的频率cfi和1/i成正比cfi是文档频率(collectionfrequency):词项ti在所有文档中出现的次数(不是出现该词项的文档数目df).于是，如果最常见的词项(the)出现cf1次，那么第二常见的词项(of)出现次数为...第三常见的词项(and)出现次数为另一种表示方式:cfi=cik或logcfi=logc+klogi(k=−1)幂定律(powerlaw)的一个实例24现代信息检索25ReutersRCV1上Zipf定律的体现拟合度不是非常高，但是最重要的是如下关键性发现：高频词项很少，低频罕见词项很多25提纲26❶上一讲回顾❷压缩❸词项统计量❹词典压缩❺倒排记录表压缩现代信息检索27词典压缩相对于倒排记录表，词项较小但是我们想将词典放入内存另外，满足一些特定领域特定应用的需要，如手机、机载计算机上的应用或要求快速启动等需求因此，压缩词典相当重要27现代信息检索28回顾:定长数组方式下的词典存储空间需求：20字节4字节4字节对ReutersRCV1语料:(20+4+4)*400,000=11.2MB28现代信息检索29定长方式的不足大量存储空间被浪费即使是长度为1的词项，我们也分配20个字节不能处理长度大于20字节的词项，如HYDROCHLOROFLUOROCARBONS和SUPERCALIFRAGILISTICEXPIALIDOCIOUS而英语中每个词项的平均长度为8个字符能否对每个词项平均只使用8个字节来存储?29现代信息检索30将整部词典看成单一字符串(Dictionaryasastring)30现代信息检索31单一字符串方式下的空间消耗每个词项的词项频率需要4个字节每个词项指向倒排记录表的指针需要4个字节每个词项平均需要8个字节指向字符串的指针需要3个字节(8*400000个位置需要log2（8*400000）24位来表示)空间消耗:400,000×(4+4+3+8)=7.6MB(而定长数组方式需要11.2MB)31现代信息检索32单一字符串方式下按块存储32现代信息检索现代信息检索按块存储下的空间消耗如果不按块存储，则每4个词项指针将占据空间4×3=12B现在按块存储，假设块大小k=4，此时每4个词项只需要保留1个词项指针，但是同时需要增加4个字节来表示每个词项的长度，此时每4个词项需要3+4=7B因此，每4个词项将节省12-7=5B于是，整个词典空间将节省40,000/4*5B=0.5MB最终的词典空间将从7.6MB压缩至7.1MB33现代信息检索34不采用块存储方式下的词项查找34现代信息检索35采用块存储方式下的词项查找:稍慢35现代信息检索现代信息检索前端编码(Frontcoding)每个块当中(k=4)，会有公共前缀...8automata8automate9automatic10automation⇓...可以采用前端编码方式继续压缩8automat∗a1⋄e2⋄ic3⋄ion36现代信息检索37ReutersRCV1词典压缩情况总表37现代信息检索38课堂练习哪些前缀应该用于前端编码？需要在哪些方面有所权衡？输入:词项列表，即词汇表输出:用于前端编码的前缀列表38提纲39❶上一讲回顾❷压缩❸词项统计量❹词典压缩❺倒排记录表压缩现代信息检索40倒排记录表压缩倒排记录表空间远大于词典，至少10倍以上压缩关键：对每条倒排记录进行压缩目前每条倒排记录表中存放的是docID.对于ReutersRCV1(800,000篇文档),当每个docID可以采用4字节（即32位）整数来表示当然，我们也可以采用log2800,000≈19.620位来表示每个docID.我们的压缩目标是：压缩后每个docID用到的位数远小于20比特40现代信息检索41关键思想:存储docID间隔而不是docID本身每个倒排记录表中的docID是从低到高排序例子:COMPUTER:283154,283159,283202,...存储间隔能够降低开销：283159-283154=5,283202-283154=43于是可以顺序存储间隔(第一个不是间隔):COMPUTER:283154,5,43,...高频词项的间隔较小因此，可以对这些间隔采用小于20比特的存储方式41现代信息检索42对间隔编码42现代信息检索43变长编码目标:对于ARACHNOCENTRIC及其他罕见词项,对每个间隔仍然使用20比特对于THE及其他高频词项，每个间隔仅仅使用很少的比特位来编码为了实现上述目标，需要设计一个变长编码(variablelengthencoding)可变长编码对于小间隔采用短编码而对于长间隔采用长编码43现代信息检索44可变字节(VB)码被很多商用/研究系统所采用变长编码及对齐敏感性(指匹配时按字节对齐还是按照位对齐)的简单且不错的混合产物设定一个专用位(高位)c作为延续位(continuationbit)如果间隔表示少于7比特，那么c置1，将间隔编入一个字节的后7位中否则：将低7位放入当前字节中，并将c置0，剩下的位数采用同样的方法进行处理，最后一个字节的c置1（表示结束）44现代信息检索45VB编码的例子45现代信息检索46VB编码算法46现代信息检索47VB编码的解码算法47现代信息检索48其它编码除字节外，还可以采用不同的对齐单位：比如32位(word)、16位及4位(nibble)等等如果有很多很小的间隔，那么采用可变字节码会浪费很多空间，而此时采用4位为单位将会节省空间最近一些工作采用了32位的方式–参考讲义末尾的参考材料48现代信息检索49ϒ编码另外一种变长编码是基于位的编码ϒ编码是其中最出名的一种首先，在介绍ϒ编码之前先介绍一元码(unarycode)一元码：将n表示成n个1和最后一个0比如：3的一元码是111040的一元码是11111111111111111111111111111111111111110