好資料學(xué)習(xí)一-《信息檢索導(dǎo)論》課后練習(xí)答案王

斌

2013/9/28

最后更新日期

布爾檢索第一章

o畫出下列文檔集所對應(yīng)的倒排索引（參考圖1-3中的例子）習(xí)題1-1[*]newhomesalestopforecasts1文檔home

salesriseinjuly2文檔increaseinhomesalesinjuly3文檔julynewhomesalesrise4文檔

解答：

forecaststf------->wfdf1=wf-idfidfq.wftfwf=歸一化的d

home1digital------->iio0001?33?211?30.5204

invideo0------->0100000?2203110.5203.112

increase------->3

julycameras1------->1500002?2.301?321.30140.677

2.301

new------->1?4

rise------->?24

sales------->Doc11??2?3Doc34

Doc2

top------->1

習(xí)題考慮如下幾篇文檔：[*]1-2

breakthroughdrugforschizophrenia文檔1

newschizophreniadrug

2文檔

newapproachfortreatmentofschizophrenia文檔3

newhopesforschizophreniapatients4文檔

a.畫出文檔集對應(yīng)的詞項一文檔矩陣；

解答：

文檔1文檔2文檔3文檔4

001approach0

00breakthrough10

0110drug

1

1

for

1

0

更多精品文檔.

好資料學(xué)習(xí)---10hopes00

1011new

00Oof

1

10patients

00

1111schizophrenia

0

0

1

treatment

0

中的例子)。b.畫出該文檔集的倒排索引(參考圖1-3o解答：參考a

中的文檔集，如果給定如下查詢，那么返回的結(jié)果是什么？習(xí)題對于習(xí)題l-2schizophreniaANDdruga.2)

,文檔解答：｛文檔1

)b.forANDNOT(drugORapproach4｝

文檔解答：｛

所對應(yīng)的倒分別是Brutus和Caesar[*]對于如下查詢，能否仍然在O(x+y)次內(nèi)完成？其中x和y習(xí)題1-4排記錄表長度。

如果不能的話，那么我們能達到的時間復(fù)雜度是多少？BrutusANDNOTCaesara.

BrutusORNOTCaesar

b.

解答：次內(nèi)完成。通過集合的減操作即可。具體做法參考習(xí)題1-11。a.可以在O(x+y)的倒排記錄表需要提取其他所有

詞項對應(yīng)的倒因為NOTCaesarb.不能。不可以在O(x+y)次內(nèi)完成。排記錄表。所以需要遍歷幾乎全體倒排記錄表，于是

時間復(fù)雜度即為所有倒排記錄表的長度的和。O(x+N-y)N,即O(N)或者說

將倒排記錄表合并算法推廣到任意布爾查詢表達式，其時間復(fù)雜度是多少？比如，對于查詢習(xí)題1-5[*]

(BrutusORCaesar)ANDNOT(AntonyORCleopatra)

c.我們能在線性時間內(nèi)完成合并嗎？這里的線性是針對什么來說的？我們還能對此加以改進嗎？

也就是說可以為所有倒排記錄表長度之和。q解答：時間復(fù)雜度為O(qN),其中為表達式中詞項的個數(shù)，N的線性時間內(nèi)

完成合并。由于任意布爾表達式處理算法復(fù)雜度的上N在詞項個數(shù)q及所有倒排記錄表長度界為0(N),所以上述復(fù)雜

度無法進一步改進。

假定我們使用分配律來改寫有關(guān)AND和OR的查詢表達式。習(xí)題中的查詢寫成析取范式；a.通過分配律將習(xí)

題1-512

b.改寫之后的查詢的處理過程比原始查詢處理過程的效率高還是低？

c.上述結(jié)果對任何查詢通用還是依賴于文檔集的內(nèi)容和詞本身？

解答：析取范式為：a.(BrutusAndNotAnthonyAndNotCleopatra)OR(CaesarANDNOTAnthonyANDNOTCleopatra)

,得到的倒排記錄表都括號內(nèi)。操作這里的析取范式處理比前面的合取范式更有效。這是因為這里先進行b.ANDOR不大，再進行操作

效率就不會很低。而前面需要先進行操作，得到的中間倒排記錄表會更大一些。OR更多精品文檔.

學(xué)習(xí)-一好資料

C.上述結(jié)果不一定對，比如兩個罕見詞A和B構(gòu)成的查詢(AORB)ANDNOT(HONGORKONG),假設(shè)HONG

中結(jié)果一起出現(xiàn)很頻繁。此時合取方式可能處理起來更高效。如果在析取范式中僅有詞項的非操作時，bKONG不對“

習(xí)題1-7[*]請推薦如下查詢的處理次序。

d.(tangerineORtrees)AND(marmaladeORskies)AND(kaleidoscopeOReyes)

其中，每個詞項對應(yīng)的倒排記錄表的長度分別如下：

詞項倒排記錄表長度

213312eyes

87009kaleidoscope

107913marmalade

271658skies

tangerine46653

316812

trees

解答：由于：46653+316812=363465?(tangerineORtrees)

107913+271658=379571?(marmaladeORskies)(kaleidoscopeOReyes)?87009+213312=30321

所以推薦處理次序為：AND(tangerineORtrees)AND(marmaladeORskies))(kaleidoscopeOReyes

1-8(*］習(xí)題對于查詢friendsANDromansAND(NOTcountrymen)

提出一種在確定查詢順序時對邏輯如何利用的文檔頻率來估計最佳的查詢處理次序？特別地，countrymen非進行處理

的方法。

解答：令friends、romans和countrymen的文檔頻率分別為x、y、z。如果z極高，則將N-z作為NOTcountrymen的

長度估計值，然后按照X、V、N-z從小到大合并。如果z極低，則按照x、v、z從小到大合并。

習(xí)題對于邏輯與構(gòu)成的查詢，按照倒排記錄表從小到大的處理次序是不是一定是最優(yōu)的？如果是，請給出解釋;

如果不是，請給出反例。

解答：不一定。比如三個長度分別為x,y,z的倒排記錄表進行合并，其中x>y>z,如果x和y的交集為空集，那么有可能

先合并x、y效率更高。

習(xí)題1-10[**]對于查詢xORy,按照圖1-6的方式，給出一個合并算法。

解答：

1answer<-()

2whilepl!=NILandp2!=NIL

3doifdoclD(pl)=doclD(p2)

4thenADD(answerzdoclD(pl))

5pl<-next(pl)

6p2<-next(p2)

更多精品文檔.

--好資料學(xué)習(xí)elseifdoclD(pl)<doclD(p2)7

ADD(answerzdoclD(pl))then8

pl<-next(pl)

9

ADD(answer,doclD(p2))10else

p2<-next(p2)11

〃*還有剩余12ifpl!=NIL

thenwhilepl!=NILdoADD(answer,doclD(pl))13

elsewhilep2!=NILdoADD(answerzdoclD(p2))14

return(answer)15

?為什么原始的處理方法非常耗時？給出一個針對該查詢的高xANDNOTy1-11[*]如何處理查詢習(xí)題

效合并算法。

幾乎要遍歷所有倒排表，因此如果采用列舉倒排表的方式非常耗時?？梢圆捎脙蓚€NOTy解答：由于。算法如下：xAND

NOTy有序集合求減的方式處理

Meger(pl,p2)

answer1()

2whilepl!=NILandp2!=NIL

3doifdoclD(pl)=doclD(p2)

4thenpl?next(pl)

5p2?next(p2)

6elseifdoclD(pl)<doclD(p2)

7thenADD(answer,doclD(pl))

8pl?next(pl)

9elseADD(answerzdoclD(p2))

10p2?next(p2)

11ifpl!=NIL〃*還有剩余

12thenwhilepl!=NILdoADD(answer,doclD(pl))

13return(answer)

習(xí)題1-12[*]利用Westlaw系統(tǒng)的語法構(gòu)造一個查詢，通過它可以找到professor、teacher或lecturer中的任意一個詞，

并且該詞和動詞explain在一個句子中出現(xiàn)，其中explain以某種形式出現(xiàn)。

解答:professorteacherlecturer/sexplain!

習(xí)題1-13[*]在一些商用搜索引擎上試用布爾查詢，比如，選擇一個詞(如burglar),然后將如下查詢提交給搜索引擎

(i)burglar;(ii)burglarANDburglar;(iii)burglarORburglaro

對照搜索引擎返回的總數(shù)和排名靠前的文檔，這些結(jié)果是否滿足布爾邏輯的意義？對于大多數(shù)搜索引擎來說，它們往往

不滿足。你明白這是為什么嗎？如果采用其他詞語，結(jié)論又如何？比如以下查詢

(i)knight;(ii)conquer;(iii)knightORconquero

更多精品文檔.

學(xué)習(xí)--好資料

第一章詞匯表和倒排記錄表*]請判斷如下說法是否正確。習(xí)題2-1[a.在布爾檢索系

統(tǒng)中，進行詞干還原從不降低正確率。b.在布爾檢索系統(tǒng)中，進行詞干還原從不降低召回率。c.詞干還原會增加詞

項詞典的大小。詞干還原應(yīng)該在構(gòu)建索引時調(diào)用，而不應(yīng)在查詢處理時調(diào)用。d.

錯d錯a錯b對c解答：

2-7[*]考慮利用如下帶有跳表指針的倒排記錄表習(xí)題

和一個中間結(jié)果表（如下所示，不存在跳表指針）進行合并操作。101

10095979935892-10所示的倒排記錄表合并算法，請問：采用圖）（plskip）?跳表指針實際跳轉(zhuǎn)的次

數(shù)是多少（也就是說，指針p的下一步將跳到a.i>75

24一—次，當(dāng)兩個表進行合并時，倒排記錄之間的比較次數(shù)是多少？【如下答案不一定正確，有人利用程序b.

21次，需要回到算法，本小題不扣分，下面不考慮重新比較同意對數(shù)字】計算需要<3,3>,<5,5>,<9,89>,

次：解答：

18<15/89>/<24/89>/<75/89>/<92/89>/<81/89>/<84/89>/<89/89>/<92/95>/<115/95>/<96/95>/<96/97>/<97/97>,<100/99>/<100/100

><115z101>

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>/<96/97>,<97/97>/<100/99>/<100,100>/<115/101>

文〉；位置位置下面給出的是一個位置索引的一部分，格式為：詞項：文檔〈習(xí)題位置

1,2,-*]1:2-9[>o1,2,…

檔2:〈位置；〉〉；7:<17angels:2:〈36,174,252,651〉；4:〈12,22,102,432;〈3,13,23,193〉1,17,74,222〈〉；4:〈8,78,108,458〉;

7:fools:2:

"8,328,528〉〈〉；4:13,43,113,433〉;7:<fear:2:<87,704,722,901;〉;7:〈10,20,110,470,500〉〈5,15,25,195in:2:

〈3,37,76,444,851〉;4:

;）>;7:〈4,14,404〉rush:2:〈2,66,194,321,702;4:〈9,69,149,429,569;〈199,319,599,709〉14,24,774,944to:2:

〈47,86,234,999〉;4:〈〉；7:

〈15,35,155〉；7:20,320〉（（tread:2:57,94,333）;4:

;〈16,36,736〉〉where:2:〈〉67,124,393,1001;4:<11,41,101,421,431;7:

那么哪些文檔和以下的查詢匹配？其中引號內(nèi)的每個表達式都是一個短語查詢。?！癴oolsrushin”a.

解答：文檔2、4、7

aw

b.”foolsrushin”ANDangelsfeartotread0

更多精品文檔.

好資料學(xué)習(xí)--4

文檔解答:

第二章典及容錯式檢索索引的話,那么對應(yīng)該查詢應(yīng)該會fi*mo*er,如果采用2-gram習(xí)

題3-5再次考慮321節(jié)中的查詢節(jié)的輪排索引查詢，但是產(chǎn)生什么樣的布爾查詢？你能否舉一個詞項的例子，使該詞

匹配3.2.1并不滿足剛才產(chǎn)生的布爾查詢？$fANDfiANDmoANDerANDr$

索引下的布爾查詢：2-gram解答：321節(jié)的輪排索引查詢，但是并不滿足上述布爾查詢詞項和ibuster（海盜）滿足

o的長度，請證明s1和s2的編輯距離不可能超過max{|s11,|s2|）3-7習(xí)題如果|si|表示字符串si中的每個字符依

次替換為，將s1轉(zhuǎn)換為s2的一種做法為:將s1證明:不失一般性，假設(shè)|s1|v=|s2|,的后|s2|=max{|s1|,|s2|}|s2|-|s1|

個字符，上述操作的總次數(shù)為s2中的前|s1|個字符，然后添加s21s2|=max{|s1|,|s2|}根據(jù)編輯距離的定義，其應(yīng)該小

于

矩5X5中的算法結(jié)果，其中的alice3-8計算paris和之間的編輯距離，給出類似于圖3-5習(xí)題陣包含每個前綴子串

之間的計算結(jié)果。解答：

個可3-11考慮四詞查詢catchedintherye,假定根據(jù)獨立的詞項拼寫校正方法，每個詞都有5習(xí)題57

需要考慮多少可能的短語拼寫形式（提那么，選的正確拼寫形式。如果不對空間進行縮減的話，

種變化可能）？示：同時要考慮原始查詢本身，也就是每個詞項有6解答：6*6*6*6=1296習(xí)題soundex3-14編碼一

致的專有名詞。找出兩個拼寫不一致但，相同解答：Mary,Mira（soundex）本題答案不唯一，可能有其他答案，編碼必

須一致。但是soundex更多精品文檔.

好資料學(xué)習(xí)-索引構(gòu)建第四章

,每次比較都有兩次磁盤尋道ID對的數(shù)目）7■次比較（T是詞項ID一文檔習(xí)題4-1如果需要7log2過程。假定使用磁

盤而不是內(nèi)存進行存儲，并且不采用優(yōu)化的排序算法（也就是說不使用前面4-lReuters-RCVl構(gòu)建索引需要多長時間？計

算時假定采用表提到的外部排序算法），那么對于中的系統(tǒng)參數(shù)。解答：8丁=10對于Reuters-RCVl,一388s=26575424s=7382

h=308）*5*102*（10*logl0為：因此排序時間（文檔分析時間可以忽略不計）2day

個詞項分區(qū)，假定使用的集=3=10個分區(qū)文件，/4?3二15對于〃個數(shù)據(jù)片，r習(xí)題語料進行分

布式索引構(gòu)架下對Reuters-RCVl群的機器的參數(shù)如表4-1所示，那么在MapReduce需要多長時

間？不一樣，不同同學(xué)用的不同版本，還有本題過程具有【給助教：教材不同印刷版本表4-2爭

議。暫不扣分】

：解答【整個計算過程是近似的，要了解過程】（一）、MAP階段【讀入語料（已經(jīng)不帶XML標記信息了，參考表5-6）,

詞條化，寫入分區(qū)文件】：

⑴讀入語料：

5,占6B每個詞條詞條，（考慮標點和空格）基于表4-2,ReutersRCV1共有8*10篇文檔，每篇文檔有20085而那第3行的

數(shù)據(jù)，注表（近似1GB,4-2對應(yīng)于表5-1因此整個語料庫的大小為8*10*200*6=9.6*10B

,這里近似計算，但是不處理，因此實際的原始文檔集大小應(yīng)該略高于0.96G里的數(shù)據(jù)已經(jīng)經(jīng)過去數(shù)字3行的結(jié)果）

5-1要認為沒有處理就得到表第8/15B9.6*10將整個語料庫分成15份，則每份大小為3=1.28S

/15*2*10每一份讀入機器的時間為：9.6*1085參考對每一份語料在機器上進行詞條化處理，（2）詞條化：得到

8*10*200=1.6*10個詞項ID-文檔ID（98個字節(jié)，詞條*8=1.28*10,共占1.6*10）ID4-2表和圖4-6,注意此時重復(fù)的詞項ID-

文檔對還沒有處理看詞條化主要是做了去數(shù)字和大化的時間暫時忽略不計【從題目無法得到詞條化這一部分時間，從

表5-1。小寫轉(zhuǎn)換，當(dāng)然也感覺這一部分的處理比較簡單，可以忽略】寫入分區(qū)文件：每一份語料得到的詞項(3)ID-

文檔ID(Key-Value)存儲到分區(qū)所花的時間為：-89=1.71S(1.28*10/15)*2*10

⑷MAP階段時間：MAPMAP臺機器進行1015由于分成份，但只有操作，所以上述操作需要兩步，因此，整個MAP更

多精品文檔.

學(xué)習(xí)——好資料(1.28+1.71)*2=6.0s

過程所需時間為

階段【讀入分區(qū)文件，排序，寫入倒排索引】：(二八REDUCEo按Key聚合，即變成Key,list(Vl,V2..)⑴讀入分區(qū)文件

【讀入過程中已經(jīng)實現(xiàn)所有Key-Value對中的Value聚合過程在內(nèi)存中實現(xiàn)，速度很快，該時間不計。另外，網(wǎng)絡(luò)傳輸

時間這里也不計算】：8臺索引器上每臺所分配的倒排記錄數(shù)目為，因此3根據(jù)表4-2,所有倒排記錄的數(shù)目為1.6*108

組成，因此每臺索引器上需要讀入的倒排記錄表數(shù)字節(jié)文檔ID1.6*10/3,而每條記錄由4字節(jié)詞項ID和49字節(jié)。據(jù)為

1.28*10/3-89=8.551.28*10/3*2*10于是，每臺索引器讀數(shù)據(jù)的時間為(2)排序：-888=13.7s

/3)*10/3*log(1.6*10每臺索引器排序所花的時間為1.6*102列表，和文檔ID寫入倒排索引文件【此時倒排文件已經(jīng)實現(xiàn)

文檔(3)ID的去重，假定只存儲詞項ID］：并不存儲其他信息(如詞項的DF及在每篇文檔中的TF還有指針等等展85

/3*4+10/3*4=4/3*10字節(jié)個需要寫入磁盤的索引大小為(據(jù)表4-2,詞項總數(shù)為4*10)4*10-88=2.7s*2*10索引寫入磁盤的

時間為：4/3*108.5+13.7+2.7=24.9⑷REDUCE階段時間為：

(三)因此，整個分布式索引的時間約為6.0+8.5+13.7+2.7=30.9s

索引壓縮第五章文檔集詞典在兩種不同按塊存儲壓縮方法下的空間大小。其中，第一種估計

Reuters-RCVl習(xí)題5-2

女=16方法中卜=8,第二種方法中。解答：字節(jié)，所有個詞項節(jié)省7*3-8=137*3個字節(jié)，同時增加8個字節(jié)，于是每

8每8個詞項會節(jié)省7.6MB-0.65MB=6.95MB

13*400000/8=650K,因此，此時索引大小為詞項共節(jié)省字節(jié)，15*3-16=2916個詞項節(jié)省同時增加16個字節(jié)，每16于是

每個詞項會節(jié)省15*3個字節(jié)，，因此，此時索引大小為7.6MB-0.725MB=6.875MB所有詞項共節(jié)省29*400000/16=725K

距間其對應(yīng)的,270,400)及26512,10,11,,15,62,63,,268表倒5-6習(xí)題考慮排記錄(4。假定倒排記錄表的長度和倒

排記錄表分開獨立存儲，這130)3〃2,3,1,,47,1,20214表(,6,

樣系統(tǒng)能夠知道倒排記錄表什么時候結(jié)束。采用可變字節(jié)碼：1字節(jié)來編碼的最大間距是多少？⑴能夠使用字節(jié)來

編碼的最大間距是多少？2(ii)能夠使用(只計算對這些數(shù)字序列進行編碼上述倒排記錄表總共需要多少空間(iii)采用可

變字節(jié)編碼時，的空間消耗)？解答：7……)0即可表示間距1,也算對，因為不存在(i)2-1=127(答1280間距，14)也

算對16384(ii)2-1=16383(答(iii)1+1+1+1+1+1+1+2+1+1+2=13

對于下列采用］5-8［習(xí)題*y編碼的間距編碼結(jié)果，請還原原始的間距序列及倒排記錄表。更多精品文檔.

好資料學(xué)習(xí)——1110001110101011111101101111011

解答：1110001;11010;101;11111011011;11011

1001;110;11;111011;111

32+16+8+2+1=59;79;6;3;

9;15;18;77;84

文檔評分、詞項權(quán)重計算及向量空間模型第六章叱中的D℃3中

幾個詞項的tf情況，采用圖6-8、6-10考慮圖6-9中的3篇文檔DoclDoc2、習(xí)題值。insurance及best的tf-idf值來計

算所有詞項car、auto>

Doc3Doc2Doc1

car24274

auto0333

insurance29033

best

17

0

14

值6-10中所使用的tf圖6-9習(xí)題解答：idf=1.65,idf=2.08>idf=1.62,idf=1.5,bestautoinsurancecar于是，各

詞項在各文檔中的tf-idf結(jié)果如下表：

car24*1.65=39.6

27*1.65=44.554*1.65=6.6

auto0

3*2.08=6.24

33*2.08=68.64

insurance29*1.62=46.98

0

33*1.62=53.46

best

14*1.5=21

0

17*1.5=25.5

習(xí)題6-12公式(6-7)中對數(shù)的底對公式(6-9)會有什么影響？對于給定查詢來說，對數(shù)的底是否會對文檔的排序造

成影響？

解答：沒有影響。

假定idf采用與(6-7)不同的底x計算，根據(jù)對數(shù)換底公式有。

idf(x)=log(N/df)=log(N/df)/logx=idf/logx,ttttx

更多精品文檔.

一一好資料學(xué)習(xí)的計算中該常數(shù)可以作為公因，在公式(6-9)idft(x)和idft之間只相差一個常數(shù)因子l/logx由于子提

出，因此文檔的排序不會改變。

的向量空間相似度并及文檔digitalcamerasandvideocameras6-19計算查詢digitalcameras習(xí)題對應(yīng)的列)wf6-l的空列

中。假定N=10000000,對查詢及文檔中的詞項權(quán)重(將結(jié)果填入表看成and采用對數(shù)方法計算，查詢的權(quán)重計算采用

idf,而文檔歸一化采用余弦相似度計算。將121

是停用詞。請在tf列中給出詞項的出現(xiàn)頻率，并計算出最后的相似度結(jié)果。習(xí)題6-19中的余弦相似度計算表6-1

檔文查詢dq?"詞wftfq=wf-idfdftfwfidfwf

4=歸一化的?digital10000

100000video

50000cameras

【本質(zhì)上這里沒有考慮查詢向量的歸一化，即沒有考慮查詢向量的大小，嚴格上不是余弦相似解答：度】檔文查詢

d?q詞u

值，采用如下權(quán)重計算機制來計算獲得和idf個詞項和3篇文檔中的tf4習(xí)題6-23考慮習(xí)題6-10中（ii）ntc.atc。得分最

高的兩篇文檔：（i）nnn.atc；

，然后計算內(nèi)積，于是有：根據(jù)題意文檔采用nnn,查詢采用atc（i）解答：

文檔查詢q

Docl得分詞項歸一化tf-idftf-idfidftfidftftf-idf2727car11.651.6510.560

30.3533auto0.52.081.04123.3101insurance0.55011.621.6200best0.5091141.511.514

文檔Doc2查詢q

得分詞項歸一化idftf-idfidftftftf-idftf-idf更多精品文檔.

好資料學(xué)習(xí)-一一40.560411.65car11.65

1.0410.3532.08auto0.5333332.0371.62insurance331.6211330.5500.5091.5best1011.5

0

文檔Doc3查詢q

詞項得分歸一化tf-idfidftftfidftf-idftf-idf1.651.65240.56024car1111.04Oauto02.080.50.353

38.0461.62291.62290.550insurance1111.50.509best1.511717

Score(q/Doc3)>Score(q/Doc2)>Score(q/Docl)nnn.atcT,于是，在

ate,然后計算內(nèi)積，于是有：(ii)根據(jù)題意文檔采用ntc,查詢采用

Docl文檔查詢q

詞項得分歸一化歸一化idftf-idftfidftf(a)tf-idftf-idf

tf-idf

0.897car2711.651.6544.551.650.5600.1250.353auto0.56.242.0832.081.040.76

insurance10.5501.621.6201.6200

best

11.51.50.509141.5210.423

查詢qDoc2文檔

詞項歸一歸一得分

化化

idftf(a)tf-idftf-idftfidftf-idf

tf-i

df

car1.6511.650.5601.6546.60.075

auto0.52.081.040.353332.080.786

68.

64

0.660.61333insurance0.55011.6253.461.621.62best

11.51.50.50901.500

查詢q文檔Doc3

得分詞項歸一化歸一化tf(a)idftf-idfidftf-idftftf-idf

tf-idf

更多精品文檔.

好資料學(xué)習(xí)

carauto11.651.650.5602439.60.5950.92

doc20.351.211.65

??doc3?doc1

1car(0)

為零的不應(yīng)

該出現(xiàn)在倒

排記錄中，有

的也算

對】?docl

【按道理，

tfauto?doc2

?doc3

docl?doc2?i

nsurance?do

c3doc2

docldoc3??

best?

auto0.52.081.040.353000

insurance0.251.212.08

(0)1.7

insurance11.621.620.550291.620.706

46.98

bestbest11.51.50.5090.5171.525.50.383

所以,倒排記0.71(0)1.4

錄表如下：1

Score(q/Doc3)>Score(q,Docl)>Score(q,Doc2)

下，于是，在nnn.atc

一個完整搜索系統(tǒng)中的評分計算第七章

已經(jīng)能夠充分保證找到前)水給定單個詞項組成的查詢，7-3請解釋為什么采用全局勝者表。習(xí)題，如何對上述思

路進行修正？>1)K篇文檔。如果只有s個詞項組成的查詢(s解答：用于區(qū)(idfidf已經(jīng)不起作用了r篇文檔構(gòu)成t的勝

者表。單詞項查詢，詞項t所對應(yīng)的tf最高的),所以此時已經(jīng)足夠了。別不同詞的先天權(quán)重

【這一問本人也不知道該怎么答，不權(quán)重了。。因此，不再獨立。對于s個詞項組成的查詢，有idf扣分吧】

的靜態(tài)得分分別和Doc2nnn.atc權(quán)重計算的數(shù)據(jù)，假定Docl習(xí)題7-5重新考察習(xí)題6-23中基于的靜態(tài)得分進行取值，

才能分別保證它能夠成Doc3。請確定在公式(7-2)下，如何對2是1和的排名第一、第二或第三的結(jié)果。為查詢best

carinsurance算出(7-2)(6-12)解答：這道題不扣分吧。。整個書上有關(guān)余弦相似度的計算這塊都有問題【即按照公式的數(shù)，

例子中都沒有考慮查詢向量的16-4)卻是大于到01之間的數(shù)，但實際例子(例的應(yīng)該是算出的根本不是什么余弦相似度。

整個一團亂】中nnn.atc大小。另外，按照習(xí)題6-23

1.471.39、如果相似度先采用nnn.atc計算，最后除以文檔向量的大小，則三篇文檔的得分分別為：1.68。和g(d3)>1.79

排名第一：

-g(d3)+1.68>3.47z

2.39<g(d3)+1.68<3.47,0.71<g(d3)<1.79排名第二：一

0<g(d3)<0.71排名第三：-

,畫出當(dāng)使用靜態(tài)10.5DOC3和的靜態(tài)得分分別是0.25、和Doc2Docl6-10習(xí)題7-7設(shè)定圖中、值求和結(jié)果進行排序的

倒排記錄表。得分與歐幾里得歸一化tf

7-2計算得下表：解^答：按照公式doc3doe1doc2

1.58

1.13

0.59

更多精品文檔.

好資料學(xué)習(xí)-一

信息檢索的評價第八章

個檢索結(jié)果(左邊的結(jié)果10考慮一個有4篇相關(guān)文檔的信息需求，考察兩個系統(tǒng)的前習(xí)題8-8[*]

排名靠前)，相關(guān)性判定的情況如下所示：NNNRRRNRNN1系統(tǒng)

RRNNN

系統(tǒng)2NRNNR

計算兩個系統(tǒng)的MAP值并比較大小。a.

得分？b.上述結(jié)果直觀上看有意義嗎？能否從中得出啟發(fā)如何才能獲得高的MAP正確性進行排序的結(jié)果進行對比。

中按照c.計算兩個系統(tǒng)的RMAP值，并與a解答:(1+2/3+3/9+4/10)/4=0.6a.系統(tǒng)1

(1/2+2/5+3/6+4/7)/4=0.492系統(tǒng)2

3-5篇之內(nèi)b.相關(guān)文檔出現(xiàn)得越靠前越好，最好前面2R-Precision=0.25c.系統(tǒng)1的R-Precision=0.5,系統(tǒng)

，下面給出了某系統(tǒng)8在10000篇文檔構(gòu)成的文檔集中，某個查詢的相關(guān)文檔總數(shù)為習(xí)題8-9[**]

篇相6表示)和不相關(guān)(用N表示)情況，其中有針對該查詢的前20個有序結(jié)果的相關(guān)(用R關(guān)文檔：NNNNR

RNNNRRRNNNNNNRN

20篇文檔的正確率是多少？前a.

P@20=6/20=30%

?

F值是多少前20篇文檔的b.iFl=3/7=0.429

R@20=6/8=75%,150

召回率水平上的插值正確率是多少？在25%c.1

召回率水平上的插值正確率是多少？在33%d.

3/9=33.3%

MAP值。假定該系統(tǒng)所有返回的結(jié)果數(shù)目就是20,請計算其e.(l+l+3/9+4/ll+5/15+6/20)/8=0.4163

篇文檔，那么篇文檔只是結(jié)果中最靠前的20篇文檔，上述假定該系統(tǒng)返回了所有的1000020是多少？該系統(tǒng)可能的

最大f.MAP,此時有：位開始，接連兩篇相關(guān)文檔，此時可以獲得最大的從第21MAp更多精品文檔.

——好資料學(xué)習(xí)(1+1+3/9+4/11+5/15+6/20+7/21+8/22)/8=0.503

是多少？該系統(tǒng)可能的最小g.MAP(l+l+3/9+4/ll+5/15+6/20+7/9999+8/10000)/8=0.4165

的到(g)h.在一系列實驗中，只有最靠前的20篇文檔通過人工來判定，(e)的結(jié)果用于近似從(f)(采用絕所造成的誤差有

多大⑴通過(e)而不是和(g)來計算MAPMAP取值范圍。對于上例來說，對值來計算)？10.4163-(0.503+0.4165)/21=0.043

相關(guān)反饋及查詢擴展第九章CDscheapsoftware并對這兩篇文檔進行了判斷：包含內(nèi)容

用戶查看了兩篇文檔dl和d2,習(xí)題9-3：為不相關(guān)文檔。假設(shè)直接使dl的文檔為相關(guān)文檔，而內(nèi)容為cheapthrillsDVDs

的文檔d2cheapCDs(不進行歸一化也不加上文檔頻率因子)，也不對向量進行長度歸一化。采用詞項的頻率作為權(quán)重

Y=0.25,o請問修改后的查詢向量是多少？其中(9-3)進行Rocchio相關(guān)反饋，a=1,B=0.75用公式

解答：

搜索系統(tǒng)，并且為了提高效率，系統(tǒng)只基于返回網(wǎng)頁WebOmar實現(xiàn)了一個帶相關(guān)反饋的習(xí)題9-4：的查詢是的標題文

本進行相關(guān)反饋。用戶對結(jié)果進行判定，假定第一個用戶Jinxingbananaslug

返回的前三個網(wǎng)頁的標題分別是：bananaslugAriolimaxcolumbianus

SantaCruzmountainsbananaslug

SantaCruzCampusMascot

的搜索引擎只基于詞項頻率（不包括