中國科學(xué)院大學(xué)現(xiàn)代信息檢索課后習(xí)題答案

1、精選優(yōu)質(zhì)文檔-傾情為你奉上信息檢索導(dǎo)論課后練習(xí)答案王斌最后更新日期 2013/9/28第一章 布爾檢索習(xí)題1-1 *畫出下列文檔集所對應(yīng)的倒排索引（參考圖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習(xí)題1-2 *考慮如下幾篇文檔：文檔1 breakthrough drug for schizophrenia文檔2 new schizophrenia drug文檔3 new approach for treatment of schizophrenia文檔4 new hopes for schizophrenia patientsa. 畫出文檔集對應(yīng)的詞項(xiàng)文檔矩陣；解答：文檔1文檔2文檔3文檔4

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

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

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

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

7、一起出現(xiàn)很頻繁。此時合取方式可能處理起來更高效。如果在析取范式中僅有詞項(xiàng)的非操作時，b中結(jié)果不對。習(xí)題 1-7 *請推薦如下查詢的處理次序。d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes）其中，每個詞項(xiàng)對應(yīng)的倒排記錄表的長度分別如下：詞項(xiàng) 倒排記錄表長度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 所以推薦處理次序?yàn)椋?kaleidoscope OR eyes）AND (tangerine OR trees) AND (marmalade OR skies)習(xí)題1-8* 對于查詢e. friends AND romans AND (NOT countrymen)如何利用countrymen的文檔頻率來估計最佳的查詢處理次序？特別地，提出一種在確定查詢順序時對邏輯非進(jìn)行處理的方法。解答：令friends、romans和c

9、ountrymen的文檔頻率分別為x、y、z。如果z極高，則將N-z作為NOT countrymen的長度估計值，然后按照x、y、N-z從小到大合并。如果z極低，則按照x、y、z從小到大合并。習(xí)題 1-9 *對于邏輯與構(gòu)成的查詢，按照倒排記錄表從小到大的處理次序是不是一定是最優(yōu)的？如果是，請給出解釋；如果不是，請給出反例。解答：不一定。比如三個長度分別為x,y,z的倒排記錄表進(jìn)行合并，其中x>y>z，如果x和y的交集為空集，那么有可能先合并x、y效率更高。習(xí)題 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) 習(xí)題 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) 習(xí)題 1-12 *利用Westlaw系統(tǒng)的語法構(gòu)造一個查詢，通過它可以找到professor、teacher或lecturer中的任意一個詞，并且該詞和動詞expla

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

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

15、步將跳到skip（p1）？一次，24>75b. 當(dāng)兩個表進(jìn)行合并時，倒排記錄之間的比較次數(shù)是多少？【如下答案不一定正確，有人利用程序計算需要21次，需要回到算法，本小題不扣分，下面不考慮重新比較同意對數(shù)字】解答： 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. 如果不使用跳表指針，那么倒排記錄之間的比較次數(shù)是多少？解答： 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>習(xí)題 2-9 *下面給出的是一個位置索引的一部分，格式為：詞項(xiàng): 文檔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、詢匹配？其中引號內(nèi)的每個表達(dá)式都是一個短語查詢。a. “fools rush in”。解答： 文檔2、4、7b. “fools rush in” AND “angels fear to tread”。解答： 文檔4第三章 詞典及容錯式檢索習(xí)題 3-5再次考慮3.2.1節(jié)中的查詢fi*mo*er，如果采用2-gram索引的話，那么對應(yīng)該查詢應(yīng)該會產(chǎn)生什么樣的布爾查詢？你能否舉一個詞項(xiàng)的例子，使該詞匹配3.2.1節(jié)的輪排索引查詢，但是并不滿足剛才產(chǎn)生的布爾查詢？解答： 2-gram索引下的布爾查詢：$f AND fi AND mo AND er AND r$ 詞項(xiàng)filibuster(海盜)滿足

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

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

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

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

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

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

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

27、05個) 4*105/3*4+108/3*4=4/3*108字節(jié)索引寫入磁盤的時間為：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 第五章 索引壓縮習(xí)題 5-2估計Reuters-RCV1文檔集詞典在兩種不同按塊存儲壓縮方法下的空間大小。其中，第一種方法中k = 8，第二種方法中k = 16。解答：每8個詞項(xiàng)會節(jié)省7*3個字節(jié)，同時增加8個字節(jié)，于是每8個詞項(xiàng)節(jié)省7*3-8=13字節(jié)，所有詞項(xiàng)共節(jié)省13*/8=650K，因此，此時索引大小為7.6MB-

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

29、能夠使用2字節(jié)來編碼的最大間距是多少？(iii) 采用可變字節(jié)編碼時，上述倒排記錄表總共需要多少空間（只計算對這些數(shù)字序列進(jìn)行編碼的空間消耗）？解答： (i) 27-1=127 (答128也算對，因?yàn)椴淮嬖?間距，0即可表示間距1，)(ii) 214-1=16383 (答16384也算對)(iii) 1+1+1+1+1+1+1+2+1+1+2=13 習(xí)題 5-8 *對于下列采用 編碼的間距編碼結(jié)果，請還原原始的間距序列及倒排記錄表。解答： 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 第六章 文檔評分、詞項(xiàng)權(quán)重計算及向量空間模型習(xí)題 6-10考慮圖6-9中的3篇文檔Doc1、Doc2、Doc3中幾個詞項(xiàng)的tf情況，采用圖6-8中的idf值來計算所有詞項(xiàng)car、auto、insurance及best的tf-idf值。Doc1Doc2Doc3car27424auto3330insurance033329best14017圖6-9習(xí)題 6-10中所使用的tf值解答：idfcar=1.65，idfauto=2.08，idfinsurance=1.62，idfbest=1.5， 于是，各詞項(xiàng)在各文檔中的tf-idf結(jié)果如下表：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創(chuàng)業(yè)首先要有“風(fēng)險意識”，要能承受住風(fēng)險和失敗。還要有責(zé)任感，要對公司、員工、投資者負(fù)責(zé)。務(wù)實(shí)精神也必不可少，必須踏實(shí)做事；17*1.5=25.5習(xí)題 6-12公式（6-7）中對數(shù)的底對公式（6-9）會有什么影響？對于給定查詢來說，對數(shù)的底是否會對文檔的排序造成影響？4、宏觀營銷環(huán)境分析附件（一）：解答：沒有影響。 假定idf采用與(6-7)不同的底x計算

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

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

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

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

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

37、621.620.55033133best11.51.50.509010 詞項(xiàng)查詢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) 根據(jù)題意文檔采用n

38、tc，查詢采用atc，然后計算內(nèi)積，于是有：詞項(xiàng)查詢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詞項(xiàng)查詢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詞項(xiàng)查詢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)第七章 一個完整搜索系統(tǒng)中的評分計算習(xí)題 7-3給定單個詞項(xiàng)組成的查詢，請解釋為什么采用全局勝者表（r=K）已經(jīng)能夠充分保證找到前K篇文檔。如果只有s個詞項(xiàng)組成的查詢（s>1），如何對上述思路進(jìn)行修正？解答：詞項(xiàng)t所對應(yīng)的tf最高的r篇文檔構(gòu)成t的勝者表。單詞項(xiàng)查詢，idf已經(jīng)不起作用了(idf用于區(qū)別不同詞的先天權(quán)重)，所以此時已經(jīng)足夠了。對于s個詞項(xiàng)組成的查詢，有idf權(quán)重了。因此，不再獨(dú)立?！具@一問本人也不知道該怎么答，不扣分吧】習(xí)題 7-5重新考察習(xí)題6-

41、23中基于nnn.atc權(quán)重計算的數(shù)據(jù)，假定Doc1和Doc2的靜態(tài)得分分別是1和2。請確定在公式（7-2）下，如何對Doc3的靜態(tài)得分進(jìn)行取值，才能分別保證它能夠成為查詢best car insurance的排名第一、第二或第三的結(jié)果。解答：這道題不扣分吧。整個書上有關(guān)余弦相似度的計算這塊都有問題【即按照公式(7-2) (6-12)算出的應(yīng)該是0到1之間的數(shù)，但實(shí)際例子(例6-4)卻是大于1的數(shù)，例子中都沒有考慮查詢向量的大小。另外，按照習(xí)題6-23中nnn.atc算出的根本不是什么余弦相似度。整個一團(tuán)亂】如果相似度先采用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 習(xí)題 7-7設(shè)定圖6-10中Doc1、Doc2和Doc3的靜態(tài)得分分別是0.25、0.5和1，畫出當(dāng)使用靜態(tài)得分與歐幾里得歸一化tf值求和結(jié)果進(jìn)行排序的倒排記錄表。解答：按照公式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為零的不應(yīng)該出現(xiàn)在倒排記錄中，有的也算對】insuranceàdoc3àdoc2àdoc1 best àdoc3àdoc1àdoc2第八章 信息檢索的評價習(xí)題 8-8 *考慮一個有4篇相關(guān)文檔的信息需求，考察兩個系統(tǒng)的前10個檢索結(jié)果（左邊的結(jié)果排名靠前），相關(guān)性判定的情況如下所示：系統(tǒng)1 R N R N

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

45、總數(shù)為8，下面給出了某系統(tǒng)針對該查詢的前20個有序結(jié)果的相關(guān)（用R表示）和不相關(guān)（用N表示）情況，其中有6篇相關(guān)文檔：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%，F(xiàn)1=3/7=0.429150c. 在25%召回率水平上的插值正確率是多少？1d. 在33%召回率水平上的插值正確率是多少？3/9=33.3%e. 假定該系統(tǒng)所有返回的結(jié)果數(shù)目就是20，請計算其MAP值。(1+1+3/9+4/11+5/15+6/20)/8=0.4163假定該系統(tǒng)返回了所

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

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