发布时间 : 星期六 文章信息检索导论-王斌 第一次课后练习(1-4)更新完毕开始阅读68ab01010622192e453610661ed9ad51f01d54b3
信息检索导论 第一次课后练习(第1讲-第4讲)
1. 习题 1-3 [*]
对于习题 1-2中的文档集，如果给定如下查询，那么返回的结果是什么？ a. schizophrenia AND drug
b. for AND NOT (drug OR approach） 解答：
习题1-2的文档集如下：
文档 1 breakthrough drug for schizophrenia 文档 2 new schizophrenia drug
文档 3 new approach for treatment of schizophrenia 文档 4 new hopes for schizophrenia patients 词项文档对应如下：
词项 docID 词项 breakthrough 1 approach drug 1 breakthrough for 1 drug schizophrenia 1 drug new 2 for schizophrenia 2 for drug 2 for new 3 hopes approach 3 => new for 3 new treatment 3 new of 3 of schizophrenia 3 patients new 4 schizophrenia hopes 4 schizophrenia for 4 schizophrenia schizophrenia 4 schizophrenia patients 4 treatment 它对应的倒排索引表如下： 词项 文档频率 倒排记录表 approach 1 → 3 breakthrough 1 → 1 drug 2 → 1→2 for 3 → 1→3→4 hopes 1 → 4
new 3 → 2→3→4 of 1 → 3 patients 1 → 4
schizophrenia 4 → 1→2→3→4 treatment 1 → 3
docId 3 1 1 2 1 3 4 4 2 3 4 3 4 1 2 3 4 3
a. schizophrenia AND drug
schizophrenia → 1→2→3→4 AND drug → 1→2
得出交集 => 1→2 结果为文档1和2
b. for AND NOT (drug OR approach） 先求drug OR approach drug → 1→2 OR approach → 3
得出并集 → 1→2→3 则NOT (drug OR approach） → 4 AND for → 1→3→4 得出交集 → 4 所以结果为文档4
2. 习题1-7
请推荐如下查询的处理次序。
d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes） 其中，每个词项对应的倒排记录表的长度分别如下： 词项 倒排记录表长度 eyes 213312 kaleidoscope 87009 marmalade 107913 skies 271658 tangerine 46653 trees 316812 解答：
先将词项倒排记录表按从小到大排序： 词项 倒排索引表 tangerine 46653 kaleidoscope 87009 marmalade 107913 eyes 213312 skies 271658 trees 316812
每个OR查询后的保守估计的索引表大小从小到大排序： kaleidoscope OR eyes 300321 tangerine OR trees 363465 marmalade OR skies 379571 所以该查询的处理次序为：
kaleidoscope OR eyes→tangerine OR trees→marmalade OR skies→(tangerine OR trees) AND (kaleidoscope OR eyes）→(tangerine OR trees) AND (kaleidoscope OR eyes）AND (marmalade OR skies)
3. 习题2-1
请判断如下说法是否正确。
a. 在布尔检索系统中，进行词干还原从不降低正确率。 b. 在布尔检索系统中，进行词干还原从不降低召回率。 c. 词干还原会增加词项词典的大小。
d. 词干还原应该在构建索引时调用，而不应在查询处理时调用。 解答：
A错，因为词干还原相当于扩充出同一个词干表示的多个词，会降低正确率。 B对
C错，词干还原的目的是为了减少屈折变化的形式，并且有时会将派生词转化为基本形式，会减少词项词典的大小。
D错，应该同时做才能保证索引中和查询词的匹配。
4. 习题2-3
如下词经过 Porter词干还原工具处理后会输出同样的结果，你认为哪对（几对）词不应该输出同样的结果？为什么？ a. abandon/abandonment b. absorbency/absorbent c. marketing/markets d. university/universe e. volume/volumes 解答：
c中marketing的意思为营销，market的意思为市场，这两个词虽然词干相同，但意思不同，不应该输出同样的结果。
D同理，university是大学，而universe是宇宙。
5. 习题2-6 【注：每一对数字之间只比较1次，而不是图2-10算法中的可能多次比较】对于两个词组成的查询，其中一个词（项）的倒排记录表包含下面 16 个文档 ID： [4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180]
而另一个词（项）对应的倒排记录表仅仅包含一个文档 ID：[47]
请分别采用如下两种策略进行倒排记录表合并并计算所需要的比较次数，同时简要地说明计算的正确性。
a. 使用标准的倒排记录表。
b. 使用倒排记录表+跳表的方式，跳表指针设在P处。 解答：
A．4,6,10,12,14,16,18,20,22,32,47都分别和47比较了一次，共比较了11次
B．调表指针设在P=16=4处，即列表一的调表指针往后跳四个元素，将列表整理如下： [4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180] 红色是有调表指针的索引，120是跳到180
其中4,14,22,120,32,47分别和47比较了一次，总共比较了6次
6. 习题3-2
写出由词项 mama 生成的轮排索引词汇表中的条目。 解答：
mama$ ama$m ma$ma a$mam
7. 习题3-8
计算 paris 和 alice 之间的编辑距离，给出类似于图 3-5 中的算法结果，其中的 5 × 5 矩包含每个前缀子串之间的计算结果。 解答：
alice01122334455paris11223344556121223344552122334455623122334455 332233445563423233445544333244556453434233445544443344556454534344
8. 习题3-11
考虑四词查询 catched in the rye，假定根据独立的词项拼写校正方法，每个词选的正确拼写形式。 那么， 如果不对空间进行缩减的话， 需要考虑多少可能的短语拼写形式 （提示：同时要考虑原始查询本身，也就是每个词项有 6种变化可能）？ 解答：6*6*6*6=1296
9. 习题4-1
如果需要Tlog2T次比较（T是词项ID—文档ID对的数目），每次比较都有两次磁盘寻道过程。假定使用磁盘而不是内存进行存储，并且不采用优化的排序算法（也就是说不使用前面提到的外部排序算法），那么对于Reuters-RCV1构建索引需要多长时间？计算时假定采用表 4-1中的系统参数。 解答：
对于Reuters-RCV1，T=108
根据4-1中的系统参数，比较时间为0.01ms=10?8s，平均寻道时间为：5ms = 5×10?3s 所以构建索引的时间为：2*(108*log2108)*5*10-3s = 26575424s=7382h=308day
10. 习题4-3
对于 n = 15个数据片，r = 10个分区文件，j = 3 个词项分区，假定使用的集群的机器的参数
如表 4-1所示，那么在 MapReduce 构架下对 Reuters-RCV1语料进行分布式索引需要多长时间？ 解答：
MapReduce分为Map和Reduce两个子任务过程。
·首先是map，将输入的数据片映射成键-值对，每个分析器将输出结果存在本地的中间文件。
(1) 基于表4-2，Reuters RCV1共有8*105篇文档，每篇200词条，每个词条占6B，因此整个语料库的大小为：8*105 *200*6=9.6*108 B 分成15份：9.6*108 /15 B
每一份读入机器的时间为：9.6*108 /15*2*10-8 =1.28s (2) 词条化：
每一份语料在机器上进行词条化处理，得到词项ID-文档ID对个数为：8*105 *200=1.6*108 共占字节数：1.6*108 *8=1.28*109 (3) 写入分区文件：
每一份语料得到的词项ID-文档ID (Key-Value)存储到分区所花的时间为：(1.28*109 /15)*2*10-8 =1.71s (4) MAP阶段时间：
10台机器对15份语料进行MAP操作，整个MAP过程所需时间为(1.28+1.71)*2=6.0s ·REDUCE阶段,读入分区文件，排序，写入倒排索引 (1) 读入分区文件
每台索引器上需要读入的倒排记录表数据为1.28*109 /3字节 每台索引器读数据的时间为1.28*109 /3*2*10-8 =8.5s
(2) 排序：每台索引器排序所花的时间为1.6*108 /3*log2(1.6*108 /3)*10-8 =13.7s (3) 写入倒排索引文件：
需要写入磁盘的索引大小为：4*105 /3*4+108 /3*4=4/3*108 字节 索引写入磁盘的时间为：4/3*108 *2*10-8 =2.7s (4) REDUCE阶段时间为： 8.5+13.7+2.7=24.9
·因此，整个分布式索引的时间约为6.0+8.5+13.7+2.7=30.9s