查询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

零途云:香港站群云服务器16IP220元/月,云服务器低至39元/月

零途云(Lingtuyun.com)新上了香港站群云服务器 – CN2精品线路,香港多ip站群云服务器16IP/5M带宽,4H4G仅220元/月,还有美国200g高防云服务器低至39元/月起。零途云是一家香港公司,主要产品香港cn2 gia线路、美国Cera线路云主机,美国CERA高防服务器,日本CN2直连服务器;同时提供香港多ip站群云服务器。即日起,购买香港/美国/日本云服务器享受9折优惠,新...

DMIT(8.72美元)日本国际线路KVM月付8折起,年付5折

DMIT.io是成立于2018年的一家国外主机商,提供VPS主机和独立服务器租用,数据中心包括中国香港、美国洛杉矶和日本等,其中日本VPS是新上的节点,基于KVM架构,国际线路,1Gbps带宽,同时提供月付循环8折优惠码,或者年付一次性5折优惠码,优惠后最低每月8.72美元或者首年65.4美元起,支持使用PayPal或者支付宝等付款方式。下面列出部分日本VPS主机配置信息,价格以月付为例。CPU:...

PacificRack 下架旧款方案 续费涨价 谨慎自动续费

前几天看到网友反馈到PacificRack商家关于处理问题的工单速度慢,于是也有后台提交个工单问问,没有得到答复导致工单自动停止,不清楚商家最近在调整什么。而且看到有网友反馈到,PacificRack 商家的之前年付低价套餐全部下架,而且如果到期续费的话账单中的产品价格会涨价不少。所以,如果我们有需要续费产品的话,谨慎选择。1、特价产品下架我们看到他们的所有原来发布的特价方案均已下架。如果我们已有...

pr查询为你推荐
mediawikimediawiki 怎么开启 visual editer 可视化编辑器access数据库修复Access数据库恢复,有些表被损坏或有些表的部分记录被损坏,求解啊企业电子邮局企业邮箱怎么使用?filezilla_serverFileZilla无法连接服务器怎么解决银花珠树晓来看关于下雪景的诗句2828商机网千元能办厂?28商机网是真的吗?加多宝与王老吉加多宝王老吉有什么区别吗?电子商务世界电子商务最先起源于那个国家,什么时间即时通请问有没有人知道即时通是什么?怎样先可以开??三五互联股票三五互联是干什么的?
韩国vps俄罗斯美女 万网域名管理 国外bt paypal认证 美国仿牌空间 52测评网 数字域名 申请个人网站 什么是刀片服务器 息壤代理 metalink 东莞服务器 申请免费空间和域名 超级服务器 服务器论坛 lamp兄弟连 阿里云个人邮箱 中国电信宽带测速 hdroad winserver2008 更多