《第讲词汇表和倒排记录表Thetermvocabularyandpostings》由会员分享，可在线阅读，更多相关《第讲词汇表和倒排记录表Thetermvocabularyandpostings（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 lists2011/9/14现代信息检索 提纲2上一讲回顾上一讲回顾 文档文档词项词项通常做法+非英语处理
2、英语跳表指针跳表指针短语查询短语查询提纲3上一讲回顾 文档词项通常做法+非英语处理英语跳表指针短语查询 现代信息检索上一讲回顾倒排索引的基本知识组成: 词典和倒排记录表构建中的关键步骤: 按词项排序布尔查询的处理线性时间内求交集查询优化现代信息检索 5倒排索引对每个词项t, 保存所有包含t的 文档列表5词典(dictionary) 倒排记录表( postings) 现代信息检索 6倒排记录表的合并6现代信息检索 7倒排索引构建: 将倒排记录排序7 现代信息检索查询优化按照表从小到大(即df从小到大)的顺序进行处理:每次从最小的开始合并8相当于处理查询 (Calpurnia AND Brutus
3、) AND Caesar.BrutusCaesarCalpurnia12358162134248163264 1281316第一讲：布尔检索 现代信息检索更通用的优化策略e.g., (madding OR crowd) AND (ignoble OR strife)每个布尔表达式都能转换成上述形式(合取范式)获得每个词项的df(保守)通过将词项的df相加，估计每个OR表达式对应的倒排记录表的大小按照上述估计从小到大依次处理每个OR表达式.9第一讲：布尔检索现代信息检索 10一个布尔搜索引擎Westlaw: 例子需求：有关对政府侵权行为进行索赔的诉讼时效(What is the statute
4、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)Fr
8、iendsRomansCountrymen词条 就是一个字符串实例词条在经过进一步处理之后将放入倒排索引中的词典中后面会讲词条化中的问题-词条如何界定? 现代信息检索词条化一系列问题:Finlands capital Finland? Finlands? Finlands?Hewlett-Packard 看成Hewlett 和 Packard 两个词条?state-of-the-art:co-educationlowercase, lower-case, lower case ?San Francisco: 到底是一个还是两个词条？如何判断是一个词条？ 现代信息检索词条化中数字的处理3/20/
9、91 Mar. 12, 199120/3/9155 B.C.B-52PGP 密钥：324a3df234cb23e(800) 234-2333通常中间有空格早期的IR系统可能不索引数字但是数字却常常很有用：比如在Web上查找错误代码(一种处理方法是采用n-gram: 见第三讲)元数据是分开还是一起索引创建日期、格式等等 现代信息检索语言问题：法语和德语法语Lensemble 到底是一个还是两个词条?L ? L ? Le ?但是常常希望 lensemble 能和un ensemble匹配至少在2003年以前，Google没有这样处理国际化问题!德语中复合名词连写Lebensversicherung
10、sgesellschaftsangestellterlife insurance company employee德语检索系统往往要使用一个复合词拆分的模块，而且该模块对检索结果的提高有很大帮助(可以提高15%) 现代信息检索语言问题：中文和日文中文和日文词之间没有间隔:莎拉波娃现在居住在美国东南部的佛罗里达。分词结果无法保证百分百正确， “和尚”日文中可以同时使用多种类型的字母表日期/数字可以采用不同的格式500社情報不足時間社情報不足時間$500K(約約6,000万円万円)片假名平假名汉字罗马字母而终端用户可能完全用平假名方式输入查询！ 现代信息检索中文分词(Chinese Word Se
11、gmentation)对于中文，分词的作用实际上是要找出一个个的索引单位例子：李明天天都准时上班索引单位字：李 明 天 天 都 准 时 上 班索引量太大，查全率百分百，但是查准率低，比如查“明天” 这句话也会出来词：李明 天天 都 准时 上班索引量大大降低，查准率较高，查全率不是百分百，而且还会受分词错误的影响，比如上面可能会切分成：李 明天 天都 准时 上班，还有： 他和服务人员照相字词混合方式/k-gram/多k-gram混合一般原则，没把握的情况下细粒度优先24 现代信息检索中文分词和检索以下是当前某些研究的结论或猜测，仅供参考并非分词精度高一定检索精度高评价标准不同分词规范问题： 鸡蛋
12、、鸭蛋、鹌鹑蛋目标不同检索中的分词：查询和文档切分采用一致的分词系统速度快倾向细粒度，保证召回率多粒度并存搜索引擎中的分词方法猜想：大词典+统计+启发式规则25 现代信息检索语言问题：阿拉伯文阿拉伯文 (或希伯来文) 通常从右到左书写，但是某些部分(如数字)是从左到右书写词之间是分开的，但是单词中的字母形式会构成复杂的连接方式 开始Algeria achieved its independence in 1962 after 132 years of French occupation.在Unicode编码方式下，表面的表示方式很复杂，但是存储上倒是十分直接 现代信息检索停用词根据停用词表(s
13、top 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 Motors（GM，通用公司）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时，同时也查c
18、ar拼写错误的处理(ClintonKlinten)一种解决方法是soundex方法，基于发音建立词之间的关系(Soundex方法将在后面介绍) 现代信息检索词形归并(Lemmatization)将单词的屈折变体形式还原为原形例子：am, are, is becar, cars, cars, cars carthe boys cars are different colors the boy car be different color词性归并意味中将单词的变形形式“适当”还原成一般词典中的单词形式found find? found? 现代信息检索词干还原（Stemming）将词项归约(redu
19、ce)成其词干(stem)，然后再索引“词干还原” 意味着词缀的截除与语言相关比如，将 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 SScaressescaressScatscat 现代信息检索Porter中的典型规则sses ssies iational atetional tion 规则适用条件的表达 (m1) EMENT replacement replaccement cement 现代信息检索Martin Porter(应该是)英国人，(应该是)剑桥大学2000年度 Tony Kent Strix award得主信息检索领域另一个著名的奖项Porters stemmer，有很多语言的版本Snowball
21、工具，支持多种语言的stemming(法语、德语、葡萄牙语、西班牙语挪威语等等)39 现代信息检索其他词干还原工具(stemmer)Lovins: http:/p.lancs.ac.uk/computing/ research/stemming/general/lovins.htm单遍扫描，最长词缀剔除 (大概 250条规则)全部基于词形分析 对于检索来说最多只能提供一定的帮助(at most modest benefits for retrieval)词干还原及其它归一化工作对检索的帮助英语： 结果要一分为二，对某些查询来说提高了召回率，但是对另外一些查询来说降低了正确率比如, operat
22、ive (dentistry) oper对西班牙语、德语、芬兰语等语言非常有用其中对于芬兰语有30% 的性能提高!40 现代信息检索语言特性上述很多转换处理具体实现时都与语言本身有关，并且常常和具体应用有关上述过程可以插件方式植入索引过程存在很多开源和商业插件可用 现代信息检索词典入口示意图ensemble.french時間時間.japaneseMIT.englishmit.germanguaranteed.englishentries.englishsometimes.englishtokenization.english可以按(或不按)语言分组，后面还会讲到提纲43上一讲回顾 文档词项通常
23、做法+非英语处理英语跳表指针短语查询现代信息检索 FASTER POSTINGS MERGES:SKIP POINTERS/SKIP LISTS快速倒排表合并跳表法 现代信息检索基本合并算法的回顾两个指针，同步扫描，线性时间128312484148641238111721BrutusCaesar28两个表长度为m和n的话，上述合并时间复杂度为 O(m+n)能否做得更好？答案是可以(如果索引不常变化的话) 现代信息检索索引构建时为倒排记录表增加跳表指针为什么可以加快速度?可以跳过那些不可能的检索结果如何做?也就是在什么地方加跳表指针?1282484148643112381117213111411
24、28基于跳表指针的查询处理128248414864311238111721311141128假定匹配到上下的指针都指向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短语查询及位置索引 现代信息检索短语查询输入查询作为一个短语整体，比如 “sta
26、nford university” “中国科学院”因此，句子 “I went to university at Stanford” 就不应该是答案 （“我去了中国 农业 科学院”）有证据表明，用户很容易理解短语查询的概念，这也是很多搜索引擎”高级搜索”中比较成功的一个功能。但是很多查询是隐式短语查询， information retrieval textbook information retrieval textbook这种情况下，倒排索引仅仅采用如下方式是不够的 term + docIDs 现代信息检索第一种做法: 双词(Biword)索引每两个连续的词组成词对(作为短语)来索引比如文本片
27、段 “Friends, Romans, Countrymen” 会产生两个词对friends romansromans countrymen索引构建时，将每个词对看成一个词项放到词典中这样的话，两个词组成的短语查询就能直接处理 现代信息检索更长的短语查询处理例子： stanford university palo alto，处理方法： 将其拆分成基于双词的布尔查询式:stanford university AND university palo AND palo alto 如果不检查文档，无法确认满足上述表达式的文档是否真正满足上述短语查询。也就是说满足上述布尔表达式只是满足短语查询的充分条件
28、。很难避免伪正例的出现！ 现代信息检索扩展的双词（Extended Biword）对待索引文档进行词性标注将词项进行组块，每个组块包含名词 (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.合并表
30、，考虑 “to be or not to be”.to: 2:1,17,74,222,551; 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位置索引存储单元倒排记录表的数目文档大小 现代信
32、息检索一些经验规律位置索引的大小大概是无位置信息索引的2-4倍位置索引大概是原始文本容量的35-50%提醒：上述经验规律适用于英语及类英语的语言 现代信息检索混合索引上述两种索引方式可以混合使用对某些特定的短语 (如“Michael Jackson”, “Britney Spears”) ，如果采用位置索引的方式那么效率不高还有“The Who”（英国一著名摇滚乐队），采用位置索引，效率更低Williams et al. (2004)对一种混合的索引机制进行了评估采用混合机制，那么对于典型的Web查询(比例)来说，相对于只使用位置索引而言，仅需要其 的时间相对于只使用位置索引，空间开销只增加了
33、26% 现代信息检索本讲小结索引构建过程(特别是预处理）如何对索引文档进行处理来得到词典理解文档(document)的概念词条化(Tokenization)，理解词条(token)的概念词项生成，理解词项(term)的概念倒排记录表更快的合并算法: 跳表法(skip list)短语查询的处理及带位置信息的倒排索引 现代信息检索参考资料信息检索导论第 2章MG 3.6, 4.3; MIR 7.2Porters stemmer: http:/www.tartarus.org/martin/PorterStemmer/跳表理论: Pugh (1990)Multilevel skip lists gi
34、ve same O(log n) efficiency as treesH.E. Williams, J. Zobel, and D. Bahle. 2004. “Fast Phrase Querying with Combined Indexes”, ACM Transactions on Information Systems.http:/www.seg.rmit.edu.au/research/research.php?author=4D. Bahle, H. Williams, and J. Zobel. Efficient phrase querying with an auxiliary index. SIGIR 2002, pp. 215-221. 现代信息检索课后练习习题2-1习题2-6习题2-9
