1、精選優質文檔-傾情為你奉上信息檢索導論課后練習答案王斌最后更新日期 2013/9/28第一章 布爾檢索習題1-1 *畫出下列文檔集所對應的倒排索引（參考圖1-3中的例子）。文檔 1 new home sales top forecasts文檔 2 home sales rise in july文檔 3 increase in home sales in july文檔 4 july new home sales rise解答：forecasts->1home->1 à2 à3 à4in->2 à3increase->3july-&g

2、t;2 à3 à4new->1 à4rise->2 à4sales->1 à2 à 3 à4top->1習題1-2 *考慮如下幾篇文檔：文檔1 breakthrough drug for schizophrenia文檔2 new schizophrenia drug文檔3 new approach for treatment of schizophrenia文檔4 new hopes for schizophrenia patientsa. 畫出文檔集對應的詞項文檔矩陣；解答：文檔1文檔2文檔3文檔4

3、approach0010breakthrough1000drug1100for1011hopes0001new0111of0010patients0001schizophrenia1111treatment0010b. 畫出該文檔集的倒排索引（參考圖 1-3中的例子）。解答：參考a。習題1-3 *對于習題1-2中的文檔集，如果給定如下查詢，那么返回的結果是什么？a. schizophrenia AND drug解答：文檔1，文檔2b. for AND NOT (drug OR approach）解答：文檔4習題1-4 * 對于如下查詢，能否仍然在O(x+y)次內完成？其中x和y分別是Brutu

4、s和Caesar所對應的倒排記錄表長度。如果不能的話，那么我們能達到的時間復雜度是多少？a. Brutus AND NOT Caesarb. Brutus OR NOT Caesar解答：a. 可以在O(x+y)次內完成。通過集合的減操作即可。具體做法參考習題1-11。b. 不能。不可以在O(x+y)次內完成。因為NOT Caesar的倒排記錄表需要提取其他所有詞項對應的倒排記錄表。所以需要遍歷幾乎全體倒排記錄表，于是時間復雜度即為所有倒排記錄表的長度的和N，即O(N) 或者說O(x+N-y)。習題1-5 * 將倒排記錄表合并算法推廣到任意布爾查詢表達式，其時間復雜度是多少？比如，對于查詢c.

5、 (Brutus OR Caesar) AND NOT (Antony OR Cleopatra)我們能在線性時間內完成合并嗎？這里的線性是針對什么來說的？我們還能對此加以改進嗎？解答：時間復雜度為O(qN)，其中q為表達式中詞項的個數，N為所有倒排記錄表長度之和。也就是說可以在詞項個數q及所有倒排記錄表長度N的線性時間內完成合并。由于任意布爾表達式處理算法復雜度的上界為O(N)，所以上述復雜度無法進一步改進。習題1-6 *假定我們使用分配律來改寫有關AND和OR的查詢表達式。12a. 通過分配律將習題1-5中的查詢寫成析取范式；b. 改寫之后的查詢的處理過程比原始查詢處理過程的效率高還是低？

6、c. 上述結果對任何查詢通用還是依賴于文檔集的內容和詞本身？解答：a. 析取范式為：(Brutus And Not Anthony And Not Cleopatra) OR (Caesar AND NOT Anthony AND NOT Cleopatra)b. 這里的析取范式處理比前面的合取范式更有效。這是因為這里先進行AND操作(括號內)，得到的倒排記錄表都不大，再進行OR操作效率就不會很低。而前面需要先進行OR操作，得到的中間倒排記錄表會更大一些。c. 上述結果不一定對，比如兩個罕見詞A和B構成的查詢 (A OR B) AND NOT(HONG OR KONG)，假設HONG KONG

7、一起出現很頻繁。此時合取方式可能處理起來更高效。如果在析取范式中僅有詞項的非操作時，b中結果不對。習題 1-7 *請推薦如下查詢的處理次序。d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes）其中，每個詞項對應的倒排記錄表的長度分別如下：詞項 倒排記錄表長度eyes 213 312kaleidoscope 87 009marmalade 107 913skies 271 658tangerine 46 653trees 316 812解答：由于：(tangerine OR trees) è

8、; 46653+ = (marmalade OR skies)è + = (kaleidoscope OR eyes）è 87009+ = 30321 所以推薦處理次序為：(kaleidoscope OR eyes）AND (tangerine OR trees) AND (marmalade OR skies)習題1-8* 對于查詢e. friends AND romans AND (NOT countrymen)如何利用countrymen的文檔頻率來估計最佳的查詢處理次序？特別地，提出一種在確定查詢順序時對邏輯非進行處理的方法。解答：令friends、romans和c

9、ountrymen的文檔頻率分別為x、y、z。如果z極高，則將N-z作為NOT countrymen的長度估計值，然后按照x、y、N-z從小到大合并。如果z極低，則按照x、y、z從小到大合并。習題 1-9 *對于邏輯與構成的查詢，按照倒排記錄表從小到大的處理次序是不是一定是最優的？如果是，請給出解釋；如果不是，請給出反例。解答：不一定。比如三個長度分別為x,y,z的倒排記錄表進行合并，其中x>y>z，如果x和y的交集為空集，那么有可能先合并x、y效率更高。習題 1-10 *對于查詢x OR y，按照圖1-6的方式，給出一個合并算法。解答：1 answer<- ( )2 whi

10、le p1!=NIL and p2!=NIL3 do if docID(p1)=docID(p2)4 then ADD(answer,docID(p1)5p1<- next(p1)6 p2<-next(p2)7 else if docID(p1)<docID(p2)8 then ADD(answer,docID(p1)9 p1<- next(p1)10 else ADD(answer,docID(p2)11p2<-next(p2)12 if p1!=NIL / x還有剩余 13 then while p1!=NIL do ADD (answer, docID(p1

11、)14 else while p2!=NIL do ADD(answer,docID(p2)15 return(answer) 習題 1-11 * 如何處理查詢x AND NOT y？為什么原始的處理方法非常耗時？給出一個針對該查詢的高效合并算法。解答：由于NOT y幾乎要遍歷所有倒排表，因此如果采用列舉倒排表的方式非常耗時。可以采用兩個有序集合求減的方式處理 x AND NOT y。算法如下：Meger(p1,p2)1answer ()2while p1!=NIL and p2!=NIL3do if docID(p1) =docID(p2)4thenp1ßnext(p1)5p2&#

12、223;next(p2)6else if docID(p1)<docID(p2)7thenADD(answer, docID(p1)8p1ßnext(p1)9elseADD(answer, docID(p2)10p2ßnext(p2)11 if p1!=NIL / x還有剩余 12 then while p1!=NIL do ADD (answer, docID(p1)13 return(answer) 習題 1-12 *利用Westlaw系統的語法構造一個查詢，通過它可以找到professor、teacher或lecturer中的任意一個詞，并且該詞和動詞expla

13、in在一個句子中出現，其中explain以某種形式出現。解答： professor teacher lecturer /s explain!習題 1-13 *在一些商用搜索引擎上試用布爾查詢，比如，選擇一個詞（如burglar），然后將如下查詢提交給搜索引擎(i) burglar；(ii) burglar AND burglar；(iii) burglar OR burglar。對照搜索引擎返回的總數和排名靠前的文檔，這些結果是否滿足布爾邏輯的意義？對于大多數搜索引擎來說，它們往往不滿足。你明白這是為什么嗎？如果采用其他詞語，結論又如何？比如以下查詢 (i) knight；(ii) conqu

14、er；(iii) knight OR conquer。第二章 詞匯表和倒排記錄表習題 2-1 *請判斷如下說法是否正確。a. 在布爾檢索系統中，進行詞干還原從不降低正確率。b. 在布爾檢索系統中，進行詞干還原從不降低召回率。c. 詞干還原會增加詞項詞典的大小。d. 詞干還原應該在構建索引時調用，而不應在查詢處理時調用。解答： a錯 b 對 c錯 d 錯習題2-7 *考慮利用如下帶有跳表指針的倒排記錄表和一個中間結果表（如下所示，不存在跳表指針）進行合并操作。3589959799100101采用圖2-10所示的倒排記錄表合并算法，請問：a. 跳表指針實際跳轉的次數是多少（也就是說，指針p1的下一

15、步將跳到skip（p1）？一次，24>75b. 當兩個表進行合并時，倒排記錄之間的比較次數是多少？【如下答案不一定正確，有人利用程序計算需要21次，需要回到算法，本小題不扣分，下面不考慮重新比較同意對數字】解答： 18次： <3,3>, <5,5>, <9,89>, <15,89>,<24,89>,<75,89>,<92,89>,<81,89>,<84,89>,<89,89>,<92,95>,<115,95>,<96,95>,<

16、96,97>,<97,97>,<100,99>,<100,100><115,101>c. 如果不使用跳表指針，那么倒排記錄之間的比較次數是多少？解答： 19次： <3,3>,<5,5>,<9,89>,<15,89>,<24,89>,<39,89>,<60,89>,<68,89>,<75,89>,<81,89>,<84,89>,<89,89><92,95>, <96,95>,&

17、lt;96,97>,<97,97>,<100,99>,<100,100>,<115,101>習題 2-9 *下面給出的是一個位置索引的一部分，格式為：詞項: 文檔1: 位置1, 位置2, ; 文檔2: 位置1, 位置2, 。angels: 2: 36,174,252,651; 4: 12,22,102,432; 7: 17;fools: 2: 1,17,74,222; 4: 8,78,108,458; 7: 3,13,23,193;fear: 2: 87,704,722,901; 4: 13,43,113,433; 7: 18,328,52

18、8;in: 2: 3,37,76,444,851; 4: 10,20,110,470,500; 7: 5,15,25,195;rush: 2: 2,66,194,321,702; 4: 9,69,149,429,569; 7: 4,14,404;to: 2: 47,86,234,999; 4: 14,24,774,944; 7: 199,319,599,709;tread: 2: 57,94,333; 4: 15,35,155; 7: 20,320;where: 2: 67,124,393,1001; 4: 11,41,101,421,431; 7: 16,36,736;那么哪些文檔和以下的查

19、詢匹配？其中引號內的每個表達式都是一個短語查詢。a. “fools rush in”。解答： 文檔2、4、7b. “fools rush in” AND “angels fear to tread”。解答： 文檔4第三章 詞典及容錯式檢索習題 3-5再次考慮3.2.1節中的查詢fi*mo*er，如果采用2-gram索引的話，那么對應該查詢應該會產生什么樣的布爾查詢？你能否舉一個詞項的例子，使該詞匹配3.2.1節的輪排索引查詢，但是并不滿足剛才產生的布爾查詢？解答： 2-gram索引下的布爾查詢：$f AND fi AND mo AND er AND r$ 詞項filibuster(海盜)滿足

20、3.2.1節的輪排索引查詢，但是并不滿足上述布爾查詢習題 3-7如果 |si | 表示字符串si的長度，請證明s1和s2的編輯距離不可能超過max|s1|, |s2|。證明：不失一般性，假設|s1|<= |s2|，將s1轉換為s2的一種做法為：將s1中的每個字符依次替換為s2中的前|s1|個字符，然后添加s2的后|s2|-|s1|個字符，上述操作的總次數為|s2|= max|s1|, |s2|，根據編輯距離的定義，其應該小于|s2|= max|s1|, |s2|習題 3-8計算paris和 alice之間的編輯距離，給出類似于圖3-5中的算法結果，其中的5 × 5 矩陣包含每個

21、前綴子串之間的計算結果。解答：57習題 3-11考慮四詞查詢catched in the rye，假定根據獨立的詞項拼寫校正方法，每個詞都有5個可選的正確拼寫形式。那么，如果不對空間進行縮減的話，需要考慮多少可能的短語拼寫形式（提示：同時要考慮原始查詢本身，也就是每個詞項有6種變化可能）？解答：6*6*6*6=1296習題 3-14找出兩個拼寫不一致但soundex編碼一致的專有名詞。解答：Mary, Mira (soundex相同)，本題答案不唯一，可能有其他答案，但是soundex編碼必須一致。第四章 索引構建習題 4-1如果需要T log2 T次比較（T是詞項ID文檔ID對的數目），每次

22、比較都有兩次磁盤尋道過程。假定使用磁盤而不是內存進行存儲，并且不采用優化的排序算法（也就是說不使用前面提到的外部排序算法），那么對于Reuters-RCV1構建索引需要多長時間？計算時假定采用表4-1中的系統參數。解答：對于Reuters-RCV1，T=108因此排序時間(文檔分析時間可以忽略不計)為：2*(108*log2108)*5*10-3s = s = 7382 h=308 day習題 4-3對于n = 15個數據片，r = 10個分區文件，j = 3個詞項分區，假定使用的集群的機器的參數如表4-1所示，那么在MapReduce構架下對Reuters-RCV1語料進行分布式索引需要多長

23、時間？【給助教：教材不同印刷版本表4-2不一樣，不同同學用的不同版本，還有本題過程具有爭議。暫不扣分】解答【整個計算過程是近似的，要了解過程】：(一)、MAP階段【讀入語料(已經不帶XML標記信息了，參考表5-6)，詞條化，寫入分區文件】： (1) 讀入語料：基于表4-2，Reuters RCV1共有8*105篇文檔，每篇文檔有200詞條，每個詞條(考慮標點和空格)占6B，因此整個語料庫的大小為 8*105*200*6=9.6*108B （近似1GB，注表4-2對應于表5-1第3行的數據，而那里的數據已經經過 去數字 處理，因此實際的原始文檔集大小應該略高于0.96G，這里近似計算，但是不要認

24、為沒有處理就得到表5-1第3行的結果）將整個語料庫分成15份，則每份大小為9.6*108/15 B每一份讀入機器的時間為：9.6*108/15*2*10-8=1.28s(2) 詞條化：每一份語料在機器上進行詞條化處理，得到8*105*200=1.6*108個詞項ID-文檔ID對(參考表4-2和圖4-6，注意此時重復的 詞項ID-文檔ID對 還沒有處理)，共占1.6*108*8=1.28*109個字節，詞條化的時間暫時忽略不計【從題目無法得到詞條化這一部分時間，從表5-1看詞條化主要是做了去數字和大小寫轉換，當然也感覺這一部分的處理比較簡單，可以忽略】。(3) 寫入分區文件：每一份語料得到的詞項

25、ID-文檔ID (Key-Value)存儲到分區所花的時間為： (1.28*109/15)*2*10-8=1.71s(4) MAP階段時間：由于分成15份，但只有10臺機器進行MAP操作，所以上述MAP操作需要兩步，因此，整個MAP過程所需時間為 (1.28+1.71)*2=6.0s(二)、REDUCE階段【讀入分區文件，排序，寫入倒排索引】： (1) 讀入分區文件【讀入過程中已經實現所有Key-Value對中的Value按Key聚合，即變成Key, list(V1,V2.)。聚合過程在內存中實現，速度很快，該時間不計。另外，網絡傳輸時間這里也不計算】：根據表4-2，所有倒排記錄的數目為1.6

26、*108，因此3臺索引器上每臺所分配的倒排記錄數目為 1.6*108/3,而每條記錄由4字節詞項ID和4字節文檔ID組成，因此每臺索引器上需要讀入的倒排記錄表數據為 1.28*109/3字節。于是，每臺索引器讀數據的時間為 1.28*109/3*2*10-8=8.5s(2) 排序：每臺索引器排序所花的時間為 1.6*108/3*log2(1.6*108/3)*10-8=13.7s(3) 寫入倒排索引文件【此時倒排文件已經實現文檔ID的去重，假定只存儲詞項ID和文檔ID列表，并不存儲其他信息(如詞項的DF及在每篇文檔中的TF還有指針等等)】：需要寫入磁盤的索引大小為(據表4-2，詞項總數為4*1

27、05個) 4*105/3*4+108/3*4=4/3*108字節索引寫入磁盤的時間為：4/3*108*2*10-8=2.7s(4) REDUCE階段時間為： 8.5+13.7+2.7=24.9(三) 因此，整個分布式索引的時間約為6.0+8.5+13.7+2.7=30.9s 第五章 索引壓縮習題 5-2估計Reuters-RCV1文檔集詞典在兩種不同按塊存儲壓縮方法下的空間大小。其中，第一種方法中k = 8，第二種方法中k = 16。解答：每8個詞項會節省7*3個字節，同時增加8個字節，于是每8個詞項節省7*3-8=13字節，所有詞項共節省13*/8=650K，因此，此時索引大小為7.6MB-

28、0.65MB=6.95MB每16個詞項會節省15*3個字節，同時增加16個字節，于是每16個詞項節省15*3-16=29字節，所有詞項共節省29*/16=725K，因此，此時索引大小為7.6MB-0.725MB=6. 875MB 習題 5-6考慮倒排記錄表（4, 10, 11, 12, 15, 62, 63, 265, 268, 270, 400）及其對應的間距表（4, 6, 1, 1, 3, 47, 1, 202,3, 2, 130）。假定倒排記錄表的長度和倒排記錄表分開獨立存儲，這樣系統能夠知道倒排記錄表什么時候結束。采用可變字節碼：(i) 能夠使用1字節來編碼的最大間距是多少？(ii)

29、能夠使用2字節來編碼的最大間距是多少？(iii) 采用可變字節編碼時，上述倒排記錄表總共需要多少空間（只計算對這些數字序列進行編碼的空間消耗）？解答： (i) 27-1=127 (答128也算對，因為不存在0間距，0即可表示間距1，)(ii) 214-1=16383 (答16384也算對)(iii) 1+1+1+1+1+1+1+2+1+1+2=13 習題 5-8 *對于下列采用 編碼的間距編碼結果，請還原原始的間距序列及倒排記錄表。解答： 1110 001; 110 10; 10 1; 11011; 110 111001; 110; 11; ; 1119; 6; 3; 32+16+8+2+1=

30、59; 79; 15;18;77;84 第六章 文檔評分、詞項權重計算及向量空間模型習題 6-10考慮圖6-9中的3篇文檔Doc1、Doc2、Doc3中幾個詞項的tf情況，采用圖6-8中的idf值來計算所有詞項car、auto、insurance及best的tf-idf值。Doc1Doc2Doc3car27424auto3330insurance033329best14017圖6-9習題 6-10中所使用的tf值解答：idfcar=1.65，idfauto=2.08，idfinsurance=1.62，idfbest=1.5， 于是，各詞項在各文檔中的tf-idf結果如下表：Doc1Doc2D

31、oc3car27*1.65=44.554*1.65=6.624*1.65=39.6auto3*2.08=6.2433*2.08=68.640insurance033*1.62=53.46329*1.62=46.98best14*1.5=210創業首先要有“風險意識”，要能承受住風險和失敗。還要有責任感，要對公司、員工、投資者負責。務實精神也必不可少，必須踏實做事；17*1.5=25.5習題 6-12公式（6-7）中對數的底對公式（6-9）會有什么影響？對于給定查詢來說，對數的底是否會對文檔的排序造成影響？4、宏觀營銷環境分析附件（一）：解答：沒有影響。 假定idf采用與(6-7)不同的底x計算

32、，根據對數換底公式有。功能性手工藝品。不同的玉石具有不同的功效，比如石榴石可以促進血液循環，改善風濕和關節炎；白水晶則可以增強記憶力；茶晶能夠幫助鎮定情緒，緩解失眠、頭昏等癥狀。顧客可以根據自己的需要和喜好自行搭配，每一件都獨一無二、與眾不同。idft(x)=logx(N/dft)=log(N/dft)/logx=idft/logx，在大學生對DIY手工藝品價位調查中，發現有46% 的女生認為在十元以下的價位是可以接受；48% 的認為在10-15元；6% 的則認為50-100元能接受。如圖1-2所示由于idft(x)和idft之間只相差一個常數因子1/logx，在公式(6-9)的計算中該常數可

33、以作為公因子提出，因此文檔的排序不會改變。8、你是如何得志DIY手工藝制品的？這里有營業員們向顧客們示范著制作各種風格炯異的飾品，許多顧客也是學得不亦樂乎。據介紹，經常光顧“碧芝”的都是些希望得到世界上“獨一無二”飾品的年輕人，他們在琳瑯滿目的貨架上挑選，然后親手串連，他們就是偏愛這種的方式，完全自助在現場，有上班族在里面精挑細選成品，有細心的小女孩在仔細盤算著用料和價錢，準備自己制作的原料。可以想見，用本來稀奇的原料，加上別具匠心的制作，每一款成品都必是獨一無二的。而這也許正是自己制造所能帶來最大的快樂吧。（二）DIY手工藝品的“熱賣化”121年輕有活力是我們最大的本錢。我們這個自己動手做的

34、小店，就應該與時尚打交道，要有獨特的新穎性，這正是我們年輕女孩的優勢。習題 6-19計算查詢digital cameras及文檔digital cameras and video cameras的向量空間相似度并將結果填入表6-1的空列中。假定N=10 000 000，對查詢及文檔中的詞項權重（wf對應的列）采用對數方法計算，查詢的權重計算采用idf，而文檔歸一化采用余弦相似度計算。將 and 看成是停用詞。請在tf列中給出詞項的出現頻率，并計算出最后的相似度結果。表6-1習題6-19中的余弦相似度計算300元以下 300400元 400500 500元以上詞查詢文檔tfwfdfidfqi=w

35、f-idftfwfdi=歸一化的wfdigital10 000video100 000cameras50 000解答：【本質上這里沒有考慮查詢向量的歸一化，即沒有考慮查詢向量的大小，嚴格上不是余弦相似度】詞查詢文檔tfwfdfidfqi=wf-idftfwfdi=歸一化的wfdigital1110 00033110.520video00100 00020110.5203.112cameras1150 0002.3012.30121.3010.677習題 6-23考慮習題 6-10中4個詞項和3篇文檔中的tf和idf值，采用如下權重計算機制來計算獲得得分最高的兩篇文檔：(i) nnn.atc ；

36、(ii) ntc.atc。解答：(i) 根據題意文檔采用nnn，查詢采用atc，然后計算內積，于是有：詞項查詢q文檔Doc1得分tfidftf-idf歸一化tf-idftfidftf-idfcar11.651.650.5602712723.310auto0.52.081.040.353313insurance11.621.620.550010best11.51.50.50914114詞項查詢q文檔Doc2得分tfidftf-idf歸一化tf-idftfidftf-idfcar11.651.650.56041432.037auto0.52.081.040.35333133insurance11.

37、621.620.55033133best11.51.50.509010 詞項查詢q文檔Doc3得分tfidftf-idf歸一化tf-idftfidftf-idfcar11.651.650.5602412438.046auto0.52.081.040.353010insurance11.621.620.55029129best11.51.50.50917117           于是，在nnn.atc下，Score(q,Doc3)>Score(q,Doc2)>Score(q,Doc1)(ii) 根據題意文檔采用n

38、tc，查詢采用atc，然后計算內積，于是有：詞項查詢q文檔Doc1得分tf(a)idftf-idf歸一化tf-idftfidftf-idf歸一化tf-idfcar11.651.650.560271.6544.550.8970.76auto0.52.081.040.35332.086.240.125insurance11.621.620.55001.6200best11.51.50.509141.5210.423詞項查詢q文檔Doc2得分tf(a)idftf-idf歸一化tf-idftfidftf-idf歸一化tf-idfcar11.651.650.56041.656.60.0750.66aut

39、o0.52.081.040.353332.0868.640.786insurance11.621.620.550331.6253.460.613best11.51.50.50901.500詞項查詢q文檔Doc3得分tf(a)idftf-idf歸一化tf-idftfidftf-idf歸一化tf-idfcar11.651.650.560241.6539.60.5950.92auto0.52.081.040.35302.0800insurance11.621.620.550291.6246.980.706best11.51.50.509171.525.50.383    

40、0; 于是，在nnn.atc下，Score(q,Doc3)>Score(q,Doc1)>Score(q,Doc2)第七章 一個完整搜索系統中的評分計算習題 7-3給定單個詞項組成的查詢，請解釋為什么采用全局勝者表（r=K）已經能夠充分保證找到前K篇文檔。如果只有s個詞項組成的查詢（s>1），如何對上述思路進行修正？解答：詞項t所對應的tf最高的r篇文檔構成t的勝者表。單詞項查詢，idf已經不起作用了(idf用于區別不同詞的先天權重)，所以此時已經足夠了。對于s個詞項組成的查詢，有idf權重了。因此，不再獨立。【這一問本人也不知道該怎么答，不扣分吧】習題 7-5重新考察習題6-

41、23中基于nnn.atc權重計算的數據，假定Doc1和Doc2的靜態得分分別是1和2。請確定在公式（7-2）下，如何對Doc3的靜態得分進行取值，才能分別保證它能夠成為查詢best car insurance的排名第一、第二或第三的結果。解答：這道題不扣分吧。整個書上有關余弦相似度的計算這塊都有問題【即按照公式(7-2) (6-12)算出的應該是0到1之間的數，但實際例子(例6-4)卻是大于1的數，例子中都沒有考慮查詢向量的大小。另外，按照習題6-23中nnn.atc算出的根本不是什么余弦相似度。整個一團亂】如果相似度先采用nnn.atc計算，最后除以文檔向量的大小，則三篇文檔的得分分別為：1

42、.39、1.47和1.68。 排名第一：g(d3)+1.68>3.47, g(d3)>1.79 排名第二：2.39< g(d3)+1.68 <3.47, 0.71< g(d3)<1.79 排名第三：0< g(d3) < 0.71 習題 7-7設定圖6-10中Doc1、Doc2和Doc3的靜態得分分別是0.25、0.5和1，畫出當使用靜態得分與歐幾里得歸一化tf值求和結果進行排序的倒排記錄表。解答：按照公式7-2計算得下表：doc1doc2doc3car1.130.591.58auto0.351.211 (0)insurance0.25 (0)1.

43、211.7best0.710.5 (0)1.41所以，倒排記錄表如下：car àdoc3 àdoc1 àdoc2auto àdoc2àdoc 3 àdoc1 【按道理，tf為零的不應該出現在倒排記錄中，有的也算對】insuranceàdoc3àdoc2àdoc1 best àdoc3àdoc1àdoc2第八章 信息檢索的評價習題 8-8 *考慮一個有4篇相關文檔的信息需求，考察兩個系統的前10個檢索結果（左邊的結果排名靠前），相關性判定的情況如下所示：系統1 R N R N

44、N N N N R R系統2 N R N N R R R N N Na. 計算兩個系統的MAP值并比較大小。b. 上述結果直觀上看有意義嗎？能否從中得出啟發如何才能獲得高的MAP得分？c. 計算兩個系統的R正確性值，并與a中按照MAP進行排序的結果進行對比。解答：a. 系統1 (1+2/3+3/9+4/10)/4=0.6 系統2 (1/2+2/5+3/6+4/7)/4=0.492 b. 相關文檔出現得越靠前越好，最好前面3-5篇之內c. 系統1的R-Precision= 0.5, 系統2 R-Precision= 0.25 習題 8-9 *在10 000篇文檔構成的文檔集中，某個查詢的相關文檔

45、總數為8，下面給出了某系統針對該查詢的前20個有序結果的相關（用R表示）和不相關（用N表示）情況，其中有6篇相關文檔：R R N N N N N N R N R N N N R N N N N Ra. 前20篇文檔的正確率是多少？P20=6/20=30%b. 前20篇文檔的F1值是多少?R20=6/8=75%，F1=3/7=0.429150c. 在25%召回率水平上的插值正確率是多少？1d. 在33%召回率水平上的插值正確率是多少？3/9=33.3%e. 假定該系統所有返回的結果數目就是20，請計算其MAP值。(1+1+3/9+4/11+5/15+6/20)/8=0.4163假定該系統返回了所

46、有的10 000篇文檔，上述20篇文檔只是結果中最靠前的20篇文檔，那么f. 該系統可能的最大MAP是多少？從第21位開始，接連兩篇相關文檔，此時可以獲得最大的MAP，此時有：(1+1+3/9+4/11+5/15+6/20+7/21+8/22)/8=0.503g. 該系統可能的最小MAP是多少？(1+1+3/9+4/11+5/15+6/20+7/9999+8/10000)/8=0.4165h. 在一系列實驗中，只有最靠前的20篇文檔通過人工來判定，(e)的結果用于近似從(f)到(g)的MAP取值范圍。對于上例來說，通過(e)而不是(f)和(g)來計算MAP所造成的誤差有多大（采用絕對值來計算）

47、？ |0.4163-(0.503+0.4165)/2|=0.043第九章 相關反饋及查詢擴展習題9-3：用戶查看了兩篇文檔d1 和 d2，并對這兩篇文檔進行了判斷：包含內容CDs cheap software cheap CDs的文檔d1為相關文檔，而內容為cheap thrills DVDs 的文檔d2為不相關文檔。假設直接使用詞項的頻率作為權重 （不進行歸一化也不加上文檔頻率因子），也不對向量進行長度歸一化。采用公式（9-3）進行Rocchio相關反饋，請問修改后的查詢向量是多少？其中 = 1， = 0.75， = 0.25。解答： 習題9-4： Omar實現了一個帶相關反饋的Web搜索系統，并且為了提高效率，系統只基于返回網頁的標題文本進行相關反饋。用戶對結果進行判定，假定第一個用