●章 搜索引擎及其技術架構 1
1.1 搜索引擎為何重要 1
1.1.1  互聯網的發展 1
1.1.2 商業搜索引擎公司的發展 3
1.1.3 搜索引擎的重要地位 3
1.2 搜索引擎技術發展史 4
1.2.1 史前時代：分類目錄的一代 4
1.2.2 代：文本檢索的一代 5
1.2.3 第二代：鏈接分析的一代 5
1.2.4 第三代：用戶中心的一代 5
1.3 搜索引擎的3個目標 6
1.4 搜索引擎的3個核心問題 7
1.4.1 3個核心問題 7
1.4.2 與技術發展的關繫 8
1.5 搜索引擎的技術架構 9
第2章 網絡爬蟲 12
2.1 通用爬蟲框架 12
2.2 優秀爬蟲的特性 15
2.3 爬蟲質量的評價標準 18
2.4 抓取策略 19
2.4.1 寬度優先遍歷策略（Breath First） 20
2.4.2 非完全PageRank策略（Partial PageRank） 21
2.4.3 OCIP策略（Online Page Importance Computation） 23
2.4.4 大站優先策略（Larger Sites First） 23
2.5 網頁更新策略 23
2.5.1 歷史參考策略 24
2.5.2 用戶體驗策略 24
2.5.3 聚類抽樣策略 24
2.6 暗網抓取（Deep Web Crawling） 26
2.6.1 查詢組合問題 27
2.6.2 文本框填寫問題 29
2.7 分布式爬蟲 30
2.7.1 主從式分布爬蟲（Master-Slave） 31
2.7.2 對等式分布爬蟲（Peer to Peer） 31
本章提要 34
本章參考文獻 34
第3章 搜索引擎索引 36
3.1 索引基礎 36
3.1.1 單詞—文檔矩陣 37
3.1.2 倒排索引基本概念 37
3.1.3 倒排索引簡單實例 39
3.2 單詞詞典 42
3.2.1 哈希加鏈表 42
3.2.2 樹形結構 43
3.3 倒排列表（Posting List） 44
3.4 建立索引 45
3.4.1 兩遍文檔遍歷法（2-Pass In-Memory Inversion） 45
3.4.2 排序法（Sort-based Inversion） 46
3.4.3 歸並法（Merge-based Inversion） 49
3.5 動態索引 50
3.6 索引更新策略 51
3.6.1 完全重建策略（Complete Re-Build） 51
3.6.2 再合並策略（Re-Merge） 52
3.6.3 原地更新策略（In-Place） 55
3.6.4 混合策略（Hybrid） 57
3.7 查詢處理 57
3.7.1 一次一文檔（Doc at a Time） 58
3.7.2 一次一單詞（Term at a Time） 59
3.7.3 跳躍指針（Skip Pointers） 60
3.8 多字段索引 62
3.8.1 多索引方式 62
3.8.2 倒排列表方式 63
3.8.3 擴展列表方式（Extent List） 64
3.9 短語查詢 64
3.9.1 位置信息索引（Position Index） 65
3.9.2 雙詞索引（Nextword Index） 66
3.9.3 短語索引（Phrase Index） 67
3.9.4 混合方法 67
3.10 分布式索引（Parallel Indexing） 68
3.10.1 按文檔劃分（Document Partitioning） 69
3.10.2 按單詞劃分（Term Partitioning） 70
3.10.3 兩種方案的比較 72
本章提要 73
本章參考文獻 73
第4章 索引壓縮 76
4.1 詞典壓縮 76
4.2 倒排列表壓縮算法 78
4.2.1 評價索引壓縮算法的指標 79
4.2.編碼與二進制編碼 79
4.2.3 Elias Gamma算法與Elias Delta算法 81
4.2.4 Golomb算法與Rice算法 81
4.2.5 變長字節算法（Variable Byte） 83
4.2.6 SimpleX 繫列算法 84
4.2.7 PForDelta算法 86
4.3 文檔編號重排序（DocID Reordering） 89
4.4 靜態索引裁剪（Static Index Pruning） 93
4.4.1 以單詞為中心的索引裁剪 94
4.4.2 以文檔為中心的索引裁剪 96
本章提要 97
本章參考文獻 97
第5章 檢索模型與搜索排序 99
5.1 布爾模型（Boolean Model） 101
5.2 向量空間模型（Vector Space Model） 102
5.2.1 文檔表示 102
5.2.2 相似性計算 104
5.2.3 特征權重計算 106
5.3 概率檢索模型 108
5.3.1 概率排序原理 108
5.3.獨立模型（Binary Independent Model） 110
5.3.3 BM25模型 113
5.3.4 BM25F模型 115
5.4 語言模型方法 116
5.5 機器學習排序（Learning to Rank） 119
5.5.1 機器學習排序的基本思路 120
5.5.2 單文檔方法（PointWise Approach） 121
5.5.3 文檔對方法（PairWise Approach） 122
5.5.4 文檔列表方法（ListWise Approach） 123
5.6 檢索質量評價標準 125
5.6.1 精確率與召回率 126
5.6.2 P@10指標 127
5.6.3 MAP指標（Mean Average Precision） 128
本章提要 129
本章參考文獻 129
第6章 鏈接分析 131
6.1 Web圖 131
6.2 兩個概念模型及算法之間的關繫 133
6.2.1 隨機遊走模型（Random Surfer Model） 133
6.2.2 子集傳播模型 135
6.2.3 鏈接分析算法之間的關繫 136
6.3 PageRank算法 137
6.3.1 從入鏈數量到PageRank 137
6.3.2 PageRank計算 138
6.3.3 鏈接陷阱（Link Sink）與遠程跳轉（Teleporting） 139
6.4 HITS算法（Hypertext Induced Topic Selection） 140
6.4.1 Hub頁面與Authority頁面 140
6.4.2 相互增強關繫 141
6.4.3 HITS算法 142
6.4.4 HITS算法存在的問題 144
6.4.5 HITS算法與PageRank算法比較 145
6.5 SALSA算法 146
6.5.1 確定計算對像集合 146
6.5.2 鏈接關繫傳播 148
6.5.3 Authority權值計算 150
6.6 主題敏感PageRank（Topic Sensitive PageRank） 152
6.6.1 主題敏感PageRank與PageRank的差異 152
6.6.2 主題敏感PageRank計算流程 153
6.6.3 利用主題敏感PageRank構造個性化搜索 156
6.7 Hilltop算法 156
6.7.1 Hilltop算法的一些基本定義 157
6.7.2 Hilltop算法 158
6.8 其他改進算法 162
6.8.1 智能遊走模型（Intelligent Surfer Model） 162
6.8.2 偏置遊走模型（Biased Surfer Model） 163
6.8.3 PHITS算法（Probability Analogy of HITS） 163
6.8.4 BFS算法（Backward Forward Step） 163
本章提要 164
本章參考文獻 164
第7章 雲存儲與雲計算 166
7.1 雲存儲與雲計算概述 167
7.1.1 基本假設 167
7.1.2 理論基礎 168
7.1.3 數據模型 170
7.1.4 基本問題 170
7.1.5 Google的雲存儲與雲計算架構 171
7.2 Google文件繫統（GFS） 173
7.2.1 GFS設計原則 174
7.2.2 GFS整體架構 174
7.2.3 GFS主控服務器 176
7.2.4 繫統交互行為 178
7.3 Chubby鎖服務 179
7.4 BigTable 181
7.4.1 BigTable的數據模型 181
7.4.2 BigTable整體結構 183
7.4.3 BigTable的管理數據 184
7.4.4 主控服務器（Master Server） 186
7.4.5 子表服務器（Tablet Server） 187
7.5 Megastore繫統 191
7.5.1 實體群組切分 192
7.5.2 數據模型 193
7.5.3 數據讀寫與備份 195
7.6 Map/Reduce雲計算模型 195
7.6.1 計算模型 196
7.6.2 整體邏輯流程 197
7.6.3 應用示例 198
7.7 咖啡因繫統——Percolator 199
7.7.1 事務支持 200
7.7.2 觀察/通知體繫結構 202
7.8 Pregel圖計算模型 203
7.9 Dynomo雲存儲繫統 206
7.9.1 數據劃分算法（Partitioning Algorithm） 207
7.9.2 數據備份（Replication） 208
7.9.3 數據讀寫 208
7.9.4 數據版本控制 209
7.10 PNUTS雲存儲繫統 210
7.10.1 PNUTS整體架構 211
7.10.2 211
7.10.3 子表控制器與數據路由器 213
7.10.4 雅虎消息代理 213
7.10.5 數據一致性 214
7.11 HayStack存儲繫統 215
7.11.1 HayStack整體架構 216
7.11.2 目錄服務 218
7.11.3 HayStack緩存 219
7.11.4 HayStack存儲繫統 219
本章提要 222
本章參考文獻 222
第8章 網頁反作弊 224
8.1 內容作弊 224
8.1.1 常見內容作弊手段 225
8.1.2 內容農場（Content Farm） 226
8.2 鏈接作弊 227
8.3 頁面隱藏作弊 230
8.4 Web 2.0作弊方法 231
8.5 反作弊技術的整體思路 232
8.5.1 信任傳播模型 233
8.5.2 不信任傳播模型 234
8.5.3 異常發現模型 234
8.6 通用鏈接反作弊方法 236
8.6.1 TrustRank算法 237
8.6.2 BadRank算法 238
8.6.3 SpamRank 239
8.7 專用鏈接反作弊技術 240
8.7.1 識別鏈接農場 240
8.7.2 識別Google轟炸 241
8.8 識別內容作弊 241
8.9 反隱藏作弊 241
8.9.1 識別頁面隱藏 241
8.9.2 識別網頁重定向 242
8.10 搜索引擎反作弊綜合框架 242
本章提要 244
本章參考文獻 244
第9章 用戶查詢意圖分析 246
9.1 搜索行為及其意圖 246
9.1.1 用戶搜索行為 246
9.1.2 用戶搜索意圖分類 248
9.2 搜索日志挖掘 250
9.2.1 查詢會話（Query Session） 250
9.2.2 點擊圖（Click Graph） 251
9.2.3 查詢圖（Query Graph） 252
9.3 相關搜索 253
9.3.1 基於查詢會話的方法 253
9.3.2 基於點擊圖的方法 254
9.4 查詢糾錯 255
9.4.1 編輯距離（Edit Distance） 256
9.4.2 噪聲信道模型（Noise Channel Model） 257
本章提要 257
本章參考文獻 258
0章 網頁去重 259
10.1 通用去重算法框架 261
10.2 Shingling算法 262
10.3 I-Match算法 265
10.4 SimHash算法 268
10.4.1 文檔指紋計算 269
10.4.2 相似文檔查找 270
10.5 SpotSig算法 272
10.5.1 特征抽取 272
10.5.2 相似文檔查找 273
本章提要 274
本章參考文獻 274
1章 搜索引擎緩存機制 276
11.1 搜索引擎緩存繫統架構 277
11.2 緩存對像 279
11.3 緩存結構 281
11.4 緩存淘汰策略（Evict Policy） 283
11.4.1 動態策略 284
11.4.2 混合策略 284
11.5 緩存更新策略（Refresh Policy） 285
本章提要 286
本章參考文獻 287
2章 搜索引擎發展趨勢 288
12.1 個性化搜索 288
12.2 社會化搜索 290
12.3 實時搜索 291
12.4 移動搜索 293
12.5 地理位置感知搜索 294
12.6 跨語言搜索 296
12.7 多媒體搜索 298
12.8 情境搜索 299