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

《信息检索导论》课后练习答案王斌最后更新日期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文档4approach0010breakthrough100012drug1100for1011hopes0001new0111of0010patients0001schizophrenia1111treatment0010b.画出该文档集的倒排索引（参考图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操作，得到的中间倒排记录表会更大一些。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[*]对于查询e.friendsANDromansAND(NOTcountrymen)如何利用countrymen的文档频率来估计最佳的查询处理次序？特别地，提出一种在确定查询顺序时对逻辑非进行处理的方法。解答：令friends、romans和countrymen的文档频率分别为x、y、z。如果z极高，则将N-z作为NOTcountrymen的长度估计值，然后按照x、y、N-z从小到大合并。如果z极低，则按照x、y、z从小到大合并...