信息檢索導論 (修訂版)

本書是信息檢索的教材，旨在從電腦科學的視角提供一種現代的信息檢索方法。書中從基本概念講解網絡搜索以及文本分類和文本聚類等，對收集、索引和搜索文檔系統的設計和實現的方方面面、評估系統的方法、機器學習方法在文本收集中的應用等給出了最新的講解。

[美]克里斯托夫·曼寧（Christopher Manning） 計算機科學家，斯坦福大學教授，斯坦福大學人工智能實驗室主任，ACM會士、AAAI會士、ACL會士。
目前的研究目標為計算機如何智能地處理、理解和生成人類語言資料。
曼寧博士是深度學習在自然語言處理應用方面的先鋒人物，在樹遞歸神經網絡、語義分析、神經機器翻譯、深度語言理解等方面均有令業界矚目的研究成果。

[美]普拉巴卡爾·拉格萬（Prabhakar Raghavan）Google高#副總裁，目前負責谷歌的廣告與商業產品、基礎設施團隊。
之前作為Google App和Google Cloud的副總裁，帶領團隊做出了突出業績。
在加入Google前任職於Yahoo!，是Yahoo!實驗室的創建者和負責人。
拉格萬博士畢業於加州大學伯克利分校，長期擔任斯坦福大學計算機科學系顧問教授，主要研究方向是文本及Web數據挖掘、隨機算法等，是美國國家工程院院士、ACM會士、IEEE會士。

[德]欣里希·舒策（Hinrich Schütze） 德國慕尼黑大學信息與語言處理中心主任，計算語言學家，斯坦福大學博士。
曾在美國矽谷工作多年。

王斌博士，小米公司AI實驗室NLP方向首#科學家，前中國#學院信息工程研究所研究員、博導，中國#學院大學教授。

李鹏博士，中國#學院信息工程研究所高#工程師，碩士生導師。

第 1章 布爾檢索 . 1
1.1　一個信息檢索的例子　2
1.2　構建倒排索引的初體驗 .　5
1.3　布爾查詢的處理　8
1.4　對基本布爾操作的擴展及有序檢索　11
1.5　參考文獻及補充讀物 .　13

第　2章 詞項詞典及倒排記錄表　14
2.1　文檔分析及編碼轉換 .　14
2.1.1　字符序列的生成 .　14
2.1.2　文檔單位的選擇 .　16
2.2　詞項集合的確定　16
2.2.1　詞條化　16
2.2.2　去除停用詞　19
2.2.3　詞項歸一化 .　20
2.2.4　詞乾還原和詞形歸並 .　23
2.3　基於跳錶的倒排記錄表快速合並算法　26
2.4　含位置信息的倒排記錄表及短語查詢　28
2.4.1　二元詞索引 .　28
2.4.2　位置信息索引 .　29
2.4.3　混合索引機制 .　31
2.5　參考文獻及補充讀物 .　32

第　3章 詞典及容錯式檢索 .　34
3.1　詞典搜索的數據結構　34
3.2　通配符查詢 .　36
3.2.1　一般的通配符查詢 .　37
3.2.2　支持通配符查詢的k-gram索引 .　38
3.3　拼寫校正　39
3.3.1　拼寫校正的實現 .　39
3.3.2　拼寫校正的方法　40
3.3.3　編輯距離　40
3.3.4　拼寫校正中的 k-gram索引　42
3.3.5　上下文敏感的拼寫校正 .　43
3.4　基於發音的校正技術　44
3.5　參考文獻及補充讀物 .　45

第　4章 索引構建 .　46
4.1　硬件基礎　46
4.2　基於塊的排序索引方法 .　47
4.3　內存式單遍掃描索引構建方法 .　50
4.4　分佈式索引構建方法 .　51
4.5　動態索引構建方法 .　54
4.6　其他索引類型　56
4.7　參考文獻及補充讀物 .　57

第　5章 索引壓縮 .　59
5.1　信息檢索中詞項的統計特性 .　59
5.1.1　Heaps定律：詞項數目的估計　61
5.1.2　Zipf定律：對詞項的分佈建模 .　62
5.2　詞典壓縮　63
5.2.1　將詞典看成單一字符串的 壓縮方法　63
5.2.2　按塊存儲　64
5.3　倒排記錄表的壓縮 .　66
5.3.1　可變字節碼 .　67
5.3.2　γ編碼　68
5.4　參考文獻及補充讀物　74

第　6章 文檔評分、詞項權重計算及 向量空間模型　76
6.1　參數化索引及域索引　76
6.1.1　域加權評分　78
6.1.2　權重學習　79
6.1.3　最優權重g 的計算　80
6.2　詞項頻率及權重計算 .　81
6.2.1　逆文檔頻率 .　81
6.2.2　tf-idf 權重計算　82
6.3　向量空間模型　83
6.3.1　內積　83
6.3.2　查詢向量　86
6.3.3　向量相似度計算 .　87
6.4　其他tf-idf 權重計算方法 .　88
6.4.1　tf的亞線性尺度變換方法 .　88
6.4.2　基於最大值的tf歸一化 .　88
6.4.3　文檔權重和查詢權重機制　89
6.4.4　文檔長度的回轉歸一化 .　89
6.5　參考文獻及補充讀物　92

第　7章 一個完整搜索系統中的評分計算　93
7.1　快速評分及排序 .　93
7.1.1　非精確返回前K篇文檔的方法 .　94
7.1.2　索引去除技術 .　94
7.1.3　勝者表 .　95
7.1.4　靜態得分和排序 .　95
7.1.5　影響度排序　96
7.1.6　簇剪枝方法 .　97
7.2　信息檢索系統的組成　98
7.2.1　層次型索引　98
7.2.2　查詢詞項的鄰近性 .　98
7.2.3　查詢分析及文檔評分函數的 設計 .　99
7.2.4　搜索系統的組成 .　100
7.3　向量空間模型對各種查詢操作的支持　101
7.3.1　布爾查詢　101
7.3.2　通配符查詢 .　102
7.3.3　短語查詢　102
7.4　參考文獻及補充讀物 .　102

第　8章 信息檢索的評價 .　103
8.1　信息檢索系統的評價 .　103
8.2　標準測試集 .　104
8.3　無序檢索結果集合的評價 .　105
8.4　有序檢索結果的評價方法 .　108
8.5　相關性判定 .　112
8.6　更廣的視角看評價：系統質量及用戶效用 .　115
8.6.1　系統相關問題 .　115
8.6.2　用戶效用　115
8.6.3　對已有系統的改進 .　116
8.7　結果片段 .　116
8.8　參考文獻及補充讀物 .　118

第　9章 相關反饋及查詢擴展　120
9.1　相關反饋及偽相關反饋 .　120
9.1.1　Rocchio相關反饋算法 .　122
9.1.2　基於概率的相關反饋方法　125
9.1.3　相關反饋的作用時機　125
9.1.4　Web上的相關反饋 .　126
9.1.5　相關反饋策略的評價　127
9.1.6　偽相關反饋 .　127
9.1.7　間接相關反饋 .　128
9.1.8　小結　128
9.2　查詢重構的全局方法 .　128
9.2.1　查詢重構的詞匯表工具　128
9.2.2　查詢擴展　129
9.2.3　同義詞詞典的自動構建　130
9.3　參考文獻及補充讀物 .　131

第　10章 XML檢索　133
10.1　XML的基本概念　134
10.2　XML檢索中的挑戰性問題 .　137
10.3　基於向量空間模型的XML檢索 .　140
10.4　XML檢索的評價　144
10.5　XML檢索：以文本為中心與以數據為中心的對比 .　146
10.6　參考文獻及補充讀物 .　148

第　11 章 概率檢索模型　150
11.1　概率論基礎知識 .　150
11.2　概率排序原理　151
11.2.1　1/0風險的情況　151
11.2.2　基於檢索代價的概率排序 原理　152
11.3　二值獨立模型　152
11.3.1　排序函數的推導 .　153
11.3.2　理論上的概率估計方法　155
11.3.3　實際中的概率估計方法　156
11.3.4　基於概率的相關反饋方法　157
11.4　概率模型的相關評論及擴展　158
11.4.1　概率模型的評論 .　158
11.4.2　詞項之間的樹型依賴　159
11.4.3　Okapi BM25：一個非二值的 模型　160
11.4.4　IR中的貝葉斯網絡 方法　161
11.5　參考文獻及補充讀物 .　162

第　12章 基於語言建模的信息檢索模型　163
12.1　語言模型 .　163
12.1.1　有窮自動機和語言模型　163
12.1.2　語言模型的種類 .　165
12.1.3　詞的多項式分佈 .　166
12.2　查詢似然模型 .　167
12.2.1　IR中的查詢似然模型　167
12.2.2　查詢生成概率的估計　167
12.2.3　Ponte和Croft進行的實驗　169
12.3　語言建模的方法與其他檢索方法的 比較 .　171
12.4　擴展的LM方法　172
12.5　參考文獻及補充讀物 .　173

第　13章 文本分類及樸素貝葉斯方法　175
13.1　文本分類問題 .　177
13.2　樸素貝葉斯文本分類 .　178
13.3　伯努利模型 .　182
13.4　NB的性質　183
13.5　特徵選擇 .　188
13.5.1　互信息 .　188
13.5.2　2 統計量 .　191
13.5.3　基於頻率的特徵選擇方法　192
13.5.4　多類問題的特徵選擇方法　193
13.5.5　不同特徵選擇方法的比較　193
13.6　文本分類的評價 .　194
13.7　參考文獻及補充讀物 .　199

第　14章 基於向量空間模型的文本 分類　200
14.1　文檔表示及向量空間中的關聯度計算 .　201
14.2　Rocchio分類方法 .　202
14.3　k近鄰分類器　205
14.4　線性及非線性分類器 .　209
14.5　多類問題的分類 .　212
14.6　偏差—方差折中準則 .　214
14.7　參考文獻及補充讀物 .　219

第　15章 支持向量機及文檔機器學習方法　221
15.1　二類線性可分條件下的支持向量機　221
15.2　支持向量機的擴展 .　226
15.2.1　軟間隔分類 .　226
15.2.2　多類情況下的支持向量機　228
15.2.3　非線性支持向量機　228
15.2.4　實驗結果 .　230
15.3　有關文本文檔分類的考慮 .　231
15.3.1　分類器類型的選擇　232
15.3.2　分類器效果的提高　233
15.4　ad hoc檢索中的機器學習方法 .　236
15.4.1　基於機器學習評分的簡單 例子 .　236
15.4.2　基於機器學習的檢索結果 排序 .　238
15.5　參考文獻及補充讀物 .　239

第　16章 扁平聚類 .　241
16.1　信息檢索中的聚類應用 .　242
16.2　問題描述　244
16.3　聚類算法的評價 .　246
16.4　K-均值算法　248
16.5　基於模型的聚類 .　254
16.6　參考文獻及補充讀物 .　258

第　17章 層次聚類 .　260
17.1　凝聚式層次聚類 .　260
17.2　單連接及全連接聚類算法 .　263
17.3　組平均凝聚式聚類 .　268
17.4　質心聚類　269
17.5　層次凝聚式聚類的最優性 .　270
17.6　分裂式聚類　272
17.7　簇標簽生成　273
17.8　實施中的註意事項 .　274
17.9　參考文獻及補充讀物 .　275

第　18章 矩陣分解及隱性語義索引　277
18.1　線性代數基礎　277
18.2　詞項—文檔矩陣及SVD .　280
18.3　低秩逼近　282
18.4　LSI　284
18.5　參考文獻及補充讀物 .　288

第　19章 Web搜索基礎　289
19.1　背景和歷史 .　289
19.2　Web的特性　290
19.2.1　Web圖　291
19.2.2　作弊網頁　293
19.3　廣告經濟模型 .　294
19.4　搜索用戶體驗 .　296
19.5　索引規模及其估計　297
19.6　近似重復及搭疊　300
19.7　參考文獻及補充讀物 .　303

第　20章 Web採集及索引 .　304
20.1　概述 .　304
20.1.1　採集器必須提供的 功能特點　304
20.1.2　採集器應該提供的功能特點　304
20.2　採集 .　305
20.2.1　採集器架構 .　305
20.2.2　DNS解析 .　308
20.2.3　待採集URL池 .　309
20.3　分佈式索引　311
20.4　連接服務器　312
20.5　參考文獻及補充讀物 .　314

第　21章 鏈接分析 .　316
21.1　Web圖　316
21.2　PageRank.　318
21.2.1　馬爾科夫鏈 .　318
21.2.2　PageRank的計算 .　320
21.2.3　面向主題的PageRank　322
21.3　Hub網頁及Authority網頁　325
21.4　參考文獻及補充讀物.　329

參考文獻　331
索引　.　356