现代信息检索导论作业讲评

作业讲评现代信息检索导论不要抄袭有两位同学一次作业都没交，请认识他们的同学转告一下。作业说明第一次作业EstimatethetimeandspacecomplexityoftheSPIMindexingalgorithm把空间复杂度与实际内存使用情况混淆第一次作业DesignaMapReducealgorithmforcountingtheoccurrenceno.ofa“phrase”ofnorderedwordsW1…Wn直接使用(tid,did,pos)三元组第二次作业编程题WritetwoCfunctionstoencodeanddecodevariable-byteintegers.WritetwoCfunctionstoencodeanddecodeγintegers.(*)WritetwoCfunctionstoencodeanddecodeδintegers[Exercise5.9].基本上都做的很好编码理解有误精简代码第三次作业第一题Computethevectorspacesimilaritybetweenthequery“digitalcameras”andthedocument“digitalcamerasandvideocameras”byfillingouttheemptycolumnsinTable6.1(p132).AssumeN=10,000,000,logarithmictermweighting(wfcolumns)forqueryanddocument,idfweightingforthequeryonlyandcosinenormalizationforthedocumentonly.Treatandasastopword.Entertermcountsinthetfcolumns.Givethefinalsimilarityscore.第三次作业第一题query“digitalcameras”document“digitalcamerasandvideocameras”N=10,000,000查询文档dtfwfdfidfqtfwfdq*dlog(N/DF)wf*idf1+log(tf)normalize(wf)digital1110,000log(1000)=3311+log(1)=10.521.56video00100,000log(100)=2011+log(1)=10.520cameras1150,000log(200)=2.32.321+log(2)=1.30.681.564第三次作业第二题Wesuggestedthatthepostingsforstaticqualityorderingbeindecreasingorderofg(d).Whydoweusethedecreasingratherthantheincreasingorder?Howtodolinearmergeofpostingswithg(d)?WriteaCfunctiontopresentyouridea.忽略了did未保持g(d)的顺序第三次作业第二题第四次作业第二题在10000篇文档构成的文档集中，某个查询的相关文档总数为8，下面给出了某系统针对前20个有序结果的相关（R）和不相关（N）情况：RRNNNNNNRNRNNNRNNNNRA.前20篇文档的正确率：P=6/20=30%B.前20篇文档的F1值：F1=2PR/(R+P)

其中R=6/8，故F1=0.4286第四次作业第二题RRNNNNNNRNRNNNRNNNNRC.在25%召回率水平上的插值正确率：100%D.在33%召回率水平上的插值正确率：36.4%第四次作业第二题RRNNNNNNRNRNNNRNNNNRE.假定该系统所有返回结果的数目就是20，则MAP=(1+2/2+3/9+4/11+5/15+6/20+0+0)/8=0.4163第四次作业第二题RRNNNNNNRNRNNNRNNNNRF.该系统可能的最大MAP:

当第21和22篇文档都是相关文档时，MAP达到最大值。MAP=(1+2/2+3/9+4/11+5/15+6/20+7/21+8/22)/8=0.5034G.该系统可能的最小MAP:

当第9999和10000篇文档是相关文档时，MAP达到最小值。MAP=(1+2/2+3/9+4/11+5/15+6/20+7/9999+8/10000)/8=0.4165第四次作业第二题RRNNNNNNRNRNNNRNNNNRH.在一系列实验中，只有最靠前的20篇文档通过人工来判定，（E）的结果用于近似从（F）到（G）的MAP取值范围。对于上例来说，通过（E）而不是（F）和（G）来计算MAP所造成的误差有多大（采用绝对值来计算）？|MAPF-MAPG|=0.0869第四次作业第三题WriteaCprogramtohighlightthekeywordsofaninputqueryinthetextofaninputdocument,whereboththequeryanddocumenttextareinputasacharacterstring:

constchar*q=“word1word2word3”;

constchar*doc_text=“<anycopyoftextcontainingthewords>”;

(Requirements:firstsegmentthetexttosentences,thenselectthem.)要求用C语言首先分句Highlight整个查询出现的地方，而不是查询中某个单词程序应该生成一个HTML文件第五次作业第二题Givethreereasonswhyrelevancefeedbackhasbeenlittleusedinwebsearch.用户不愿意进行显示反馈（延长搜索交互时间）相关反馈会造成长查询，降低系统效率相关反馈主要用于提高召回率，而WEB检索中准确率能提升用户体验很难使普通用户理解并使用第五次作业第三题WhyispositivefeedbacklikelytobemoreusefulthannegativefeedbacktoanIRsystem?正反馈返回的相关文档中相似度更高，聚类性质强，容易带来更多的相关文档Whymightonlyusingonenonrelevantdocumentbemoreeffectivethanusingseveral?在实际检索中绝大部分文档都是不相关文档，相关文档的聚类不够强，容易相互抵消第五次作业第四题Omarhasimplementedarelevancefeedbackwebsearchsystem,whereheisgoingtodorelevancefeedbackbasedonlyonwordsinthetitletextreturnedforapage(forefficiency).Theuserisgoingtorank3results.Thefirstuser,Jinxing,queriesfor:bananaslugandthetopthreetitlesreturnedare:bananaslugAriolimaxcolumbianusSantaCruzmountainsbananaslugSantaCruzCampusMascot Jinxingjudgesthefirsttwodocumentsrelevant,andthethirdnonrelevant.AssumethatOmar’ssearchengineusestermfrequencybutnolengthnormalizationnorIDF.AssumethatheisusingtheRocchiorelevancefeedbackmechanism,withα=β=

γ=1.Showthefinalrevisedquerythatwouldberun.(Pleaselistthevectorelementsinalphabeticalorder.)第五次作业第四题Query:bananaslugDocuments:(R)bananaslugAriolimaxcolumbianus(R)SantaCru