内容发布更新时间 : 2024/6/29 21:01:17星期一 下面是文章的全部内容请认真阅读。
《信息检索导论》课后练习答案
王斌
最后更新日期 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 home in increase july new rise sales top
习题1-2 [*] 考虑如下几篇文档：
文档1 breakthrough drug for schizophrenia
文档2 new schizophrenia drug
文档3 new approach for treatment of schizophrenia 文档4 new hopes for schizophrenia patients
-------> -------> -------> -------> -------> -------> -------> -------> -------> 1 1 ? 2 ? 3 2 ? 1 ? 2 ? 1 ? 1 2 ? 3 3 ? 4 4 3 ? 4 4 4 2 ? 3 ? a. 画出文档集对应的词项—文档矩阵；
解答： approach breakthrough drug for hopes new
文档1 0 1 1 1 0 0
文档2 0 0 1 0 0 1
文档3 1 0 0 1 0 1
文档4 0 0 0 1 1 1
of patients schizophrenia treatment
0 0 1 0
0 0 1 0
1 0 1 1
0 1 1 0
b. 画出该文档集的倒排索引（参考图 1-3中的例子）。
解答：参考a。
习题1-3 [*] 对于习题1-2中的文档集，如果给定如下查询，那么返回的结果是什么？
a. schizophrenia AND drug
解答：{文档1，文档2}
b. for AND NOT (drug OR approach） 解答：{文档4}
习题1-4 [*] 对于如下查询，能否仍然在O(x+y)次内完成？其中x和y分别是Brutus和Caesar所对应的倒排记录表长度。如果不能的话，那么我们能达到的时间复杂度是多少？
a. Brutus AND NOT Caesar b. Brutus OR NOT Caesar
解答：
a. 可以在O(x+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)，其中q为表达式中词项的个数，N为所有倒排记录表长度之和。也就是说可以在词项个数q及所有倒排记录表长度N的线性时间内完成合并。由于任意布尔表达式处理算法复杂度的上界为O(N)，所以上述复杂度无法进一步改进。
习题1-6 [**] 假定我们使用分配律来改写有关AND和OR的查询表达式。
a. 通过分配律将习题1-5中的查询写成析取范式；
12
解答：
a. 析取范式为：(Brutus And Not Anthony And Not Cleopatra) OR (Caesar AND NOT Anthony AND NOT Cleopatra)
b. 这里的析取范式处理比前面的合取范式更有效。这是因为这里先进行AND操作(括号内)，得到的倒排记录表都不大，再进行OR操作效率就不会很低。而前面需要先进行OR操作，得到的中间倒排记录表会更大一些。 c. 上述结果不一定对，比如两个罕见词A和B构成的查询 (A OR B) AND NOT(HONG OR KONG)，假设HONG KONG一起出现很频繁。此时合取方式可能处理起来更高效。如果在析取范式中仅有词项的非操作时，b中结果 不对。
b. 改写之后的查询的处理过程比原始查询处理过程的效率高还是低？ c. 上述结果对任何查询通用还是依赖于文档集的内容和词本身？
习题 1-7 [*] 请推荐如下查询的处理次序。
d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes）
其中，每个词项对应的倒排记录表的长度分别如下：
词项 倒排记录表长度 eyes 213 312 kaleidoscope 87 009 marmalade 107 913 skies 271 658 tangerine 46 653 trees 316 812 解答：
由于：
(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极高，则将N-z作为NOT countrymen的长度估计值，然后按照x、y、N-z从小到大合并。如果z极低，则按照x、y、z从小到大合并。
习题 1-9 [**] 对于逻辑与构成的查询，按照倒排记录表从小到大的处理次序是不是一定是最优的？如果是，请给出解释；如果不是，请给出反例。
解答：不一定。比如三个长度分别为x,y,z的倒排记录表进行合并，其中x>y>z，如果x和y的交集为空集，那么有可能先合并x、y效率更高。
习题 1-10 [**] 对于查询x OR y，按照图1-6的方式，给出一个合并算法。
解答：
1 answer<- ( )
2 while p1!=NIL and p2!=NIL 3 do if docID(p1)=docID(p2) 4 then ADD(answer,docID(p1)) 5 p1<- next(p1) 6 p2<-next(p2)
7 else if docID(p1) 10 else ADD(answer,docID(p2)) 11 p2<-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几乎要遍历所有倒排表，因此如果采用列举倒排表的方式非常耗时。可以采用两个有序集合求减的方式处理 x AND NOT y。算法如下： Meger(p1,p2) 1 answer () 2 while p1!=NIL and p2!=NIL 3 do if docID(p1) =docID(p2) 4 then p1?next(p1) 5 p2?next(p2) 6 else if docID(p1) 11 if p1!=NIL // 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。 对照搜索引擎返回的总数和排名靠前的文档，这些结果是否满足布尔逻辑的意义？对于大多数搜索引擎来说，它们往往不满足。你明白这是为什么吗？如果采用其他词语，结论又如何？比如以下查询 (i) knight；(ii) conquer；(iii) knight OR conquer。 第二章 词汇表和倒排记录表 习题 2-1 [*] 请判断如下说法是否正确。 a. 在布尔检索系统中，进行词干还原从不降低正确率。 b. 在布尔检索系统中，进行词干还原从不降低召回率。 c. 词干还原会增加词项词典的大小。 d. 词干还原应该在构建索引时调用，而不应在查询处理时调用。 解答： a错 b 对 c错 d 错 习题2-7 [*] 考虑利用如下带有跳表指针的倒排记录表 和一个中间结果表（如下所示，不存在跳表指针）进行合并操作。 3 5 89 95 97 99 100 101 采用图2-10所示的倒排记录表合并算法，请问： 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>,<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. “fools rush in”。 解答： 文档2、4、7 b. “fools rush 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的编辑距离不可能超过max{|s1|, |s2|}。