這就是搜索引擎:核心技術詳解 这就是搜索引擎:核心技术详解

張俊林，本科畢業於天津大學管理學院，2004年於中科院軟件所直接獲得博士學位並留所從事科研工作，研究方向為搜索引擎與自然語言處理。曾多次參加美國國防部DARPA項目舉辦的信息檢索評測會議TREC“高精度檢索”任務，在TREC2004獲得高精度檢索系統評測總成績第一名（包括微軟劍橋研究院、UIUC等17個國際高水平信息檢索科研隊伍參加此項評測），並在包括ACL、COLING、IJCNLP等多種高水平國際會議及國內期刊發表20多篇學術論文。2005年在CSDN博客發布系列博文“搜索引擎設計實用教程：以百度為例”，在網絡上獲得了廣泛轉載與良好口碑。2006年作為聯合創始人建立了智能信息聚合網站“玩聚網”，曾先後於阿里巴巴搜索技術中心任資深搜索技術研究員、房價網首席研究員，現任職於新浪微博，從事微博搜索與語義分析及推薦方面的研發工作。

第1章搜索引擎及其技術架構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.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.2二元獨立模型（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 

第10章網頁去重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 

第11章搜索引擎緩存機制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 

第12章搜索引擎發展趨勢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