信息檢索實驗202102-信息檢索-HW2-202102-信息檢索-HW2-沈晨玙-2019092121

實驗項目名稱：詞典、倒排記錄表和容錯式檢索的實驗實驗時間：2022年4月1日(周五)-2022年4月13日(周三)和兩個中間結果表(如下所示，不存在跳表指針)分別進行合并操作。a.跳表指針實際跳轉的次數(shù)分別是多少(也就是說，指針pl的下一步將跳到skipb.當兩個表進行合并時，倒排記錄之間的c.如果不使用跳表指針，那么倒排記錄之間的比較次數(shù)分別是多少?請在報告中附上詳細的文字說明。(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是一個正整數(shù)):“-x”、“+x”和“x”,其中，“-x”表示第一個詞項在第二個詞項的左側且間隔在x之內詞項在第二個詞項的右側且間隔在x之內，“x”表示第一個詞項與第二個詞項的間隔(左側和右側均可)在x之內。要求在以下例子上驗證算法的正確性：(ranking,filtering,-4)請在報告中附上代碼截圖(不要復制源代碼，請用截圖的方式)、運行結果截圖和詳細的文字說明。程序要有詳細的注釋。(30分)基于動態(tài)規(guī)劃(dynamicprogramming)來計算兩個字符串的編輯距離(editdistance)的算法，并用Java語言或其他常用語言實現(xiàn)該算法。要求計算以下15組單詞的編輯距請在報告中附上代碼截圖(不要復制源代碼，請用截圖的方式)、運行結果截圖和詳細的文字說明。程序要有詳細的注釋。(15分)報告寫作。要求：主要思路有明確的說明，重點代碼有詳細的注釋，行文邏輯清晰、可讀性強，報告整體寫作較為專業(yè)。(20分)(1)本次實驗課作業(yè)滿分為100分。(2)本次實驗課作業(yè)截至時間2022年4月13日(周三)22:0(3)報告正文：請在指定位置填寫，本次實驗需要單獨提交源程序文件(源程序單(4)個人信息：WORD文件名中的“姓名”、“學號”,請改為你的姓名和學號；實驗報告的首頁，請準確填寫“學院”、“專業(yè)”、“報告人”、“學號”、“班級”、“實驗報告提交時間”等信息。(5)提交方式：截至時間前，請在Blackboard平臺中提分。(7)延遲提交，不得分；如有特殊情況，請于截至日期之后的48小時內發(fā)郵件到panweike@,并在郵件中注明課程名稱、作業(yè)名稱、姓名、學(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.如果不使用跳表指針，那么倒排記錄之間的比較次數(shù)分別是多少?[<3,3>,'<5,5>,'<9,9>,<15,96>',<24,96>''<81,96>','<84,96>',<89,96>',1<92,96>',<96,96>','<97,99>','<100,99>'2、和2560120150進行合并操作：[<3,25>,'<5,25>,<9,25>','<15,25'<68,120>',1<75,120>',<81,120>,<84,120>',1<89,120>',1<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分)+++++++++++++++++++++++++++++++++++++++++++++首先定義一個數(shù)據(jù)結構值得注意的是，添加了一個skip指針。如果該節(jié)點可以跳轉，則ski點，否則為None1.根據(jù)list添加節(jié)點2.添加單節(jié)點#將list中的元素添加到鏈表中首先根據(jù)鏈表長度計算出skip指針的跳轉長度為interval=sqrt(length)interval=math.fioor(math.sgrans=#同上(不含跳表指針)defintersectWithoutSkips(p1,p2):defintersectWithoutSkips(p1,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(<'+strp2val)+!'+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調用函數(shù)，計算合并結果并輸出統(tǒng)計結果akparay:[<24,769](<7++++++++++++++++++++++++++++++++++++++++++++++++運行結果截圖和詳細的文字說明(2):帶有跳表指針的倒排記錄表和2560120150的合并操作定義list3鏈表，不加入skip指針skpcount3(4).閱讀教材《IntroductiontoInformatio鄰近搜索(proximitysearch)中的兩個倒排記錄表(postingslists)的合并算法，并用Java60個文檔(每行表示一個document,按空格切詞，文檔中的單詞全部轉換為小寫)建立positionalindex,兩個詞項之間的間距(注：相鄰的兩個詞項的間距為1)的形式包括以下三種情形(x是一個正整數(shù)):其中，“-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-]'#刪除空串#詞項出現(xiàn)過#詞項在doc_index中出現(xiàn)過hashtable[term][doc_index+1].append(term_in#詞項在doc_index中第一次出現(xiàn)hashtable[term][doc_index+1]=[term_in#詞項第一次出現(xiàn)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_doclD1]#二重循環(huán)遍歷term出現(xiàn)的位置并比較#如果pos1在符合條件的范圍內，則加入臨時答案列表Iifhip_Posl]inrange(l2[P_Pos2]+range#格式化臨時答案列表#答案為三元組<文檔ID,詞項在p1中的位置，詞項在p2中的位置>ans.append([doclD1,n[p_pos+++++++++++++++++++++++++++++++++++++++++++++++++++strl,str2,k=ranking,'filteprint(thashtablel",str1,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[str1],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[str1],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[str1l,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動態(tài)規(guī)劃(dynamicprogramming)來計算兩個字符串的編輯距離(editdistance)的算法，并用Java語言或其他常用語言實現(xiàn)該算法。要求計算以下15組單詞的編輯距離：請在報告中附上代碼截圖(不要復制源代碼，請用截圖的方式)、運行結果截圖和詳細的文字說明。程序要有詳細的注釋。(15分)+++++++++++++++++++++++++++++++++++++++++++++++++++算法思想：動態(tài)規(guī)劃所以，當sl[i]==s2[j],dp[i][