第2讲 词汇表和倒排记录表 The term vocabulary and postings

《第2讲 词汇表和倒排记录表 The term vocabulary and postings》由会员分享，可在线阅读，更多相关《第2讲 词汇表和倒排记录表 The term vocabulary and postings（67页珍藏版）》请在装配图网上搜索。

1、Introduction to Information Retrieval 现代信息检索现代信息检索中科院研究生院2011年秋季课程现代信息检索 更新时间：Modern Information Retrieval授课人：王斌http:/ introduction to Information retrieval”网上公开的课件，地址 http:/nlp.stanford.edu/IR-book/第2讲 词汇表和倒排记录表 The term vocabulary and postings lists2021/9/14现代信息检索 提纲2上一讲回忆上一讲回忆 文档文档词项词项通常做法通常做法+非英

2、语处理非英语处理英语英语跳表指针跳表指针短语查询短语查询提纲3上一讲回忆 文档词项通常做法+非英语处理英语跳表指针短语查询 现代信息检索上一讲回忆 倒排索引的根本知识 组成:词典和倒排记录表 构建中的关键步骤:按词项排序 布尔查询的处理 线性时间内求交集 查询优化现代信息检索 5倒排索引对每个词项t,保存所有包含t的 文档列表5词典(dictionary)倒排记录表(postings)现代信息检索 6倒排记录表的合并6现代信息检索 7倒排索引构建:将倒排记录排序7 现代信息检索查询优化 按照表从小到大(即df从小到大)的顺序进行处理:每次从最小的开始合并8相当于处理查询(Calpurnia A

3、ND Brutus)AND Caesar.BrutusCaesarCalpurnia12358162134248163264 1281316第一讲：布尔检索 现代信息检索更通用的优化策略 e.g.,(madding OR crowd)AND(ignoble OR strife)每个布尔表达式都能转换成上述形式(合取范式)获得每个词项的df(保守)通过将词项的df相加，估计每个OR表达式对应的倒排记录表的大小 按照上述估计从小到大依次处理每个OR表达式.9第一讲：布尔检索现代信息检索 10一个布尔搜索引擎Westlaw:例子需求：有关对政府侵权行为进行索赔的诉讼时效(What is the st

4、atute of limitations in cases involving the federal tort claims act?查询：LIMIT!/3 STATUTE ACTION/S FEDERAL/2 TORT/3 CLAIM/3=within 3 words,/S=in same sentence10现代信息检索 11Google中是否使用布尔模型？Google默认是与(AND)操作，输入查询w1 w2.wn意味着 w1 AND w2 AND.AND wn当返回文档不包含某个词wi 时，可能是如下情形:指向该页面的锚文本包含wi页面包含 wi 的变形(不同形态的同一词，拼写校对，

5、同义等等)长查询(n large)布尔表达式返回的结果少简单的布尔检索 vs.结果的排序简单的布尔检索只返回匹配上的文档，不考虑结果顺序Google和其他大局部精心设计的布尔引擎均对结果进行排序，以使好的结果排在差的结果的前面11 现代信息检索本讲的内容 索引构建过程(特别是预处理 如何对索引文档进行处理来得到词典 理解文档(document)的概念 词条化(Tokenization)，理解词条(token)的概念 词项生成，理解词项(term)的概念 倒排记录表 更快的合并算法:跳表法(skip list)短语查询的处理及带位置信息的倒排索引提纲13上一讲回忆 文档词项通常做法+非英语处理英

6、语跳表指针短语查询 现代信息检索Tokenizer词条流FriendsRomansCountrymen回忆倒排索引构建Linguistic modules修改后的词条friendromancountrymanIndexer倒排索引friendromancountryman24213161待索引文档Friends,Romans,countrymen.词条化工具语言分析工具词典 现代信息检索文档分析 文档格式处理 pdf/word/excel/html?文档语言识别 文档编码识别文档语言识别和编码识别理论上都可以看成分类问题，基于后面章节的分类方法可以处理。但是实际中，常常采用启发式方法 现代信息

7、检索多格式/语言并存 待索引文档集可能同时包含多种语言的文档 在同一索引中词汇表中包含来自多个语言的词项 有时文档或者其部件中包含多种语言/格式 法语邮件中带一个德语的pdf格式附件 如何确定索引的单位？文件为单位？邮件为单位？如果邮件带有5个附件，怎么办？一组文件？(比方采用html格式写的某个PPT文档)提纲17上一讲回忆 文档词项通常做法+非英语处理英语跳表指针短语查询现代信息检索 TOKENS AND TERMS词条和词项 现代信息检索词条化(Tokenization)输入:“Friends,Romans and Countrymen 输出:词条(Token)Friends Roman

8、s Countrymen 词条 就是一个字符串实例 词条在经过进一步处理之后将放入倒排索引中的词典中 后面会讲 词条化中的问题-词条如何界定?现代信息检索词条化 一系列问题:Finlands capital Finland?Finlands?Finlands?Hewlett-Packard 看成Hewlett 和 Packard 两个词条?state-of-the-art:co-education lowercase,lower-case,lower case?San Francisco:到底是一个还是两个词条？如何判断是一个词条？现代信息检索词条化中数字的处理 3/20/91 Mar.12,

9、199120/3/91 55 B.C.B-52 PGP 密钥：324a3df234cb23e(800)234-2333 通常中间有空格 早期的IR系统可能不索引数字 但是数字却常常很有用：比方在Web上查找错误代码(一种处理方法是采用n-gram:见第三讲)元数据是分开还是一起索引 创立日期、格式等等 现代信息检索语言问题：法语和德语 法语 Lensemble 到底是一个还是两个词条?L?L?Le?但是常常希望 lensemble 能和un ensemble匹配 至少在2003年以前，Google没有这样处理 国际化问题!德语中复合名词连写 Lebensversicherungsgesells

10、chaftsangestellter life insurance company employee 德语检索系统往往要使用一个复合词拆分的模块，而且该模块对检索结果的提高有很大帮助(可以提高15%)现代信息检索语言问题：中文和日文 中文和日文词之间没有间隔:莎拉波娃现在居住在美国东南部的佛罗里达。分词结果无法保证百分百正确，“和尚 日文中可以同时使用多种类型的字母表 日期/数字可以采用不同的格式500社情報缺乏時間社情報缺乏時間$500K(約約6,000万円万円)片假名平假名汉字罗马字母而终端用户可能完全用平假名方式输入查询！现代信息检索中文分词(Chinese Word Segmentat

11、ion)对于中文，分词的作用实际上是要找出一个个的索引单位 例子：李明天天都准时上班 索引单位 字：李 明 天 天 都 准 时 上 班 索引量太大，查全率百分百，但是查准率低，比方查“明天 这句话也会出来 词：李明 天天 都 准时 上班 索引量大大降低，查准率较高，查全率不是百分百，而且还会受分词错误的影响，比方上面可能会切分成：李 明天 天都 准时 上班，还有：他和效劳人员照相 字词混合方式/k-gram/多k-gram混合 一般原那么，没把握的情况下细粒度优先24 现代信息检索中文分词和检索 以下是当前某些研究的结论或猜测，仅供参考 并非分词精度高一定检索精度高 评价标准不同 分词标准问题

12、：鸡蛋、鸭蛋、鹌鹑蛋 目标不同 检索中的分词：查询和文档切分采用一致的分词系统 速度快 倾向细粒度，保证召回率 多粒度并存 搜索引擎中的分词方法 猜测：大词典+统计+启发式规那么25 现代信息检索语言问题：阿拉伯文 阿拉伯文(或希伯来文)通常从右到左书写，但是某些局部(如数字)是从左到右书写 词之间是分开的，但是单词中的字母形式会构成复杂的连接方式 开始 Algeria achieved its independence in 1962 after 132 years of French occupation.在Unicode编码方式下，外表的表示方式很复杂，但是存储上倒是十分直接 现代信息检

13、索停用词 根据停用词表(stop list),将那些最常见的词从词典中去掉。比方直观上可以去掉：一般不包含语义信息的词:the,a,and,to,be 汉语中的“的、“得、“地等等。这些词都是高频词:前30个词就占了 30%的倒排记录表空间 现代信息检索系统中倾向于不去掉停用词:在保存停用词的情况下，采用良好的压缩技术(第五章)后，停用词所占用的空间可以大大压缩，最终它们在整个倒排记录表中所占的空间比例很小 采用良好的查询优化技术(第七章)根本不会增加查询处理的开销 所谓的停用词并不一定没用，比方：短语查询:“King of Denmark、歌曲名或者台词等等:“Let it be,“To b

14、e or not to be、“关系型 查询“flights to London 现代信息检索词条归一化(Normalization)成词项 将文档和查询中的词归一化成同一形式：U.S.A.和 USA 归一化的结果就是词项，而词项就是我们最终要索引的对象 可以采用隐式规那么的方法来表示多个词条可以归一成同一词项，比方 剔除句点 U.S.A.,USA USA 剔除连接符 anti-discriminatory,antidiscriminatory antidiscriminatory 现代信息检索归一化中的语言问题 重音符:如法语中 rsum vs.resume.日耳曼语系中的元音变化:如德语中

15、的 Tuebingen vs.Tbingen 应该是一致的 最重要的准那么:用户在输入查询时遇到这些词如何输入?即使在有重音符号的语言中，用户也往往不输入这些符号 常常归一化成不带重音符号的形式 Tuebingen,Tbingen,Tubingen Tubingen 现代信息检索归一化中的语言问题 时间格式 7月30日 vs.7/30 日语中用假名或者汉字表示日期 词条化和归一化都可能与语言相关，因此必须要做语言识别 另外，谨记要将文档和查询中的同义词归一化成同一形式Morgen will ich in MIT 是德语的“mit”吗?提纲31上一讲回忆 文档词项通常做法+非英语处理英语跳表指针

16、短语查询 现代信息检索大小写问题 可以将所有字母转换成小写形式 例外:句中的大写单词？e.g.,General MotorsGM，通用公司 Fed(美联储)vs.fed(饲养)SAIL(印度钢铁管理局)vs.sail(航行)通常情况下将所有字母转成小写是一种很适宜的方式，因为用户倾向于用小写方式输入 Google的例子:查询 C.A.T.排名第一的结果是“cat而不是 Caterpillar Inc.现代信息检索归一化成词项 除了前面互换方式(即能够归一化成同一词项的词条之间完全平等，可以互换)之外，另一种方式是非对称扩展(asymmetric expansion)一个非对称扩展更适合的的例子

17、 输入:window搜索:window,windows 输入:windows 搜索:Windows,windows,window 输入:Windows 搜索:Windows 为什么反过来不行？这种方法可能更强大，但是效率低一些 现代信息检索同义词词典(Thesauri)及soundex方法 同义词和同音/同形异义词的处理 E.g.,手动建立词典，记录这些词对 car=automobile color=colour 利用上述词典进行索引 当文档包含 automobile时,利用car-automobile进行索引 或者对查询进行扩展 当查询包含 automobile时，同时也查car 拼写错误的

18、处理(ClintonKlinten)一种解决方法是soundex方法，基于发音建立词之间的关系(Soundex方法将在后面介绍)现代信息检索词形归并(Lemmatization)将单词的屈折变体形式复原为原形 例子：am,are,is be car,cars,cars,cars car the boys cars are different colors the boy car be different color 词性归并意味中将单词的变形形式“适当复原成一般词典中的单词形式 found find?found?现代信息检索词干复原Stemming 将词项归约(reduce)成其词干(stem

19、)，然后再索引“词干复原 意味着词缀的截除 与语言相关 比方，将 automate(s),automatic,automation都复原成 automatfor example compressed and compression are both accepted as equivalent to compress.for exampl compress andcompress ar both acceptas equival to compress 现代信息检索Porter算法 英语词干复原中最常用的算法 结果说明该方法不差于其他的词干复原方法 一些规定+5 步骤的归约过程 这些步骤有先后

20、顺序 每一步都包含一系列命令 一些规定，比方:选择可应用规那么组中包含最长词缀的规那么 SSES SScaresses caress Scatscat 现代信息检索Porter中的典型规那么 sses ss ies i ational ate tional tion 规那么适用条件的表达 (m1)EMENT replacement replac cement cement 现代信息检索Martin Porter(应该是)英国人，(应该是)剑桥大学 2000年度 Tony Kent Strix award得主 信息检索领域另一个著名的奖项 Porters stemmer，有很多语言的版本 Sno

21、wball 工具，支持多种语言的stemming(法语、德语、葡萄牙语、西班牙语挪威语等等)39 现代信息检索其他词干复原工具(stemmer)research/stemming/general/lovins.htm 单遍扫描，最长词缀剔除(大概 250条规那么)全部基于词形分析 对于检索来说最多只能提供一定的帮助(at most modest benefits for retrieval)词干复原及其它归一化工作对检索的帮助 英语：结果要一分为二，对某些查询来说提高了召回率，但是对另外一些查询来说降低了正确率 比方,operative(dentistry)oper 对西班牙语、德语、芬兰语等

22、语言非常有用 其中对于芬兰语有30%的性能提高!40 现代信息检索语言特性 上述很多转换处理具体实现时 都与语言本身有关，并且 常常和具体应用有关 上述过程可以插件方式植入索引过程 存在很多开源和商业插件可用 现代信息检索词典入口示意图ensemble.french時間時間.japaneseMIT.englishmit.germanguaranteed.englishentries.englishsometimes.englishtokenization.english可以按(或不按)语言分组，后面还会讲到提纲43上一讲回忆 文档词项通常做法+非英语处理英语跳表指针短语查询现代信息检索 FAS

23、TER POSTINGS MERGES:SKIP POINTERS/SKIP LISTS快速倒排表合并跳表法 现代信息检索根本合并算法的回忆 两个指针，同步扫描，线性时间128312484148641238111721BrutusCaesar28两个表长度为m和n的话，上述合并时间复杂度为 O(m+n)能否做得更好？答案是可以(如果索引不常变化的话)现代信息检索索引构建时为倒排记录表增加跳表指针 为什么可以加快速度?可以跳过那些不可能的检索结果 如何做?也就是在什么地方加跳表指针?128248414864311238111721311141128基于跳表指针的查询处理1282484148643

24、11238111721311141128假定匹配到上下的指针都指向8，接下来两个指针都向下移动一位。比较41和11，11小此时看11上面的跳表指针，指向31，31仍然比41小，于是下指针可以直接跳过中间的11、17、21、31跳表法 现代信息检索跳表指针的位置 指针数目过多过少都不适宜，要有一个均衡性:指针越多 跳步越短 更容易跳转，但是需要更多的与跳表指针指向记录的比较 指针越少 比较次数越少，但是跳步越长 成功跳转的次数少 现代信息检索跳表指针的位置 简单的启发式策略：对于长度为L的倒排记录表，每 L 处放一个跳表指针，即均匀放置。均匀放置方法忽略了查询词项的分布情况 如果索引相对静态，均

25、匀方式方法是一种很简便的方法，但是如果索引经常更新造成L经常变化，均匀方式方式就很不方便 跳表方式在过去肯定是有用的，但是对于现代的硬件设备而言，如果合并的倒排记录表不能全部放入内存的话，上述方式不一定有用(Bahle et al.2002)更大的倒排记录表(含跳表)的 I/O开销可能远远超过内存中合并带来的好处提纲50上一讲回忆 文档词项通常做法+非英语处理英语跳表指针短语查询现代信息检索 PHRASE QUERIES AND POSITIONAL INDEXES短语查询及位置索引 现代信息检索短语查询 输入查询作为一个短语整体，比方“stanford university “中国科学院 因

26、此，句子“I went to university at Stanford 就不应该是答案“我去了中国 农业 科学院 有证据说明，用户很容易理解短语查询的概念，这也是很多搜索引擎高级搜索中比较成功的一个功能。但是很多查询是隐式短语查询，information retrieval textbook information retrieval textbook 这种情况下，倒排索引仅仅采用如下方式是不够的 term+docIDs 现代信息检索第一种做法:双词(Biword)索引 每两个连续的词组成词对(作为短语)来索引 比方文本片段“Friends,Romans,Countrymen 会产生两个词

27、对 friends romans romans countrymen 索引构建时，将每个词对看成一个词项放到词典中 这样的话，两个词组成的短语查询就能直接处理 现代信息检索更长的短语查询处理 例子：stanford university palo alto，处理方法：将其拆分成基于双词的布尔查询式:stanford university AND university palo AND palo alto 如果不检查文档，无法确认满足上述表达式的文档是否真正满足上述短语查询。也就是说满足上述布尔表达式只是满足短语查询的充分条件。很难防止伪正例的出现！现代信息检索扩展的双词Extended Biw

28、ord 对待索引文档进行词性标注 将词项进行组块，每个组块包含名词(N)和冠词/介词(X)称具有NX*N形式的词项序列为扩展双词(extended biword)将这样扩展词对作为词项放入词典中 例子:catcher in the rye(书名：麦田守望者)N X X N 查询处理：将查询也分析成 N和X序列 将查询切分成扩展双词 在索引中查找:catcher rye 现代信息检索关于双词索引 会出现伪正例子 由于词典中词项数目剧增，导致索引空间也激增 如果3词索引，那么更是空间巨大，无法忍受 双词索引方法并不是一个标准的做法(即倒排索引中一般不会全部采用双词索引方法)，但是可以和其他方法混合

29、使用 现代信息检索第二种解决方法:带位置信息索引(Positional indexes)在倒排记录表中，对每个term在每篇文档中的每个位置(偏移或者单词序号)进行存储:现代信息检索位置索引的例子 对于输入的短语查询，需要在文档的层次上进行迭代(不同位置上)合并 不仅仅简单合并，还要考虑位置匹配1,2,4,5这几篇文章中哪篇包含“to beor not to be?现代信息检索短语查询的处理 短语查询：“to be or not to be 对每个词项，抽出其对应的倒排记录表:to,be,or,not.合并表，考虑“to be or not to be.to:2:1,17,74,222,551

30、;4:8,16,190,429,433;7:13,23,191;.be:1:17,19;4:17,191,291,430,434;5:14,19,101;.邻近搜索中的搜索策略与此类似，不同的是此时考虑前后位置之间的距离不大于某个值 现代信息检索邻近式查询(Proximity query)LIMIT!/3 STATUTE/3 FEDERAL/2 TORT /k 表示“在 k 个词之内 很明显，位置索引可以处理邻近式查询，而双词索引却不能 现代信息检索位置索引的大小 位置索引增加了位置信息，因此空间较大，但是可以采用索引压缩技术进行处理(参见第五讲)当然，相对于没有位置信息的索引，位置索引的存储

31、空间明显大于无位置信息的索引 另外，位置索引目前是实际检索系统的标配，这是因为实际中需要处理短语(显式和隐式)和邻近式查询 现代信息检索位置索引的大小 词项在每篇文档中的每次出现都需要一个存储单元 因此索引的大小依赖于文档的平均长度 平均Web页面的长度 1000 个词项 美国证监会文件(SEC filings),书籍,甚至一些史诗 和容易就超过 100,000 个词项 假定某个词项的出现频率是0.1%Why?1001100,000111000位置索引存储单元倒排记录表的数目文档大小 现代信息检索一些经验规律 位置索引的大小大概是无位置信息索引的2-4倍 位置索引大概是原始文本容量的35-50

32、%提醒：上述经验规律适用于英语及类英语的语言 现代信息检索混合索引 上述两种索引方式可以混合使用 对某些特定的短语(如“Michael Jackson,“Britney Spears)，如果采用位置索引的方式那么效率不高 还有“The Who英国一著名摇滚乐队，采用位置索引，效率更低 Williams et al.(2004)对一种混合的索引机制进行了评估 采用混合机制，那么对于典型的Web查询(比例)来说，相对于只使用位置索引而言，仅需要其 的时间 相对于只使用位置索引，空间开销只增加了26%现代信息检索本讲小结 索引构建过程(特别是预处理 如何对索引文档进行处理来得到词典 理解文档(doc

33、ument)的概念 词条化(Tokenization)，理解词条(token)的概念 词项生成，理解词项(term)的概念 倒排记录表 更快的合并算法:跳表法(skip list)短语查询的处理及带位置信息的倒排索引 现代信息检索参考资料?信息检索导论?第 2章 MG 3.6,4.3;MIR 7.2 Porters stemmer:/tartarus.org/martin/PorterStemmer/跳表理论:Pugh(1990)Multilevel skip lists give same O(log n)efficiency as trees H.E.Williams,J.Zobel,and D.Bahle.2004.“Fast Phrase Querying with Combined Indexes,ACM Transactions on Information Systems.D.Bahle,H.Williams,and J.Zobel.Efficient phrase querying with an auxiliary index.SIGIR 2002,pp.215-221.现代信息检索课后练习 习题2-1 习题2-6 习题2-9