lecture2-dictionary-信息检索导论-王斌-PPT-课件-第2章

IntroductiontoInformationRetrieval现代信息检索中科院研究生院2011年秋季课程《现代信息检索》更新时间：ModernInformationRetrieval授课人：王斌~wangbin*改编自”AnintroductiontoInformationretrieval”网上公开的课件，地址第2讲词汇表和倒排记录表Thetermvocabularyandpostingslists2011/9/14现代信息检索提纲2❶上一讲回顾❷文档❸词项通常做法+非英语处理英语❹跳表指针❺短语查询提纲3❶上一讲回顾❷文档❸词项通常做法+非英语处理英语❹跳表指针❺短语查询现代信息检索上一讲回顾倒排索引的基本知识组成:词典和倒排记录表构建中的关键步骤:按词项排序布尔查询的处理线性时间内求交集查询优化现代信息检索5倒排索引对每个词项t,保存所有包含t的文档列表5词典(dictionary)倒排记录表(postings)现代信息检索6倒排记录表的合并6现代信息检索7倒排索引构建:将倒排记录排序7现代信息检索查询优化按照表从小到大(即df从小到大)的顺序进行处理:每次从最小的开始合并8相当于处理查询(CalpurniaANDBrutus)ANDCaesar.BrutusCaesarCalpurnia123581621342481632641281316第一讲：布尔检索现代信息检索更通用的优化策略e.g.,(maddingORcrowd)AND(ignobleORstrife)每个布尔表达式都能转换成上述形式(合取范式)获得每个词项的df(保守)通过将词项的df相加，估计每个OR表达式对应的倒排记录表的大小按照上述估计从小到大依次处理每个OR表达式.9第一讲：布尔检索现代信息检索10一个布尔搜索引擎Westlaw:例子需求：有关对政府侵权行为进行索赔的诉讼时效(Whatisthestatuteoflimitationsincasesinvolvingthefederaltortclaimsact?）查询：LIMIT!/3STATUTEACTION/SFEDERAL/2TORT/3CLAIM/3=within3words,/S=insamesentence10现代信息检索11Google中是否使用布尔模型？Google默认是与(AND)操作，输入查询[w1w2...wn]意味着w1ANDw2AND...ANDwn当返回文档不包含某个词wi时，可能是如下情形:指向该页面的锚文本包含wi页面包含wi的变形(不同形态的同一词，拼写校对，同义等等)长查询(nlarge)布尔表达式返回的结果少简单的布尔检索vs.结果的排序简单的布尔检索只返回匹配上的文档，不考虑结果顺序Google和其他大部分精心设计的布尔引擎均对结果进行排序，以使好的结果排在差的结果的前面11现代信息检索本讲的内容索引构建过程(特别是预处理）如何对索引文档进行处理来得到词典理解文档(document)的概念词条化(Tokenization)，理解词条(token)的概念词项生成，理解词项(term)的概念倒排记录表更快的合并算法:跳表法(skiplist)短语查询的处理及带位置信息的倒排索引提纲13❶上一讲回顾❷文档❸词项通常做法+非英语处理英语❹跳表指针❺短语查询现代信息检索Tokenizer词条流FriendsRomansCountrymen回顾倒排索引构建Linguisticmodules修改后的词条friendromancountrymanIndexer倒排索引friendromancountryman24213161待索引文档Friends,Romans,countrymen.词条化工具语言分析工具词典现代信息检索文档分析文档格式处理pdf/word/excel/html?文档语言识别文档编码识别文档语言识别和编码识别理论上都可以看成分类问题，基于后面章节的分类方法可以处理。但是实际中，常常采用启发式方法……现代信息检索多格式/语言并存待索引文档集可能同时包含多种语言的文档在同一索引中词汇表中包含来自多个语言的词项有时文档或者其部件中包含多种语言/格式法语邮件中带一个德语的pdf格式附件如何确定索引的单位？文件为单位？邮件为单位？如果邮件带有5个附件，怎么办？一组文件？(比如采用html格式写的某个PPT文档)提纲17❶上一讲回顾❷文档❸词项通常做法+非英语处理英语❹跳表指针❺短语查询现代信息检索TOKENSANDTERMS词条和词项现代信息检索词条化(Tokenization)输入:“Friends,RomansandCountrymen”输出:词条(Token)FriendsRomansCountrymen词条就是一个字符串实例词条在经过进一步处理之后将放入倒排索引中的词典中后面会讲词条化中的问题-词条如何界定?现代信息检索词条化一系列问题:Finland’scapitalFinland?Finlands?Finland’s?Hewlett-Packard看成Hewlett和Packard两个词条?state-of-the-art:co-educationlowercase,lower-case,lowercase?SanFrancisco:到底是一个还是两个词条？如何判断是一个词条？现代信息检索词条化中数字的处理3/20/91Mar.12,199120/3/9155B.C.B-52PGP密钥：324a3df234cb23e[phone]通常中间有空格早期的IR系统可能不索引数字但是数字却常常很有用：比如在Web上查找错误代码(一种处理方法是采用n-gram:见第三讲)元数据是分开还是一起索引创建日期、格式等等现代信息检索语言问题：法语和德语法语L‘ensemble到底是一个还是两个词条?L?L’?Le?但是常常希望l’ensemble能和unensemble匹配至少在2003年以前，Google没有这样处理国际化问题!德语中复合名词连写Lebensversicherungsgesellschaftsangestellter‘lifeinsurancecompanyemployee’德语检索系统往往要使用一个复合词拆分的模块，而且该模块对检索结果的提高有很大帮助(可以提高15%)现代信息检索语言问题：中文和日文中文和日文词之间没有间隔:莎拉波娃现在居住在美国东南部的佛罗里达。分词结果无法保证百分百正确，“和尚”日文中可以同时使用多种类型的字母表日期/数字可以采用不同的格式フォーチュン500社は情報不足のため時間あた$500K(約6,000万円)片假名平假名汉字罗马字母而终端用户可能完全用平假名方式输入查询！现代信息检索中文分词(ChineseWordSegmentation)对于中文，分词的作用实际上是要找出一个个的索引单位例子：李明天天都准时上班索引单位字：李明天天都准时上班索引量太大，查全率百分百，但是查准率低，比如查“明天”这句话也会出来词：李明天天都准时上班索引量大大降低，查准率较高，查全率不是百分百，而且还会受分词错误的影响，比如上面可能会切分成：李明天天都准时上班，还有：他和服务人员照相字词混合方式/k-gram/多k-gram混合一般原则，没把握的情况下细粒度优先24现代信息检索中文分词和检索以下是当前某些研究的结论或猜测，仅供参考并非分词精度高一定检索精度高评价标准不同分词规范问题：鸡蛋、鸭蛋、鹌鹑蛋……目标不同检索中的分词：查询和文档切分采用一致的分词系统速度快倾向细粒度，保证召回率多粒度并存搜索引擎中的分词方法猜想：大词典+统计+启发式规则25现代信息检索语言问题：阿拉伯文阿拉伯文(或希伯来文)通常从右到左书写，但是某些部分(如数字)是从左到右书写词之间是分开的，但是单词中的字母形式会构成复杂的连接方式←→←→←开始‘Algeriaachieveditsindependencein1962after132yearsofFrenchoccupation.’在Unicode编码方式下，表面的表示方式很复杂，但是存储上倒是十分直接现代信息检索停用词根据停用词表(stoplist),将那些最常见的词从词典中去掉。比如直观上可以去掉：一般不包含语义信息的词:the,a,and,to,be汉语中的“的”、“得”、“地”等等。这些词都是高频词:前30个词就占了~30%的倒排记录表空间现代信息检索系统中倾向于不去掉停用词:在保留停用词的情况下，采用良好的压缩技术(第五章)后，停用词所占用的空间可以大大压缩，最终它们在整个倒排记录表中所占的空间比例很小采用良好的查询优化技术(第七章)基本不会增加查询处理的开销所谓的停用词并不一定没用，比如：短语查询:“KingofDenmark”、歌曲名或者台词等等:“Letitbe”,“Tobeornottobe”、“关系型”查询“flightstoLondon”现代信息检索词条归一化(Normalization)成词项将文档和查询中的词归一化成同一形式：U.S.A.和USA归一化的结果就是词项，而词项就是我们最终要索引的对象可以采用隐式规则的方法来表示多个词条可以归一成同一词项，比如剔除句点U.S.A.,USAUSA剔除连接符anti-discriminatory,antidiscriminatoryantidiscriminatory现代信息检索归一化中的语言问题重音符:如法语中résumévs.resume.日耳曼语系中的元音变化:如德语中的Tuebingenvs.Tübingen应该是一致的最重要的准则:用户在输入查询时遇到这些词如何输入?即使在有重音符号的语言中，用户也往往不输入这些符号常常归一化成不带重音符号的形式Tuebingen,Tübingen,TubingenTubingen现代信息检索归一化中的语言问题时间格式7月30日vs.7/30日语中用假名或者汉字表示日期词条化和归一化都可能与语言相关，因此必须要做语言识别另外，谨记要将文档和查询中的同义词归一化成同一形式MorgenwillichinMIT…是德语的“mit”吗?提纲31❶上一讲回顾❷文档❸词项通常做法+非英语处理英语❹跳表指针❺短语查询现代信息检索大小写问题可以将所有字母转换成小写形式例外:句中的大写单词？e.g.,GeneralMotors（GM，通用公司）Fed(美联储)vs.fed(饲养)SAIL(印度钢铁管理局)vs.sail(航行)通常情况下将所有字母转成小写是一种很合适的方式，因为用户倾向于用小写方式输入Google的例子:查询C.A.T.排名第一的结果是“cat”而不是CaterpillarInc.现代信息检索归一化成词项除了前面互换方式(即能够归一化成同一词项的词条之间完全平等，可以互换)之外，另一种方式是非对称扩展(asymmetricexpansion)一个非对称扩展更适合的的例子输入:window搜索:window,windows输入:windows搜索:Windows,windows,window输入:Windows搜索:Windows为什么反过来不行？这种方法可能更强大，但是效率低一些现代信息检索同义词词典(Thesauri)及soundex方法同义词和同音/同形异义词的处理E.g.,手动建立词典，记录这些词对car=automobilecolor=colour利用上述词典进行索引当文档包含automobile时,利用car-a