信息檢索:實現和評價搜尋引擎

信息檢索:實現和評價搜尋引擎

《信息檢索:實現和評價搜尋引擎》是2012年1月機械工業出版社出版的一本圖書,作者是(美)Stefan Büttcher, (加)Charles L.A.Clarke, (加)Gordon V.Cormack。

基本信息

叢書名: 計算機科學叢書 出版社:機械工業出版社

上架時間:2011-12-16

出版日期:2012 年1月

開本:16開

頁碼:1

版次:1-1

所屬分類: 計算機

內容簡介

《信息檢索:實現和評價搜尋引擎》從多個視角對信息檢索技術進行了深入講解,內容涵蓋了信息檢索系統的架構、基礎技術、詞條和詞項、靜態和動態倒排索引、查詢處理、索引壓縮技術、機率模型、語言模型、分類和過濾、融合和元學習、評價方法以及並行信息檢索、web檢索和xml檢索等具體套用。本書以模組化的方式進行組織,理論性強,體系完整,同時強調實踐。作者以認真嚴謹的態度實現了書中絕大部分的主要方法,並詳盡地描述了各種方法的適用環境以及取得的效果。

《信息檢索:實現和評價搜尋引擎》可作為高等院校信息管理與信息系統、計算機科學與技術、情報學、圖書館學以及電子商務等專業的高年級本科生和研究生的教材和參考書,對於從事信息檢索與網路分析等實際工作的從業人員也具有較高的參考價值。

目錄

《信息檢索:實現和評價搜尋引擎》

information retrieval: implementing and evaluating search engines

出版者的話

譯者序

前言

符號

第一部分基 礎 知 識

第1章緒論

1.1什麼是信息檢索

1.1.1web搜尋

1.1.2其他搜尋套用

1.1.3其他信息檢索套用

1.2信息檢索系統

1.2.1信息檢索系統基礎架構

1.2.2文檔及其更新

1.2.3性能評價

1.3使用電子文本

1.3.1文本格式

1.3.2英文文本中的分詞

.1.3.3詞項分布

1.3.4語言模型

1.4測試集

1.5開源信息檢索系統

1.5.1lucene

1.5.2indri

1.5.3wumpus

1.6延伸閱讀

1.7練習

1.8參考文獻

第2章基礎技術

2.1倒排索引

2.1.1延伸例子:詞組查找

2.1.2實現倒排索引

2.1.3文檔和其他元素

2.2檢索與排名

2.2.1向量空間模型

2.2.2鄰近度排名

2.2.3布爾檢索

2.3評價

2.3.1查全率和查準率

2.3.2排名檢索的有效性指標

2.3.3創建測試集

2.3.4效率指標

2.4總結

2.5延伸閱讀

2.6練習

2.7參考文獻

第3章詞條與詞項

3.1英語

3.1.1標點與大寫

3.1.2詞幹提取

3.1.3停詞

3.2字元

3.3字元n?gram

3.4歐洲語言

3.5cjk語言

3.6延伸閱讀

3.7練習

3.8參考文獻

第二部分索引

第4章靜態倒排索引

4.1索引的組成部分和索引的生命周期

4.2詞典

4.3位置信息列表

4.4交錯詞典和位置信息列表

4.5索引的構建

4.5.1基於記憶體的索引構建法

4.5.2基於排序的索引構建法

4.5.3基於合併的索引構建法

4.6其他索引

4.7總結

4.8延伸閱讀

4.9練習

4.10參考文獻

第5章查詢處理

5.1排名檢索的查詢處理

5.1.1document?at?a?time查詢處理

5.1.2term?at?a?time查詢處理

5.1.3預計算得分貢獻

5.1.4影響力排序

5.1.5靜態索引裁剪

5.2輕量級結構

5.2.1廣義索引表

5.2.2操作符

5.2.3例子

5.2.4實現

5.3延伸閱讀

5.4練習

5.5參考文獻

第6章索引壓縮

6.1通用數據壓縮

6.2符號數據壓縮

6.2.1建模和編碼

6.2.2哈夫曼編碼

6.2.3算術編碼

6.2.4基於符號的文本壓縮

6.3壓縮位置信息列表

6.3.1無參數間距壓縮

6.3.2參數間距壓縮

6.3.3上下文感知的壓縮方法

6.3.4高查詢性能的索引壓縮

6.3.5壓縮效果

6.3.6解碼性能

6.3.7文檔重排

6.4壓縮詞典

6.5總結

6.6延伸閱讀

6.7練習

6.8參考文獻

第7章動態倒排索引

7.1批量更新

7.2增量式索引更新

7.2.1連續倒排列表

7.2.2非連續倒排列表

7.3文檔刪除

7.3.1無效列表

7.3.2垃圾回收

7.4文檔修改

7.5討論及延伸閱讀

7.6練習

7.7參考文獻

第三部分檢索和排名

第8章機率檢索

8.1相關性建模

8.2二元獨立模型

8.3robertson/sp?rck jones權重公式

8.4詞頻

8.4.1bookstein的雙泊松模型

8.4.2雙泊松模型的近似

8.4.3查詢詞頻

8.5文檔長度:bm25

8.6相關反饋

8.6.1詞項選擇

8.6.2偽相關反饋

8.7區域權重:bm25f

8.8實驗對比

8.9延伸閱讀

8.10練習

8.11參考文獻

第9章語言模型及其相關方法

9.1從文檔中產生查詢

9.2語言模型和平滑

9.3使用語言模型排名

9.4kullback?leibler距離

9.5隨機差異性

9.5.1一個隨機模型

9.5.2精華性

9.5.3文檔長度規範化

9.6段落檢索及排名

9.6.1段落評分

9.6.2實現

9.7實驗對比

9.8延伸閱讀

9.9練習

9.10參考文獻

第10章分類和過濾

10.1詳細示例

10.1.1面向主題的批過濾

10.1.2線上過濾

10.1.3從歷史樣本中學習

10.1.4語言分類

10.1.5線上自適應垃圾郵件過濾系統

10.1.6二元分類的閾值選擇

10.2分類

10.2.1比值和比值比

10.2.2構造分類器

10.2.3學習模型

10.2.4特徵工程

10.3機率分類器

10.3.1機率估計

10.3.2聯合機率估計

10.3.3實際考慮

10.4線性分類器

10.4.1感知器算法

10.4.2支持向量機

10.5基於相似度的分類器

10.5.1rocchio法

10.5.2基於記憶的方法

10.6廣義線性模型

10.7信息理論模型

10.7.1模型比較

10.7.2序列壓縮模型

10.7.3決策樹與樹樁

10.8實驗對比

10.8.1面向主題的線上過濾器

10.8.2線上自適應垃圾信息過濾

10.9延伸閱讀

10.10練習

10.11參考文獻

第11章融合和元學習

11.1搜尋結果融合

11.1.1固定臨界值合成

11.1.2排名和得分合成

11.2疊加自適應過濾器

11.3疊加批分類器

11.3.1holdout驗證

11.3.2交叉驗證

11.4bagging

11.5boosting

11.6多類排名和分類

11.6.1文檔得分與類別得分

11.6.2文檔排名融合與類別排名融合

11.6.3多類方法

11.7學習排名

11.7.1什麼是學習排名

11.7.2學習排名的方法

11.7.3最佳化什麼

11.7.4分類的學習排名

11.7.5排名檢索的學習

11.7.6letor數據集

11.8延伸閱讀

11.9練習

11.10參考文獻

第四部分評價

第12章度量有效性

12.1傳統的有效性指標

12.1.1查全率和查準率

12.1.2前k個文檔的查準率

12.1.3平均查準率

12.1.4排名倒數

12.1.5算術平均與幾何平均

12.1.6用戶滿意度

12.2trec

12.3在評價中使用統計

12.3.1基礎和術語

12.3.2置信區間

12.3.3比較評價

12.3.4被認為有害的假設檢驗

12.3.5配對和未配對差值

12.3.6顯著性檢驗

12.3.7統計檢驗的效度和檢驗力

12.3.8報告指標的查準率

12.3.9元分析

12.4最小化判定工作

12.4.1為判定選擇合適的文檔

12.4.2對池進行抽樣

12.5非傳統的有效性指標

12.5.1分級相關性

12.5.2不完整判定和偏差判定

12.5.3新穎性和多樣性

12.6延伸閱讀

12.7練習

12.8參考文獻

第13章度量效率

13.1效率標準

13.1.1吞吐量和延遲

13.1.2匯總統計和用戶滿意度

13.2排隊論

13.2.1肯德爾符號

13.2.2m/m/1排隊模型

13.2.3延遲量和平均利用率

13.3查詢調度

13.4快取

13.4.1三級快取

13.4.2快取策略

13.4.3預取搜尋結果

13.5延伸閱讀

13.6練習

13.7參考文獻

第五部分套用和擴展

第14章並行信息檢索

14.1並行查詢處理

14.1.1文檔劃分

14.1.2詞項劃分

14.1.3混合方案

14.1.4冗餘和容錯

14.2mapreduce

14.2.1基本框架

14.2.2合併

14.2.3輔助關鍵字

14.2.4機器失效

14.3延伸閱讀

14.4練習

14.5參考文獻

第15章web搜尋

15.1web的結構

15.1.1web圖

15.1.2靜態與動態網頁

15.1.3暗網

15.1.4web的規模

15.2查詢與用戶

15.2.1用戶意圖

15.2.2點擊曲線

15.3靜態排名

15.3.1基本pagerank

15.3.2擴展的pagerank

15.3.3pagerank的性質

15.3.4其他連結分析方法:hits和salsa

15.3.5其他靜態排名方法

15.4動態排名

15.4.1錨文本

15.4.2新穎性

15.5評價web搜尋

15.5.1指定頁面發現

15.5.2用戶隱式反饋

15.6web爬蟲

15.6.1爬蟲的組成

15.6.2抓取順序

15.6.3重複與近似重複

15.7總結

15.8延伸閱讀

15.8.1連結分析

15.8.2錨文本

15.8.3隱式反饋

15.8.4web爬蟲

15.9練習

15.10參考文獻

第16章xml檢索

16.1xml的本質

16.1.1文檔類型定義

16.1.2xml模式

16.2路徑、樹和flwor

16.2.1xpath

16.2.2nexi

16.2.3xquery

16.3索引和查詢處理

16.4排名檢索

16.4.1排名元素

16.4.2重疊元素

16.4.3可檢索元素

16.5評價

16.5.1測試集

16.5.2有效性指標

16.6延伸閱讀

16.7練習

16.8參考文獻

第六部分附錄

附錄a計算機性能

譯者序

Information Retrieval: Implementing and Evaluating Search Engines

由於手機、個人電腦、網際網路等信息工具的快速發展和進化,個人可獲取和管理的信息量呈爆發式增長,如何快速準確地找到所需的信息成為信息處理中的一個難題。信息檢索技術是解決該問題的主要方法,其最初來源於圖書內容的索引和檢索,近些年來由於網際網路的發展,以此為基礎的搜尋引擎技術使其受到了廣泛的關注和研究。國內無論是高等院校相關專業方向的研究生,還是對搜尋技術感興趣的研究者和開發人員,都迫切需要一本全面專業的信息檢索書籍。

國內引進了多本信息檢索領域的書籍,本書是其中較新較有特色的一本。它以模組化的方式進行組織,從多個視角對信息檢索技術進行了深入的解析,並補充了相關學科的基本知識,例如通用的符號數據壓縮技術、統計分析、機器學習、資料庫、Web結構、XML等等,使讀者免去了查閱大量資料和其他書籍的麻煩。這本書理論性強,體系完整,同時也很強調實踐。作者以認真嚴謹的態度對書中絕大部分的主要方法給出了實現細節和分析,並通過實驗對比了這些方法,詳盡地描述了各種方法的適用環境以及取得的效果,為信息檢索在具體環境下的套用提供了很好的參考。在每一章最後的延伸閱讀和參考文獻部分,讀者還可以了解到該章相關知識點的研究歷史、發展和目前最新狀況,也可據此對相關內容進行更深入的了解和研究。課後練習也經過了精心的設計,各章習題彼此關聯、循序漸進,能夠幫助讀者更好地理解各章的知識點。

感謝原著作者無私地分享了他們在信息檢索領域內的獨特見解和研究成果。在過去幾個月中,胡清蘭、吳燦榮、李仕釗、黃錦捷、李蕾、黃蕉平、黃璡都參與了部分翻譯、審校工作。感謝徐亞波老師及其學生給出的寶貴意見。當然,本書的翻譯工作得以順利完成,還要感謝機械工業出版社的王春華編輯和其他所有工作人員在各方面的支持和幫助。最後,對於給予我們無私幫助的那些人致以誠摯的謝意。

由於譯者水平有限,書中疏漏在所難免,敬請讀者批評指正。

陳健、黃晉

2011年6月29日

前言

Information Retrieval: Implementing and Evaluating Search Engines

信息檢索奠定了現代搜尋引擎的基石。在這本教材中,我們針對計算機科學、計算機工程和軟體工程的研究生以及專業人員介紹了信息檢索。選擇的主題引起了大部分讀者的興趣,涵蓋了算法、數據結構、索引、檢索和評價的核心主題,為讀者今後的學習提供廣博的基礎。同時考慮Web搜尋引擎、並行系統和XML檢索在已有和新的套用場景的特性。

我們的目的是在理論與實踐之間取得平衡,稍微偏向於實踐,強調實現和實驗。只要有可能,本書中的方法都通過實驗進行了對比和驗證。每一章都包含了練習和學生項目。本書其中一位作者開發的一個多用戶開源信息檢索系統Wumpus,提供了模型實現,可作為學生練習的基礎。可以通過

獲取Wumpus。

本書組織

本書以模組化結構組織,可分為5個部分。第一部分提供了介紹性的材料。第二至第四部分,每部分專注於一個重要主題領域:索引、檢索和評價。閱讀完第一部分後,第二至第四部分都可以分別單獨閱讀。第五部分主要基於前面部分的內容來介紹具體的套用領域。

第一部分涵蓋了信息檢索的基礎知識。第1章討論基本概念,包括信息檢索系統的架構、術語、文本特徵、文檔格式、詞項分布、語言模型和測試集。第2章介紹3個重要主題(索引、檢索和評價)的基礎。這3個主題稍後在各自所屬的部分(第二至第四部分)有詳細介紹。這一章也為讀者可以獨立閱讀每個主題或多或少地提供了基礎。第一部分的最後一章,即第3章,繼續介紹了在第1章中引入、在第2章中結束的部分主題。它涉及的問題與具體的自然(即人類)語言相關,特別是分詞(tokenization)——為了進行索引和檢索而將一個文檔轉化成一個詞項序列的過程。一個信息檢索系統必須能夠處理由多種自然語言混合的文檔,而這一章就是從這方面討論幾種主要語言的重要特性。

第二部分主要討論倒排索引的創建、訪問和維護。第4章討論建立和訪問靜態(static)索引的算法,這種索引適用於不常變動的文檔集,即當文檔發生變動時,有足夠的時間來重新從頭建立索引。第5章討論索引訪問和查詢過程,這一章介紹一種輕量級的方法來處理文檔結構,並使用這種方法來支持布爾約束。第6章介紹索引壓縮。第7章提出用於維護動態(dynamic)文檔集的算法,也就是文檔的更新相對於查詢次數是頻繁的,同時要求更新必須迅速。

第三部分介紹了檢索方法和算法。第8章和第9章介紹並比較兩種基於文檔內容的重要排名檢索方法:機率模型和語言模型。通過使用文檔結構、反饋和查詢擴展,可考慮利用一些顯式的相關信息來提高這些方法的有效性。我們討論了每種方法的細節。第10章介紹用於文檔分類和過濾的技術,包括用於分類的基本的機器學習算法。第11章介紹將證據和參數調整進行整合的技術,以及元學習算法及其在排名中的套用。

信息檢索評價是第四部分的主題,用獨立的章節分別介紹了有效性和效率。第12章給出了基本的有效性度量指標,探討了用於評價有效性的統計基礎,並討論了一些在最近10年裡提出的度量指標,它們已經超出了傳統信息檢索評價方法的範圍。第13章介紹了從回響時間和吞吐量來評價信息檢索系統性能的方法。

第五部分是全書的最後一部分,內容涉及一些具體的套用領域,借用並擴展了來自前四個部分的一些基本內容。第14章介紹了並行搜尋引擎的架構和操作。第15章討論了關於Web搜尋引擎的一些主題,包括連結分析、抓取和重複檢查。第16章介紹了XML文檔集上的信息檢索。

書中的每一章都包含了一個小節為深入閱讀提供了參考文獻,還提供了一組練習題。練習題一般偏向於考查和擴展相應章節介紹的概念。有些練習只需用鉛筆和紙花上幾分鐘就能做好;有些則是需要大量編程的項目。這些參考文獻和練習題同時也為我們提供了機會來學習一些在該章的正文部分沒有涵蓋的重要概念和主題。

下面的示意圖展示了本書的各章和各部分之間的關係。箭頭表示各章之間的依賴關係。本書的組織使得讀者可以關注主題的不同方面。從資料庫系統實現的觀點來教授的課程可以包括第1~2、4~7和13~14章。專注於理論的傳統信息檢索課程可以包括第1~3、8~12和16章。關於Web檢索基礎的課程可以包括第1~2、4~5、8和13~15章。每一種涵蓋的章節數約占全書的1/2~2/3,可以在一個3~4個月的研究生課程中完成。

本書的組織。各章之間的箭頭表示它們之間的依賴關係

背景

我們假設讀者擁有計算機科學、計算機工程、軟體工程或相關學科的本科相當的基本背景知識,包括:(1)基本數據結構的概念,例如鍊表數據結構、B?樹和哈希函式;(2)算法和時間複雜度分析;(3)作業系統、磁碟設備、記憶體管理和檔案系統。另外,我們假設一些讀者熟悉初等機率論和統計學,包括如隨機變數、分布和機率群分布函式等概念。

致謝

我們的很多同事花費了大量的時間幫助我們審閱了與其專業領域相關的章節的草稿。我們在這裡特別感謝Eugene Agichtein,Alina Alt,Lauren Griffith,Don Metzler,Tor Myklebust,Fabrizio Silvestri,Mark Smucker,Torsten Suel,Andrew Trotman,Olga Vechtomova,William Webber和Justin Zobel為我們提出了很多寶貴的意見。同時感謝匿名審稿人為我們提供了積極的意見和反饋。

有幾個班的研究生起草了早期的一些材料。我們感謝他們的耐心和忍耐。4個學生——Mohamad Hasan Ahmadi,John Akinyemi,Chandra Prakash Jethani和Andrew Kane——非常嚴謹地審閱了草稿,幫助我們找出和解決了很多問題。另外3個學生——Azin Ashkan,Maheedhar Kolla和Ian Mackinnon——志願幫助我們在2007年秋季學期進行了一次課內評價,對第一部分中的很多練習有很大的貢獻。Jack Wang校對了第3章中關於CJK語言的材料。Kelly Itakura提供了日文輸入。

Web站點

.

序言

Information Retrieval: Implementing and Evaluating Search Engines

學術巨匠齊聚一堂編撰了一部信息檢索的優秀教材。Stefan Büttcher、Charles Clarke和Gordon Cormack以合計超過五十年的研究經驗,組成了橫跨三代的信息檢索研究泰斗組合。Büttcher是Clarke的博士生,而Clarke是Cormack的博士生。他們三人都以對信息檢索的深入洞察和建立實用搜尋系統的熱情而聞名,這種組合在一個充滿世界級的研究專家的領域中是很少見的。

本書涵蓋了搜尋引擎的各個重要組成部分,從爬蟲到索引到查詢過程。大部分章節用於介紹索引、檢索方法和評價的核心主題。重點放在實現和實驗上,以讓讀者了解到信息檢索系統的底層細節,包括索引壓縮和索引更新策略,同時讓讀者理解在實際中哪一種方法效果更好。關於評價的兩章提供了評價搜尋引擎的方法論和統計學基礎,使得讀者能夠知道:例如改變搜尋引擎的排名公式是否對檢索結果的質量有一個正面的影響。關於分類的一章介紹了對高級搜尋操作非常有用的機器學習技術,例如如何將查詢限制在某種特定語言書寫的文檔中,或者如何過濾搜尋結果中的不良信息。關於並行信息檢索和Web搜尋的章節描述了從一個基本的信息檢索系統變為一個涵蓋數十億文檔並同時為成千上萬的用戶服務的大規模檢索服務系統時所必須做出的改變。

通過引用數以百計的研究文獻,作者對當今信息檢索研究狀況給出了指導性的概述,這個概述的高度遠遠超過了那些一般的綜述。通過使用一個運行樣例集和一個通用框架,他們具體描述了在每個環節中的重要方法——為什麼這些方法行得通,它們是如何實現的,以及它們是如何工作的。為了寫這本書,作者幾乎實現和測試了每一個重要的方法,進行了數百次實驗,並增加了對實驗結果的闡述。每一章最後的練習題鼓勵讀者自己動手去建立系統並進行探索。

這本書是所有信息檢索研究者和從業人員的必讀教材!

Amit Singhal,Google Fellow

相關詞條

熱門詞條

聯絡我們