查询pr查询

pr查询  时间:2021-04-18  阅读:()
信息检索与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

Spinservers美国圣何塞服务器$111/月流量10TB

Spinservers是Majestic Hosting Solutions,LLC旗下站点,主营美国独立服务器租用和Hybrid Dedicated等,数据中心位于美国德克萨斯州达拉斯和加利福尼亚圣何塞机房。TheServerStore.com,自 1994 年以来,它是一家成熟的企业 IT 设备供应商,专门从事二手服务器和工作站业务,在德克萨斯州拥有 40,000 平方英尺的仓库,库存中始终有...

LOCVPS新上日本软银线路VPS,原生IP,8折优惠促销

LOCVPS在农历新年之后新上架了日本大阪机房软银线路VPS主机,基于KVM架构,配备原生IP,适用全场8折优惠码,最低2GB内存套餐优惠后每月仅76元起。LOCVPS是一家成立于2012年的国人VPS服务商,提供中国香港、韩国、美国、日本、新加坡、德国、荷兰、俄罗斯等地区VPS服务器,基于KVM或XEN架构(推荐选择KVM),线路方面均选择国内直连或优化方案,访问延迟低,适合建站或远程办公使用。...

轻云互联22元/月,美国硅谷、圣何塞CN2GIA云服务器,香港沙田cn2建站vps仅25元/月

轻云互联怎么样?轻云互联,广州轻云网络科技有限公司旗下品牌,2018年5月成立以来,轻云互联以性价比的价格一直为提供个人,中大小型企业/团队云上解决方案。本次轻云互联送上的是美国圣何塞cn2 vps(免费50G集群防御)及香港沙田cn2 vps(免费10G集群防御)促销活动,促销产品均为cn2直连中国大陆线路、采用kvm虚拟技术架构及静态内存。目前,轻云互联推出美国硅谷、圣何塞CN2GIA云服务器...

pr查询为你推荐
操作httpapple.com.cn苹果官网怎么序列号查询激活时间filezillaserver如何使用filezilla serverdell服务器bios设置dell怎样进入bios设置界面波音737起飞爆胎飞机会爆胎的吗?flashftp下载《蔓蔓青萝(全)》.TXT_微盘下载flashftp下载禁室迷情夜下载地址给我 谢谢要能下载出来的重庆网站制作重庆网站制作哪家好,重庆做网站制作的公司有谁比较了解的,应该去哪里做好些?本公司www阅读http
如何注册网站域名 企业主机 godaddy优惠码 nerd 174.127.195.202 服务器日志分析 空间合租 中国电信宽带测速网 江苏双线服务器 国外视频网站有哪些 新睿云 空间登录首页 东莞idc 重庆电信服务器托管 美国凤凰城 主机管理系统 中国域名 accountsuspended web服务器 asp介绍 更多