該系列文章是《An Introduce to Information Retrieval》Chapter 1 的讀書(shū)筆記。

?

?

IR的概念很廣泛，即使從錢包中拿出一張信用卡并輸入卡號(hào)也是一種形式的信息檢索。在學(xué)術(shù)領(lǐng)域，我們這樣定義IR：

?????? 信息檢索(IR)就是一種從大量數(shù)據(jù)集合中(通常指存儲(chǔ)在計(jì)算機(jī)中文檔)尋找滿足信息需求的非結(jié)構(gòu)化(通常指文本)得數(shù)據(jù)(通常指文檔)。

?

?

布爾檢索模型(Boolean Retrieval)

?

要點(diǎn)： (1) 倒排/反向索引模型? inverted indexes

????????? (2) 簡(jiǎn)單的布爾表達(dá)式如何處理這些索引

?

1.1? 詞—文檔的關(guān)聯(lián)矩陣索引? a term-document matrix

?

(1) Unix/Linux? grep- 命令

?

????? 這個(gè)命令或許大家都用過(guò)，它是Unix/Linux中用于在指定文件中查找特定的搜索字符串的命令。它的原理是利用 正則表達(dá)式 在文檔集合中 進(jìn)行線性順序掃描(sort of linear scan)。 這種方式對(duì)于現(xiàn)代計(jì)算機(jī)的運(yùn)行速度而言，在有限的數(shù)據(jù)規(guī)模下做簡(jiǎn)單的查詢足夠應(yīng)付了。

?

(2) Web data 的搜索面臨的現(xiàn)實(shí)問(wèn)題

?

? ??? ▲ 網(wǎng)絡(luò)在線數(shù)據(jù)量(web data/online data)巨大，其增長(zhǎng)的速度遠(yuǎn)大于計(jì)算機(jī)的硬件發(fā)展速度。 如何快速的檢索需要查詢的內(nèi)容？ 這一點(diǎn)線性順序掃描時(shí)永遠(yuǎn)做不到的。

????? ▲ web搜索面臨的是廣大用戶群，其查詢表達(dá)式的方式靈活多樣(并不一定是布爾表達(dá)式)。甚至有的時(shí)候并沒(méi)有準(zhǔn)確的查詢含義。比如查詢query： Romans NEAR courtyman。 這里的NEAR到底是指Romans，courtyman這兩詞需要在文章中同一個(gè)句子里出現(xiàn)，還是相隔若干詞。 如何更好的響應(yīng)用戶的靈活多變的查詢方法，提供更加人性化得服務(wù)呢？

????? ▲ 檢索結(jié)果的排序問(wèn)題也是一個(gè)現(xiàn)實(shí)問(wèn)題。用戶需要看到的是最滿意的答案，那么查詢返回的若干文檔， 到底哪些與用戶查詢最相關(guān)呢？

?

(3)布爾模型的詞—文檔關(guān)聯(lián)矩陣索引模型

?

?????? 線性順序掃面對(duì)于web data來(lái)說(shuō)是不可能的。目前，解決高效檢索大量非結(jié)構(gòu)化的信息的公認(rèn)最好手段就是建立 索引(indexes) 。下面就是一個(gè)簡(jiǎn)單的索引模型——關(guān)聯(lián)矩陣。

?

?????? 1. 詞—文檔關(guān)聯(lián)矩陣? 如下圖，列表示文檔，行表示文檔中的詞。

?

?

?????????? 其中如果Term1出現(xiàn)在Doc1中，則矩陣(1,1)標(biāo)示為1，否則為0。

?

?????? 2. 建立布爾查詢表達(dá)式(boolean query)。? Antony and Brutus not Caesar 也就是我們需要找到包含Antony ,Brutus同時(shí)不包含Caesar 詞語(yǔ)的文檔。

?????? 3. 使用位運(yùn)算:??? Antony and Brutus not Caesar =? 110001 & 110100 & (~110111) =000000. 很可惜，一篇都沒(méi)有。

?

(4) 關(guān)聯(lián)矩陣模型的缺陷

?

??????? 上面這個(gè)簡(jiǎn)單索引模型并不適合Web data的檢索。對(duì)于大數(shù)據(jù)量而言，這個(gè)矩陣實(shí)在是太大了，不可能全部放進(jìn)內(nèi)存。而且更嚴(yán)重的是矩陣太稀疏了。況且對(duì)于檢索結(jié)果的排序問(wèn)題也是解決不了的。

?

?

1.2? 倒排索引? inverted index

?

倒排索引絕對(duì)是一個(gè)偉大的發(fā)現(xiàn)。當(dāng)前很多搜索引擎或者開(kāi)發(fā)包都使用了這個(gè)模型，比如Lucene。

?

(1) 倒排索引結(jié)構(gòu)： 1. 詞語(yǔ)組成的字典結(jié)構(gòu) ——Dictionary ? 如下圖左側(cè)

?????????????????????????? ? 2. 文檔組成的位置鏈 —— Postiong? 如下圖右側(cè)

????????

(2) 創(chuàng)建過(guò)程

????? 1. 將每一個(gè)文檔中的詞語(yǔ)與文檔ID(唯一標(biāo)示文檔)組成一個(gè)Pair，存入index。如左圖A

????? 2. 將index中的詞語(yǔ)按字典序排序。如中圖B

????? 3. 如果相同詞語(yǔ)來(lái)自同一個(gè)文檔，則只記錄一次。相同詞語(yǔ)來(lái)自不同文檔，則合并成進(jìn)posting。如右圖C

?

(3) 索引存儲(chǔ)方法

?

????? 很顯然，對(duì)于倒排索引，我們必須把Dictionary和Posting都存儲(chǔ)起來(lái)。一般Dictionary可以全部加載進(jìn)內(nèi)存中，而Posting存放在磁盤(pán)中，當(dāng)需要查找Posting的時(shí)候，再會(huì)將某一個(gè)詞語(yǔ)所指向的Posting加載進(jìn)內(nèi)存。

?

????? Dictionary in menory

???????????? 很多時(shí)候使用Hash表的形式，也用連續(xù)存儲(chǔ)的數(shù)組結(jié)構(gòu)。

????? Posting in menory：?

??????????? 1. 單鏈表( singly linked lists) ，在將新文檔插入Posting中的時(shí)候付出的代價(jià)較少。這一點(diǎn)很適合高頻率從網(wǎng)上抓取內(nèi)容并更新文檔。

??????????? 2. 可變長(zhǎng)數(shù)組(variable length arrays)，節(jié)約了指針?biāo)枰念~外空間。并且對(duì)于擁有內(nèi)存緩存區(qū)的現(xiàn)代計(jì)算機(jī)而言，連續(xù)內(nèi)存的結(jié)構(gòu)無(wú)疑會(huì)增加查詢的速度。

??????????? 3. 跳躍表(skip lists)，一種很先進(jìn)的存儲(chǔ)結(jié)構(gòu)。除了需要額外耗費(fèi)一些指針空間之外，查找效率極高。Lucene就是用了這種結(jié)構(gòu)。

?

1.3? 布爾查詢表達(dá)式的處理

?

(1)? Posting的合并算法(merge algorithm)

?

?? ? ? 假如我們需要在倒排索引上查找這樣一個(gè)表達(dá)式： Brutus AND Calpurnia。很明顯我們需要下面幾個(gè)步驟：

?????? 1. 在Dictionary中定位Brutus.

?????? 2. 檢索Brutus所指向的Posting：? 1、2、4、11、31....

?????? 3. 在Dictionary中定位Calpurnia.

?????? 4. 檢索Calpurnia所指向的Posting：? 2、31、54....

?????? 5. 合并兩個(gè)Posting.

?

?????? 對(duì)于兩個(gè)有序表的合并算法，可以采用下面的算法： 時(shí)間復(fù)雜度為O(m+n)

    //指針P1,P2分別指向兩個(gè)Posting鏈
Posting intersect(p1,p2){

        Posting answer;
        while(p1!=null&&p2!=null){
                if(p1==p2){
                     add(answer, p1->docID);
                     p1=p1->next;
                     p2=p2->next;
                }
                if(p1>p2)  p2=p2->next;
                if(p1<p2)  p1=p1->next;

        }
}
  

?

(2) 布爾表達(dá)式的優(yōu)化

?

????? Brutus AND Caesar AND Calpurnia

?

???? ? 表達(dá)式的AND順序按照每一個(gè)詞的文檔頻率遞增進(jìn)行優(yōu)化。 比如 Brutus‘s Ducument Frequence(Brutus所在文檔的數(shù)量，符號(hào)表示DF(Brutus))。DF(Brutus)=1000，DF(Caesar)=10000，DF(Calpurnia)=100。那么查詢表達(dá)式可以優(yōu)化成： (Calpurnia AND Brutus) AND Caesar。

?

?????? 理由很簡(jiǎn)單，Calpurnia AND Brutus的時(shí)間復(fù)雜度(利用上面的合并算法)為O(1100)，其合并后的中間結(jié)果R=DF(Calpurnia AND Brutus)<DF(Calpurnia)=100。此時(shí)將這個(gè)中將結(jié)果R AND Caesar 的時(shí)間復(fù)雜度不會(huì)超過(guò)O(100+10000)。而且最后結(jié)果頁(yè)不會(huì)操作DF<DF(Calpurnia AND Brutus)<100?？偟臅r(shí)間復(fù)雜度為O(1100+10100)=O(11200)

?????? 如果使用原表達(dá)式， Brutus AND Caesa的時(shí)間復(fù)雜度為O(11000)，且中間結(jié)果為R=DF( Brutus AND Caesa )< DF(Brutus)=1000。然后R AND Calpurnia的時(shí)間復(fù)雜度可能達(dá)到O(1000+100)。兩次AND操作的總時(shí)間復(fù)雜度為O(11000+1100)=O(12100)

?????? 明顯優(yōu)化之后的時(shí)間復(fù)雜度會(huì)少。 如果查詢表達(dá)式更長(zhǎng)，查詢?cè)~語(yǔ)的DF差距更大，那么優(yōu)化的效率會(huì)更明顯 。

?

?????? 根據(jù)上面的優(yōu)化原理，對(duì)于更加復(fù)雜的查詢表達(dá)式(madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)。我們一般都會(huì)估算OR操作兩個(gè)詞的DF之和的數(shù)量，然后進(jìn)行AND遞增排序。

?

?????? 事實(shí)上， 對(duì)于任意的布爾表達(dá)式，每一次操作的中間結(jié)果(intermediate)越小越好。 這是我們進(jìn)行優(yōu)化的原則所在。

?

(3) 自然語(yǔ)言查詢 AND 布爾查詢表達(dá)式

?

?????? 為什么我們對(duì)布爾表達(dá)式的操作只將AND，很少說(shuō)OR或NOT呢？

?

?????? 在搜索引擎實(shí)際應(yīng)用的環(huán)境下，用戶的查詢都是自然語(yǔ)言敘述的，很少直接用布爾表達(dá)式(你不能要求所有的用戶必須邏輯思維縝密吧)。 那么對(duì)于用戶提交的這些查詢，都是純粹的合并操作。

?

?????? 正是這個(gè)原因，現(xiàn)實(shí)中很多搜索引擎的應(yīng)用已經(jīng)退化成了只有AND的布爾模型了。

?

?

《Introduce to IR》布爾檢索模型