該系列文章是《An Introduce to Information Retrieval》Chapter 1 的讀書筆記。
?
?
IR的概念很廣泛，即使從錢包中拿出一張信用卡并輸入卡號也是一種形式的信息檢索。在學術領域，我們這樣定義IR：
?????? 信息檢索(IR)就是一種從大量數據集合中(通常指存儲在計算機中文檔)尋找滿足信息需求的非結構化(通常指文本)得數據(通常指文檔)。
?
?
布爾檢索模型(Boolean Retrieval)
?
要點： (1) 倒排/反向索引模型? inverted indexes
????????? (2) 簡單的布爾表達式如何處理這些索引
?
1.1? 詞—文檔的關聯矩陣索引? a term-document matrix
?
(1) Unix/Linux? grep- 命令
?
????? 這個命令或許大家都用過，它是Unix/Linux中用于在指定文件中查找特定的搜索字符串的命令。它的原理是利用 正則表達式 在文檔集合中 進行線性順序掃描(sort of linear scan)。 這種方式對于現代計算機的運行速度而言，在有限的數據規模下做簡單的查詢足夠應付了。
?
(2) Web data 的搜索面臨的現實問題
?
? ??? ▲ 網絡在線數據量(web data/online data)巨大，其增長的速度遠大于計算機的硬件發展速度。 如何快速的檢索需要查詢的內容？ 這一點線性順序掃描時永遠做不到的。
????? ▲ web搜索面臨的是廣大用戶群，其查詢表達式的方式靈活多樣(并不一定是布爾表達式)。甚至有的時候并沒有準確的查詢含義。比如查詢query： Romans NEAR courtyman。 這里的NEAR到底是指Romans，courtyman這兩詞需要在文章中同一個句子里出現，還是相隔若干詞。 如何更好的響應用戶的靈活多變的查詢方法，提供更加人性化得服務呢？
????? ▲ 檢索結果的排序問題也是一個現實問題。用戶需要看到的是最滿意的答案，那么查詢返回的若干文檔， 到底哪些與用戶查詢最相關呢？
?
(3)布爾模型的詞—文檔關聯矩陣索引模型
?
?????? 線性順序掃面對于web data來說是不可能的。目前，解決高效檢索大量非結構化的信息的公認最好手段就是建立 索引(indexes) 。下面就是一個簡單的索引模型——關聯矩陣。
?
?????? 1. 詞—文檔關聯矩陣? 如下圖，列表示文檔，行表示文檔中的詞。
?
?
?????????? 其中如果Term1出現在Doc1中，則矩陣(1,1)標示為1，否則為0。
?
?????? 2. 建立布爾查詢表達式(boolean query)。? Antony and Brutus not Caesar 也就是我們需要找到包含Antony ,Brutus同時不包含Caesar 詞語的文檔。
?????? 3. 使用位運算:??? Antony and Brutus not Caesar =? 110001 & 110100 & (~110111) =000000. 很可惜，一篇都沒有。
?
(4) 關聯矩陣模型的缺陷
?
??????? 上面這個簡單索引模型并不適合Web data的檢索。對于大數據量而言，這個矩陣實在是太大了，不可能全部放進內存。而且更嚴重的是矩陣太稀疏了。況且對于檢索結果的排序問題也是解決不了的。
?
?
1.2? 倒排索引? inverted index
?
倒排索引絕對是一個偉大的發現。當前很多搜索引擎或者開發包都使用了這個模型，比如Lucene。
?
(1) 倒排索引結構： 1. 詞語組成的字典結構 ——Dictionary ? 如下圖左側
?????????????????????????? ? 2. 文檔組成的位置鏈 —— Postiong? 如下圖右側
????????
(2) 創建過程
????? 1. 將每一個文檔中的詞語與文檔ID(唯一標示文檔)組成一個Pair，存入index。如左圖A
????? 2. 將index中的詞語按字典序排序。如中圖B
????? 3. 如果相同詞語來自同一個文檔，則只記錄一次。相同詞語來自不同文檔，則合并成進posting。如右圖C
?
(3) 索引存儲方法
?
????? 很顯然，對于倒排索引，我們必須把Dictionary和Posting都存儲起來。一般Dictionary可以全部加載進內存中，而Posting存放在磁盤中，當需要查找Posting的時候，再會將某一個詞語所指向的Posting加載進內存。
?
????? Dictionary in menory
???????????? 很多時候使用Hash表的形式，也用連續存儲的數組結構。
????? Posting in menory：?
??????????? 1. 單鏈表( singly linked lists) ，在將新文檔插入Posting中的時候付出的代價較少。這一點很適合高頻率從網上抓取內容并更新文檔。
??????????? 2. 可變長數組(variable length arrays)，節約了指針所需要的額外空間。并且對于擁有內存緩存區的現代計算機而言，連續內存的結構無疑會增加查詢的速度。
??????????? 3. 跳躍表(skip lists)，一種很先進的存儲結構。除了需要額外耗費一些指針空間之外，查找效率極高。Lucene就是用了這種結構。
?
1.3? 布爾查詢表達式的處理
?
(1)? Posting的合并算法(merge algorithm)
?
?? ? ? 假如我們需要在倒排索引上查找這樣一個表達式： Brutus AND Calpurnia。很明顯我們需要下面幾個步驟：
?????? 1. 在Dictionary中定位Brutus.
?????? 2. 檢索Brutus所指向的Posting：? 1、2、4、11、31....
?????? 3. 在Dictionary中定位Calpurnia.
?????? 4. 檢索Calpurnia所指向的Posting：? 2、31、54....
?????? 5. 合并兩個Posting.
?
?????? 對于兩個有序表的合并算法，可以采用下面的算法： 時間復雜度為O(m+n)
//指針P1,P2分別指向兩個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) 布爾表達式的優化
?
????? Brutus AND Caesar AND Calpurnia
?
???? ? 表達式的AND順序按照每一個詞的文檔頻率遞增進行優化。 比如 Brutus‘s Ducument Frequence(Brutus所在文檔的數量，符號表示DF(Brutus))。DF(Brutus)=1000，DF(Caesar)=10000，DF(Calpurnia)=100。那么查詢表達式可以優化成： (Calpurnia AND Brutus) AND Caesar。
?
?????? 理由很簡單，Calpurnia AND Brutus的時間復雜度(利用上面的合并算法)為O(1100)，其合并后的中間結果R=DF(Calpurnia AND Brutus)<DF(Calpurnia)=100。此時將這個中將結果R AND Caesar 的時間復雜度不會超過O(100+10000)。而且最后結果頁不會操作DF<DF(Calpurnia AND Brutus)<100。總的時間復雜度為O(1100+10100)=O(11200)
?????? 如果使用原表達式， Brutus AND Caesa的時間復雜度為O(11000)，且中間結果為R=DF( Brutus AND Caesa )< DF(Brutus)=1000。然后R AND Calpurnia的時間復雜度可能達到O(1000+100)。兩次AND操作的總時間復雜度為O(11000+1100)=O(12100)
?????? 明顯優化之后的時間復雜度會少。 如果查詢表達式更長，查詢詞語的DF差距更大，那么優化的效率會更明顯 。
?
?????? 根據上面的優化原理，對于更加復雜的查詢表達式(madding OR crowd) AND (ignoble OR strife) AND (killed OR slain)。我們一般都會估算OR操作兩個詞的DF之和的數量，然后進行AND遞增排序。
?
?????? 事實上， 對于任意的布爾表達式，每一次操作的中間結果(intermediate)越小越好。 這是我們進行優化的原則所在。
?
(3) 自然語言查詢 AND 布爾查詢表達式
?
?????? 為什么我們對布爾表達式的操作只將AND，很少說OR或NOT呢？
?
?????? 在搜索引擎實際應用的環境下，用戶的查詢都是自然語言敘述的，很少直接用布爾表達式(你不能要求所有的用戶必須邏輯思維縝密吧)。 那么對于用戶提交的這些查詢，都是純粹的合并操作。
?
?????? 正是這個原因，現實中很多搜索引擎的應用已經退化成了只有AND的布爾模型了。
?
?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索：z360901061
微信掃一掃加我為好友
QQ號聯系： 360901061
您的支持是博主寫作最大的動力，如果您喜歡我的文章，感覺我的文章對您有幫助，請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧，狠狠點擊下面給點支持吧，站長非常感激您！手機微信長按不能支付解決辦法：請將微信支付二維碼保存到相冊，切換到微信，然后點擊微信右上角掃一掃功能，選擇支付二維碼完成支付。
【本文對您有幫助就好】元
