中国科学院大学现代信息检索课后习题答案.docx 16页

'《信息检索导论》课后练习答案王斌最后更新日期2013/9/28第一章布尔检索习题1-1[*]　画出下列文档集所对应的倒排索引（参考图1-3中的例子）。文档1newhomesalestopforecasts文档2homesalesriseinjuly文档3increaseinhomesalesinjuly文档4julynewhomesalesrise解答：forecasts------->1home------->1à2à3à4in------->2à3increase------->3july------->2à3à4new------->1à4rise------->2à4sales------->1à2à3à4top------->1习题1-2[*]　考虑如下几篇文档：文档1breakthroughdrugforschizophrenia文档2newschizophreniadrug文档3newapproachfortreatmentofschizophrenia文档4newhopesforschizophreniapatientsa.画出文档集对应的词项—文档矩阵；解答：文档1文档2文档3文档4approach0010breakthrough1000drug1100for1011hopes0001new0111 of0010patients0001schizophrenia1111treatment0010b.画出该文档集的倒排索引（参考图1-3中的例子）。解答：参考a。习题1-3[*]　对于习题1-2中的文档集，如果给定如下查询，那么返回的结果是什么？a.schizophreniaANDdrug解答：{文档1，文档2}b.forANDNOT(drugORapproach）解答：{文档4}习题1-4[*]对于如下查询，能否仍然在O(x+y)次内完成？其中x和y分别是Brutus和Caesar所对应的倒排记录表长度。如果不能的话，那么我们能达到的时间复杂度是多少？a.BrutusANDNOTCaesarb.BrutusORNOTCaesar解答：a.可以在O(x+y)次内完成。通过集合的减操作即可。具体做法参考习题1-11。b.不能。不可以在O(x+y)次内完成。因为NOTCaesar的倒排记录表需要提取其他所有词项对应的倒排记录表。所以需要遍历几乎全体倒排记录表，于是时间复杂度即为所有倒排记录表的长度的和N，即O(N)或者说O(x+N-y)。习题1-5[*]将倒排记录表合并算法推广到任意布尔查询表达式，其时间复杂度是多少？比如，对于查询c.(BrutusORCaesar)ANDNOT(AntonyORCleopatra)我们能在线性时间内完成合并吗？这里的线性是针对什么来说的？我们还能对此加以改进吗？解答：时间复杂度为O(qN)，其中q为表达式中词项的个数，N为所有倒排记录表长度之和。也就是说可以在词项个数q及所有倒排记录表长度N的线性时间内完成合并。由于任意布尔表达式处理算法复杂度的上界为O(N)，所以上述复杂度无法进一步改进。习题1-6[**]　假定我们使用分配律来改写有关AND和OR的查询表达式。12a.通过分配律将习题1-5中的查询写成析取范式；b.改写之后的查询的处理过程比原始查询处理过程的效率高还是低？c.上述结果对任何查询通用还是依赖于文档集的内容和词本身？解答：a.析取范式为：(BrutusAndNotAnthonyAndNotCleopatra)OR(CaesarANDNOTAnthonyANDNOTCleopatra)b.这里的析取范式处理比前面的合取范式更有效。这是因为这里先进行AND操作(括号内)，得到的倒排记录表都不大，再进行OR操作效率就不会很低。而前面需要先进行OR操作，得到的中间倒排记录表会更大一些。c.上述结果不一定对，比如两个罕见词A和B构成的查询(AORB)ANDNOT(HONGORKONG)，假设HONGKONG一起出现很频繁。此时合取方式可能处理起来更高效。如果在析取范式中仅有词项的非操作时，b中结果不对。习题1-7[*]　请推荐如下查询的处理次序。d.(tangerineORtrees)AND(marmaladeORskies)AND(kaleidoscopeOReyes） 其中，每个词项对应的倒排记录表的长度分别如下：词项倒排记录表长度eyes213312kaleidoscope87009marmalade107913skies271658tangerine46653trees316812解答：由于：(tangerineORtrees)è46653+316812=363465(marmaladeORskies)è107913+271658=379571(kaleidoscopeOReyes）è87009+213312=30321所以推荐处理次序为：(kaleidoscopeOReyes）AND(tangerineORtrees)AND(marmaladeORskies)习题1-8[*]对于查询a.friendsANDromansAND(NOTcountrymen)如何利用countrymen的文档频率来估计最佳的查询处理次序？特别地，提出一种在确定查询顺序时对逻辑非进行处理的方法。解答：令friends、romans和countrymen的文档频率分别为x、y、z。如果z极高，则将N-z作为NOTcountrymen的长度估计值，然后按照x、y、N-z从小到大合并。如果z极低，则按照x、y、z从小到大合并。习题1-9[**]　对于逻辑与构成的查询，按照倒排记录表从小到大的处理次序是不是一定是最优的？如果是，请给出解释；如果不是，请给出反例。解答：不一定。比如三个长度分别为x,y,z的倒排记录表进行合并，其中x>y>z，如果x和y的交集为空集，那么有可能先合并x、y效率更高。习题1-10[**]　对于查询xORy，按照图1-6的方式，给出一个合并算法。解答：1answer<-()2whilep1!=NILandp2!=NIL3doifdocID(p1)=docID(p2)4thenADD(answer,docID(p1))5p1<-next(p1)6p2<-next(p2)7elseifdocID(p1)75b.当两个表进行合并时，倒排记录之间的比较次数是多少？【如下答案不一定正确，有人利用程序计算需要21次，需要回到算法，本小题不扣分，下面不考虑重新比较同意对数字】解答：18次：<3,3>,<5,5>,<9,89>,<15,89>,<24,89>,<75,89>,<92,89>,<81,89>,<84,89>,<89,89>,<92,95>,<115,95>,<96,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,95>,<96,97>,<97,97>,<100,99>,<100,100>,<115,101>习题2-9[*]　下面给出的是一个位置索引的一部分，格式为：词项:文档1:〈位置1,位置2,…〉;文档2:〈位置1,位置2,…〉。angels:2:〈36,174,252,651〉;4:〈12,22,102,432〉;7:〈17〉;fools:2:〈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,328,528〉;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〉;4:〈15,35,155〉;7:〈20,320〉;where:2:〈67,124,393,1001〉;4:〈11,41,101,421,431〉;7:〈16,36,736〉;那么哪些文档和以下的查询匹配？其中引号内的每个表达式都是一个短语查询。a.“foolsrushin”。解答：文档2、4、7b.“foolsrushin”AND“angelsfeartotread”。解答：文档4第三章词典及容错式检索习题3-5　再次考虑3.2.1节中的查询fi*mo*er，如果采用2-gram索引的话，那么对应该查询应该会产生什么样的布尔查询？你能否举一个词项的例子，使该词匹配3.2.1节的轮排索引查询，但是并不满足刚才产生的布尔查询？解答：2-gram索引下的布尔查询：$fANDfiANDmoANDerANDr$词项filibuster(海盗)满足3.2.1节的轮排索引查询，但是并不满足上述布尔查询习题3-7　如果|si|表示字符串si的长度，请证明s1和s2的编辑距离不可能超过max{|s1|,|s2|}。 证明：不失一般性，假设|s1|<=|s2|，将s1转换为s2的一种做法为：将s1中的每个字符依次替换为s2中的前|s1|个字符，然后添加s2的后|s2|-|s1|个字符，上述操作的总次数为|s2|=max{|s1|,|s2|}，根据编辑距离的定义，其应该小于|s2|=max{|s1|,|s2|}习题3-8　计算paris和alice之间的编辑距离，给出类似于图3-5中的算法结果，其中的5×5矩阵包含每个前缀子串之间的计算结果。解答：57习题3-11　考虑四词查询catchedintherye，假定根据独立的词项拼写校正方法，每个词都有5个可选的正确拼写形式。那么，如果不对空间进行缩减的话，需要考虑多少可能的短语拼写形式（提示：同时要考虑原始查询本身，也就是每个词项有6种变化可能）？解答：6*6*6*6=1296习题3-14　找出两个拼写不一致但soundex编码一致的专有名词。解答：Mary,Mira(soundex相同)，本题答案不唯一，可能有其他答案，但是soundex编码必须一致。第四章索引构建习题4-1　如果需要Tlog2T次比较（T是词项ID—文档ID对的数目），每次比较都有两次磁盘寻道过程。假定使用磁盘而不是内存进行存储，并且不采用优化的排序算法（也就是说不使用前面提到的外部排序算法），那么对于Reuters-RCV1构建索引需要多长时间？计算时假定采用表4-1中的系统参数。解答：对于Reuters-RCV1，T=108因此排序时间(文档分析时间可以忽略不计)为：2*(108*log2108)*5*10-3s=26575424s=7382h=308day习题4-3　对于n=15个数据片，r=10个分区文件，j=3个词项分区，假定使用的集群的机器的参数如表4-1所示，那么在MapReduce构架下对Reuters-RCV1语料进行分布式索引需要多长时间？【给助教：教材不同印刷版本表4-2不一样，不同同学用的不同版本，还有本题过程具有争议。暂不扣分】 解答【整个计算过程是近似的，要了解过程】：(一)、MAP阶段【读入语料(已经不带XML标记信息了，参考表5-6)，词条化，写入分区文件】：(1)读入语料：基于表4-2，ReutersRCV1共有8*105篇文档，每篇文档有200词条，每个词条(考虑标点和空格)占6B，因此整个语料库的大小为8*105*200*6=9.6*108B（近似1GB，注表4-2对应于表5-1第3行的数据，而那里的数据已经经过去数字处理，因此实际的原始文档集大小应该略高于0.96G，这里近似计算，但是不要认为没有处理就得到表5-1第3行的结果）将整个语料库分成15份，则每份大小为9.6*108/15B每一份读入机器的时间为：9.6*108/15*2*10-8=1.28s(2)词条化：每一份语料在机器上进行词条化处理，得到8*105*200=1.6*108个词项ID-文档ID对(参考表4-2和图4-6，注意此时重复的词项ID-文档ID对还没有处理)，共占1.6*108*8=1.28*109个字节，词条化的时间暂时忽略不计【从题目无法得到词条化这一部分时间，从表5-1看词条化主要是做了去数字和大小写转换，当然也感觉这一部分的处理比较简单，可以忽略】。(3)写入分区文件：每一份语料得到的词项ID-文档ID(Key-Value)存储到分区所花的时间为：(1.28*109/15)*2*10-8=1.71s(4)MAP阶段时间：由于分成15份，但只有10台机器进行MAP操作，所以上述MAP操作需要两步，因此，整个MAP过程所需时间为(1.28+1.71)*2=6.0s(二)、REDUCE阶段【读入分区文件，排序，写入倒排索引】：(1)读入分区文件【读入过程中已经实现所有Key-Value对中的Value按Key聚合，即变成Key,list(V1,V2..)。聚合过程在内存中实现，速度很快，该时间不计。另外，网络传输时间这里也不计算】：根据表4-2，所有倒排记录的数目为1.6*108，因此3台索引器上每台所分配的倒排记录数目为1.6*108/3,而每条记录由4字节词项ID和4字节文档ID组成，因此每台索引器上需要读入的倒排记录表数据为1.28*109/3字节。于是，每台索引器读数据的时间为1.28*109/3*2*10-8=8.5s(2)排序：每台索引器排序所花的时间为1.6*108/3*log2(1.6*108/3)*10-8=13.7s(3)写入倒排索引文件【此时倒排文件已经实现文档ID的去重，假定只存储词项ID和文档ID列表，并不存储其他信息(如词项的DF及在每篇文档中的TF还有指针等等)】：需要写入磁盘的索引大小为(据表4-2，词项总数为4*105个)4*105/3*4+108/3*4=4/3*108字节索引写入磁盘的时间为：4/3*108*2*10-8=2.7s(4)REDUCE阶段时间为：8.5+13.7+2.7=24.9(三)因此，整个分布式索引的时间约为6.0+8.5+13.7+2.7=30.9s 第五章索引压缩习题5-2　估计Reuters-RCV1文档集词典在两种不同按块存储压缩方法下的空间大小。其中，第一种方法中k=8，第二种方法中k=16。解答：每8个词项会节省7*3个字节，同时增加8个字节，于是每8个词项节省7*3-8=13字节，所有词项共节省13*400000/8=650K，因此，此时索引大小为7.6MB-0.65MB=6.95MB每16个词项会节省15*3个字节，同时增加16个字节，于是每16个词项节省15*3-16=29字节，所有词项共节省29*400000/16=725K，因此，此时索引大小为7.6MB-0.725MB=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）。假定倒排记录表的长度和倒排记录表分开独立存储，这样系统能够知道倒排记录表什么时候结束。采用可变字节码：(i)能够使用1字节来编码的最大间距是多少？(ii)能够使用2字节来编码的最大间距是多少？(iii)采用可变字节编码时，上述倒排记录表总共需要多少空间（只计算对这些数字序列进行编码的空间消耗）？解答：(i)27-1=127(答128也算对，因为不存在0间距，0即可表示间距1，……)(ii)214-1=16383(答16384也算对)(iii)1+1+1+1+1+1+1+2+1+1+2=13习题5-8[*]　对于下列采用γ编码的间距编码结果，请还原原始的间距序列及倒排记录表。1110001110101011111101101111011解答：1110001;11010;101;11111011011;110111001;110;11;111011;1119;6;3;32+16+8+2+1=59;79;15;18;77;84第六章文档评分、词项权重计算及向量空间模型习题6-10　考虑图6-9中的3篇文档Doc1、Doc2、Doc3中几个词项的tf情况，采用图6-8中的idf值来计算所有词项car、auto、insurance及best的tf-idf值。Doc1Doc2Doc3car27424auto3330insurance033329best14017图6-9　习题6-10中所使用的tf值 解答：idfcar=1.65，idfauto=2.08，idfinsurance=1.62，idfbest=1.5，于是，各词项在各文档中的tf-idf结果如下表：Doc1Doc2Doc3car27*1.65=44.554*1.65=6.624*1.65=39.6auto3*2.08=6.2433*2.08=68.640insurance033*1.62=53.46329*1.62=46.98best14*1.5=21017*1.5=25.5习题6-12　公式（6-7）中对数的底对公式（6-9）会有什么影响？对于给定查询来说，对数的底是否会对文档的排序造成影响？解答：没有影响。假定idf采用与(6-7)不同的底x计算，根据对数换底公式有。idft(x)=logx(N/dft)=log(N/dft)/logx=idft/logx，由于idft(x)和idft之间只相差一个常数因子1/logx，在公式(6-9)的计算中该常数可以作为公因子提出，因此文档的排序不会改变。121习题6-19　计算查询digitalcameras及文档digitalcamerasandvideocameras的向量空间相似度并将结果填入表6-1的空列中。假定N=10000000，对查询及文档中的词项权重（wf对应的列）采用对数方法计算，查询的权重计算采用idf，而文档归一化采用余弦相似度计算。将and看成是停用词。请在tf列中给出词项的出现频率，并计算出最后的相似度结果。表6-1　习题6-19中的余弦相似度计算词查　　询文　　档tfwfdfidfqi=wf-idftfwfdi=归一化的wfdigital10000video100000cameras50000解答：【本质上这里没有考虑查询向量的归一化，即没有考虑查询向量的大小，严格上不是余弦相似度】词查　　询文　　档tfwfdfidfqi=wf-idftfwfdi=归一化的wfdigital111000033110.520video0010000020110.5203.112cameras11500002.3012.30121.3010.677习题6-23　考虑习题6-10中4个词项和3篇文档中的tf和idf值，采用如下权重计算机制来计算获得得分最高的两篇文档：(i)nnn.atc；(ii)ntc.atc。解答：(i)根据题意文档采用nnn，查询采用atc，然后计算内积，于是有：词项查询q文档Doc1得分 tfidftf-idf归一化tf-idftfidftf-idfcar11.651.650.5602712723.310auto0.52.081.040.353313insurance11.621.620.550010best11.51.50.50914114词项查询q文档Doc2得分tfidftf-idf归一化tf-idftfidftf-idfcar11.651.650.56041432.037auto0.52.081.040.35333133insurance11.621.620.55033133best11.51.50.509010 词项查询q文档Doc3得分tfidftf-idf归一化tf-idftfidftf-idfcar11.651.650.5602412438.046auto0.52.081.040.353010insurance11.621.620.55029129best11.51.50.50917117      于是，在nnn.atc下，Score(q,Doc3)>Score(q,Doc2)>Score(q,Doc1)(ii)根据题意文档采用ntc，查询采用atc，然后计算内积，于是有：词项查询q文档Doc1得分tf(a)idftf-idf归一化tf-idftfidftf-idf归一化tf-idfcar11.651.650.560271.6544.550.8970.76auto0.52.081.040.35332.086.240.125insurance11.621.620.55001.6200best11.51.50.509141.5210.423词项查询q文档Doc2得分tf(a)idftf-idf归一化tfidftf-idf归一化 tf-idftf-idfcar11.651.650.56041.656.60.0750.66auto0.52.081.040.353332.0868.640.786insurance11.621.620.550331.6253.460.613best11.51.50.50901.500词项查询q文档Doc3得分tf(a)idftf-idf归一化tf-idftfidftf-idf归一化tf-idfcar11.651.650.560241.6539.60.5950.92auto0.52.081.040.35302.0800insurance11.621.620.550291.6246.980.706best11.51.50.509171.525.50.383   于是，在nnn.atc下，Score(q,Doc3)>Score(q,Doc1)>Score(q,Doc2)第七章一个完整搜索系统中的评分计算习题7-3　给定单个词项组成的查询，请解释为什么采用全局胜者表（r=K）已经能够充分保证找到前K篇文档。如果只有s个词项组成的查询（s>1），如何对上述思路进行修正？解答：词项t所对应的tf最高的r篇文档构成t的胜者表。单词项查询，idf已经不起作用了(idf用于区别不同词的先天权重)，所以此时已经足够了。对于s个词项组成的查询，有idf权重了。。因此，不再独立。【这一问本人也不知道该怎么答，不扣分吧】习题7-5　重新考察习题6-23中基于nnn.atc权重计算的数据，假定Doc1和Doc2的静态得分分别是1和2。请确定在公式（7-2）下，如何对Doc3的静态得分进行取值，才能分别保证它能够成为查询bestcarinsurance的排名第一、第二或第三的结果。解答：这道题不扣分吧。。整个书上有关余弦相似度的计算这块都有问题【即按照公式(7-2)(6-12)算出的应该是0到1之间的数，但实际例子(例6-4)却是大于1的数，例子中都没有考虑查询向量的大小。另外，按照习题6-23中nnn.atc算出的根本不是什么余弦相似度。整个一团乱】如果相似度先采用nnn.atc计算，最后除以文档向量的大小，则三篇文档的得分分别为：1.39、1.47和1.68。–排名第一：g(d3)+1.68>3.47,g(d3)>1.79–排名第二：2.39doc1>doc2>doc3第十三章文本分类及朴素贝叶斯方法习题13-2[*]　表13-5中的文档中，对于如下的两种模型表示，哪些文档具有相同的模型表示？哪些文档具有不同的模型表示？对于不同的表示进行描述。(i)贝努利模型，(ii)多项式模型。第十四章基于向量空间模型的文本分类第十五章支持向量机及文档机器学习方法第十六章扁平聚类第十七章层次聚类第十八章矩阵分解及隐性语义索引第十九章Web搜索基础第二十章Web采集及索引第二十一章链接分析'