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

《中国科学院大学现代信息检索课后习题答案(共16页).docx》由会员分享，可在线阅读，更多相关《中国科学院大学现代信息检索课后习题答案(共16页).docx（17页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精选优质文档-倾情为你奉上信息检索导论课后练习答案王斌最后更新日期 2013/9/28第一章 布尔检索习题1-1 *画出下列文档集所对应的倒排索引（参考图1-3中的例子）。文档 1 new home sales top forecasts文档 2 home sales rise in july文档 3 increase in home sales in july文档 4 july new home sales rise解答：forecasts-1home-1 2 3 4in-2 3increase-3july-2 3 4new-1 4rise-2 4sales-1 2 3 4top-1习题1-

2、2 *考虑如下几篇文档：文档1 breakthrough drug for schizophrenia文档2 new schizophrenia drug文档3 new approach for treatment of schizophrenia文档4 new hopes for schizophrenia patientsa. 画出文档集对应的词项文档矩阵；解答：文档1文档2文档3文档4approach0010breakthrough1000drug1100for1011hopes0001new0111of0010patients0001schizophrenia1111treatment

3、0010b. 画出该文档集的倒排索引（参考图 1-3中的例子）。解答：参考a。习题1-3 *对于习题1-2中的文档集，如果给定如下查询，那么返回的结果是什么？a. schizophrenia AND drug解答：文档1，文档2b. for AND NOT (drug OR approach）解答：文档4习题1-4 * 对于如下查询，能否仍然在O(x+y)次内完成？其中x和y分别是Brutus和Caesar所对应的倒排记录表长度。如果不能的话，那么我们能达到的时间复杂度是多少？a. Brutus AND NOT Caesarb. Brutus OR NOT Caesar解答：a. 可以在O(x

4、+y)次内完成。通过集合的减操作即可。具体做法参考习题1-11。b. 不能。不可以在O(x+y)次内完成。因为NOT Caesar的倒排记录表需要提取其他所有词项对应的倒排记录表。所以需要遍历几乎全体倒排记录表，于是时间复杂度即为所有倒排记录表的长度的和N，即O(N) 或者说O(x+N-y)。习题1-5 * 将倒排记录表合并算法推广到任意布尔查询表达式，其时间复杂度是多少？比如，对于查询c. (Brutus OR Caesar) AND NOT (Antony OR Cleopatra)我们能在线性时间内完成合并吗？这里的线性是针对什么来说的？我们还能对此加以改进吗？解答：时间复杂度为O(qN

5、)，其中q为表达式中词项的个数，N为所有倒排记录表长度之和。也就是说可以在词项个数q及所有倒排记录表长度N的线性时间内完成合并。由于任意布尔表达式处理算法复杂度的上界为O(N)，所以上述复杂度无法进一步改进。习题1-6 *假定我们使用分配律来改写有关AND和OR的查询表达式。12a. 通过分配律将习题1-5中的查询写成析取范式；b. 改写之后的查询的处理过程比原始查询处理过程的效率高还是低？c. 上述结果对任何查询通用还是依赖于文档集的内容和词本身？解答：a. 析取范式为：(Brutus And Not Anthony And Not Cleopatra) OR (Caesar AND NOT

6、 Anthony AND NOT Cleopatra)b. 这里的析取范式处理比前面的合取范式更有效。这是因为这里先进行AND操作(括号内)，得到的倒排记录表都不大，再进行OR操作效率就不会很低。而前面需要先进行OR操作，得到的中间倒排记录表会更大一些。c. 上述结果不一定对，比如两个罕见词A和B构成的查询 (A OR B) AND NOT(HONG OR KONG)，假设HONG KONG一起出现很频繁。此时合取方式可能处理起来更高效。如果在析取范式中仅有词项的非操作时，b中结果不对。习题 1-7 *请推荐如下查询的处理次序。d. (tangerine OR trees) AND (marm

7、alade OR skies) AND (kaleidoscope OR eyes）其中，每个词项对应的倒排记录表的长度分别如下：词项 倒排记录表长度eyes 213 312kaleidoscope 87 009marmalade 107 913skies 271 658tangerine 46 653trees 316 812解答：由于：(tangerine OR trees) 46653+ = (marmalade OR skies) + = (kaleidoscope OR eyes） 87009+ = 30321 所以推荐处理次序为：(kaleidoscope OR eyes）AND

8、(tangerine OR trees) AND (marmalade OR skies)习题1-8* 对于查询e. friends AND romans AND (NOT countrymen)如何利用countrymen的文档频率来估计最佳的查询处理次序？特别地，提出一种在确定查询顺序时对逻辑非进行处理的方法。解答：令friends、romans和countrymen的文档频率分别为x、y、z。如果z极高，则将N-z作为NOT countrymen的长度估计值，然后按照x、y、N-z从小到大合并。如果z极低，则按照x、y、z从小到大合并。习题 1-9 *对于逻辑与构成的查询，按照倒排记录表

9、从小到大的处理次序是不是一定是最优的？如果是，请给出解释；如果不是，请给出反例。解答：不一定。比如三个长度分别为x,y,z的倒排记录表进行合并，其中xyz，如果x和y的交集为空集，那么有可能先合并x、y效率更高。习题 1-10 *对于查询x OR y，按照图1-6的方式，给出一个合并算法。解答：1 answer- ( )2 while p1!=NIL and p2!=NIL3 do if docID(p1)=docID(p2)4 then ADD(answer,docID(p1)5p1- next(p1)6 p2-next(p2)7 else if docID(p1)docID(p2)8 th

10、en ADD(answer,docID(p1)9 p1- next(p1)10 else ADD(answer,docID(p2)11p2-next(p2)12 if p1!=NIL / 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 * 如何处理查询x AND NOT y？为什么原始的处理方法非常耗时？给出一个针对该查询的高效合并算法。解答：由于NOT y几乎要遍历所有倒排表，因此如果采用列举倒

11、排表的方式非常耗时。可以采用两个有序集合求减的方式处理 x AND NOT y。算法如下：Meger(p1,p2)1answer ()2while p1!=NIL and p2!=NIL3do if docID(p1) =docID(p2)4thenp1next(p1)5p2next(p2)6else if docID(p1)75b. 当两个表进行合并时，倒排记录之间的比较次数是多少？【如下答案不一定正确，有人利用程序计算需要21次，需要回到算法，本小题不扣分，下面不考虑重新比较同意对数字】解答： 18次： , , , ,c. 如果不使用跳表指针，那么倒排记录之间的比较次数是多少？解答： 19

12、次： , ,习题 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

13、: 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. “fools rush in”。解答： 文档2、4、7b. “fools rus

14、h in” AND “angels fear to tread”。解答： 文档4第三章 词典及容错式检索习题 3-5再次考虑3.2.1节中的查询fi*mo*er，如果采用2-gram索引的话，那么对应该查询应该会产生什么样的布尔查询？你能否举一个词项的例子，使该词匹配3.2.1节的轮排索引查询，但是并不满足刚才产生的布尔查询？解答： 2-gram索引下的布尔查询：$f AND fi AND mo AND er AND r$ 词项filibuster(海盗)满足 3.2.1节的轮排索引查询，但是并不满足上述布尔查询习题 3-7如果 |si | 表示字符串si的长度，请证明s1和s2的编辑距离不可

15、能超过max|s1|, |s2|。证明：不失一般性，假设|s1|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)idf

16、tf-idf归一化tf-idftfidftf-idf归一化tf-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

17、.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个词项组成的查询（s1），如何对上述思路进行修正？解答：词项t所对应的tf最高的r篇文档构成t的胜者表。单词项查询，idf已经不起作用了(idf用于区别不同词的先天权重)，所以此时已经足够了。对于s个词项组成的查询，有idf权重了。因此

18、，不再独立。【这一问本人也不知道该怎么答，不扣分吧】习题 7-5重新考察习题6-23中基于nnn.atc权重计算的数据，假定Doc1和Doc2的静态得分分别是1和2。请确定在公式（7-2）下，如何对Doc3的静态得分进行取值，才能分别保证它能够成为查询best car insurance的排名第一、第二或第三的结果。解答：这道题不扣分吧。整个书上有关余弦相似度的计算这块都有问题【即按照公式(7-2) (6-12)算出的应该是0到1之间的数，但实际例子(例6-4)却是大于1的数，例子中都没有考虑查询向量的大小。另外，按照习题6-23中nnn.atc算出的根本不是什么余弦相似度。整个一团乱】如果相

19、似度先采用nnn.atc计算，最后除以文档向量的大小，则三篇文档的得分分别为：1.39、1.47和1.68。 排名第一：g(d3)+1.683.47, g(d3)1.79 排名第二：2.39 g(d3)+1.68 3.47, 0.71 g(d3)1.79 排名第三：0 g(d3) 0.71 习题 7-7设定图6-10中Doc1、Doc2和Doc3的静态得分分别是0.25、0.5和1，画出当使用静态得分与欧几里得归一化tf值求和结果进行排序的倒排记录表。解答：按照公式7-2计算得下表：doc1doc2doc3car1.130.591.58auto0.351.211 (0)insurance0.2

20、5 (0)1.211.7best0.710.5 (0)1.41所以，倒排记录表如下：car doc3 doc1 doc2auto doc2doc 3 doc1 【按道理，tf为零的不应该出现在倒排记录中，有的也算对】insurancedoc3doc2doc1 best doc3doc1doc2第八章 信息检索的评价习题 8-8 *考虑一个有4篇相关文档的信息需求，考察两个系统的前10个检索结果（左边的结果排名靠前），相关性判定的情况如下所示：系统1 R N R N N N N N R R系统2 N R N N R R R N N Na. 计算两个系统的MAP值并比较大小。b. 上述结果直观上看

21、有意义吗？能否从中得出启发如何才能获得高的MAP得分？c. 计算两个系统的R正确性值，并与a中按照MAP进行排序的结果进行对比。解答：a. 系统1 (1+2/3+3/9+4/10)/4=0.6 系统2 (1/2+2/5+3/6+4/7)/4=0.492 b. 相关文档出现得越靠前越好，最好前面3-5篇之内c. 系统1的R-Precision= 0.5, 系统2 R-Precision= 0.25 习题 8-9 *在10 000篇文档构成的文档集中，某个查询的相关文档总数为8，下面给出了某系统针对该查询的前20个有序结果的相关（用R表示）和不相关（用N表示）情况，其中有6篇相关文档：R R N

22、N N N N N R N R N N N R N N N N Ra. 前20篇文档的正确率是多少？P20=6/20=30%b. 前20篇文档的F1值是多少?R20=6/8=75%，F1=3/7=0.429150c. 在25%召回率水平上的插值正确率是多少？1d. 在33%召回率水平上的插值正确率是多少？3/9=33.3%e. 假定该系统所有返回的结果数目就是20，请计算其MAP值。(1+1+3/9+4/11+5/15+6/20)/8=0.4163假定该系统返回了所有的10 000篇文档，上述20篇文档只是结果中最靠前的20篇文档，那么f. 该系统可能的最大MAP是多少？从第21位开始，接连两篇相关文档，此时可以获得最大的MAP，此时有：(1+1+3/9+4/11+5/15+6/20+7/21+8/22)/8=0.503g. 该系统可能的最小MAP是多少？(1+1+3/9+4/11+5/15+6/20+7/9999+8/10000)/8=0.4165h. 在一系列实验中，只有最靠前的20篇文档通过人工来判定，(e)的结果用于近似从(f)到(g)的MAP取值范围。对于上例来说，通过(e)而不是(f)和(g)来计算MAP所造成的误差有多大（采用绝对值来计算）？ |0.4163-(0.503+0.4165)/2|=0.043第九章 相关反馈及查询扩展习题