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

内容发布更新时间 : 2024/12/25 23:47:08星期一 下面是文章的全部内容请认真阅读。

证明:不失一般性,假设|s1|<= |s2|,将s1转换为s2的一种做法为:将s1中的每个字符依次替换

为s2中的前|s1|个字符,然后添加s2的后|s2|-|s1|个字符,上述操作的总次数为|s2|= max{|s1|, |s2|},根据编辑距离的定义,其应该小于|s2|= max{|s1|, |s2|}

习题 3-8 计算paris和 alice之间的编辑距离,给出类似于图3-5中的算法结果,其中的5 × 5

矩阵包含每个前缀子串之间的计算结果。 解答:

习题 3-11 考虑四词查询catched in the rye,假定根据独立的词项拼写校正方法,每个词都有5

个可选的正确拼写形式。那么,如果不对空间进行缩减的话,需要考虑多少可能的短语拼写形式(提示:同时要考虑原始查询本身,也就是每个词项有6种变化可能)? 解答:6*6*6*6=1296

习题 3-14 找出两个拼写不一致但soundex编码一致的专有名词。

解答:Mary, Mira (soundex相同),本题答案不唯一,可能有其他答案,但是soundex编码必须一

致。

57

第四章 索引构建

习题 4-1 如果需要T log2 T次比较(T是词项ID—文档ID对的数目),每次比较都有两次磁盘寻

道过程。假定使用磁盘而不是内存进行存储,并且不采用优化的排序算法(也就是说不使用前

面提到的外部排序算法),那么对于Reuters-RCV1构建索引需要多长时间?计算时假定采用表4-1中的系统参数。 解答:

对于Reuters-RCV1,T=10

88-3

因此排序时间(文档分析时间可以忽略不计)为:2*(10*log210)*5*10s = 26575424s = 7382 h=308 day

习题 4-3 对于

8

n = 15个数据片,r = 10个分区文件,j = 3个词项分区,假定使用

的集群的机器的参数如表4-1所示,那么在MapReduce构架下对Reuters-RCV1语料进行分布式索引需要多长时间?

【给助教:教材不同印刷版本表4-2不一样,不同同学用的不同版本,还有本题过程具有争议。暂不扣分】

解答【整个计算过程是近似的,要了解过程】:

(一)、MAP阶段【读入语料(已经不带XML标记信息了,参考表5-6),词条化,写入分区文件】: (1) 读入语料:

5

基于表4-2,Reuters RCV1共有8*10篇文档,每篇文档有200词条,每个词条(考虑标点和空格)占

58

6B,因此整个语料库的大小为 8*10*200*6=9.6*10B (近似1GB,注表4-2对应于表5-1第3行的数据,而那里的数据已经经过 去数字 处理,因此实际的原始文档集大小应该略高于0.96G,这里近似计算,但是不要认为没有处理就得到表5-1第3行的结果)

8

将整个语料库分成15份,则每份大小为9.6*10/15 B

8-8

每一份读入机器的时间为:9.6*10/15*2*10=1.28s

58

(2) 词条化:每一份语料在机器上进行词条化处理,得到8*10*200=1.6*10个词项ID-文档ID对(参

89

考表4-2和图4-6,注意此时重复的 词项ID-文档ID对 还没有处理),共占1.6*10*8=1.28*10个字节,词条化的时间暂时忽略不计【从题目无法得到词条化这一部分时间,从表5-1看词条化主要是做了去数字和大小写转换,当然也感觉这一部分的处理比较简单,可以忽略】。

(3) 写入分区文件:每一份语料得到的词项ID-文档ID (Key-Value)存储到分区所花的时间为:

9-8

(1.28*10/15)*2*10=1.71s (4) MAP阶段时间:

由于分成15份,但只有10台机器进行MAP操作,所以上述MAP操作需要两步,因此,整个MAP过程所需时间为 (1.28+1.71)*2=6.0s

(二)、REDUCE阶段【读入分区文件,排序,写入倒排索引】:

(1) 读入分区文件【读入过程中已经实现所有Key-Value对中的Value按Key聚合,即变成Key, list(V1,V2..)。聚合过程在内存中实现,速度很快,该时间不计。另外,网络传输时间这里也不计算】:

8

根据表4-2,所有倒排记录的数目为1.6*10,因此3台索引器上每台所分配的倒排记录数目为 8

1.6*10/3,而每条记录由4字节词项ID和4字节文档ID组成,因此每台索引器上需要读入的倒排记录表

9

数据为 1.28*10/3字节。

9-8

于是,每台索引器读数据的时间为 1.28*10/3*2*10=8.5s (2) 排序:

88-8

每台索引器排序所花的时间为 1.6*10/3*log2(1.6*10/3)*10=13.7s (3) 写入倒排索引文件【此时倒排文件已经实现文档ID的去重,假定只存储词项ID和文档ID列表,并不存储其他信息(如词项的DF及在每篇文档中的TF还有指针等等)】:

5588

需要写入磁盘的索引大小为(据表4-2,词项总数为4*10个) 4*10/3*4+10/3*4=4/3*10字节

8-8

索引写入磁盘的时间为:4/3*10*2*10=2.7s (4) REDUCE阶段时间为: 8.5+13.7+2.7=24.9

(三) 因此,整个分布式索引的时间约为6.0+8.5+13.7+2.7=30.9s

第五章 索引压缩

习题 5-2 估计Reuters-RCV1文档集词典在两种不同按块存储压缩方法下的空间大小。其中,第一种方法中k = 8,第二种方法中k = 16。 解答:

每8个词项会节省7*3个字节,同时增加8个字节,于是每8个词项节省7*3-8=13字节,所有词项共节省13*400000/8=650K,因此,此时索引大小为7.6MB-0.65MB=6.95MB

每16个词项会节省15*3个字节,同时增加16个字节,于是每16个词项节省15*3-16=29字节,所有词项共节省29*400000/16=725K,因此,此时索引大小为7.6MB-0.725MB=6. 875MB

习题 5-6 考虑倒排记录表(4, 10, 11, 12, 15, 62, 63, 265, 268, 270, 400)及其对

应的间距表(4, 6, 1, 1, 3, 47, 1, 202,3, 2, 130)。假定倒排记录表的长度和倒排记录表分开独立存储,这样系统能够知道倒排记录表什么时候结束。采用可变字节码: (i) 能够使用1字节来编码的最大间距是多少? (ii) 能够使用2字节来编码的最大间距是多少?

(iii) 采用可变字节编码时,上述倒排记录表总共需要多少空间(只计算对这些数字序列进行编码的空间消耗)? 解答:

(i) 2-1=127 (答128也算对,因为不存在0间距,0即可表示间距1,……) (ii) 2-1=16383 (答16384也算对) (iii) 1+1+1+1+1+1+1+2+1+1+2=13

习题 5-8 [*] 对于下列采用γ 编码的间距编码结果,请还原原始的间距序列及倒排记录表。

1110001110101011111101101111011 解答:

1110 001; 110 10; 10 1; 111110 11011; 110 11 1001; 110; 11; 111011; 111 9; 6; 3; 32+16+8+2+1=59; 7 9; 15;18;77;84

147

第六章 文档评分、词项权重计算及向量空间模型

习题 6-10 考虑图6-9中的3篇文档Doc1、Doc2、Doc3中几个词项的tf情况,采用图6-8中的idf

值来计算所有词项car、auto、insurance及best的tf-idf值。

Doc1 27 3 0 14 Doc2 4 33 33 0 Doc3 24 0 29 17 car auto insurance best 图6-9 习题 6-10中所使用的tf值

解答:

idfcar=1.65,idfauto=2.08,idfinsurance=1.62,idfbest=1.5,

于是,各词项在各文档中的tf-idf结果如下表:

Doc1 27*1.65=44.55 3*2.08=6.24 0 Doc2 4*1.65=6.6 33*2.08=68.64 33*1.62=53.46 Doc3 24*1.65=39.6 0 29*1.62=46.98 car auto insurance best

14*1.5=21 0 17*1.5=25.5 习题 6-12 公式(6-7)中对数的底对公式(6-9)会有什么影响?对于给定查询来说,对数的底

是否会对文档的排序造成影响?

解答:没有影响。

假定idf采用与(6-7)不同的底x计算,根据对数换底公式有。

idft(x)=logx(N/dft)=log(N/dft)/logx=idft/logx,

由于idft(x)和idft之间只相差一个常数因子1/logx,在公式(6-9)的计算中该常数可以作为公因子提出,因此文档的排序不会改变。

习题 6-19 计算查询digital cameras及文档digital cameras and video cameras的向量空间

相似度并将结果填入表6-1的空列中。假定N=10 000 000,对查询及文档中的词项权重(wf对应的列)采用对数方法计算,查询的权重计算采用idf,而文档归一化采用余弦相似度计算。将 and 看成是停用词。请在tf列中给出词项的出现频率,并计算出最后的相似度结果。

表6-1 习题6-19中的余弦相似度计算

查 询 词 tf digital video cameras wf df 10 000 100 000 50 000 idf 文 档 121 qi=wf-idf tf wf di=归一化的wf qi?di

解答:【本质上这里没有考虑查询向量的归一化,即没有考虑查询向量的大小,严格上不是余弦相似度】 查 询 词 tf digital video cameras 1 0 1 wf 1 0 1 df 10 000 100 000 50 000 idf 3 2 文 档 qi=wf-idf tf wf 3 0 1 1 2 1 1 di=归一化的wf 0.520 0.520 qi?di 3.112 2.301 2.301 1.301 0.677

习题 6-23 考虑习题 6-10中4个词项和3篇文档中的tf和idf值,采用如下权重计算机制来计算获

得得分最高的两篇文档:(i) nnn.atc ;(ii) ntc.atc。

解答:(i) 根据题意文档采用nnn,查询采用atc,然后计算内积,于是有:

查询q 词项 car auto insurance best tf 1 0.5 1 1 idf tf-idf 1.65 2.08 1.62 1.5 1.65 1.04 1.62 1.5 归一化tf-idf 0.560 0.353 0.550 0.509 tf 27 3 0 14 文档Doc1 idf tf-idf 1 1 1 1 27 3 0 14 23.310 得分

查询q 词项 car auto insurance best tf 1 0.5 1 1 idf tf-idf 1.65 2.08 1.62 1.5 1.65 1.04 1.62 1.5 归一化tf-idf 0.560 0.353 0.550 0.509 tf 4 33 33 0 文档Doc2 idf tf-idf 1 1 1 1 4 33 33 0 32.037 得分

查询q 词项 car auto insurance best

文档Doc3 归一化tf-idf 0.560 0.353 0.550 0.509 tf 24 0 29 17 idf tf-idf 1 1 1 1 24 0 29 17 38.046 得分 tf 1 0.5 1 1 idf 1.65 2.08 1.62 1.5 tf-idf 1.65 1.04 1.62 1.5 于是,在nnn.atc下,Score(q,Doc3)>Score(q,Doc2)>Score(q,Doc1)

(ii) 根据题意文档采用ntc,查询采用atc,然后计算内积,于是有: 查询q 词项 car auto insurance best tf(a) 1 0.5 1 1 idf tf-idf 1.65 2.08 1.62 1.5 1.65 1.04 1.62 1.5 归一化tf-idf 0.560 0.353 0.550 0.509 tf 27 3 0 14 文档Doc1 idf tf-idf 归一化 得分 tf-idf 1.65 44.55 0.897 2.08 1.62 1.5 6.24 0.125 0 21 0 0.423 0.76

词项 查询q 文档Doc2 得分