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

内容发布更新时间 : 2024/12/26 11:44:55星期一 下面是文章的全部内容请认真阅读。

《信息检索导论》课后练习答案

王斌

最后更新日期 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|}。

联系客服:779662525#qq.com(#替换为@) 苏ICP备20003344号-4 ceshi