《信息組織與檢索》作業答案

第一章布爾檢索

習題1-2

考慮如下幾篇文檔：

文檔1breakthroughdrugforschizophrenia

文檔2newschizophreniadrug

文檔3newapproachfortreatmentofschizophrenia

文檔4newhopesforschizophreniapatients

a.畫出文檔集對應的詞項一文檔矩陣；

b.畫出該文檔集的倒排索引（參考圖中的例子）。

Term-Documentmatrix:

1234

approach0010

breakthrough1000

drug1100

for1011

hopes0001

new0111

of0010

patients0001

schizophrenia1111

treatment0010

InvertedIndex:

approach->3

breakthrough->1

drug->l->2

for->l->3->4

hopes->4

new->2->3->4

of->3

patients->4

schizophrenia->l->2->3->4

treatment>3

注意：倒排索引中的詞表(dictionary)和每個詞項的倒排列表(postinglist)需要排序，便

于查找。這里我們暫不考慮詞的正規化處理(如hopes->hope)。

補充習題1

寫出AND查詢的偽代碼

?面向過程風格的偽代碼：

給定兩個指針pl和P2,分別指向兩倒排列表listl和Iist2(鏈表實現)的首元素；令docld(pl)

表示pl所指向的元素的docld查詢結果存放在answer列表里。

這里應用了“化歸”思想(將新問題轉化歸為舊問題來解決)。這里，比較兩排序列表的首

元素，排除較小的docld(不可能有匹配)后，我們構造出新的剩余列表，再次進行兩列表

的首元素的比較。

Whilepl!=nullANDp2!=null

Ifpl?>dodd==p2?>docld〃對兩(乘馀)列表的首元素進行比較

insert(answer;pl)；

pl=pl->next；〃構造新的剩余列表，迭代執行

p2=p2->next；//

Elseifpl->docld<p2->docld

pl=pl->next；//pl->docld不可能有匹配；構造新的剩余列表

Else

p2=p2->next；//p2->docld不可能有匹配；構造新的剩余列表

End

?面向對象風格的偽代碼：

注：為一個數據結構(對象)定義方法，通過方法操作自己的內部數據(List對象里隱

含包含了一個成員變量，它是真正的鏈表或變長數組)。

Whilelistl.currentltem()!=nullANDIist2.currentltem()!=null

Iflistl.currentltem().getDocld()==list2.currentltem().getDocld()

answer.insert(listl.currentltem());

listl.moveToNext();

list2.moveToNext();

Elseiflistl.currentltem().getDocld()<list2.currentltem().getDocld()

listl.moveToNext();

Else

list2.moveToNext();

End

習題1-10

寫出OR查詢的偽代碼

?面向過程風格的偽代碼：

給定兩個指針pl和p2,分別指向兩倒排列表listl和Iist2(鏈表實現)的首元素；令docld(pl)

表示pl所指向的元素的docld；查詢結果存放在answer列表里。

Whilepl!=nullANDp2!=null

Ifpl->docld==p2->docld

insert(answer;pl)；

pl=pl->next；

p2=p2->next；〃構造新的剩余列表，迭代執行

Elseifpl->docld<p2->docld

insert(answer;pl)；

pl=pl->next；〃構造新的剩余列表，迭代執行

Else

insert(answei;p2)：

p2=p2->next；〃構造新的剩余列表，迭代執行

End

Whilepl!=null〃條件為真時,加入listl的剩余元素(此時Iist2已遍歷到結尾)

insert(answecpl)；

pl=pl->next；

END

Whilep2!=null〃條件為真時，加入Iist2的剩余元素(此時listl已遍歷到結尾)

insert(answecp2)；

p2=pl->next；

END

?面向對象風格的偽代碼：

Whilelistl.currentltem()!=nullANDIist2.currentltem()!=null

Iflistl.currentltem().getDocld()==list2.currentltem().getDocld()

answer.insert(listl.currentltem());

listl.moveToNext();

list2.moveToNext();

Elseiflistl.currentltem().getDocld()<list2.currentltem().getDocld()

answer.insert(listl.currentltem());

listl.moveToNext();

Else

answer.insert(list2.currentltem());

list2.moveToNext();

End

Whilelistl.currentltem()!=null

answer.insert(listl.currentltem());

listl.moveToNext();

END

WhileIist2.currentltem()!=null

answer.insert(list2.currentltem());

list2.moveToNext();

END

補充習題2

若一個文集有1000篇文檔，有40篇是關于信管專業建設的。我的信息需求是了解信管專業

的專業建設情況,用某搜索引擎在這個文集上搜索，查詢詞為“信管”，搜出100篇包含“信

管”的文檔，這其中有20篇是信管專業建設方面的，其它80篇是關于信管的其它情況。請

問該查詢的正確率和召回率是多少

正確率=20/100=0.2

召回率=20/40=0.5

第二章詞項詞典及倒排記錄表

習題2-1

a.在布爾檢索系統中，進行詞干還原從不降低正確率。

錯；相當于擴充出同一個詞干表示的多個詞，會降低正確率。

b.在布爾檢索系統中，進行詞干還原從不降低召回率。

對。

c.詞干還原會增加詞項詞典的大小。

錯。

d.詞干還原應該在構建索引時調用，而不應在查詢處理時調用。

錯；應同時做才能保證索引中和查詢詞的匹配。

習題2-2

請給出如下單詞的歸一化形式(歸一化形式也可以是詞本身)。

a.'Cos->cos

b.Shi'ite->shiite（'是隔音號）

c.cont'd->contd（contd.可表示contained包括；continued繼續）

d.Hawai'i->hawaii

e.O'Rourke->orourke

習題2-3

如下詞經過Porter詞干還原工具處理后會輸出同樣的結果，你認為哪對(兒對)詞不應

該輸出同樣的結果？為什么？

a.abandon/abandonment

b.absorbency/absorbent

c.marketing/markets

d.university/universe

e.volume/volumes

按Porter詞干還原算法，這幾組詞都可以被還原為相應的詞干。但是這里問的是哪些組做詞

干還原不合適，原因是某組的兩個詞雖然來源于同一個詞干，但是它們的意思不同，如果做

詞干還原處理會降低正確率。

c組不做詞干還原。marketing表示營銷，market表示市場。

d組不做詞干還原。university表示大學，universe表示宇宙。

習題2-6

對于兩個詞組成的查詢，其中一個詞(項)的倒排記錄表包含下面16個文檔ID：

[4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180]

而另一個詞(項)對應的倒排記錄表僅僅包含一個文檔ID：

[47]

請分別采用如下兩種策略進行倒排記錄表合并并計算所需要的比較次數，同時簡要地說明計

算的正確性。

a.使用標準的倒排記錄表。

比較：(4,47),(6,47),(10,47),(12,47),(14,47),(16,47),(18,47),(20,47),(22,47),(32,47),

(47,47)o共比較11次。

b.使用倒排記錄表+跳表的方式，跳表指針設在P“2處(P是列表長度)。

P=16。也就說第一個列表的跳表指針往后跳4個元素。

下圖藍色表示安裝了跳表指針的元素，其中120跳到180上。

[4,6,10,12,14,16,18,20,22,32,47,81,120,122,157,180]

比較：(4,47),(14,47),(22,47),(120,47),(32,47),(47,47)。共比較6次。

習題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,528)；

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)；

那么哪些文檔和以下的查詢匹配？其中引號內的每個表達式都是一個短語查詢。

a."foolsrushin”；

文檔2、4、7o

b."foolsrushin“ANDuangelsfeartotread

文檔4。

補充習題1

k詞鄰近AND合并算法

前提：

考慮位置索引。

要求查找這樣的文檔，它同時包含詞A和詞B,且兩詞文中的距離在k個詞以內。

給定兩個指針pl和P2,分別指向兩個詞A和B的兩倒排列表(鏈表實現)的首元素;

令pi->doc表示pi所指向文檔對象的結構體。

對于一個文檔對象，該詞出現的各個位置的列表為posListc用ql(q2)表示詞A(詞B)

當前指向文檔對象指向的posList指向的位置。用qi->pos表示該位置。

查詢結果存放在answer列表里。

算法：

Whilepl!=nullANDp2!=null

Ifpl->docld==p2->docld〃對兩(剩余)列表的首元素進行比較

Whileql!=nullANDq2!=null

Ifql->pos-q2->pos<=kORq2->pos-ql->pos<=k

insert(answerzpl);

break;〃跳出這個循環，找到一個k臨近即可

Elselfql->pos-q2->pos>k//q2不可能被匹配上，忽略它

q2=q2->next;〃生成新的剩余列表

ElseIfq2->pos-ql->pos>k//ql不可能被匹配上，忽略它

ql=ql->next;〃生成新的剩余列表

EndIf

EndWhile

pl二plonext;〃構造新的剩余列表，迭代執行

p2=p2->next;

Elseifpl->docld<p2->docld

pl=pl->next；〃pl->docld不可能有匹配；構造新的剩余列表

日se

p2=p2->next；〃p2->docld不可能有匹配；構造新的剩余列表

End

第六章文檔評分、詞項權重計算及向量空間模型

習題6-2

上面的例6-1中，如果gl=0.2,g2=0.31及g3=0.49,那么對于一個文檔來說所有可能的

不同得分有多少？

得分1：0

得分2：gl=0.2

得分3：g2=0.31

得分4g3=0.49

得分5：gl+g2=0.51

得分6：gl+g3=0.69

得分7：g2+g3=0.8

得分8：gl+g2+g3=1.0

習題6-10

考慮圖6-9中的3篇文檔Docl、Doc2、Doc3中幾個詞項的tf情況，采用圖6-8中的idf

值來計算所有詞項car、auto、insurance及best的tf-idf值（這乜改為df來的計E工就假設七

Docl,Doc2Doc3的這個文集）。

Doc1Doc2Doc3

car27424

auto3330

insurance03329

best14017

圖6-9習題6-10中所使用的tf值

解答:

wtd=max(l+log10(l+tf),0)

DoclDoc2Doc3

Car2.43141.60212.3802

Auto1.47712.51850

insurance02.51852.4624

Best2.146102.2304

idf

dftt

car30

auto20.1761

insurance20.1761

best20.1761

這里N=3o

tf-idft,d=Wt/idft

DoclDoc2Doc3

car000

auto0.26010.44350

insurance00.44350.4336

best0.377900.3928

例6-4

假設文檔集中的文檔數目N=1000000,詞表為{auto,best,car,insurance},這四個詞的df值

分別為

5000,50000,10000,1000o

設某文檔d的rawtf向量為[1,0,1,2],對查詢q="bestcarinsurance〃，問該文檔-查詢的相似

度打分score(q,d)是？

解答:

idf

dftt

auto50002.3010

best500001.3010

car100002.0000

insurance10003.0000

這里N=1000000o

文檔d的tf-idf.量：

歸一化

rawtftzCjwtid=max(l+log10(l+tf),0)tf-idftd=wt/d*idftv(d)=

tf-idf)

auto11.00002.30100.4646

best0000

car11.00002.00000.4038

insurance21.30103.90310.7881

查詢q的tf-idf向量（Wt,d=l）

rawtft/qwt/q=max(l+logio(l+tf),0)tf-idft,q=wt,q*idftv(q)=歸一化

tf-idf畝

auto0000

best111.30100.3394

car112.00000.5218

insurance113.00000.7827

score(q,d)=v(q),*v(d)=0.8275

第八章信息檢索的評價

習題8-8

考慮一個有4篇相關文檔的信息需求，考察兩個系統的前10個檢索結果（左邊的結果排名

靠前），相關性判定的情況如下所示：

系統1RNRNNNNNRR

系統2NRNNRRRNNN

a.計算兩個系統的MAP值并比較大小。

b.上述結果直觀上看有意義嗎？能否從中得出啟發如何才能獲得高的MAP得分？

c.計算兩個系統的R-precision值，并與a中按照MAP進行排序的結果進行對比。

解答：

a.按MAP的定義，這里|Q|=1,m=4。在查詢結果中遇到每個相關文檔對前面的所有文檔

計算一個Precision,MAP將這些Precision值求平均。

MAP（系統1）=（1/4）*（1+2/3+3/9+4/10）=0.6

MAP（系統2）=（1/4）*（1/2+2/5+3/6+4/7）=0.49

系統1的MAP值大。

b.相關的查詢結果排名越靠前，則MAP越大。

c.按R-precision的定義，假設總共有|Rei|篇相關文檔,在查詢結果中取前|Rel|個文檔，

計算其precision?

R-precision（系統1）=2/4=1/2

R-precision（系統1）=1/4

系統1的R-precision值大。與MAP給出系統打分排序的結果一致。

習題8-10

下表中是兩個判定人員基于某個信息需求對12個文檔進行相關性判定的結果（0=不

相關，1=相關）。假定我們開發了一個IR系統，針對該信息需求返回了文檔｛4,5,6,7,8｝。

docID判斷1判斷2

100

200

311

411

510

610

710

810

901

1001

1101

1201

a.計算兩個判斷之間的kappa統計量；

b.當兩個判斷均認為是相關文檔時才認為該文檔相關，此時計算上述系統的正確率、召回

率及Fi值；

c.只要有一個判斷認為是相關文檔則認為該文檔相關，此時計算上述系統的正確率、召回

率及Fi值。

解答：

a.計算kappa統計量：

P(A)就是實際觀察到的一致意見的概率，總共12篇文檔，其中2篇兩人一致選Yes,2

篇兩人一致選No。因此，P(A)=(2+2)/12=l/3°

P(E)是隨機情況下的一致意見的概率。假設每個人對每個文檔的Yes(或No)打分的概

率Py(或Pn)是獨立同分布的(i.i.d.),則P(E)=Py*Py+Pn*Pn。其中，Py是2*12次打分中為

Yes的比例,py=12/24=l/2；Pn是2*12次打分中為No的比例，p°=12/24=1/2。代入P(E),得：

P(E)=(l/2)A2+(l/2)A2=l/2?

Kappa=(P(A)-P(E))/(l-P(E))=(l/3-l/2)/(l-l/2)=-l/3<0.67,這是一個負數，說明實際的一致

性結果還不如隨機產生的一致性結果，因此可以判定兩人給出的相關性打分不一致。

b.文檔集中共有12篇文檔，其中2文檔相關({3,4}),其它10篇都不相關。查詢結果為

{4,5,6,7,8},其中只有1篇文檔相關({4}).

該查詢的

Precision,P=l/5；

Recall,R=l/2；

Fi=2P*R/(P+R)=0.28。

c.文檔集中共有12篇文檔，其中10文檔相關，其它2篇都不相關({1,2})。查詢結果為

{4,5,6,7,8},全部都相關。

該查詢的

Precision,P=l；

Recall,R=5/12；

Fi=2P*R/(P+R)=0.67。

注：因Kappa統計量認為兩人打分不一致，所以修正方法b比較合理，而c非常不合理。

第十三章文本分類與樸素貝葉斯方法

習題13-3

位置獨立性假設的基本原則是，詞項在文檔的位置k上出現這個事實并沒有什么有用的信息。

請給出這個假設的反例。提示：可以考慮那些套用固定文檔結構的文檔。

解答：如果一個詞出現在不同域中，它的重要性不同。比如出現在標題中的詞一般很重要。

習題13-9

基于表13-10中的數據，進行如下計算：

(i)估計多項式NB分類器的參數；

(ii)將(i)中的分類器應用到測試集；

表13-10用于參數估計的數據

文檔ID文檔中的詞屬于c=C/7//7a類？

訓練集1TaipeiTaiwanyes

2MacaoTaiwanShanghaiyes

3JapanSapporono

4SapporoOsakaTaiwanno

?

測試集5TaiwanTaiwanSapporo

P(China)=2/4=l/2;P(非China)=2/4=l/2.

詞典中有7個詞Japan,Macao,Osaka,Sapporo,Shanghai,Taipei,Taiwan.

測試集中，China類共有5個詞；非China類共有5個詞。

P(Taiwan|China類)=(2+1)/(5+7)=1/4(加一平滑，下同)

P(Taiwan|非China類)=(1+1)/(5+7)=1/6

P(Sapporo|China類)=(0+1)/(5+7)=1/12

P(Sapporo|非China類)=(2+1)/(5+7)=1/4

按單字詞語言模型，

類類類A

P(China|d5)ocP(China)*P(Taiwan|China)2*P(Sapporo|China

^)=l/2*(l/4)A2*l/12=l/384.

P(非China類㈤ocP(非China類)*P(Taiwan|非China類)A2