查询pr查询

信息检索与Web搜索第4讲词典及容错式检索Dictionaryandtolerantretrieval授课人:高曙明*改编自"现代信息检索"网上公开课件(http://ir.
ict.
ac.
cn/~wangbin)词典数据结构用于存储词项词汇表的数据结构采用定长数组的词典结构空间消耗:20字节4字节4字节快速词项定位给定查询词项"信息",如何在词典中快速找到这个词项需要支持快速查找的词典数据结构哈希表方式搜索树方式选择何种方式需要考虑以下因素:词项数目是否固定或者说词项数目是否持续增长词项的相对访问频率如何词项的数目有多少基于哈希表的词典索引方法:将每个词项通过哈希函数映射成一个整数查询处理:对查询词项进行哈希,如果有冲突,则解决冲突,最后在定长数组中定位优点:在哈希表中的定位速度快于树中的定位速度查询时间是常数缺点:不支持前缀搜索(比如所有以automat开头的词项)如果词汇表不断增大,需要定期对所有词项重新哈希基于搜索树的词典索引方法:采用搜索树作为词典的索引,一般采用平衡二叉树优点:可以支持前缀查找缺点:搜索速度略低于哈希表方式:O(logM),其中M是词汇数使二叉树重新保持平衡开销很大改进:采用B-树减轻上述问题B-树定义:每个内部节点的子节点数目在[a,b]之间,其中a,b为合适的正整数,e.
g.
,[2,4].
二叉搜索树示例平衡性,字符集有预定的排序方式B-树示例子节点数目在[2,4]区间通配查询通配查询:指词项中带有通配符"*"的查询分类:尾通配符查询mon*:找出所有包含以mon开头的词项的文档首通配符查询*mon:找出所有包含以mon结尾的词项的文档中间通配符查询m*nchen:找出所有包含以m开头并以nchen结尾的词项的文档作用:满足用户的以下需求用户需要进行拼写不确定的查询用户需要查找某个查询词项的所有变形通配查询的处理处理方法:mon*:采用B-树词典结构,搜索区间mon≤tg.
,anasteroidthatfellformthesky上下文敏感(Context-sensitive)法纠错时考虑周围的单词能纠正上例中的错误form/from词独立纠错法基本思想:对于一个需要纠错的查询词,在其可能的正确拼写中,选择距离最近中的最常见的一个可能正确拼写的来源:文档集上的词项词汇表计算两个词的邻近度(相似度)最常见的选择:词频(文档集中或用户查询记录中)核心问题:词之间的邻近度计算两种方法:基于编辑距离的邻近度计算基于k-gram重合度的邻近度计算基于编辑距离的邻近度计算编辑距离(Editdistance或者Levenshteindistance):两个字符串s1和s2之间的编辑距离是指从s1转换成s2所需要的最少的基本操作数目基本操作:插入(insert)、删除(delete)、替换(replace)例子:cat-cart:1;cat-cut:1;cat-act:2计算方法:采用动态规划算法进行计算Levenshtein距离:实例fast中的f、s、t分别用c、t、s替换,即可得到cats,所以代价是3,即距离是3Levenshtein距离:算法Levenshtein距离:算法(i-1,j-1)(i-1,j)(i,j-1)(i,j)左邻居Levenshtein矩阵单元的组成从左上角邻居到来的开销(copy或replace)从上方邻居到来的代价(delete)从左方邻居到来的代价(insert)上述三者之中最低的代价Levenshtein距离:例子带权重的编辑距离特点:对不同字符进行的操作赋予不同的权重必要性分析:将字符m替换成n与将字符m替换成q应该有区别,前者的权重应该更小目的:通过考虑出错操作发生概率的因素,提高距离计算准确性利用编辑距离进行拼写校正给定查询词,穷举词汇表中和该查询的编辑距离(或带权重的编辑聚类)低于某个预定值的所有词项将结果推荐给用户代价很大,实际当中往往通过启发式策略提高效率限制在与查询词具有相同首字母的词项保证两者之间具有较长公共子串基于k-gram重合度的邻近度计算k-gram重合度:指∣A∩B∣/∣A∪B∣,其中A、B分别是两个词的k-gram集合例子:bord与boardroom之间的2-gram重合度A=5,B=10A∩B=3,A∪B=10+5-3=12重合度=3/12基于K-gram索引的拼写校正查询词bord的2-gram索引片段主要步骤确定查询词项的k-gram集合,A利用k-gram索引返回A相关倒排记录表中的词项对去重后的词,计算其与查询词的k-gram重合度根据给定阈值,确定匹配上的正确词项返回上下文敏感的拼写校正对于flewformHeathrow,如何纠错form一种方法:基于命中数(hit-based)的拼写校正对于每个查询词项返回相近的"正确"词项组合所有可能,分别进行查询,取具有最高命中数者搜索"fledformHeathrow"搜索"flewforeHeathrow"搜索"flewfromHeathrow"会有最高的结果命中数问题:假定flew有7个可能的候选词,form有20个,Heathrow有3个,那么需要穷举出多少个查询更高效的方法:基于查询库确定合理的组合基于发音的校正(Soundex)目标:寻找发音相似的单词,对查询进行扩展,提高检索效果比如,对查询词chebyshev,将其扩展到tchebyscheff算法步骤:将词典中每个词项转换成一个4字符缩减形式(即进行Soundex编码),构建词典的soundex索引对查询词项做同样的处理基于soundex索引搜索音似词Soundex编码算法保留词项的首字母将后续所有的A、E、I、O、U、H、W及Y等字母转换为0.
按照如下方式将字母转换成数字:B,F,P,V1C,G,J,K,Q,S,X,Z2D,T3;L4;M,N5;R6将连续出现的两个同一字符转换为一个字符直至再没有这种现象出现.
在结果字符串中剔除0,并在结果字符串尾部补足0,然后返回前四个字符,该字符由1个字母加上3个数字组成.
例子:HERMAN的Soundex编码保留HERMAN→0RM0N0RM0N→0650506505→655返回H655注意:HERMANN会产生同样的编码Soundex的应用情况在IR中并不非常普遍适用于"高召回率"任务(e.
g.
,国际刑警组织Interpol在全球范围内追查罪犯)ZobelandDart(1996)提出了一个更好的发音匹配方法参考资料《信息检索导论》第3章、MG4.
2高效拼写校正方法:K.
Kukich.
Techniquesforautomaticallycorrectingwordsintext.
ACMComputingSurveys24(4),Dec1992.
J.
ZobelandP.
Dart.
Findingapproximatematchesinlargelexicons.
Software-practiceandexperience25(3),March1995.
http://citeseer.
ist.
psu.
edu/zobel95finding.
htmlMikaelTillenius:EfficientGenerationandRankingofSpellingErrorCorrections.
Master'sthesisatSweden'sRoyalInstituteofTechnology.
http://citeseer.
ist.
psu.
edu/179155.
html参考资料PeterNorvig:Howtowriteaspellingcorrectorhttp://norvig.
com/spell-correct.
htmlhttp://ifnlp.
org/irSoundex演示Levenshtein距离的演示PeterNorvig的拼写校正工具课后作业见课程网页:http://www.
cad.
zju.
edu.
cn/home/smgao/IR