最新信息檢索導(dǎo)論

1、信息檢索導(dǎo)論 第一次課后練習(xí)（第1講-第4講）1.習(xí)題 1-3 *對于習(xí)題1-2中的文檔集，如果給定如下查詢，那么返回的結(jié)果是什么?a. schizophre nia AND drugb. for AND NOT (drug OR approach)解答：習(xí)題1-2的文檔集如下：文檔 1 breakthrough drug for schizophre nia文檔 2 new schizophrenia drug文檔 3 new approach for treatment of schizophrenia文檔 4 new hopes for schizophrenia patients詞項(xiàng)文

2、檔對應(yīng)如下：詞項(xiàng)docID詞項(xiàng)docIdbreakthrough1approach3drug1breakthrough1for1drug1schizophre nia1drug2new2for1schizophre nia2for3drug2for4new3hopes4approach3=new2for3new3treatme nt3new4of3of3schizophre nia3patie nts4new4schizophre nia1hopes4schizophre nia2for4schizophre nia3schizophre nia4schizophre nia4patie nt

3、s4treatme nt3它對應(yīng)的倒排索引表如下:詞項(xiàng)文檔頻率倒排記錄表approach13breakthrough11drug21f 2for3f1f 3 f 4hopes1f4new3f2f 3 f 4of1f3patie nts1f4schizophre nia4f1f 2 f 3 f 4treatme nt1f3a. schizophrenia AND drug1f2f3f4schizophreniaAND drug1f2得出交集=1f2結(jié)果為文檔 1 和 2b. for AND NOT (drug OR approach) 先求 drug OR approachdrugf1f2ORa

4、pproachf3得出并集f1f2f3則 NOT(drug OR approach)f4ANDforf1f3f4得出交集f4所以結(jié)果為文檔 42. 習(xí)題 1-7 請推薦如下查詢的處理次序。d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes) 其中，每個(gè)詞項(xiàng)對應(yīng)的倒排記錄表的長度分別如下：倒排記錄表長度詞項(xiàng)eyes kaleidoscope marmalade21331287009107913skies271658tangerinetrees解答：先將詞項(xiàng)倒排記錄表按從小到大排序： 倒排索引表466

5、53316812詞項(xiàng)tangerine kaleidoscope marmalade4665387009107913eyes skies213312271658316812trees每個(gè) OR 查詢后的保守估計(jì)的索引表大小從小到大排序：kaleidoscope OR eyes tangerine OR trees marmalade OR skies 所以該查詢的處理次序?yàn)椋?00321363465379571kaleidoscope OR eyestangerine OR treesmarmalade OR skieL (tangerine OR trees) AND (kaleidosco

6、pe OR eyes) (tangerine OR trees) AND (kaleidoscope OR eyes) AND (marmalade OR skies)3. 習(xí)題2-1請判斷如下說法是否正確。a. 在布爾檢索系統(tǒng)中，進(jìn)行詞干還原從不降低正確率。b. 在布爾檢索系統(tǒng)中，進(jìn)行詞干還原從不降低召回率。c. 詞干還原會(huì)增加詞項(xiàng)詞典的大小。d. 詞干還原應(yīng)該在構(gòu)建索引時(shí)調(diào)用，而不應(yīng)在查詢處理時(shí)調(diào)用。解答：A錯(cuò)，因?yàn)樵~干還原相當(dāng)于擴(kuò)充出同一個(gè)詞干表示的多個(gè)詞，會(huì)降低正確率。B對C錯(cuò)，詞干還原的目的是為了減少屈折變化的形式，并且有時(shí)會(huì)將派生詞轉(zhuǎn)化為基本形式， 會(huì)減少詞項(xiàng)詞典的大小。D錯(cuò)，應(yīng)該

7、同時(shí)做才能保證索引中和查詢詞的匹配。4. 習(xí)題2-3如下詞經(jīng)過 Porter詞干還原工具處理后會(huì)輸出同樣的結(jié)果，你認(rèn)為哪對（幾對）詞不應(yīng)該 輸出同樣的結(jié)果？為什么？a. aba ndon/aba ndonmentb. absorbe ncy/absorbe ntc. marketi ng/marketsd. uni versity/uni versee. volume/volumes解答：c中marketing的意思為營銷，market的意思為市場，這兩個(gè)詞雖然詞干相同，但意思不同， 不應(yīng)該輸出同樣的結(jié)果。D同理，university是大學(xué)，而universe是宇宙。5. 習(xí)題2-6【注：每一

8、對數(shù)字之間只比較1次，而不是圖2-10算法中的可能多次比較】對于兩個(gè)詞組成的查詢，其中一個(gè)詞（項(xiàng)）的倒排記錄表包含下面16個(gè)文檔ID:4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180而另一個(gè)詞（項(xiàng)）對應(yīng)的倒排記錄表僅僅包含一個(gè)文檔ID: 47請分別采用如下兩種策略進(jìn)行倒排記錄表合并并計(jì)算所需要的比較次數(shù)，同時(shí)簡要地說明計(jì)算的正確性。a. 使用標(biāo)準(zhǔn)的倒排記錄表。b. 使用倒排記錄表+跳表的方式，跳表指針設(shè)在.P處。解答：A. 4,6,10,12,14,16,18,20,22,32,47 都分別和 47 比較了一次，共比較了11 次B. 調(diào)表指針設(shè)

9、在.P= 16 =4處，即列表一的調(diào)表指針往后跳四個(gè)元素，將列表整理如下：4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180紅色是有調(diào)表指針的索引，120是跳到180其中4,14,22,120,32,47分別和47比較了一次，總共比較了 6次6. 習(xí)題3-2寫出由詞項(xiàng) mama生成的輪排索引詞匯表中的條目。解答：mama$ama$mma$maa$mam7. 習(xí)題3-8計(jì)算paris和alice之間的編輯距離，給出類似于圖 3-5中的算法結(jié)果，其中的5 x 5矩 包含每個(gè)前綴子串之間的計(jì)算結(jié)果。解答：8. 習(xí)題3-11考慮四詞查詢 catched

10、in the rye，假定根據(jù)獨(dú)立的詞項(xiàng)拼寫校正方法，每個(gè)詞選的正確拼寫 形式。那么，如果不對空間進(jìn)行縮減的話，需要考慮多少可能的短語拼寫形式（提示：同時(shí)要考慮原始查詢本身，也就是每個(gè)詞項(xiàng)有6種變化可能）？解答：6*6*6*6=12969. 習(xí)題4-1如果需要Tlog2T次比較（T是詞項(xiàng)ID文檔ID對的數(shù)目），每次比較都有兩次磁盤尋道過程。 假定使用磁盤而不是內(nèi)存進(jìn)行存儲(chǔ)，并且不采用優(yōu)化的排序算法（也就是說不使用前面提到的外部排序算法），那么對于Reuters-RCV1構(gòu)建索引需要多長時(shí)間？計(jì)算時(shí)假定采用表4-1中的系統(tǒng)參數(shù)。解答：對于 Reuters-RCV1, T=108根據(jù)4-1中的系統(tǒng)

11、參數(shù)，比較時(shí)間為0.01ms=10-8s,平均尋道時(shí)間為：5ms = 5 x -10所以構(gòu)建索引的時(shí)間為：2*（10 8*log 2108）*5*10 -3s = 26575424s=7382h=308day10. 習(xí)題4-3 如表4-1所示，那么在 MapReduce構(gòu)架下對 Reuters-RCV1語料進(jìn)行分布式索引需要多長 時(shí)間？對于n = 15個(gè)數(shù)據(jù)片,r = 10個(gè)分區(qū)文件，j = 3個(gè)詞項(xiàng)分區(qū),假定使用的集群的機(jī)器的參數(shù)解答：倒排記錄夷l】lap過程甘區(qū)丈件索閒蕃g-PMapReduce分為Map和Reduce兩個(gè)子任務(wù)過程。首先是map，將輸入的數(shù)據(jù)片映射成鍵 -值對，每個(gè)分析器

12、將輸出結(jié)果存在本地的中間文 件。(1)基于表4-2, Reuters RCV1共有8*105篇文檔，每篇200詞條，每個(gè)詞條占6B,因此整個(gè) 語料庫的大小為：8*105 *200*6=9.6*108 B分成 15 份：9.6*108 /15 B每一份讀入機(jī)器的時(shí)間為：9.6*108 /15*2*10-8 =1.28s詞條化：每一份語料在機(jī)器上進(jìn)行詞條化處理，得到詞項(xiàng)ID-文檔ID對個(gè)數(shù)為：8*105 *200=1.6*108 共占字節(jié)數(shù)：1.6*108 *8=1.28*109(3)寫入分區(qū)文件：每一份語料得到的詞項(xiàng)ID-文檔ID (Key-Value)存儲(chǔ)到分區(qū)所花的時(shí)間為：(1.28*109/15)*2*10-8 =1.71s (4)MAP階段時(shí)間：10臺(tái)機(jī)器對15份語料進(jìn)行 MAP操作，整個(gè)MAP過程所需時(shí)間為(1.28+1.71)*2=6.0s REDUCE階段，讀入分區(qū)文件，排序，寫入倒排索引(1)讀入分區(qū)文件每臺(tái)索引器上需要讀入的倒排記錄表數(shù)據(jù)為1.28*109 /3字節(jié)每臺(tái)索引器讀數(shù)據(jù)的時(shí)間為1.28*109 / 3*2*10-8 =8.5s 排序：每臺(tái)索引器排序所花