最新信息檢索導(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詞項文

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

3、s4treatme nt3它對應(yī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) 其中，每個詞項對應(yīng)的倒排記錄表的長度分別如下：倒排記錄表長度詞項eyes kaleidoscope marmalade21331287009107913skies271658tangerinetrees解答：先將詞項倒排記錄表按從小到大排序： 倒排索引表466

5、53316812詞項tangerine kaleidoscope marmalade4665387009107913eyes skies213312271658316812trees每個 OR 查詢后的保守估計的索引表大小從小到大排序：kaleidoscope OR eyes tangerine OR trees marmalade OR skies 所以該查詢的處理次序為：300321363465379571kaleidoscope 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)中，進行詞干還原從不降低正確率。b. 在布爾檢索系統(tǒng)中，進行詞干還原從不降低召回率。c. 詞干還原會增加詞項詞典的大小。d. 詞干還原應(yīng)該在構(gòu)建索引時調(diào)用，而不應(yīng)在查詢處理時調(diào)用。解答：A錯，因為詞干還原相當于擴充出同一個詞干表示的多個詞，會降低正確率。B對C錯，詞干還原的目的是為了減少屈折變化的形式，并且有時會將派生詞轉(zhuǎn)化為基本形式， 會減少詞項詞典的大小。D錯，應(yīng)該

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

8、對數(shù)字之間只比較1次，而不是圖2-10算法中的可能多次比較】對于兩個詞組成的查詢，其中一個詞（項）的倒排記錄表包含下面16個文檔ID:4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180而另一個詞（項）對應(yīng)的倒排記錄表僅僅包含一個文檔ID: 47請分別采用如下兩種策略進行倒排記錄表合并并計算所需要的比較次數(shù)，同時簡要地說明計算的正確性。a. 使用標準的倒排記錄表。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)表指針往后跳四個元素，將列表整理如下：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寫出由詞項 mama生成的輪排索引詞匯表中的條目。解答：mama$ama$mma$maa$mam7. 習(xí)題3-8計算paris和alice之間的編輯距離，給出類似于圖 3-5中的算法結(jié)果，其中的5 x 5矩 包含每個前綴子串之間的計算結(jié)果。解答：8. 習(xí)題3-11考慮四詞查詢 catched

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

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

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