信息检索导论_王斌译_课后习题答案

【实例简介】
现代信息检索导论_王斌译_课后习题答案
习题1-7[]请推荐如下查询的处理次序。 d. (tangerine OR trees)AND(marmalade Or skies)AND(kaleidoscope OR eyes 其中,每个词项对应的倒排记录表的长度分别如下: 词项 倒排记录表长度 213312 kaleidoscope 87009 marmalade 107913 271658 tangerine 46653 trees 316812 解答 由于 (tangerine OR trees)+46653+316812= 363465 (marmalade OR skies))107913+271658=379571 (kaleidoscope OR eyes)-87009+213312=30321 所以推荐处理次序为 (kaleidoscope oR eyes)AND(tangerine OR trees) aNd(marmalade oR skies) 习题1-8[]对于查询 e. friends ANd romans ANd(NOT countrymen) 如何利用 countrymen的文档频率来估计最佳的查询处理次序?特别地,提出一种在确定查询顺序时对逻 辑非进行处理的方法。 解答:爷 friends、 romans和 countrymen的文档频率分别为x、y、z。如果z极高,则将Nz作为NOT countrymen的长度估计值,然后按照x、y、Nz从小到大合并。如果z极低,则按照x、y、z从小到大合 并。 习题1-9[*]对于逻辑与构成的查询,按照倒排记录表从小到大的处理次序是不是一定是最优的?如果 是,请给出解释;如果不是,请给出反例。 解答:不一定。比如三个长度分别为x,yz的倒排记录表进行合并,其中xy>z,如果x和y的交集为空集 那么有可能先合并x、y效率更高。 习题1-10[*]对于查询xORy,按照图16的方式,给出一个合并算法。 解答 1 answer<-() 2 while p1!=NL and p2l=NIL 3 do if docID(p1)=docID(p2) 4 then ADD(answer, docID(p1)) p p2<-next(p2) 7 else if dociD(p1)<docID(p2) 8 then ADD(answer, docID(p1) p1<-next(p1) 10 else ADD(answer, docID(p2) p2<-next(p2) 12ip1!=NL//x还有剩余 13 then while p1! =NiL do Add(answer, docID(p1)) 14 else while p2!=NIL do add(answer, docID(p2)) 15 return (answer) 习题1-11[如何处理查询 AND NOT y?为什么原始的处理方法非常耗时?给出一个针对该查询的高效 合并算法。 解答:由于NOTy几乎要遍历所有倒排表,因此如果采用列举倒排表的方式非常耗时。可以采用两个 有序集合求减的方式处理 X AND NOT y。算法如下 Meger(p1, p2) answer 2 while p1!=NIL and p2 =NIL 3 do if docID(p1)=docID(p2) 4 then p1gnext(p1) p2区next(p2) 6 else if docid(p1)docID (p2) 7 then ADD(answer, dociD(p1)) p1]next(p1) 9 else ADD(answer docID(p2)) p区]next(p2) 11ifp1!=NL//X还有剩余 12 then while p1!=NiL do add(answer, docID(p1)) 13 return(answer) 习题1-12[利用 Westlaw系统的语法构造一个查询,通过它可以找到 professor、 teacher或 lecturer 中的任意一个词,并且该词和动词 explain在一个句子中出现,其中 explain以某种形式出现。 解答: professor teacher lecturer /s explain! 习题1-13[在一些商用搜索引擎上试用布尔查询,比如,选择一个词(如 burglar),然后捋如 下查询提交给搜索引擎 (i)burglar ;(ii) burglar AND burglar ;(iii)burglar OR burglar 对照搜索引擎返回的总数和排名靠前的文档,这些结果是否满足布尔逻辑的意义?对于大多数 搜索引擎来说,它们往往不满足。你明白这是为什么吗?如果采用其他词语,结论又如何?比 如以下查询 (1)knight;()conquer;(i1i knight OR conquero 第二章词汇表和倒排记录表 习题2-1[请判断如下说法是否正确。 a.在布尔检索系统中,进行词干还原从不降低正确率。 b.在布尔检秦系统中,进行词干还原从不降低召回率。 C.词干还原会增加词项词典的大小。 d.词干还原应该在构建索引时调用,而不应在查询处理时调用。 解答:a错b对c错d错 习题27[”]者虑利用如下带有跳表指针的倒排记录表 和一个中间结果表(如下所示,不存在跳表指针)进行合并操作。 358995979910010° 采用图210所示的倒排记录表合并算法,请问 a.跳表指针实际跳转的次数是多少(也就是说,指针p1的下一步将跳到skip(P1))? 次,24->75 b.当两个表进行合并时,倒排记录之间的比较次数是多少?【如下答案不一定正确,有人利用程 序计算需要21次,需要回到算法,本小题不扣分,下面不考虑重新比较同意对数字】 解答:18次:<3,3>,<5,5>,<9,89 <15,89>,<24,89,75,89,92,89,81,89,84,89,89,89,92,95,4115,953,%6,95>,96,97>, 97,97,100,99,<100,100>115,101> C.如果不使用跳表指针,那么倒排记录之间的比较次数是多少? 解答:19次 3,3>,5,5>,9,89,15,89,24,89,39,89,60,89,68,89,75,89,81,89,84,89,<89,89 92,95,<96,9,9,97,<9797,100,99,<100,100,<115,101> 习题29[]下面给出的是一个位匱索引的一部分,格式为:词项:文档1:〈位置1,位置2,…,;文档 2:〈位置1,位匱2,…}。 angels:z:(36,174,252,651);4:(12,22,102,432;7:(17); fools:z:(1,17,74,222);4:.(⑧8,78,108,458);7:③3,13,23,193); fear:2:(87,704,722,901);4:(13,43,113,433);7:18,328528); in:2:③3,37,76,444,851);4:(10,20,110,470,500);7:{5,15,25,195; rush:2:2,66,194,321,702);4:⑨9,69,149,429,569;7:(4,14,404》; to:2:(47,86,234,999;4:(14,24,774,944);7:(199,319,599,709; tread:2:〈57,94,333;34:(15,35,155);7:(20,320); where:z:(67,124,393,1001};4:〈11,41,101,421,431);7:〈16,36,736); 那么哪些文档和以下的查询匹配?其中引号内的每个表达式都是一个短语查询 a.“ fools rush in 解答:文档2、4、7 b.“ fools rush in”AND“ angels fear to tread”。 解答:文档4 第三章词典及容错式检索 习题35再次考虑321书中的查询 fi mo*er,如果采用2gam索引的话,那么对应该查询应该会 产生什么样的布尔查询?你能否举一个词项的例子,使该词匹配3.2.1节的轮排索引查询,但是 并不满足刚才产生的布尔查询? 解答:2-gram索引下的布尔查询: Sf ANd fi AND mo AND er ANdrS 词项 Filibuster(海盗)满足3.2.1书的轮排索引查询,但是并不满足上述布尔查询 习题3-7如果|si|表示字符串s的长度,请证明s1和s2的编辑距离不可能超过max{l1,|2} 证明不失一般性,假设ls1=ls2|,将s1转换为s2的一种做法为:将s1中的每个字符依次替换为 s2中的前|s1个字符,然后添加s2的后|2s1个字符,上述操作的总次数为|s2|=max{s1 2},根据编辑距离的定义,其应该小于s2=max{|s1,|s2} 习题3-8计算 paris和 alice之间的编辑距离,给出类似于图3-5中的算法结果,其中的5×5矩阵 包含每个前缀子串之间的计算结果。 解答: SOLU TION 心 4|4 45 56 22235855 34 56 42 3|3 55 4 5 43 42 3|3 44 44 4|5 6454 53 44 习题3-11考虑四词查询 catched in the rye,假定根据独立的词项拼写校正方法,每个词都有5个 57 可选的正确拼写形式。那么,如果不对空间进行缩减的话,需要考忠多少可能的短语拼写形式 (提示:同时要考虑原始查询本身,也就是每个词项有6种变化可能)? 解答:6*66*6=1296 习题3-14找出两个拼写不一致但 soundex编码一致的专有名词。 解答:№ary,Mira( soundex相同),本题答案不唯一,可能有其他答案,但是 soundex编码必须 致。 第四章索引构建 习题41如果需要Tlog27次比较(T是词项|D-文档D对的数目),每次比较都有两次磁盘寻道 过程。假定使用磁盘而不是内存进行存储,并且不采用优化的排序算法(也就是说不使用前面 提到的外部排序算法),那么对于 Reuters- RCV1构建索引需要多长时间?计算时假定采用表41 中的系统参数。 解答 对于 Reuters-RCy1,T=103 因此排序时间(文档分析时间可以忽略不计)为:2*(10og210)5-103s=265754245=7382 h=308 day 习题4-3对于n=15个数据片,r=10个分区文件,j=3个词项分区,假定使用的集 群的机器的参数如表4-1所示,那么在 MapReduce构架下对 Reuters-RCV1语料进行分布式索 引需要多长时间? 【给助教:教材不同印刷版本表4-2不一样,不同同学用的不同版本,还有本题过程具 有争议。暂不扣分】 裂片 分配 丰控节点 分配 倒记录表 a- f g-pq-z果 析韻 南引器 a-fg-p 分析菪 “gP 篱引器 公析罪 afgP2(司器92 Map阶段 分区文件 ue阶段 解答【整个计算过程是近似的,要了解过程】 (一)、MAP阶段【读入语料(已经不带MML标记信息了,参考表56),词条化,写入分区文件】: (1)读入语料 基于表42, Reuters rcv1共有8*105篇文档,每篇文档有200词案,每个词条(考虑标点和空格)占 6B,因此整个语料库的大小为84105*2006=96*103B(近似1GB,注表42对应于表5-1第3行的数据,而 那里的数据已经经过去数字处理,因此实际的原始文档集大小应该略高于0.96G,这里近似计算,但是 不要认为没有处理就得到表51第3行的结果) 捋整个语料库分成15份,则每份大小为96*108/15B 每一份读入机器的时间为:9.6*108/15*2*108=1.285 (2)词条化:每一份语料在机器上进行词条化处理,得到8105200=1.610个词项D文档D对(参考 表42和图46,注意此时重复的词项|D文档1D对还没有处理),共占1.6*108-8=1.28*109个字节,词条化 的时间暂时忽略不计【从题目无法得到词粲化这一部分时间,从表5-1看词条化主要是做了去数字和大小 写转换,当然也感觉这一部分的处理比较简单,可以忽略】。 (3)写入分区文件:每一份语料得到的词项D文档ID( Key-Value)存储到分区所花的时间为 (1.28*109/15)2*108=1.715 (4)MAP阶段时间 由于分成1份,但只有10台机器进行MAP操作,所以上述MAP操作需要两步,因此,整个MAP过程所 需时间为(128+1.71)*2=6.05 (二)、 REDUCE阶段【读入分区文件,排序,写入倒排索引】 (1)读入分区文件【读入过程中已经实现所有Key-vaue对中的vaue按Key聚合,即变成Key, ist(v1,V2…)。聚合过程在内存中实现,速度很快,该时间不计。另外,网络传输时间这里也不计算】 根据表42,所有倒排记录的数目为1.6*108,因此3台索引器上每台所分配的倒排记录数目为 .6*108/3,而每粲记录由4字节词项1D和4字节文档D组成,因此每台索引器上需要读入的倒排记录表数据 为1.28*109/3字节。 于是,每台索引器读数据的时间为1.28*109/3*2*10%=8.55 (2)排序 每台索引器排序所花的时间为16108/3+og2(1.6108/3)*108=13.7s (3)写入倒排索引文件【此时倒排文件已经实现文档D的去重,假定只存储词项|D和文档D列表,并 不存储其他信息(如词项的DF及在每篇文档中的TF还有指针等等]: 需要写入磁盘的索引大小为(据表42,词项总数为4105个)4105/34+108/3*4=4/3*10字节 索引写入磁盘的时间为:4/3*108*2*108=2.75 (4) REDUCE阶段时间为:8.5+13.7+27=249 (三)因此,整个分布式索引的时间约为60+85+13.7+27=30.9s 第五章索引压缩 习题5-2估计 Reuters- RCV1文档集词典在两种不同按块存储压缩方法下的空间大小。其中,第一 种方法中k=8,第二种方法中k=16 解答 每8个词项会节省7*3个字节,同时增加8个字节,于是每8个词项节省7*3-8=13字节,所有词项 共节省13*4000008=650K,因此,此时索引大小为76MB-065MB=695MB 每16个词项会节省15*3个字节,同时增加16个字节,于是每16个词项节省15*3-16=29字节,所 有词项共节省29*400000%16=725K,因此,此时索引大小为76MB-0725MB=6.875MB 习题5-6考虑倒排记录表(4,10,11,12,15,62,63,265,268,270,400)及其对应的间 距表(4,6,1,1,3,47,1,202,3,2,130)。假定倒排记录表的长度和倒排记录表分开独立 存储,这样系统能够知道倒排记录表什么时候结束。采用可变字节码 ()能够使用1字节来编码的最大间距是多少? i)能够使用2字节来编码的最大间距是多少? (ⅲi)采用可变字节编码时,上述倒排记录表总共需要多少空间(只计算对这些数字序列进行编 码的空间消耗)? 解答 (i)27-1=127(答128也算对,因为不存在0间距,0即可表示间距1,… (i)214-1=16383(答16384也算对 (i)+1+1+1+1+1+1+2+1+1+2=13 习题5-8[]对于下列采用y编码的间距编码结果,请还原原始的间距序列及倒排记录表。 1110001110101011111101101111011 解答 1110001;11010;101;11111011011;11011 1001;110;11;111011;111 9;6;3;32+16+8+2+1=59;7 9;15;18;77;84 第六章文档评分、词项权重计算及向量空间模型 习题6-10考虑图6-9中的3篇文档DC1、Doc2、Doc3中几个词项的t情况,采用图6-8中的idf值来 计算所有词项car、auto、 insurance及best的t-idf值。 Doc 1 Doc2 Dock can 24 auto 0 Insurance 33 best 14 17 图6-9习题6-10中所使用的值 解答 idfcar=1.65, idfauto = 2.08, idfinsurance =1.62. idfcest=1.5 于是,各词项在各文档中的id结果如下表 Doc2 Doc 27*1.65=44.55 41.65=6.6 2441.65=39.6 auto 3*2.08=6.24 33*2.08=68.64 Insurance 33-1.62=53.46 29*1.62-46.98 best 14*1.5=21 17*1.5=25.5 习题6-12公式(67)中对数的底对公式(69)会有什么影响?对于给定查询来说,对数的底是 否会对文档的排序造成影响? 解答:没有影响。 假定df采用与(6-7)不同的底x计算,根据对数换底公式有。 idf(x)=log(N/df)=log(N/df t)/log=idft/log 由于idt(x)和dt之间只相差一个常数因子1/logx,在公式(69)的计算中该常数可以作为公因 子提出,因此文档的排序不会改变。 习题6-19计算查询 digital cameras及文档 digital cameras and video cameras的向量空间相似 度并将结果填入表61的空列中。假定N=10000000,对查询及文档中的词项权重(wf对应的 列)采用对数方法计算,查询的权重计算采用df,而文档归一化采用余弦相似度计算。将and 看成是停用词。请在tf列中给出词项的出现频率,并计算出最后的相似度结果。 表6-1习题6-19中的余弦相似度计算 查询 文档 df wf-idf tf wf 归一化的wf digital 10000 vIdeo 100000 cameras 50000 解答:【本质上这里没有考虑查询向量的归一化,即没有考虑查询向量的大小,严格上不是余弦相 似度】 查询 文档 qi=wf-idf tf wf d=归一化的wf digitalis 100003 10.520 video 1000002 0.520 3.112 cameras 500002.3012.301 21.3010.67 习题6-23考虑习题6-10中4个词项和3篇文档中的t和idf值,采用如下权重计算机制来计算获得得 分最高的两篇文档:(i)natc;(i) ntc. atc 解答:()根据题意文档采用nn,查询采用atc,然后计算内积,于是有: 查询q 文档D 词项 if|rif归化t 得分 tf idf tf-idf idr car 1651.65 0.560 27 1|27 auto 0.5 2081.040.353 3 23.310 Insurance 1.62|1.6 0.550 best 1 15|1.5 0. 14 查询 文档Doc2 词项 tf idf tf-idf 归一化tf 得分 tf idf car 1.651.65 0.560 4 auto 0.5 2.081.04 0.353 33 32.037 Insurance 1.621.62 0.550 33 33 1.5 0.509 0 杳询q 文档Doc3 词项 idf‖t-idf 归一化t 得分 tt idf I tf-idf idf 1.651.65 0.560 24 124 auto 0.5 2.08 1.04 0.353 0 38.046 insurance 1.621.62 0.550 29 29 best 1.51.5 0.509 17 17 于是,在nn,atc下, Score(q,Doc3)> Score(q,Doc2)>5core(q,Doc1) (i)根据题意文档采用ntc,查询采用atc,然后计算内积,于是有: 查询q 文档Doc1 词项 tf df tf-idf 归一化 归 得分 tfdr化 U-idn car 1.651.650.560 27 1654.550.897 auto 0.5 201040333 2.086.240.12 0.76 insurance 1621.620.550 0 :620 0 【实例截图】
【核心代码】