信息检索导论王斌后练习14

1、信息检索导论 第一次课后练习(第1讲-第4讲)1. 习题 1-3 * 对于习题 1-2中的文档集，如果给定如下查询，那么返回的结果是什么？a. schizophrenia AND drugb. 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词项

2、文档对应如下：词项docID词项docIdbreakthrough1approach 3drug1breakthrough1for 1drug1schizophrenia1drug2new 2for1schizophrenia2for3drug2for4new 3hopes4approach 3=>new2for 3new3treatment 3new4of 3of3schizophrenia3patients4new 4schizophrenia1hopes 4schizophrenia2for 4schizophrenia3schizophrenia 4schizophrenia4p

3、atients4treatment3它对应的倒排索引表如下：词项文档频率倒排记录表approach13breakthrough11drug212for3134hopes14new3234of13patients14schizophrenia41234treatment13a. schizophrenia AND drugschizophrenia1234ANDdrug12得出交集=>12结果为文档1和2b. for AND NOT (drug OR approach）先求drug OR approachdrug12ORapproach3得出并集123则NOT(drug OR approa

4、ch）4ANDfor134得出交集4所以结果为文档42. 习题1-7请推荐如下查询的处理次序。d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes）其中，每个词项对应的倒排记录表的长度分别如下：词项 倒排记录表长度eyes 213312kaleidoscope 87009marmalade 107913skies 271658tangerine 46653trees 316812解答：先将词项倒排记录表按从小到大排序：词项倒排索引表tangerine 46653kaleidoscope 87009m

5、armalade 107913eyes 213312skies 271658trees 316812每个OR查询后的保守估计的索引表大小从小到大排序：kaleidoscope OR eyes300321tangerine OR trees363465marmalade OR skies379571所以该查询的处理次序为：kaleidoscope OR eyestangerine OR treesmarmalade OR skies(tangerine OR trees) AND (kaleidoscope OR eyes）(tangerine OR trees) AND (kaleidosco

6、pe OR eyes）AND (marmalade OR skies)3. 习题2-1请判断如下说法是否正确。a. 在布尔检索系统中，进行词干还原从不降低正确率。b. 在布尔检索系统中，进行词干还原从不降低召回率。c. 词干还原会增加词项词典的大小。d. 词干还原应该在构建索引时调用，而不应在查询处理时调用。解答：A错，因为词干还原相当于扩充出同一个词干表示的多个词，会降低正确率。B对C错，词干还原的目的是为了减少屈折变化的形式，并且有时会将派生词转化为基本形式，会减少词项词典的大小。D错，应该同时做才能保证索引中和查询词的匹配。4. 习题2-3如下词经过 Porter词干还原工具处理后会输出

7、同样的结果，你认为哪对（几对）词不应该输出同样的结果？为什么？a. abandon/abandonmentb. absorbency/absorbentc. marketing/marketsd. university/universee. volume/volumes解答：c中marketing的意思为营销，market的意思为市场，这两个词虽然词干相同，但意思不同，不应该输出同样的结果。D同理，university是大学，而universe是宇宙。5. 习题2-6 【注：每一对数字之间只比较1次，而不是图2-10算法中的可能多次比较】对于两个词组成的查询，其中一个词（项）的倒排记录表包含下

8、面 16 个文档 ID：4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180而另一个词（项）对应的倒排记录表仅仅包含一个文档 ID：47请分别采用如下两种策略进行倒排记录表合并并计算所需要的比较次数，同时简要地说明计算的正确性。a. 使用标准的倒排记录表。b. 使用倒排记录表+跳表的方式，跳表指针设在处。解答：A4,6,10,12,14,16,18,20,22,32,47都分别和47比较了一次，共比较了11次B调表指针设在=4处，即列表一的调表指针往后跳四个元素，将列表整理如下：4,6,10,12,14,16,18,20,22,32,47,81,1

9、20,122,157,180红色是有调表指针的索引，120是跳到180其中4,14,22,120,32,47分别和47比较了一次，总共比较了6次6. 习题3-2写出由词项 mama 生成的轮排索引词汇表中的条目。解答：mama$ama$mma$maa$mam7. 习题3-8计算 paris 和 alice 之间的编辑距离，给出类似于图 3-5 中的算法结果，其中的 5 × 5 矩包含每个前缀子串之间的计算结果。解答：8. 习题3-11考虑四词查询 catched in the rye，假定根据独立的词项拼写校正方法，每个词选的正确拼写形式。 那么， 如果不对空间进行缩减的话， 需要考

10、虑多少可能的短语拼写形式 （提示：同时要考虑原始查询本身，也就是每个词项有 6种变化可能）？解答：6*6*6*6=12969. 习题4-1如果需要Tlog2T次比较（T是词项ID文档ID对的数目），每次比较都有两次磁盘寻道过程。假定使用磁盘而不是内存进行存储，并且不采用优化的排序算法（也就是说不使用前面提到的外部排序算法），那么对于Reuters-RCV1构建索引需要多长时间？计算时假定采用表 4-1中的系统参数。解答：对于Reuters-RCV1，T=108根据4-1中的系统参数，比较时间为0.01ms=108s，平均寻道时间为：5ms = 5×103s所以构建索引的时间为：2*(

11、108*log2108)*5*10-3s = 26575424s=7382h=308day10. 习题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，因此整个语料库的大

12、小为：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