证明：不失一般性，假设|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 得分