lecture3-tolerant-retrieval-信息检索导论-王斌-PPT-课件-第3章

IntroductiontoInformationRetrieval现代信息检索中科院研究生院2011年秋季课程《现代信息检索》更新时间：ModernInformationRetrieval授课人：王斌~wangbin*改编自”AnintroductiontoInformationretrieval”网上公开的课件，地址第3讲词典及容错式检索Dictionaryandtolerantretrieval12011/9/15现代信息检索提纲2①上一讲回顾②词典③通配查询④编辑距离⑤拼写校正⑥Soundex现代信息检索提纲3①上一讲回顾②词典③通配查询④编辑距离⑤拼写校正⑥Soundex现代信息检索上一讲内容文档词条/词项基于跳表指针的合并短语查询的处理(双词索引和位置索引)4现代信息检索文档索引的基本单位与文件不是一回事，严格地说，一篇文档可能包含多个文件，也可能一个文件包含多篇文档依赖于具体应用句子级检索：一个句子为一篇文档段落级检索：一段文本为一篇文档……5现代信息检索6词类(type)/词条(token)的区别词条(Token)–词或者词项在文档中出现的实例，出现多次算多个词条词类(Type)–多个词条构成的等价类(equivalenceclass)集合InJune,thedoglikestochasethecatinthebarn.12个词条,9个词类词类经过一些处理(去除停用词、归一化)之后，最后用于索引的称为为词项6现代信息检索7词条化中考虑的问题词之间的边界是什么？空格？撇号还是连接符？上述边界不一定是真正的边界(比如,中文)另外荷兰语、德语、瑞典语复合词中间没有空格(Lebensversicherungsgesellschaftsangestellter)7现代信息检索8词项归一化中的问题词项实际上是一系列词条组成的等价类如何定义等价类？数字(3/20/91vs.20/3/91)大小写问题词干还原，Porter工具形态分析:屈折vs.派生其他语言中词项归一化的问题比英语中形态更复杂芬兰语:单个动词可能有12,000个不同的形式differentforms重音符号、元音变音问题（umlauts，由于一个音被另一个音词化而导致的变化，尤其是元音的变化）8现代信息检索9跳表指针9现代信息检索10位置(信息)索引10在无位置信息索引中，每条倒排记录只是一个docID在位置信息索引中，每条倒排记录是一个docID加上一个位置信息表一个查询的例子:“to1be2or3not4to5be6”TO,993427:‹1:‹7,18,33,72,86,231›;2:‹1,17,74,222,255›;4:‹8,16,190,429,433›;5:‹363,367›;7:‹13,23,191›;...›BE,178239:‹1:‹17,25›;4:‹17,191,291,430,434›;5:‹14,19,101›;...›第4篇文档能够与查询匹配！现代信息检索11位置信息索引基于位置信息索引，能够处理短语查询(phrasequery)，也能处理邻近式查询(proximityquery)11现代信息检索12本讲内容词典的数据结构：访问效率和支持查找的方式容错式检索(Tolerantretrieval):如果查询词项和文档词项不能精确匹配时如何处理？通配查询：包含通配符*的查询拼写校正：查询中存在错误时的处理12现代信息检索提纲13①上一讲回顾②词典③通配查询④编辑距离⑤拼写校正⑥Soundex现代信息检索14倒排索引索引对每个词项t,保存所有包含t的文档列表14词典(dictionary)倒排记录表(postinglist)词典(dictionary)倒排记录表(postings)现代信息检索15词典词典是指存储词项词汇表的数据结构词项词汇表(Termvocabulary):指的是具体数据词典(Dictionary):指的是数据结构15现代信息检索16采用定长数组的词典结构对每个词项，需要存储:文档频率指向倒排记录表的指针...暂定每条词项的上述信息均采用定长的方式存储假定所有词项的信息采用数组存储16现代信息检索17采用定长数组的词典结构空间消耗:20字节4字节4字节17现代信息检索词项定位(即查词典)输入“信息”，如何在词典中快速找到这个词？很多词典应用中的基本问题。以下介绍支持快速查找的词典数据结构。18信息数据挖掘1819202122现代信息检索19用于词项定位的数据结构主要有两种数据结构:哈希表和树有些IR系统用哈希表，有些系统用树结构采用哈希表或树的准则:词项数目是否固定或者说词项数目是否持续增长？词项的相对访问频率如何？?词项的数目有多少？19现代信息检索哈希表20信息数据挖掘哈希函数，输入词项，输出正整数(通常是地址)f(信息)=18,f(数据)=19，f(挖掘)=191819202122现代信息检索21哈希表每个词项通过哈希函数映射成一个整数尽可能避免冲突查询处理时：对查询词项进行哈希，如果有冲突，则解决冲突，最后在定长数组中定位优点:在哈希表中的定位速度快于树中的定位速度查询时间是常数缺点：没办法处理词项的微小变形(resumevs.résumé)不支持前缀搜索(比如所有以automat开头的词项)如果词汇表不断增大，需要定期对所有词项重新哈希21现代信息检索22树树可以支持前缀查找最简单的树结构：二叉树搜索速度略低于哈希表方式：O(logM),其中M是词汇表大小，即所有词项的数目O(logM)仅仅对平衡树成立使二叉树重新保持平衡开销很大B-树能够减轻上述问题B-树定义：每个内部节点的子节点数目在[a,b]之间，其中a,b为合适的正整数,e.g.,[2,4].22现代信息检索23二叉树23现代信息检索24B-树24现代信息检索提纲25①上一讲回顾②词典③通配查询④编辑距离⑤拼写校正⑥Soundex现代信息检索26通配查询的处理mon*:找出所有包含以mon开头的词项的文档如果采用B-树词典结构，那么实现起来非常容易，只需要返回区间mon≤tmoo上的词项t*mon:找出所有包含以mon结尾的词项的文档将所有的词项倒转过来，然后基于它们建一棵附加的树返回区间nom≤tnon上的词项t也就说，通过上述数据结构，可能得到满足通配查询的一系列词项，然后返回任一词项的文档26现代信息检索27词项中间的*号处理例子:m*nchen在B-树中分别查找满足m*和*nchen的词项集合，然后求交集这种做法开销很大另外一种方法:轮排(permuterm)索引基本思想：将每个通配查询旋转，使*出现在末尾将每个每个旋转后的结果存放在词典中，即B-树中27现代信息检索28轮排索引对于词项hello:将hello$,ello$h,llo$he,lo$hel,和o$hell加入到B-树中，其中$是一个特殊符号即在词项前面再加一层索引28现代信息检索29轮排结果→词项的映射示意图29现代信息检索30轮排索引对于hello，已经存储了hello$,ello$h,llo$he,lo$hel,和o$hell查询对于X,查询X$对于X*,查询X*$对于*X,查询X$*对于*X*,查询X*对于X*Y,查询Y$X*例子:假定通配查询为hel*o,那么相当于要查询o$hel*轮排索引称为轮排树更恰当但是轮排索引已经使用非常普遍30现代信息检索31使用轮排索引的查找过程将查询进行旋转，将通配符旋转到右部同以往一样查找B-树问题：相对于通常的B-树，轮排树的空间要大4倍以上(经验值)31现代信息检索32k-gram索引比轮排索引空间开销要小枚举一个词项中所有连读的k个字符构成的k-gram。2-gram称为二元组(bigram)例子:fromAprilisthecruelestmonthwegetthebigrams:$aapprriill$$iiss$$tthhee$$ccrruueelleesstt$$mmoonnth$同前面一样，$是一个特殊字符构建一个倒排索引，此时词典部分是所有的2-gram，倒排记录表部分是包含某个2-gram的所有词项相当于对词项再构建一个倒排索引(二级索引)32现代信息检索333-gram(trigram)索引的例子33现代信息检索34k-gram(bigram,trigram,...)索引需要注意的是，这里有两个倒排索引词典-文档的倒排索引基于词项返回文档而k-gram索引用于查找词项，基于查询包含的k-gram查找词项34现代信息检索35利用2-gram索引处理通配符查询查询mon*可以先执行布尔查询:$mANDmoANDon该布尔查询会返回所有以前缀mon开始的词项......当然也可能返回许多伪正例，比如MOON.因此，必须要做后续的过滤处理余下的词项将在词项-文档倒排索引中查找文档k-gram索引vs.轮排索引k-gram索引的空间消耗小轮排索引不需要进行后过滤35现代信息检索36课堂练习Google对通配符查询的支持极其有限比如：在Google中查询[gen*universit*]意图：想查UniversityofGeneva,但是不知道如何拼写，特别是法语中的拼写按照Google自己的说法,2010-04-29:“*操作符只能作为一个整体单词使用，而不能作为单词的一部分使用”但是这点并不完全对，尝试一下[pythag*]和[m*nchen]问题:为什么Google对通配查询并不充分支持？36现代信息检索37原因问题1:一条通配符查询往往相当于执行非常多的布尔查询对于[gen*universit*]:genevauniversityORgenevauniversitéORgenèveuniversityORgenèveuniversitéORgeneraluniversitiesOR...开销非常大问题2:用户不愿意敲击更多的键盘如果允许[pyth*theo*]代替[pythagoras’theorem]的话，用户会倾向于使用前者这样会大大加重搜索引擎的负担GoogleSuggest是一种减轻用户输入负担的好方法37现代信息检索提纲38①上一讲回顾②词典③通配查询④编辑距离⑤拼写校正⑥Soundex现代信息检索39拼写校正两个主要用途纠正待索引文档纠正用户的查询两种拼写校正的方法词独立(Isolatedword)法只检查每个单词本身的拼写错误如果某个单词拼写错误后变成另外一个单词，则无法查出,e.g.,anasteroidthatfellformthesky上下文敏感(Context-sensitive)法纠错时要考虑周围的单词能纠正上例中的错误form/from39现代信息检索40关于文档校正本课当中我们不关心文档的拼写校正问题(e.g.,MSWord)在IR领域,我们主要对OCR处理后的文档进行拼写校正处理.(OCR=opticalcharacterrecognition，光学字符识别)IR领域的一般做法是：不改变文档40现代信息检索41查询校正第一种方法:词独立(isolatedword)法假设1:对需要纠错的词存在一系列“正确单词形式”假设2:需要提供存在错误拼写的单词和正确单词之间的距离计算方式简单的拼写校正算法:返回与错误单词具有最小距离的”正确”单词例子:informaton→information可以将词汇表中所有的单词都作为候选的“正确”单词这种方式为什么有问题？41现代信息检索42使用词汇表的几种其他方式采用标准词典(韦伯词典,牛津词典等等)采用领域词典(面向特定领域的IR系统)采用