第1章 布爾檢索

• 信息檢索的定義：信息檢索（IR）是從大型集合（通常存儲在計算機上）中尋找滿足信息需求的非結構化性質（通常是文本）的材料（通常是文檔）。

1.1一個信息檢索的例子

問題描述：確定莎士比亞的作品集中，哪些戲劇包含了詞匯Brutus和Caesar而不包含Calpumia。

1.解決辦法

（1）最簡單的文檔檢索形式：計算機通過文檔進行線性掃描（Unix/Linux中文本掃描grep）
缺點：線性掃描的時間復雜度與文檔集大小成正比，不適合大規模文本檢索
無法滿足以下需求：
1.快速處理大型文檔集合
2.更靈活的匹配操作
3.檢索結果排序
（2）提前建立索引文檔：避免對每個查詢進行線性掃描，以詞項（term）為橫坐標，文檔（document）為縱坐標，根據文檔中是否出現該詞匯建立二進制詞匯-文本關聯矩陣。

圖1.1 詞匯-文檔關聯矩陣，當d列包含t行單詞時M(t,d)為1，否則為0

針對本問題，取詞匯Brutus和Caesar及Calpumia的行向量做運算（Brutus AND Caesar AND NOT Calpumia），得出問題答案: Antony and Cleopatra和Hamlet.

110100 and 110111 and 101111 = 100100

2.相關概念

• 布爾檢索模型（Boolean retrieval model）：信息檢索的一個模型，布爾檢索模型可以提出以布爾表達式的形式表示（結合邏輯運算符and，or，not）的任何查詢。該模型將每個文檔看作是一組單詞。
• 正確率（Precision）：評估一個IR系統的有效性的關鍵統計信息，返回的結果中有多少與信息需求相關.
• 召回率(recall)：評估一個IR系統的有效性的關鍵統計信息，在收集的相關文檔中，有多少是由系統返回的.

3.倒排索引（inverted index）

考慮500K*1M的詞項-文檔關聯矩陣：矩陣規模超出計算機內存而難以存儲，觀察矩陣可以發現其為稀疏矩陣，那么一個更好的方式為只記錄1的位置。

圖1.2 倒排索引的兩部分，倒排記錄表（postings）以文件ID排序

• 詞典（Dictionary）：存儲詞項，并有一個指向每個詞項的倒排記錄表的指針，通常還存儲其他的摘要信息，例如，每個詞項的文檔頻率等
• 倒排記錄表（Postings）：存儲詞項出現的文檔列表，并可能存儲其他信息，如詞項頻率（每個文檔中每個詞項的頻率）或每個文檔中詞項的位置等。
  （概念辨析：√倒排記錄(posting)：詞項對應的list中的每一個元素；√倒排表(posting list/inverted list)：一個詞項對應的整個list；√倒排記錄表（Postings）：所有詞項的倒排表一起構成）

1.2建立倒排索引

1.主要步驟：
（1）收集被索引的文檔
（2）標記文本，將每個文檔轉換為詞條（token）
（3）進行語言預處理，生成標準化詞條：
（4）通過創建一個倒排索引來索引每一項的文檔，包括一個詞典和一個倒排記錄表。（詞典通常保存在內存中，倒排記錄表通常保存在磁盤上）

√對每個詞項t, 記錄所有包含t的文檔，建立詞條序列<詞條，docID>二元組
√對詞項、文檔排序。對詞項按字母排序，對倒排記錄表按docID排序
√合并相同詞項，并記錄文檔頻率doc.freq（記錄所有包含詞項t的文檔數目）

2. For example：

圖1.3 通過排序和分組構建索引

1.3 處理布爾查詢

1.簡單的連接查詢：Brutus And Calpurnia
建立Brutus 和 Calpurnia的倒排索引，進行如下操作：
（1）在詞典里找到Brutus
（2）檢索其倒排記錄表
（3）在詞典里找到Calpurnia
（4）檢索其倒排記錄表
（5）合并倒排記錄表（合并倒排記錄表能夠快速找到包含兩個詞項的文檔）

圖1.4 合并Brutus和Calpurnia倒排記錄表

√合并算法：將指針保持在兩個列表中，同時遍歷兩列表，每一步中比較兩個指針指向的檢驗結果。如果相同則將這個檢驗放在結果列表中，并同時推進兩個指針；否則將指針指向較小的docID。
√復雜度：如果列表的長度是x和y，那么交集就是O（x+y）操作。常數時間復雜度，但在實踐中，這個常數是巨大的。要使用這種算法，關鍵是要按全局統一標準排序列表。

圖1.5 兩個倒排記錄表p1和p2的合并算法

2.擴展交集操作處理更復雜的查詢：(Brutus or Caesar) and not Calpurnia

3.查詢優化：選擇如何組織查詢的處理過程，使系統需要完成最少工作。考慮t個詞項和的查詢，例如：Brutus and Caesar and Calpurnia

√分析：將t個詞項中的所有項的倒排記錄表進行與運算。標準的啟發式算法是根據詞項的文檔頻率遞增方向處理，如果從兩個最小的倒排記錄表開始合并，那么所有的中間結果都不應該比最小的倒排記錄表大，因此可能會做最少的總工作。
√調整：在詞典中保持詞項的頻率的第一個調整，允許在訪問任何倒排記錄表之前基于內存中的數據做出這個排序決定。執行以下查詢：
(Calpurnia and Brutus) and Caesar

4.對更一般的查詢進行優化
例如：(madding or crowd) and (ignoble or strife) and (killed or slain)
((范式存在定理)任一命題公式都存在著與之等值的析取范式和合取范式，即任何布爾查詢邏輯表達式都能轉換為合取范式）

√處理步驟：
（1）獲得每個詞項的doc.freq
（2）通過將詞項的doc.freq相加，保守估計每個OR表達式對應的倒排記錄表的大小
（3）將每個OR表達式從小到大依次處理

√中間結果列表替換：
對于任意的布爾查詢，必須對復雜表達式中中間表達式的答案進行評估和臨時存儲。在查詢是純連接的情況下,比起將合并倒排記錄表作為一個有兩個輸入和一個輸出的函數,更高效的是對每個檢索的倒排記錄表以當前內存中的中間結果取交集,通過加載最少頻率詞項的倒排記錄表初始化中間結果。算法如圖：

圖1.6 返回包含輸入詞項的文檔集的連接查詢算法
（1）交集運算是不對稱的：中間結果列表在內存中，而與之交叉的列表正在從磁盤讀取。中間結果列表總是至少和其他列表一樣短，而且在許多情況下，它的數量級要短一些。
（2）時間復雜度：當列表長度的差異非常大時，使用替換技術是很有效果的。在中間結果列表中，可以通過破壞性修改或標記無效項來計算交集。或者交集可以作為中間結果列表中每個倒排記錄表中的一個二進制搜索序列。另一種可能是將長倒排記錄表存儲為哈希表，可以在常量時間內計算中間結果項。
（3）這種替代技術很難與排序列表壓縮相結合。當查詢的兩個詞項都很常見時，標準的倒排記錄表的交集操作仍然必要。

1.4 擴展的布爾模型與排名檢索

• 排名檢索模型：如向量空間模型，主要為自由文本查詢,只要輸入一個或多個單詞而非精確的語言與運營商建立查詢表達式,由系統決定哪些文檔最滿足查詢。

• 擴展的布爾檢索模型：系統通過合并額外的操作符來實現，例如，詞項接近操作符。

• 近距離操作符：一種指定操作符查詢中的兩個詞項必須在文檔中彼此接近的方法，通過限制插入詞的允許數量或引用一個句子或段落等結構單元來衡量親密度。

Eg. 商業布爾查詢：Westlaw
語法： 空格 - 分割 ；& - AND ； /s,/p和/k - 相同句子、相同段落或k個單詞中的匹配 ； “” - 字符串 ； ！ - 通配符查詢（如liab！表示匹配所有以liab開頭的單詞） ； work-site 匹配worksite、work site、worksite；

√布爾查詢優缺點：
優點：精確，文檔要么匹配查詢，要么不匹配。這為用戶提供了更大的控制和對所檢索到的內容的透明性。
缺點：使用和操作符往往會產生高精度但低的回憶搜索，而使用或操作符則提供低精度但高的回憶搜索

√對非結構化信息進行臨時搜索的基本技術的產生:
更多需求：
（1）希望能更好地確定字典中的一組詞項，并提供對拼寫錯誤和用詞不一致的檢索
（2）希望做一些接近于微軟的近距離查詢。要回答這樣的查詢，必須增加索引以捕獲文檔中詞項的近端。
（3）一個布爾模型只記錄詞項的存在或缺失，但通常希望積累證據，對那些有一個詞項的文檔給予更多的權重，而不是只包含一次的文檔。為了做到這一點，需要在倒排記錄表中使用詞項頻率信息（一個詞項在文檔中出現的次數）
（4）布爾查詢只是檢索一組匹配的文檔，希望有一個有效的方法來訂購（或排名）返回的結果。這需要有一種機制來確定文檔的分數，它封裝了一個文檔對查詢的匹配程度。

總結

以上是生活随笔為你收集整理的《introduction to information retrieval》信息检索学习笔记1 布尔检索的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。