中國科學(xué)院大學(xué)現(xiàn)代信息檢索課后習(xí)題答案-展示頁
2025-07-03 02:50本頁面
【正文】 (p2))11 p2next(p2)12 if p1!=NIL // x還有剩余 13 then while p1!=NIL do ADD (answer, docID(p1))14 else while p2!=NIL do ADD(answer,docID(p2))15 return(answer) 習(xí)題 111 [*] 如何處理查詢x AND NOT y？為什么原始的處理方法非常耗時(shí)？給出一個(gè)針對(duì)該查詢的高效合并算法。比如三個(gè)長度分別為x,y,z的倒排記錄表進(jìn)行合并，其中xyz，如果x和y的交集為空集，那么有可能先合并x、y效率更高。習(xí)題 19 [**] 對(duì)于邏輯與構(gòu)成的查詢，按照倒排記錄表從小到大的處理次序是不是一定是最優(yōu)的？如果是，請(qǐng)給出解釋；如果不是，請(qǐng)給出反例。如果z極高，則將Nz作為NOT countrymen的長度估計(jì)值，然后按照x、y、Nz從小到大合并。 87009+213312 = 30321 所以推薦處理次序?yàn)椋?kaleidoscope OR eyes）AND (tangerine OR trees) AND (marmalade OR skies)習(xí)題18[*] 對(duì)于查詢e. friends AND romans AND (NOT countrymen)如何利用countrymen的文檔頻率來估計(jì)最佳的查詢處理次序？特別地，提出一種在確定查詢順序時(shí)對(duì)邏輯非進(jìn)行處理的方法。 46653+316812 = 363465(marmalade OR skies)232。習(xí)題 17 [*] 請(qǐng)推薦如下查詢的處理次序。此時(shí)合取方式可能處理起來更高效。而前面需要先進(jìn)行OR操作，得到的中間倒排記錄表會(huì)更大一些。12a. 通過分配律將習(xí)題15中的查詢寫成析取范式；b. 改寫之后的查詢的處理過程比原始查詢處理過程的效率高還是低？c. 上述結(jié)果對(duì)任何查詢通用還是依賴于文檔集的內(nèi)容和詞本身？解答：a. 析取范式為：(Brutus And Not Anthony And Not Cleopatra) OR (Caesar AND NOT Anthony AND NOT Cleopatra)b. 這里的析取范式處理比前面的合取范式更有效。由于任意布爾表達(dá)式處理算法復(fù)雜度的上界為O(N)，所以上述復(fù)雜度無法進(jìn)一步改進(jìn)。習(xí)題15 [*] 將倒排記錄表合并算法推廣到任意布爾查詢表達(dá)式，其時(shí)間復(fù)雜度是多少？比如，對(duì)于查詢c. (Brutus OR Caesar) AND NOT (Antony OR Cleopatra)我們能在線性時(shí)間內(nèi)完成合并嗎？這里的線性是針對(duì)什么來說的？我們還能對(duì)此加以改進(jìn)嗎？解答：時(shí)間復(fù)雜度為O(qN)，其中q為表達(dá)式中詞項(xiàng)的個(gè)數(shù)，N為所有倒排記錄表長度之和。因?yàn)镹OT Caesar的倒排記錄表需要提取其他所有詞項(xiàng)對(duì)應(yīng)的倒排記錄表。b. 不能。通過集合的減操作即可。習(xí)題13 [*] 對(duì)于習(xí)題12中的文檔集，如果給定如下查詢，那么返回的結(jié)果是什么？a. schizophrenia AND drug解答：{文檔1，文檔2}b. for AND NOT (drug OR approach）解答：{文檔4}習(xí)題14 [*] 對(duì)于如下查詢，能否仍然在O(x+y)次內(nèi)完成？其中x和y分別是Brutus和Caesar所對(duì)應(yīng)的倒排記錄表長度。4top1習(xí)題12 [*] 考慮如下幾篇文檔：文檔1 breakthrough drug for schizophrenia文檔2 new schizophrenia drug文檔3 new approach for treatment of schizophrenia文檔4 new hopes for schizophrenia patientsa. 畫出文檔集對(duì)應(yīng)的詞項(xiàng)—文檔矩陣；解答：文檔1文檔2文檔3文檔4approach0010breakthrough1000drug1100for1011hopes0001new0111of0010patients0001schizophrenia1111treatment0010b. 畫出該文檔集的倒排索引（參考圖 13中的例子）。2 224。4rise2 224。3 224。4in2 224。2 224。《信息檢索導(dǎo)論》課后練習(xí)答案王斌最后更新日期 2013/9/28第一章 布爾檢索習(xí)題11 [*] 畫出下列文檔集所對(duì)應(yīng)的倒排索引（參考圖13中的例子）。文檔 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解答：forecasts1home1 224。3 224。3increase3july2 224。4new1 224。4sales1 224。 3 224。解答：參考a。如果不能的話，那么我們能達(dá)到的時(shí)間復(fù)雜度是多少？a. Brutus AND NOT Caesarb. Brutus OR NOT Caesar解答：a. 可以在O(x+y)次內(nèi)完成。具體做法參考習(xí)題111。不可以在O(x+y)次內(nèi)完成。所以需要遍歷幾乎全體倒排記錄表，于是時(shí)間復(fù)雜度即為所有倒排記錄表的長度的和N，即O(N) 或者說O(x+Ny)。也就是說可以在詞項(xiàng)個(gè)數(shù)q及所有倒排記錄表長度N的線性時(shí)間內(nèi)完成合并。習(xí)題16 [**] 假定我們使用分配律來改寫有關(guān)AND和OR的查詢表達(dá)式。這是因?yàn)檫@里先進(jìn)行AND操作(括號(hào)內(nèi))，得到的倒排記錄表都不大，再進(jìn)行OR操作效率就不會(huì)很低。c. 上述結(jié)果不一定對(duì)，比如兩個(gè)罕見詞A和B構(gòu)成的查詢 (A OR B) AND NOT(HONG OR KONG)，假設(shè)HONG KONG一起出現(xiàn)很頻繁。如果在析取范式中僅有詞項(xiàng)的非操作時(shí)，b中結(jié)果不對(duì)。d. (tangerine OR trees) AND (marmalade OR skies) AND (kaleidoscope OR eyes）其中，每個(gè)詞項(xiàng)對(duì)應(yīng)的倒排記錄表的長度分別如下：詞項(xiàng) 倒排記錄表長度eyes 213 312kaleidoscope 87 009marmalade
環(huán)評(píng)公示相關(guān)推薦
鄂ICP備17016276號(hào)-1