信息检索实验202102-信息检索-HW2-202102-信息检索-HW2-沈晨玙-2019092121

实验项目名称：词典、倒排记录表和容错式检索的实验实验时间：2022年4月1日(周五)-2022年4月13日(周三)和两个中间结果表(如下所示，不存在跳表指针)分别进行合并操作。a.跳表指针实际跳转的次数分别是多少(也就是说，指针pl的下一步将跳到skipb.当两个表进行合并时，倒排记录之间的c.如果不使用跳表指针，那么倒排记录之间的比较次数分别是多少?请在报告中附上详细的文字说明。(15分)<position1,position2,…>;doc2:<positionl,positangels:2:<36,174,252,651>;4:<12,22,102,432tread:2:<57,94,333>;4:<15,35,155>where:2:<67,124,393,1001>;4:<11,41,10请问哪些文档和以下的查询匹配?其中引号内的每个表达式都是一个短语查询。a.“angelsfear”b.“angelsfeartotread”c.“angelsfeartotread”AND“foolsrushin”请在报告中附上详细的文字说明。(10分)基于跳表指针(skippointers)的倒排记录表(postingslists)合并算法，并用Java语言或请在报告中附上代码截图(不要复制源代码，请用截图的方式)、运行结果截图和详细的文字说明。程序要有详细的注释。(4).阅读教材《IntroductiontoInformationRetrieval》第42页Fig邻近搜索(proximitysearch)中的两个倒排记录表(postingslists)的合并算法，并用Java60个文档(每行表示一个document,按空格切词，文档中的单positionalindex,两个词项之间的间距(注：相邻的两个词项的间距为1)的形式包括以下三种情形(x是一个正整数):“-x”、“+x”和“x”,其中，“-x”表示第一个词项在第二个词项的左侧且间隔在x之内词项在第二个词项的右侧且间隔在x之内，“x”表示第一个词项与第二个词项的间隔(左侧和右侧均可)在x之内。要求在以下例子上验证算法的正确性：(ranking,filtering,-4)请在报告中附上代码截图(不要复制源代码，请用截图的方式)、运行结果截图和详细的文字说明。程序要有详细的注释。(30分)基于动态规划(dynamicprogramming)来计算两个字符串的编辑距离(editdistance)的算法，并用Java语言或其他常用语言实现该算法。要求计算以下15组单词的编辑距请在报告中附上代码截图(不要复制源代码，请用截图的方式)、运行结果截图和详细的文字说明。程序要有详细的注释。(15分)报告写作。要求：主要思路有明确的说明，重点代码有详细的注释，行文逻辑清晰、可读性强，报告整体写作较为专业。(20分)(1)本次实验课作业满分为100分。(2)本次实验课作业截至时间2022年4月13日(周三)22:0(3)报告正文：请在指定位置填写，本次实验需要单独提交源程序文件(源程序单(4)个人信息：WORD文件名中的“姓名”、“学号”,请改为你的姓名和学号；实验报告的首页，请准确填写“学院”、“专业”、“报告人”、“学号”、“班级”、“实验报告提交时间”等信息。(5)提交方式：截至时间前，请在Blackboard平台中提分。(7)延迟提交，不得分；如有特殊情况，请于截至日期之后的48小时内发邮件到panweike@,并在邮件中注明课程名称、作业名称、姓名、学(8)期末考试阶段补交无效。++++++++++++++++++++++++++++++++++++++++++++++++1、和3599699100101进行合并操作：比较到24与96时，24拥有skip指针且75<96,因此第1次跳转；75拥有skip指针且92<96,因此第2次跳转；92拥有skip指针但是115>96,结束跳转。2、和2560120150进行合并操作：比较到3与25时，3拥有skip指针且24<25,因此第1次跳转；24拥有skip指针且75>25,结束跳转。比较到75与120时，75拥有skip指针且92<120,因此第2次跳转；92拥有skip指针且115<120,因此第2次跳转；++++++++++++++++++++++++++++++++++++++++++++++++1、和3599699100101进行合并操作：'<97,99>',<100,99>,<100,100>'2、和2560120150进行合并操作：[<3,25>','<24,25>','<75,25>,<39,25>','++++++++++++++++++++++++++++++++++++++++++++++++c.如果不使用跳表指针，那么倒排记录之间的比较次数分别是多少?[<3,3>,'<5,5>,'<9,9>,<15,96>',<24,96>''<81,96>','<84,96>',<89,96>',¹<92,96>',<96,96>','<97,99>','<100,99>'2、和2560120150进行合并操作：[<3,25>,'<5,25>,<9,25>','<15,25'<68,120>',¹<75,120>',<81,120>,<84,120>',¹<89,120>',¹<92,120>,'<96(2).下面给出的是一个位置索引的一部分，格式为：<position1,position2,…>;doc2:<position1,posit请问哪些文档和以下的查询匹配?其中引号内的每个表达式都是一个短语查询。a.“angelsfear”b.“angelsfeartotread”c.“angelsfeartotread”AND“foolsrushin”请在报告中附上详细的文字说明。(10分)++++++++++++++++++++++++++++++++++++++++++++++++a.“angelsfear”++++++++++++++++++++++++++++++++++++++++++++++++b.“angelsfeartotread”++++++++++++++++++++++++++++++++++++++++++++++++c.“angelsfeartotread”AND“foolsrushin”1.“foolsrushin”符合的文档：文档2中，fools-1rush-2文档4中，fools-8rush-9文档7中，fools-3rush-4in-5或fools-13rus2.与第二组结果取AND,因此最终结果为文档4(3).阅读教材《IntroductiontoInformationRetrieval》第37页Figure2.10中所描述的基于跳表指针(skippointers)的倒排记录表(postingslists)合并算法，并用请在报告中附上代码截图(不要复制源代码，请用截图的方式)、运行结果截图和详细的文字说明。程序要有详细的注释。(10分)+++++++++++++++++++++++++++++++++++++++++++++首先定义一个数据结构值得注意的是，添加了一个skip指针。如果该节点可以跳转，则ski点，否则为None1.根据list添加节点2.添加单节点#将list中的元素添加到链表中首先根据链表长度计算出skip指针的跳转长度为interval=sqrt(length)interval=math.fioor(math.sgrans=#同上(不含跳表指针)defintersectWithoutSkips(p¹,p2):defintersectWithoutSkips(p¹,p2):ans#如果val相同，则加入答案，指针后移#val较小的指针，如果存在skip指针，则不断向后跳直到val较大为止skipcount,comparecoskip_aray,compare_acompare_arayappend(<'+str(plval)+!'+str(pcompare_arayapPend(<'+str(plval)+i'+str(compare_arrayappend(<'+sr(plskipval)+!'+str(skip_arrayappend('<'+str(plval)+''+str(pl.skipvalcompare_arayappend(<'+str(pival)+!'+str(compare_arrayappend(<+str(plval)+f'+str(p2skiskip_aray.aPPend(<'+strp²val)+!'+st(p2.skdefintersectWithoutSkips_stat(pl,p2):defintersectWithoutSkips_stat(pl,p2):comparecount,compare_compare_arrayappend(<'+str(plval)+;'+str(p#如果va相同，则加入答案，指针后移#val较小的指针，如果存在skip指针，则不断向后跳直到val较大为止print(comparecount',cprint('compare_array!,c++++++++++++++++++++++++++++++++++++++++++++++++运行结果截图和详细的文字说明(1):带有跳表指针的倒排记录表和3599699100101的合并操作定义两个链表，并为list1加入skip指针，list2不加skip指针ist2.addNodes([3,5,9调用函数，计算合并结果并输出统计结果akparay:[<24,769](<7++++++++++++++++++++++++++++++++++++++++++++++++运行结果截图和详细的文字说明(2):带有跳表指针的倒排记录表和2560120150的合并操作定义list3链表，不加入skip指针skpcount3(4).阅读教材《IntroductiontoInformatio邻近搜索(proximitysearch)中的两个倒排记录表(postingslists)的合并算法，并用Java60个文档(每行表示一个document,按空格切词，文档中的单词全部转换为小写)建立positionalindex,两个词项之间的间距(注：相邻的两个词项的间距为1)的形式包括以下三种情形(x是一个正整数):其中，“-x”表示第一个词项在第二个词项的左侧且间隔在x之内，“+x”表示第一个侧和右侧均可)在x之内。要求在以下例子上验证算法的正确性：(ranking,filtering,-4)(ranking,filtering,-5),(ranking,filtering,-6),(ranking,filtering,-7),(heteroge+2),(recommendation,b请在报告中附上代码截图(不要复制源代码，请用截图的方式)、运行结果截图和++++++++++++++++++++++++++++++++++++++++++++++++#打开文件#打开文件#读取文章，并删除每行结尾的换行符doc=pd.Series(tread().spli#转换为小写，并使用正则表达式进行切割doc=doc.apply(lambdax:re.split('[^a-ZA-Z-]'#删除空串#词项出现过#词项在doc_index中出现过hashtable[term][doc_index+1].append(term_in#词项在doc_index中第一次出现hashtable[term][doc_index+1]=[term_in#词项第一次出现hashtable[term]={doc_index+1:[term_indprint('\t',doc_index,'',hashtable[term][doc_ipassithip_pos1]inrange(l2[P_Pos2]+ranges[0],l2[P_Pithip_pos1]inrange(l2[P_Pos2]+ranges[0],l2[P_P具体处理方式见以下完整代码：defpositionallntersect(isti,list2,k):defpositionallntersect(isti,list2,k):answhilep_doclD1<len(listil)andp_doclD2<len(ist2):#首先查找两个列表共同的DoclDdoclD1,doclD2=['listi][p_doclD¹]#二重循环遍历term出现的位置并比较#如果pos¹在符合条件的范围内，则加入临时答案列表Iifhip_Posl]inrange(l2[P_Pos2]+range#格式化临时答案列表#答案为三元组<文档ID,词项在p1中的位置，词项在p2中的位置>ans.append([doclD1,n[p_pos+++++++++++++++++++++++++++++++++++++++++++++++++++strl,str2,k=ranking,'filteprint(thashtablel",str¹,V):,haprint(hashtablel"",str2,V):;hapositionallntersect(hashtable[strl],hashhashtable[ranking!{3:[4],8:[4],12:[5],16:[5],hashtable[fitering]:{7:[7],8:[11],11:[5],12:[10],13:[4],18:[8],19:[3],22:[6],24:[857号文档中，ranking位置为7,filtering位置为11+++++++++++++++++++++++++++++++++++++++++++++++++++strl,str2,k=ranking,'filteriprint([hashtablel\",strt,V]:;hasprint(hashtablelV",str2,V):;haspositionallntersect(hashtable[str1,hashtranking!:(3:[4],8[4],12:[5],16:[5],27:[4fitering]:(7:[7],8:[11],11:[6],12:[10],13:[4],18:[8],19:[3],22:[6],24:[8],25:[7],26:[12号文档中，ranking位置为5,filtering位置为10;27号文档中，ranking位置为4,filtering位置为8;+++++++++++++++++++++++++++++++++++++++++++++++++++strl,str2,k=Tanking,'filterprint(hashitablell",stn,VI:,hasprint(hashtablell",str2,V):,haspositionallntersect(hashtable[strl],hashthashtable[ranking!:(3:[4],8:[4],12:[5],16:[5],27:[4hashtable[fltering!7:[7],8:[11],11:[5],12:[10],13:[41,18:[8],19:[3],22:[6],24:[8],25:12号文档中，ranking位置为5,filtering位置为10;27号文档中，ranking位置为4,filtering位置为8;57号文档中，ranking位置为7,filtering位置为11+++++++++++++++++++++++++++++++++++++++++++++++++++str,str2,k='ranking,fiteprint(hashtablel!",strt,V):;haprint(hashtablel"",str2,V):,haspositionallntersect(hashtable[str¹],hashtranking!{3:[4],8:[4],12:[5],16:[6],27:[4filtering!:7:[7],8:[11],11:[5],12:[10],13:[4],18:[8],19:[3],22:[6],24:[8],25:[7],26:[8号文档中，ranking位置为4,filtering位置为11;12号文档中，ranking位置为5,filtering位置为10;27号文档中，ranking位置为4,filtering位置为8;57号文档中，ranking位置为7,filtering位置为11++++++++++++++++++++++++++++++++++++++++++++++++str,str2,k=heterogeneous,"eampint(hashtablel",strl,V):,hapint(hashtablel!",str2,):,haspositlonalntersect[hashtable[str¹],hashthashtable[heterogeneous1:(3:[6],4:[8],6:[7],7:[4],12:[7],24:[5],30:[6],32:[8],33:[5],3hashtable[leaning]{t:[4],5:[5],7:[2],9:[2],10:[2],14:[3],16:[2],17:[2],19:[7],20:[7],7号文档中，heterogeneous位置为4,learning位置为2;30号文档中，heterogeneous位置为5,learning位置为3;33号文档中，heterogencous位置为5,learning位置为3;36号文档中，heterogeneous位置为6,learning位置为4;56号文档中，heterogencous位置为4,learning位置为2;++++++++++++++++++++++++++++++++++++++++++++++++str,str2,k=recommendation'str,str2,k=recommendation'Prini(hashtablel",strl,V):;hprini(hashtablell',str2,V,hashpositionallntersect(hashtable[str¹l,hashthashtablefrecommendation]:(t[7],2:[8],4:[10],5:[8],6:[5],9:[6],13:[7],14:[5],60:[6],51[4],53:[41],69:[6],49号文档中，recommendation位置为5,bias位置为7;50号文档中，recommendation位置为5,bias位置为3;(5).阅读教材《IntroductiontoInformationRetrieval》第59页Figure3.5动态规划(dynamicprogramming)来计算两个字符串的编辑距离(editdistance)的算法，并用Java语言或其他常用语言实现该算法。要求计算以下15组单词的编辑距离：请在报告中附上代码截图(不要复制源代码，请用截图的方式)、运行结果截图和详细的文字说明。程序要有详细的注释。(15分)+++++++++++++++++++++++++++++++++++++++++++++++++++算法思想：动态规划所以，当sl[i]==s2[j],dp[i][