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

《信息检索导论》课后练习答案王斌最后更新日期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文档4approach0010breakthrough1000drug1100for1011hopes0001new0111of0010patients0001schizophrenia1111treatment0010b.画出该文档集的倒排索引（参考图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的查询表达式。a.通过分配律将习题1-5中的查询写成析取范式；b.改写之后的查询的处理过程比原始查询处理过程的效率高还是低？c.上述结果对任何查询通用还是依赖于文档集的内容和词本身？解答：a.析取范式为：(BrutusAndNotAnthonyAndNotCleopatra)OR(CaesarANDNOTAnthonyANDNOTCleopatra)b.这里的析取范式处理比前面的合取范式更有效。这是因为这里先进行AND操作(括号内)，得到的倒排记录表都不大，再进行OR操作效率就不会很低。而前面需要先进行OR操作，得到的中间倒排记录表会更大一些。12c.上述结果不一定对，比如两个罕见词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[*]对于查询e.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的倒排记录表进行合并，其中xyz，如果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)docID(p2)8thenADD(answer,docID(p1))9p1-next(p1)10elseADD(answer,docID(p2))11p2-next(p2)12ifp1!=NIL//x还有剩余13thenwhilep1!=NILdoADD(answer,docID(p1))14elsewhilep2!=NILdoADD(answer,docID(p2))15return(answer)习题1-11[*]如何处理查询xANDNOTy？为什么原始的处理方法非常耗时？给出一个针对该查询的高效合并算法。解答：由于NOTy几乎要遍历所有倒排表，因此如果采用列举倒排表的方式非常耗时。可以采用两个有序集合求减的方式处理xANDNOTy。算法如下：Meger(p1,p2)1answer()2whilep1!=NILandp2!=NIL3doifdocID(p1)=docID(p2)4thenp1next(p1)5p2next(p2)6elseifdocID(p1)docID(p2)7thenADD(answer,docID(p1))8p1next(p1)9elseADD(answer,docID(p2))10p2next(p2)11ifp1!=NIL//x还有剩余12thenwhilep1!=NILdoADD(answer,docID(p1))13return(answer)习题1-12[*]利用Westlaw系统的语法构造一个查询，通过它可以找到professor、teacher或lecturer中的任意一个词，并且该词和动词explain在一个句子中出现，其中explain以某种形式出现。解答：professorteacherlecturer/sexplain!习题1-13[*]在一些商用搜索引擎上试用布尔查询，比如，选择一个词（如burglar），然后将如下查询提交给搜索引擎(i)burglar；(ii)burglarANDburglar；(iii)burglarORburglar。对照搜索引擎返回的总数和排名靠前的文档，这些结果是否满足布尔逻辑的意义？对于大多数搜索引擎来说，它们往往不满足。你明白这是为什么吗？如果采用其他词语，结论又如何？比如以下查询(i)knight；(ii)conquer；(iii)knightORconquer。第二章词汇表和倒排记录表习题2-1[*]请判断如下说法是否正确。a.在布尔检索系统中，进行词干还原从不降低正确率。b.在布尔检索系统中，进行词干还原从不降低召回率。c.词干还原会增加词项词典的大小。d.词干还原应该在构建索引时调用，而不应在查询处理时调用。解答：a错b对c错d错习题2-7[*]考虑利用如下带有跳表指针的倒排记录表和一个中间结果表（如下所示，不存在跳表指针）进行合并操作。3589959799100101采用图2-10所示的倒排记录表合并算法，请问：a.跳表指针实际跳转的次数是多少（也就是说，指针p1的下一步将跳到skip（p1））？一次，24—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,100115,101c.如果不使用跳表指针，那么倒排记录之间的比较次数是多少？解答：19次：3,3,5,5,9,89,15,89,24,89,39,89,60,89,68,89,75,89,81,89,84,89,89,8992,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索引的话，那么对应该查询应该会