国科大信息检索作业

《国科大信息检索作业》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、国科大2013年秋季《现代信息检索》第一次作业(第一章到第五章)以下每题10分，共计100分。1、习题1-4a.时间复杂度O(x+y)。因为倒排记录表记录的文档号是按照从小到大排列的，在扫描Brutus对应的倒排表的时指针指向文档号为x，扫描Caesar对应的倒排记录表的指针对应的文档号为y，如果xy，caesar指针后移。b.时间复杂度是O(N)，N是全部的文档数。因为结果集的大小取决于文档数N，而不是倒排记录表的长度。2、习题1-7

2、对于原始的查询，按照倒排记录表的长度从小到大查询会节省查询复杂度(tangerineORtrees)=O(46653+316812)=O(363465)(marmaladeORskies)=O(107913+271658)=O(379571)(kaleidoscopeOReyes)=O(46653+87009)=O(300321)即顺序为：(kaleidoscopeOReyes)AND(tangerineORtrees)AND(marmaladeORskies)3、习题1-10UNION(p1,p2)answer←{}whilep

3、1!=NILandp2!=NILdoifdocID(p1)=docID(p2)thenADD(answer,docID(p1))p1<-next(p1)p2<-next(p2)elseifdocID(p1)

4、)p2<-next(p2)return(answer)4、习题2-7a.由24跳到75这一次跳转b.比较为(3,3)(5,5)(9,89)(15,89)(24,89)(75,89)(75,89)(92,89)(75,89)(92,89)(81,89)(84,89)(89,89)(92,95)(115,95)(96,95)(96,97)(97,97)(100,99)(100,100)(115,101)总共21次比较c.比较为(3,3)(5,5)(9,89)(15,89)(24,89)(39,89)(60,89)(68,89)(75,

5、89)(81,89)(84,89)(89,89)(92,95)(96,95)(96,97)(97,97)(100,99)(100,101)(115,101)总共19次比较5、习题3-8alice012345P112345A212345R322345I433234S544334paris与alice之间的编辑距离为41、习题3-116*6*6*6=12962、习题4-1倒排索引的构建需要两步：1.扫描文档，建立词项文档对。2.对词项文档对进行排序。第一步时间复杂度为O(T)，文档大小为800000*200*6=9.6*108B，所需

6、时间为：读入时间+建立词项-文档对的时间为9.6*108（2*10-8）=19.2s第二步时间复杂度为O(Tlog2T)，所有倒排记录数为108。花费的时间为2*(Tlog2T)*(磁盘寻道时间+一个词项文档对的传输时间+比较时间)=2*(108*log2(108))*(5*10-3+2*10-8*8+10-8)=26575424.76s≈307.59天≈308天总时间为308天3、习题4-3　对于n=15个数据片，r=10个分区文件，j=3个词项分区，假定使用的集群的机器的参数如表4-1所示，那么在MapReduce构架下对Re

7、uters-RCV1语料进行分布式索引需要多长时间？解答【整个计算过程是近似的，数字不一定对，但是要了解过程】：(一)、MAP阶段【读入语料(已经不带XML标记信息了，参考表5-6)，词条化，写入分区文件】：(1)读入语料：基于表4-2，ReutersRCV1共有8*105篇文档，每篇文档有200词条，每个词条(考虑标点和空格)占6B，因此整个语料库的大小为8*105*200*6=9.6*108B（近似1GB，注表4-2对应于表5-1第3行的数据，而那里的数据已经经过去数字处理，因此实际的原始文档集大小应该略高于0.96G，这里近

8、似计算，但是不要认为没有处理就得到表5-1第3行的结果）将整个语料库分成15份，则每份大小为9.6*108/15B每一份读入机器的时间为：9.6*108/15*2*10-8=1.28s(2)词条化：每一份语料在机器上进行词条化处理，得到8*105*