第三讲：索引及查询处理(5章)

1、1第三讲：第三讲： 索引与查询处理索引与查询处理(5章)主讲人：朱征宇朱征宇联系电话mail：zhu_课程名称：智能信息检索课程名称：智能信息检索2一、引言一、引言v检索速度检索速度每天全世界输入超过5亿个查询，而互联网有几十亿网页高效的查询处理，对于网络搜索特别重要！v高效检索的基础高效检索的基础大多数检索计算都与数据结构有关，优秀的算法都有好的数据结构例：处理项目列表应当采用链表，根据属性查找项目可采用哈希表，一些复杂搜索(如人名)需采用B+树，。v搜索引擎的基石搜索引擎的基石文本搜索与传统的计算任务有很大不同，需采用特殊数据结构倒排索引是一种特殊数据结构，能很好

2、地服务于相关排序函数倒排索引是所有现代网络搜索引擎的核心v检索模型（第检索模型（第7章）章）查询处理算法依赖于：检索模型、以及指定索引的内容(相关)排序模型又依赖于索引的选择搜索引擎各独立部分之间有很强的依赖关系！互联网检互联网检索，什么索，什么最重要？最重要？第第5 5章章“必须再快点。必须再快点。” - David Levinson检索处理还要依靠什么？高效检索基高效检索基础是什么？础是什么？互联网依赖互联网依赖什么实现高什么实现高效检索？效检索？3二、相关排序模型二、相关排序模型2.1 抽象的相关排序模型抽象的相关排序模型v抽象的抽象的相关排序模型示例相关排序模型示例（图5-1）文档，通

3、过转换(4章)抽取出文档特征(主题特征和质量特征)查询输入和文档特征经查询处理后，得到文档的分数(排序依据)重要现象：大多数排序函数都只用到文档中少量特征！（?）使 得：倒排索引成为搜索中一个引人注目的数据结构!v人工排序时：人工排序时：可以分成好,中,差几类可以仔细地看看每个文档的内容但智能化花精力v搜索引擎：搜索引擎：确定好的特征基于特征的排序搜索引擎搜索引擎如何实现如何实现排序输出排序输出?它与人工排序的主要差异？42.2 一种一种具体的具体的相关排序模型相关排序模型v相关排序函数R的形式: (7章将详细讨论)(fi,gi都是数字特征函数，为各种特征记分)v实例(图5-2)排序模型排序模

4、型的设计难的设计难在何处？在何处？难在难在fi 和和gi 的设计的设计!即即:特征及权值的确定特征及权值的确定!相关词慈鲷(diao鱼类) 鱼钩大量查询请求的查询特征gi(Q)多数为0有的查询,更新次数会更重要，如todays weather in lonton 5三、倒排索引三、倒排索引v倒排索引倒排索引通常：文档-包含单词，反看则: 单词-附着文档(与单词关联的文档)倒排索引，通过索引项倒排索引，通过索引项(单词单词)来组织文档！来组织文档！索引项经常按照字母排列，但不是必须! 可以用哈希表来查找每个索引项，都有一个倒排列表(inverted list)(文档/单词位置)文档集中的每个文档

5、有一个唯一的编号(有效地存储文档指针)列表中的项(称pointing),可是文档编号,甚至更多信息(用于特征函数计算)传统上，倒排列表中文档编号从小到大依序排列v倒排索引的优点倒排索引的优点模型简单易行，可有效支持相关排序搜索的设计对大多数查询来说，只有一小部分索引需要处理 #倒排索引倒排索引的结构？的结构？倒排索引的优点？倒排索引为现代搜索引擎普遍采用，是最有效、最灵活的索引结构倒排索引为现代搜索引擎普遍采用，是最有效、最灵活的索引结构! !大量单词文档大量文档单词63.1 倒排表倒排表&文档检索文档检索v简单的倒排表简单的倒排表最简单形式的倒排表，只包含每个单词及相应文档的编号(例

6、子)v倒排表的交集倒排表的交集例子：如何寻找与查询“coloration freshwater”相关的句子？Coloration、freshwater两个索引项的倒排表直接求交集两个索引项的倒排表直接求交集倒排表可高效支持查询！时间开销：O(max(m,n) （n,m两倒排表各自包含的项数）#倒排索引倒排索引什么样？什么样？倒排索引倒排索引如何支持如何支持查询？查询？色彩/着色， 淡水 7简单倒排表的例子简单倒排表的例子在3句中出现注意：这里没有记录单词是否多次出现注意：这里没有记录单词是否多次出现返回返回3.2返回返回3.346个索引项个索引项文档的编号文档的编号这里看着文档这里看着文档因此

7、有46个倒排表83.2 单词计数单词计数&文档排序文档排序v存在问题存在问题简单倒排表中，文档是二元的要么出现，要么不出现对于找最相关的文档太过粗糙！例：查询“tropical fish”找到3个句子S1,S2,S3,如何排序?v带频次的倒排索引带频次的倒排索引倒排表的posting可含单词出现次数次数例子，表5-4v频次的用途频次的用途查询“tropical fish”找到的3句子，按照(前面的)相关排序函数，可以实现排序因值是4,5,3，故排序S2,S1,S3#如何改进如何改进倒排索引倒排索引?改进效果如何?93.3 单词位置单词位置&文档检索文档检索v问题问题对查询“tr

8、opical fish”若一个文档有多章节，依次是tropical fruits，saltwater fish会查出这个文档，但并不相关是否能准确判断包含该短语？v包含位置的倒排索引包含位置的倒排索引在到排表的posting中记录单词位置例子，图5-5v改进的效果改进的效果对查询,fish和tropical倒排表求交集不仅交集为S1,S2,S3；而且知道： tropical和fish均在相继位置出现!分别是:S1(1-2),S2(6-7),S2(17-18),S3(1-2)如何来改进倒如何来改进倒排索引排索引?位置信息位置信息的用途的用途?fish在句子S2中依次出现的位置返回103.4 域与

9、范围域与范围v域域文档不仅由单词构成，而且单词还有域的区分单词还有域的区分例如，句子、段落、章节、小标题、标题，甚至(邮件)时间等单词出现在什么域对查询有重要影响v例：在邮件中查询brown教授的来信， 词“brown”出现在内容还是From字段中，对于返回结果的相关性是非常不同的v又例：查询“tropical fish”， 返回文档中，词tropical和fish是否出现在标题中，文档的相关性是非常不同的v考虑域的倒排索引考虑域的倒排索引法一：为每种域(标题，小标题)，都单独建立一个倒排索引法二：倒排索引中，每一posting后用0/1表示词是/否出现在标题v范围表范围表(extent li

10、st)除了单词(索引项)的倒排表外，还有标题域的范围表。还有标题域的范围表。即每个文档的标题出现(单词起止)位置范围用途：判定单词是否出现在标题域中(同样地，其它域可类似处理) #文档的域指什么?倒排索引倒排索引需要考虑需要考虑域吗域吗?应该如何应该如何改进倒排改进倒排索引索引?什么是范围表?文档3无标题！fish出现在文档1和文档4的标题中标题域的范围(起, 止)单词的倒排表文档2有标题, 但不含fish113.5 分数分数v分数分数(特征函数值)表示单词表示单词(特征项特征项)在文档中的重要程度在文档中的重要程度(代表度)或相关度！例：tropical fish出现在标题为“Mauriti

11、us”(毛里求斯)文档中2-3次，出现在标题为“tropical fish”文档中1次，也许后者仍应更相关v特征值的用途特征值的用途一般地，在查询排序时，需利用倒排表计算特征词的分数为提高查询效率，其实也可在倒排表中预先存储这些分数值v包含特征值的倒排索引包含特征值的倒排索引在倒排索引的在倒排索引的posting中，直接包含特征值中，直接包含特征值(分数分数)例如，fish的倒排表可能是：(1:3.6)(3:2.2)表示：fish在文档1中的特征值是3.6，而在文档3中为2.2v效果分析效果分析可提升灵活性：使查询时利用计算繁琐的分数成为可能降低了灵活性：索引建立后不能改变评分了, 无单词临近

12、(短语)信息这里的分数指什么?为何在讨为何在讨论索引时论索引时提到分数提到分数?如何改进如何改进倒排索引倒排索引?改进效果?123.6 排列排列v排列问题排列问题前面讨论，均假设：倒排表中的posting应按照文档编号排列虽然这是通常的做法，但并非是唯一的方法不论哪种排列方式，目的都应是为了更好地服务于高效查询服务于高效查询/排序v不同排列方式不同排列方式可以按照特征值(分数)的高低来排列posting(仅存1种分数时)使得高分数的文档最新出现可以按照是否出现在标题对posting进行组织可以结合分数和是否出现在标题。v应注意的问题应注意的问题为提高查询效率，倒排索引常被压缩存储(下面将介绍)

13、因此，考虑排列方式时，注意分析压缩/解压/查询效率等问题还应考虑各种查询计算的需要（综合性，权衡）#排列指什么,用途?你认为应你认为应如何排列如何排列?考虑排列时应注意什么?13四、编码与压缩四、编码与压缩v存储器的类型存储器的类型外存：磁带，磁盘，CD，DVD，闪存(U盘) 等-速缓，长期存储，便宜缓存：随机访问存储器RAM，寄存器等 -速快，临时存储，昂贵v倒排索引与压缩倒排索引与压缩大规模数据集（如互联网）的倒排表依然非常庞大当包含词位置、文本范围等信息时，倒排索引容量与文档集相当。例如，TREC文本集的索引，其大小是文本集的25%-50%将频繁使用的倒排索引放入内存，可显著提高查询处理

14、效率若索引数据被压缩4倍，则内存中可多放4倍的索引数据从外存读取被压缩的倒排索引，可以减少读取时间v压缩算法选择压缩算法选择虽然压缩可节省空间，但解压需要时间应选择既减少存储空间，又利于解压和查询处理的技术应选择既减少存储空间，又利于解压和查询处理的技术如按数据块压缩下面将介绍多种无损压缩算法（特别适用于文本编号、词频、文档位置等信息) 倒排索引倒排索引需要压缩需要压缩?是否压缩是否压缩比高的算比高的算法更好法更好?144.1 墒与歧义墒与歧义v压缩的基本思路？压缩的基本思路？使用较短的代码表示常见的数据元素，较长的代码表示不常见的数据元素倒排表本质上是数字的列表，不压缩时，每个数字占用相同的

15、空间故，可以将常见的数字用较短的代码编码，不常见的用较长的代码编码v数字如何编码？数字如何编码？简单的编码方法：若数字0,1,2,3分别(用两个二进制bit)编码为：00,01,10,11，则数字0,1,0,2,0,3,0可用编码表示为：00 01 00 10 00 11 00 (空隙仅为看清)， 长度14bit可压缩为：0 01 0 10 0 11 0(这里，用较短的1bit0表示数字0，其它不变),长度10bit这样编码有问题吗？这样编码有问题吗？解码时存在歧义性：可理解为0 01 01 0 0 11 0，解码为0,1,1,0,0,3,0问题如何解决？问题如何解决？无歧义的编码方法(仅有唯

16、一途径加空格)：数字0,1,2,3编码为0,101,110,111则数字0,1,0,2,0,3,0编码为：0 101 0 110 0 111 0(空隙仅为看得清)长度13bit 解码规则：编码以0开始，则占1位，以1开始，则占3位！v熵在编码中的用途熵在编码中的用途上例中的输入似乎可预见，0比其它数字更常见(可用来降低编码数据空间)一般地，用 熵 来衡量输入的可预见性，以产生一个对此有用的编码方案返回154.2 Delta编码编码v假设与现象假设与现象假设:本章所有编码技术都假设小数字比大数字更常见！现象：文档中,许多词出现1次,有些词出现2-3次,只有很少的词出现超过10次;因此，小代码对小

17、数字编码，大代码编码大数字是有道理的！v文档编号的特点？文档编号的特点？文档编号的特点：倒排表中, 文档编号分布的熵不多！既包含一些小的文档编号，也包含一些非常大的文档编号有些文档包含很多单词，故会在倒排表中出现多次倒排表中文档编号的特点：一般按照文档的编号进行排列的（后面的编号比前面的大）故文档编号的编码，可以充分利用这一特点！vDelta编码编码(d-gaps)的思路？的思路？对文档编号的序列：1,5,9,18,23,24,30,44,45,48(第1个文档后)可利用文档编号之间的差值利用文档编号之间的差值对列表进行编码：1,4,5,9,5,1,6,14,1,3用途分析：该编码没有定义存储

18、数据的bit模式，自身不能节省空间。然而，该编码将大数字变为小数字将大数字变为小数字特别成功，(因将讨论小数字列表的压缩)因此而特别有用！例子，who-倒排表(编码为1,1,2,1,5,4,1,1,3,)和entropy-倒排表(109,3766,4533,1867,992,)分析: who常见，编码中有许多小d-gaps，entropy少见，编码中大数多，但列表不长; 压缩效果好!16v位对齐码位对齐码(4.4还将介绍以字节单位作为结尾的字节对齐码)代码区域之间的中断(空格空格)可以在任何可以在任何bit位后面位后面例子：如4.1节介绍的编码方法及下面的三种编码v一进制码一进制码编码方式：用

19、k个1编码数字k，总以0结束，编码无歧义。缺点：1进制码对压缩小数字有效，但对大数字效果差(如数字对1023，用1进制需1024bit)，而用二进制仅需10bit(但可能有歧义)vElias-码码思路：结合了一进制和二进制的长处，规避其短处。编码方式：对数k计算两个量k kd d= =Lloglog2 2k k和 ，并分别用1、2进制编码 例：表5-2vElias-码码Elias-码的缺点：k本可表示成log2k个二进制数， 但它用两倍的bit位才保证了无歧义Elias-编码方式：对kd的编码进行改进，得当如表5-3所示编码方式从而，编码长度缩短为约（2log2(log2k)+ log2k ）

20、bit位 #4.3 位对齐码位对齐码数字数字编码编码001102110311104111105111110k0178=23128=27512=29表表5-2：Elias-码的例子码的例子(相对相对1进制而言进制而言)1=200-分隔符分隔符-结束标志结束标志分隔符分隔符0二进制数的比特位数二进制数的比特位数kdkd18Kd表表5-3：Elias-码码Kdd和和Kdr可计算出可计算出KdKdd、Kdr 和和Kr194.4 字节对齐码字节对齐码v字节对齐码的重要性字节对齐码的重要性问题：一些小技巧有助于快速地解码位对齐码，但在处理字节的处理器上，处理bit位码仍然比较麻烦解决途径：实际应用中，字节

21、对齐的编码会更快vv-byte码码(变长字节)v-byte是一种表示文本很常用的方法v-byte也使用短码表示小数字，用长码表示大数字但每个码都是一系列字节，而非bit位v-byte编码方法编码方法v每个数字的编码都采用1个或多个字节个或多个字节表示v具体编码方式如表5-4和表5-5位对齐码位对齐码有问题有问题?如何设计如何设计字节对齐字节对齐码码?20但但v-byte编码方法编码方法中的多个字节仅中的多个字节仅其余字节的高位为其余字节的高位为0(每个字节每个字节8位，第位，第1位为高位，低位为高位，低7位指后位指后7位位)1 1111111128+127=255FF15*16+15=255注

22、释：16进制:0,1,2,9,a,b,c,d,e,f表示表示214.5 倒排索引的压缩倒排索引的压缩v倒排索引与压缩倒排索引与压缩为了快速支持查询处理和降低存储空间，庞大的倒排表需要压缩本节介绍Galago的positionListWriter类中使用的倒排表压缩技术从图5-5已看到，单词的位置信息如何存储在倒排索引中。下面，以其中的tropical倒排表添加了(2,197)为例来分析其方法tropical(1,1)(1,7)(2,6)(2,17)(2,197)(3,1) （括号内的第1、2个数字分别表示文档编号和单词位置）vGalago压缩方法压缩方法首先，倒排表可等效变化为等效变化为(文档

23、编号，单词出现频次，单词出现位置)：新格式 (1,2,1,7)(2,3,6,17,197)(3,1,1)其次，因频次指出了括号内位置信息出现多少次，可无歧义无歧义的写成: 简化为 1,2,1,7 2,3,6,17,197 3,1,1 (为清晰，添加了逗号分隔)(虽然这些数字都是小数字)采用delta编码编码可以使其变得更小编码为 1,2,1,6 1,3,6,11,180 1,1,1 (文档编号和单词位置都是升序)由于大多数数字都比较小，可采用v-byte压缩压缩以节省空间 (共用13字节表示)81 82 81 86 81 83 86 8B 01 B4 81 81 81 (仅数字180用01 B

24、4两字节表示)如何压缩如何压缩倒排索引倒排索引?注释：180二进制：10110100v-byte需两字节表示：0 0000001和1 0110100十六进制：01 B4224.6 跳转指针跳转指针v跳转指针的用途跳转指针的用途有许多查询，仅需要倒排索引中一小部分仅需要倒排索引中一小部分与查询有关的数据使用跳转指针可以达到此目的例子分析v效率分析效率分析采用跳转指针后，效率有明显改善。没有采用跳转指针时，需要3亿次+1百万次： 3亿亿次采用跳转指针时(分析如表5-6) ： 2千多万千多万次 为何引入为何引入跳转指针跳转指针?跳转指针跳转指针对效率改对效率改善如何善如何?23跳转指针示例分析跳转指

25、针示例分析dg,da两指针逐一扫描两倒排文件！24跳转指针效率分析跳转指针效率分析Galago一百百万个文档Animal三亿个文档每次跳每次跳k个个对每个dg需要回朔对比k次每次跳转到dg附近最后都要进行长不超过k的搜索，而平均搜索时间为k/2百万百万*k/225五、辅助结构五、辅助结构v辅助结构辅助结构虽然倒排索引是搜索引擎的主要数据结构但对于一个功能齐全的搜索系统，通常还需要其他数据结构比如：词表和统计，文档、快照和扩展系统v词表和统计词表和统计问题：倒排索引是一些倒排表的集合，如何快速找到指定倒排表？答案：采用辅助数据结构(词表词表)来查找某一倒排表解决问题的思路分析统计：有的特征函数需

26、要存储特定的词汇统计信息(词频/文档频率)若统计与特定项有关，则可存储于倒排表的开始部分统计不多(如文档的总数)时，可忽略高效存储，并用文件单独存储v*文档、快照和扩展系统文档、快照和扩展系统 #辅助结构指什么?为何要引为何要引入词表入词表?还需要其它还需要其它辅助结构辅助结构?为何要考虑统计?26解决问题的思路分析解决问题的思路分析v最简单的解决思路最简单的解决思路将每个将每个(单词的单词的)倒排表倒排表分别存储在不同文件中，文件可以单词命名分别存储在不同文件中，文件可以单词命名缺点：因单词成百上千万，倒排表文件成百上千万！ 许多文件系统对于较大文件目录，文件查找会非常慢！v更好的解决思路更

27、好的解决思路将所有倒排表存储在一个单一的文件中(称为倒排文件，inverted file)倒排文件还包括一个词汇的词汇的目录结构目录结构，是一个 索引项索引项倒排表的偏移量倒排表的偏移量 查找表查找表-词表词表v词表的处理词表的处理通常词表很小，可全部放入内存。搜索引擎启动时，词表被载入哈希表中非常大的词表，则采用B+树之类的数据结构，来最小化磁盘访问vGalago的解决思路的解决思路1）用一个词表小文件，来存储在倒排文件中各词项的倒排表的偏移量(起点)2）对于倒排文件中每32KB的数据，该文件仅包含词表的词表的一个条目一个条目(某词汇倒排表起点)(1个32TB的倒排文件，需少于1GB的词表空

28、间的词表空间，通常可存储在内存中可存储在内存中)3）为找到一个倒排表，采用二元查找在词表(倒排文件各词汇按字母排序存储)中找到最近的条目，并读取偏移量(该方法，对应每个倒排表，仅用一次磁盘寻道就能找到) #这样做有这样做有何不足何不足?有什么解有什么解决办法决办法?为什么要这为什么要这样做样做?27*文档、快照和扩展系统文档、快照和扩展系统v前面介绍的搜索引擎技术，都是返回文档编号的列表及分数v真正的搜索引擎，需要显示关于每个文档的文本信息v例如，文档的标题，URL，文本摘要v因此需要存储文档、快照等辅助文件，以及提供扩展支持(扩展系统)v一些为快速访问而设计的文档存储方式(见第3章)，可解决

29、这些需求v当然，还需要一个将搜索引擎结果从数字转换为人们可读取的独立系统 #28标记标记(token)指单词指单词v索引在被查询处理引用前，必须从文本集生成v构建小型索引并不困难，但大规模文档构建技巧构建技巧(灵活快捷灵活快捷)非常有用非常有用v图5-8给出了构建简单索引的算法算法 (伪码形式)v特点分析六、索引构建六、索引构建6.1 简单索引的构建方法简单索引的构建方法构建索引需要技巧?为新文档编号为新单词生成新的倒排表将文档插入该单词的倒排表依次处理所有文档依次处理所有文档依次处理文档的每个单词依次处理文档的每个单词去除重复单词如何创建出如何创建出倒排索引倒排索引?确定倒排表存储位置返回2

30、9算法算法(图图5-8中倒排索引中倒排索引)特点分析特点分析v应用范围应用范围图5-8索引器，可应用于索引几千个文档的小系统v两点局限两点局限要求所有倒排表都存储在内存中(对于大文档集不太可行)为顺序算法，不便于并行处理(主要障碍是各单词的倒排索引表定位采用哈希表，且内循环频繁访问它)v初步解决办法初步解决办法对哈希表加锁使分析可以并行，但这种提升对多内核设备并不足够v对大数据处理的要求对大数据处理的要求(始终是一个值得研究的技术始终是一个值得研究的技术)需要较少地依赖内存(比如利用前面提到的采用可装入内存的词表技术，而倒排表放在外存上)同时需要提高并行性(比如下面将介绍的方法：多机并行处理不

31、同文档子集，然后合并各机得到的子索引表) 有更好的解有更好的解决办法决办法?306.2 融合技术融合技术v索引的融合上节介绍算法受到内存限制，不便并行处理，适合小规模系统对大规模数据集，可采用先建立部分索引，再融合为完整索引v融合方法的思路单机方式：构建倒排索引直到内存耗尽，得到部分索引I1反复此过程，得到多个部分索引In；在按照下图5-9合并为完整索引I多台方式：并行同时构建部分索引，一台设备融合部分索引 #设倒排表已按照字母排序(内存占用更少)有相同文档编号时，索引B的文档重新编号线性扫描各1次，即可完成融合，非常节省内存！索引融合索引融合的执行过的执行过程与效率程与效率?316.3 并行

32、与分布式并行与分布式v采用并行分布式的理由采用并行分布式的理由传统的搜索引擎：一直是采用一台快速的设备来生成索引如今的 大系统：同时使用众多廉价的服务器和分布式软件来处理理由一理由一：网页规模呈爆炸式增长，采用单台设备处理几乎不可能理由二理由二：个人电脑变得强大和廉价，大型系统改用多台廉价服务器缺点缺点：廉价服务器更容易坏，服务器增多时出错增加 系统性能依赖于开发人员掌握多线程、并行编程和容错技术的程度v数据放置顺序的重要性数据放置顺序的重要性例1：采用一台设备，根据大量信用卡交易记录统计信用卡数目用哈希表因文件大不能同时在内存处理：若记录已排序，顺序读记录即可！否则处理开销更高。若记录已排序

33、，顺序读记录即可！否则处理开销更高。例2：用(多设备)分布式计算，根据信用卡交易记录统计信用卡数目各设备统计后合并，需处理卡号重复：若记录排序后分布，合并简单化！否则处理开销更高。若记录排序后分布，合并简单化！否则处理开销更高。vMapReduce的的基本思想基本思想(图图5-10)它是一个分布式编程框架，致力于数据放置和分布式数据放置方数据放置方式影响检索式影响检索效率效率?多机分布并多机分布并行的弱点行的弱点?32计算信用卡计算信用卡(消费消费)累加值：累加值：信用卡消费记录列表各信用卡消费累加值图图5-10：MapReduce的基本思想的基本思想(并行处理并行处理)作用是调整项次序作用是

34、调整项次序(归类归类)作用是对已归类项计算累加值作用是对已归类项计算累加值(可将每个矩形看成一台设备可将每个矩形看成一台设备)(对同一信用卡的记录求和对同一信用卡的记录求和)(将同一信用卡的记录放在一起将同一信用卡的记录放在一起/一台设备上一台设备上)33(归类归类)(计算累加值计算累加值)Map和和Rrduce函数函数键键-值对值对卡号卡号-消费额消费额哈希函数哈希函数累加消费值累加消费值346.4 更新更新v索引更新问题索引更新问题前面的讨论假设：先给定文档集-然后建立索引-然后用户查询实际上，互联网上文档在不断更新，搜索引擎应当能够动态响应应当能够动态响应因此，倒排索引也需要随时间变化-

35、更新！(尤其是邮件，新闻)v索引更新思路索引更新思路思路一：索引合并!思路二：结果合并！v索引合并方法索引合并方法（静态方式静态方式）(平时)先构建一个较小的新索引I1 (为新文档) ，(定期)然后与老索引I合并合并时，老索引I中已被删除文档的posting应被忽略！v结果合并方法结果合并方法（动态方式动态方式）新文档较少时，可采用结果合并(以避免合并消耗大量不必要时间)：1）将新文档加入新索引中，查询时分别在新、旧索引上处理（合并结果）2）为已删除文档建立删除文档列表(用于查询处理时，确定没有已删除文档进入用户显示结果中)3）对修改文档，采用被删除文档列表处理旧版，在最新文档列表中加入新版本

36、（新旧文档同时被输出）倒排索引倒排索引如何更新如何更新?索引合并索引合并如何实现如何实现更新更新?结果合并结果合并如何实现如何实现更新更新?35七、查询处理七、查询处理7.1 基本查询技术基本查询技术v查询处理技术查询处理技术即使最简单的算法，有索引比无索引都会好很多！更巧妙的算法，可以提高查询处理效率甚至成百倍成百倍！v最简单的查询处理算法最简单的查询处理算法document-at-a-time算法term-at-a-time算法查询处理讲究技巧?最简单的查询算法什么样?document -at-time如如何工作何工作?term-at-time如何如何工作工作?（处理思路见（处理思路见图图

37、5-15例子）例子）（处理思路见（处理思路见图图5-17例子）例子）在设计查询算法时，请联想到倒排索引的特点！36document-at-a-time检索例子检索例子算法形式描述算法形式描述(图5-16)一次处理一文档一次处理一文档(document-at-a-time)第第1步步第第2步步第第3步步第第4步步这三个词的到排表这三个词的到排表词频总和：词频总和：作为相关性排序依据作为相关性排序依据37图图5-16 document-at-a-time算法算法排序的返回所有相关文档-初始化查询相关的倒排表-初始化初始化找出相关的倒排表查询项相关的分数(5.2节方法相关排序模型)返回分数高的前k个

38、文档计算各各文档的分数 计算文档d的总分数 查询,索引,特征函数,指定返回文档的个数根据分数为文档(D=d)排序，并插入R一次处理一个文档一次处理一个文档(document-at-a-time)应添加：sD0 38图图5-17 term-at-a-time检索例子检索例子 documentQ= salt water tropical算法形式描述算法形式描述(图5-18)第一步：第一步：第二步：第二步：第三步：第三步：一次处理一查询项一次处理一查询项(term-at-a-time)!39term-at-a-time算法算法对各查询项计算分数 采用哈希表存放各个相关文档的(当前累计)分数-初始化(

39、同前说明)根据累计器分数，形成文档排序结果返回分数高的前k个文档计算查询项i的(各文档)分数计算其中每个文档d的分数(5.2节方法相关排序模型)并被累计到原分数中。（这里用到Hash函数）一次处理一个查询项一次处理一个查询项(term-at-a-time)!应添加：若d首次出现，Ad0 根据分数为文档(D=d)排序，并插入R指 sD407.2 查询优化技术查询优化技术v两类优化方法两类优化方法第一类：读取较少的较少的索引数据第二类：处理较少的较少的文档两者是相关 的！(因数据较少时很难对相同数量的文档打分)对复杂的特征函数，应主要考虑对较少文档打分;对简单的特征函数，应致力于忽略尽可能多的倒排

40、表数据.v基本优化技术基本优化技术1）倒排表跳转2）联合处理3）阈值方法4）MaxScore5）提早终止6）倒排表排列查询优化的查询优化的基本思路基本思路?有哪些优化技术?411) 倒排表跳转倒排表跳转v跳转指针(前5.4.7节)是目前最流行的忽略部分倒排表数据的方法v更复杂的方法，还有树结构(B+树等)，但并不常用v跳转指针不会根本改变倒排表读取速度读取速度 因:设倒排表长为n字节, 每c个字节加一跳转, 指针长k字节, 整个倒排表仍需读(n)字节 而用跳转指针跳过倒排表灰格长需(k*n/c) 字节时间,n/c是指针数,也与(n)相当 （一般地，取典型值c=100和k=4时，跳过一个倒排表仅

41、需读取全部数据的4%）v用跳转指针在倒排表中要找到p个posting的时间为：k*n/c + p*c/2注意：p很大(接近n/c)时，则几乎读所有到排表(间隔)，跳转无优势; c取较大可以使第1项变小，但也使2项变大(一般根据先前查询分析确定c).v跳转指针似乎可节省磁盘访问磁盘访问，实际未必。v跳转表的主要优点？跳转表的主要优点？在其中p个间隔中找那个posting均需c/2读所有跳转指针时间(因为磁盘读取序列数据，要比随机跳转好很多)1) 可降低对已从磁盘上读取的压缩数据的可降低对已从磁盘上读取的压缩数据的解码时间解码时间;2) 可极大地降低对缓存在内存中的倒排表的可极大地降低对缓存在内存

42、中的倒排表的处理时间处理时间.#422) 联合处理联合处理v什么是联合处理？什么是联合处理？指返回给用户的文档都包含所有查询项的查询方式(许多搜索引擎默认方式)v这样做的原因？这样做的原因？部分是因为用户希望部分是因为处理速度v该方法不适合什么场合？该方法不适合什么场合？不利于处理长句和段落情况的查询v该方法适合什么场合？该方法适合什么场合？有一个查询项为罕见时！ (查询fish locomotion运动/移动) 摇摆舞这样倒排求交(公共文档)时，倒排表跳过大量postingv联合处理可用于联合处理可用于doucument-at-a-time和和term-at-a-time系统系统图5-20：

43、改进的term-at-a-time算法图5-21：改进的document-at-a-time算法 #43 改进的改进的term-at-a-time算法算法同前同前依次处理各个查询项依次处理各个查询项初始化累计器A处理第1个查询项, 并形成最初的累加值A处理其它查询项同前同前最初时，累加器最初时，累加器A的指针指向起始点的指针指向起始点处理1个查询项li在在 li 中，读中，读 li 的当前文档的当前文档 若若d=d，即，即d 包含了该查询项和所包含了该查询项和所有前面查询项的文档，值应被累加有前面查询项的文档，值应被累加将将d0-d之间的累加值置之间的累加值置0(A中中未包含该查询项的文档应去

44、掉未包含该查询项的文档应去掉)在在A中，找到中，找到d或仅随或仅随d之之后的文档后的文档否则否则, 仅将仅将 li 的当前指针移到的当前指针移到d (将将d0 移动到移动到d )44d-1改进的改进的document-at-a-time算法算法同前同前同前同前每个每个li 的指针都跳到文档的指针都跳到文档d若各若各li 均均指向指向d,就累加分数就累加分数, 否则否则跳出跳出2-for, 进入进入while下一循环下一循环,处理处理1-for找到的下一个新文档找到的下一个新文档dWhile循环保证将整个循环保证将整个L中出现的中出现的文档都扫描过！文档都扫描过！但仅其中部分文档但仅其中部分文档

45、(每次每次倒排表当前指针中的最大倒排表当前指针中的最大文档文档d)计算了累加分数！计算了累加分数！旧算法中是旧算法中是: for all d I(假设已经处理过文档d)找到L中各倒排表当前指针指向的文档编号，将其中最大者赋给d。1-for若这些文档d只包含部分查询项，则必然执行2-for中的break语句，故累加分数Sd 将不保存在R中。R仅保存包含所有查询项的文档Sd值。2-for453) 阈值方法阈值方法v阈值阈值在信息检索中，通常要求确定一个参数阈值k-用户需要的结果数量！一般的搜索应用，k值都很小(10,20)因为这个k值，倒排表中大部分文档都不会显示给用户本节中，该 (thresho

46、ld)阈值用表示v研究阈值的目的和作用？研究阈值的目的和作用？阈值方法专注于研究阈值，目的是为了对更少的文档打分！对每个查询，都有某一最小分数，是被检索出的所有文档都必需达到的：这个数就是第k个最高得分文档的分数(任何没有达到该分数的文档将不会显示给用户)作用:能知道就可优化查询，避免避免将分数小于的文档加入加入优先队列v阈值如何计算？阈值如何计算？遗憾：不进行查询评价就不能正确计算出幸好：可以有方法估计它！期望：估计的值方法：若若可可后续的文档评价中，有更大分数的文档，就更新，直到处理完所有文档！464) MaxScore(最大分数最大分数)v利用估计阈值和倒排索引最大分数，可以优化查询v例

47、示分析：例示分析：查询“eucalyptus(桉树) tree” 。倒排表中tree出现频率比eucalyptus大上100倍，可以采用如下MaxScore方法：MaxScore指什么，有指什么，有何用途何用途?MaxScore475）提早终止）提早终止vMaxScaore方法，无论是否经过优化，保证查询结果都是相同的v但提早终止提早终止方法(不处理全部文档不处理全部文档)需冒质量风险(提速，但可能会降低查询效果)v例示分析：例示分析：查询“to be or not to be” (都是非常一般的项，倒排表都会非常长)MaxScore太“认真”，不放过任何项的倒排表中任何项若省略一些查询项或一

48、些倒排表中的文档(posting)，有损失但会更加高效!vterm-at-a-time提早终止法提早终止法可忽略一些查询项（到排表），类似使用停用词可读取一定数量的文档后(posting)，不在读后面的 (继续读对排序可能影响不大了)vdocument-at-a-time提早终止法提早终止法可通过忽略倒排表中非常靠后的文档(posting)！若文档是随机排序，这样做未必是好注意(查询结果影响较大)；但若文档是通过一些质量指标来排序(如pageRank),则忽略的是低质文档。提早终止指提早终止指什么，目的什么，目的何在何在?486）倒排表排列）倒排表排列v前面前面提到的倒排表都假设按照文档编号的

49、顺序排列v如果如果文档编号是随机的，最好的文档可能排在最后缺点：查询处理算法必须读取或者跳过整个到排表！v因此，因此，一个提高文档排列的途径是基于文档质量基于文档质量(多种衡量指标,如PageRank)优点1：如果许多好文档已经找到，就可提早停止搜索！优点2：MacScore阈值技术可以使用(因按质量降序排，在阈值小于 后的文档可终止)v甚至，甚至，每个倒排表根据部分分数根据部分分数排序例如，food的倒排表，首先存储包含food许多实例的文档(如饭店页面)又如，dog的倒排表，首先存储关于dog的页面(其中包含许多dog的实例)问题：该方法对评价有关food或dog的查询简单，但如何评价如何评价dog food？办法：办法：使用如同term-at-a-time检索的累加器表但不是一次读取整个到排表，而是仅读取每个倒排表前面的一小部分，一旦累加器显示找到许多好文档，即停止（可以想象：检索共现的查询项会很快）需要考虑到需要考虑到排表中文档排表中文档的排序的排序?497.3 结构化查询结构化查询v结构化查询结构化查询