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