信息檢索實(shí)驗(yàn)202102-信息檢索-HW2-202102-信息檢索-HW2-沈晨玙-2019092121

實(shí)驗(yàn)項(xiàng)目名稱：詞典、倒排記錄表和容錯(cuò)式檢索的實(shí)驗(yàn)實(shí)驗(yàn)時(shí)間：2022年4月1日(周五)-2022年4月13日(周三)和兩個(gè)中間結(jié)果表(如下所示，不存在跳表指針)分別進(jìn)行合并操作。a.跳表指針實(shí)際跳轉(zhuǎn)的次數(shù)分別是多少(也就是說，指針pl的下一步將跳到skipb.當(dāng)兩個(gè)表進(jìn)行合并時(shí)，倒排記錄之間的c.如果不使用跳表指針，那么倒排記錄之間的比較次數(shù)分別是多少?請?jiān)趫?bào)告中附上詳細(xì)的文字說明。(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請問哪些文檔和以下的查詢匹配?其中引號內(nèi)的每個(gè)表達(dá)式都是一個(gè)短語查詢。a.“angelsfear”b.“angelsfeartotread”c.“angelsfeartotread”AND“foolsrushin”請?jiān)趫?bào)告中附上詳細(xì)的文字說明。(10分)基于跳表指針(skippointers)的倒排記錄表(postingslists)合并算法，并用Java語言或請?jiān)趫?bào)告中附上代碼截圖(不要復(fù)制源代碼，請用截圖的方式)、運(yùn)行結(jié)果截圖和詳細(xì)的文字說明。程序要有詳細(xì)的注釋。(4).閱讀教材《IntroductiontoInformationRetrieval》第42頁Fig鄰近搜索(proximitysearch)中的兩個(gè)倒排記錄表(postingslists)的合并算法，并用Java60個(gè)文檔(每行表示一個(gè)document,按空格切詞，文檔中的單positionalindex,兩個(gè)詞項(xiàng)之間的間距(注：相鄰的兩個(gè)詞項(xiàng)的間距為1)的形式包括以下三種情形(x是一個(gè)正整數(shù)):“-x”、“+x”和“x”,其中，“-x”表示第一個(gè)詞項(xiàng)在第二個(gè)詞項(xiàng)的左側(cè)且間隔在x之內(nèi)詞項(xiàng)在第二個(gè)詞項(xiàng)的右側(cè)且間隔在x之內(nèi)，“x”表示第一個(gè)詞項(xiàng)與第二個(gè)詞項(xiàng)的間隔(左側(cè)和右側(cè)均可)在x之內(nèi)。要求在以下例子上驗(yàn)證算法的正確性：(ranking,filtering,-4)請?jiān)趫?bào)告中附上代碼截圖(不要復(fù)制源代碼，請用截圖的方式)、運(yùn)行結(jié)果截圖和詳細(xì)的文字說明。程序要有詳細(xì)的注釋。(30分)基于動態(tài)規(guī)劃(dynamicprogramming)來計(jì)算兩個(gè)字符串的編輯距離(editdistance)的算法，并用Java語言或其他常用語言實(shí)現(xiàn)該算法。要求計(jì)算以下15組單詞的編輯距請?jiān)趫?bào)告中附上代碼截圖(不要復(fù)制源代碼，請用截圖的方式)、運(yùn)行結(jié)果截圖和詳細(xì)的文字說明。程序要有詳細(xì)的注釋。(15分)報(bào)告寫作。要求：主要思路有明確的說明，重點(diǎn)代碼有詳細(xì)的注釋，行文邏輯清晰、可讀性強(qiáng)，報(bào)告整體寫作較為專業(yè)。(20分)(1)本次實(shí)驗(yàn)課作業(yè)滿分為100分。(2)本次實(shí)驗(yàn)課作業(yè)截至?xí)r間2022年4月13日(周三)22:0(3)報(bào)告正文：請?jiān)谥付ㄎ恢锰顚?，本次?shí)驗(yàn)需要單獨(dú)提交源程序文件(源程序單(4)個(gè)人信息：WORD文件名中的“姓名”、“學(xué)號”,請改為你的姓名和學(xué)號；實(shí)驗(yàn)報(bào)告的首頁，請準(zhǔn)確填寫“學(xué)院”、“專業(yè)”、“報(bào)告人”、“學(xué)號”、“班級”、“實(shí)驗(yàn)報(bào)告提交時(shí)間”等信息。(5)提交方式：截至?xí)r間前，請?jiān)贐lackboard平臺中提分。(7)延遲提交，不得分；如有特殊情況，請于截至日期之后的48小時(shí)內(nèi)發(fā)郵件到panweike@,并在郵件中注明課程名稱、作業(yè)名稱、姓名、學(xué)(8)期末考試階段補(bǔ)交無效。++++++++++++++++++++++++++++++++++++++++++++++++1、和3599699100101進(jìn)行合并操作：比較到24與96時(shí)，24擁有skip指針且75<96,因此第1次跳轉(zhuǎn)；75擁有skip指針且92<96,因此第2次跳轉(zhuǎn)；92擁有skip指針但是115>96,結(jié)束跳轉(zhuǎn)。2、和2560120150進(jìn)行合并操作：比較到3與25時(shí)，3擁有skip指針且24<25,因此第1次跳轉(zhuǎn)；24擁有skip指針且75>25,結(jié)束跳轉(zhuǎn)。比較到75與120時(shí)，75擁有skip指針且92<120,因此第2次跳轉(zhuǎn)；92擁有skip指針且115<120,因此第2次跳轉(zhuǎn)；++++++++++++++++++++++++++++++++++++++++++++++++1、和3599699100101進(jìn)行合并操作：'<97,99>',<100,99>,<100,100>'2、和2560120150進(jìn)行合并操作：[<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進(jìn)行合并操作：[<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).下面給出的是一個(gè)位置索引的一部分，格式為：<position1,position2,…>;doc2:<position1,posit請問哪些文檔和以下的查詢匹配?其中引號內(nèi)的每個(gè)表達(dá)式都是一個(gè)短語查詢。a.“angelsfear”b.“angelsfeartotread”c.“angelsfeartotread”AND“foolsrushin”請?jiān)趫?bào)告中附上詳細(xì)的文字說明。(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.與第二組結(jié)果取AND,因此最終結(jié)果為文檔4(3).閱讀教材《IntroductiontoInformationRetrieval》第37頁Figure2.10中所描述的基于跳表指針(skippointers)的倒排記錄表(postingslists)合并算法，并用請?jiān)趫?bào)告中附上代碼截圖(不要復(fù)制源代碼，請用截圖的方式)、運(yùn)行結(jié)果截圖和詳細(xì)的文字說明。程序要有詳細(xì)的注釋。(10分)+++++++++++++++++++++++++++++++++++++++++++++首先定義一個(gè)數(shù)據(jù)結(jié)構(gòu)值得注意的是，添加了一個(gè)skip指針。如果該節(jié)點(diǎn)可以跳轉(zhuǎn)，則ski點(diǎn)，否則為None1.根據(jù)list添加節(jié)點(diǎn)2.添加單節(jié)點(diǎn)#將list中的元素添加到鏈表中首先根據(jù)鏈表長度計(jì)算出skip指針的跳轉(zhuǎn)長度為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++++++++++++++++++++++++++++++++++++++++++++++++運(yùn)行結(jié)果截圖和詳細(xì)的文字說明(1):帶有跳表指針的倒排記錄表和3599699100101的合并操作定義兩個(gè)鏈表，并為list1加入skip指針，list2不加skip指針ist2.addNodes([3,5,9調(diào)用函數(shù)，計(jì)算合并結(jié)果并輸出統(tǒng)計(jì)結(jié)果akparay:[<24,769](<7++++++++++++++++++++++++++++++++++++++++++++++++運(yùn)行結(jié)果截圖和詳細(xì)的文字說明(2):帶有跳表指針的倒排記錄表和2560120150的合并操作定義list3鏈表，不加入skip指針skpcount3(4).閱讀教材《IntroductiontoInformatio鄰近搜索(proximitysearch)中的兩個(gè)倒排記錄表(postingslists)的合并算法，并用Java60個(gè)文檔(每行表示一個(gè)document,按空格切詞，文檔中的單詞全部轉(zhuǎn)換為小寫)建立positionalindex,兩個(gè)詞項(xiàng)之間的間距(注：相鄰的兩個(gè)詞項(xiàng)的間距為1)的形式包括以下三種情形(x是一個(gè)正整數(shù)):其中，“-x”表示第一個(gè)詞項(xiàng)在第二個(gè)詞項(xiàng)的左側(cè)且間隔在x之內(nèi)，“+x”表示第一個(gè)側(cè)和右側(cè)均可)在x之內(nèi)。要求在以下例子上驗(yàn)證算法的正確性：(ranking,filtering,-4)(ranking,filtering,-5),(ranking,filtering,-6),(ranking,filtering,-7),(heteroge+2),(recommendation,b請?jiān)趫?bào)告中附上代碼截圖(不要復(fù)制源代碼，請用截圖的方式)、運(yùn)行結(jié)果截圖和++++++++++++++++++++++++++++++++++++++++++++++++#打開文件#打開文件#讀取文章，并刪除每行結(jié)尾的換行符doc=pd.Series(tread().spli#轉(zhuǎn)換為小寫，并使用正則表達(dá)式進(jìn)行切割doc=doc.apply(lambdax:re.split('[^a-ZA-Z-]'#刪除空串#詞項(xiàng)出現(xiàn)過#詞項(xiàng)在doc_index中出現(xiàn)過hashtable[term][doc_index+1].append(term_in#詞項(xiàng)在doc_index中第一次出現(xiàn)hashtable[term][doc_index+1]=[term_in#詞項(xiàng)第一次出現(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):#首先查找兩個(gè)列表共同的DoclDdoclD1,doclD2=['listi][p_doclD1]#二重循環(huán)遍歷term出現(xiàn)的位置并比較#如果pos1在符合條件的范圍內(nèi)，則加入臨時(shí)答案列表Iifhip_Posl]inrange(l2[P_Pos2]+range#格式化臨時(shí)答案列表#答案為三元組<文檔ID,詞項(xiàng)在p1中的位置，詞項(xiàng)在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)來計(jì)算兩個(gè)字符串的編輯距離(editdistance)的算法，并用Java語言或其他常用語言實(shí)現(xiàn)該算法。要求計(jì)算以下15組單詞的編輯距離：請?jiān)趫?bào)告中附上代碼截圖(不要復(fù)制源代碼，請用截圖的方式)、運(yùn)行結(jié)果截圖和詳細(xì)的文字說明。程序要有詳細(xì)的注釋。(15分)+++++++++++++++++++++++++++++++++++++++++++++++++++算法思想：動態(tài)規(guī)劃所以，當(dāng)sl[i]==s2[j],dp[i][