目錄
第二版前言
第一版前言
第一章 引論 1
第一節(jié) 搜索引擎的概念 2
第二節(jié) 搜索引擎的發(fā)展歷史 3
第三節(jié) 一些著名的搜索引擎 6
第四節(jié) 小結 11
上篇 Web搜索引擎基本原理和技術
第二章 Web搜索引擎工作原理和體系結構 15
第一節(jié) 基本要求 15
第二節(jié) 網頁搜集 16
第三節(jié) 預處理 18
第四節(jié) 查詢服務 20
第五節(jié) 體系結構 23
第六節(jié) 小結 25
第三章 Web信息的搜集 26
第一節(jié) 概述 26
一、超文本傳輸協(xié)議 26
二、一個小型搜索引擎系統(tǒng) 27
第二節(jié) 網頁搜集 30
一、定義URL類和Page類 31
二、與服務器建立連接 35
三、發(fā)送請求和接收數(shù)據 37
四、網頁信息存儲的天網格式 38
第三節(jié) 多道搜集程序并行工作 40
一、多線程并發(fā)工作 41
二、控制對一個站點并發(fā)搜集線程的數(shù)目 42
第四節(jié) 如何避免網頁的重復搜集 43
一、記錄未訪問、已訪問URL和網頁內容摘要信息 43
二、域名與IP的對應問題 43
第五節(jié) 搜集信息的類型 45
第六節(jié) 小結 46
第四章 對搜集信息的預處理 47
第一節(jié) 索引網頁庫 47
第二節(jié) 網頁編碼識別 50
一、基本而重要的概念 50
二、常用字符編碼 52
三、常用字符編碼算法 55
四、字符的輸入和顯示 57
五、編碼識別 58
第三節(jié) 中文自動分詞 60
第四節(jié) 分析網頁和建立倒排文件 64
第五節(jié) 小結 67
第五章 信息查詢服務 68
第一節(jié) 檢索的定義 68
第二節(jié) 查詢服務的實現(xiàn) 69
一、結果集合的形成 69
二、查詢結果顯示 70
第三節(jié) 小結 71
中篇 對質量和性能的追求
第六章 可擴展搜集子系統(tǒng) 75
第一節(jié) 天網系統(tǒng)概述和集中式搜集系統(tǒng)結構 75
一、天網系統(tǒng)結構 75
二、集中式搜集系統(tǒng) 76
第二節(jié) 利用并行處理技術高效搜集網頁的一種方案 82
一、節(jié)點間URL的劃分策略 82
二、關于性能的討論 85
三、性能測試和評價 87
四、系統(tǒng)的動態(tài)可配置性設計 90
第三節(jié) 天網分布式搜集系統(tǒng) 92
第四節(jié) 對Deep Web的認識 93
一、Deep Web的成因 93
二、搜索Deep Web的方法 96
第五節(jié) 小結 98
第七章 網頁凈化與消重 100
第一節(jié) 網頁凈化與元數(shù)據提取 100
一、DocView模型 102
二、網頁的表示 103
三、提取DocView模型要素的方法 108
四、模型應用及實驗研究 112
第二節(jié) 網頁消重算法 115
一、消重算法 116
二、算法評測 118
第三節(jié) 小結 121
第八章 高性能檢索子系統(tǒng) 122
第一節(jié) 檢索系統(tǒng)基本技術 122
一、系統(tǒng)設計與結構 122
二、索引創(chuàng)建 125
三、檢索過程 127
第二節(jié) 適于查詢的網頁索引結構 129
一、倒排索引結構 129
二、平面位置索引 131
第三節(jié) 倒排索引壓縮 135
一、倒排索引壓縮技術 136
二、詞典與倒排表的壓縮 142
第四節(jié) 索引剪枝 150
一、靜態(tài)索引剪枝方法 151
二、動態(tài)索引剪枝方法 153
第五節(jié) 混合索引技術 168
一、混合索引的原理 169
二、混合索引的實現(xiàn) 171
第六節(jié) 倒排文件緩存機制 173
一、倒排文件緩存 174
二、負載特性 176
三、緩存策略的選擇 178
第七節(jié) 小結 178
第九章 相關排序與系統(tǒng)質量評估 180
第一節(jié) 傳統(tǒng)IR的相關排序技木 180
第二節(jié) 鏈接分析與相關排序 182
一、鏈接分析 182
二、Web查詢模式下的新信息 184
第三節(jié) 相關排序的一種實現(xiàn)方案 188
一、形成網頁中詞項的基本權重 189
二、利用鏈接的結構 190
三、收集用戶反饋信息 192
四、計算最終的權重 194
第四節(jié) 信息檢索技術評估 195
一、信息檢索技術評估指標 197
二、TREC和CWIRF信息檢索評估 206
三、搜索引擎技術評估 213
第五節(jié) 小結 217
下篇 Web信息資源的組織與應用服務
第十章 大規(guī)模Web歷史網頁倉儲系統(tǒng)的構建 221
第一節(jié) 國外Web歷史網頁保存現(xiàn)狀 221
一、Internet Archive 222
二、PANDORA 222
三、其他相關Web保存項目 223
第二節(jié) 中國Web信息博物館的系統(tǒng)設計 224
一、Web InfoMall的設計目標 225
二、Web InfoMall的體系結構 225
第三節(jié) 歷史網頁的存儲 227
一、數(shù)據的組織 228
二、存儲結構 229
三、數(shù)據管理與壓縮 230
四、存儲性能 232
第四節(jié) 數(shù)據訪問 232
一、PageID的索引 233
二、URI的索引 233
三、數(shù)據服務 234
四、性能與優(yōu)化 235
第五節(jié) 網頁的格式保存 236
第六節(jié) 小結 236
第十一章 大規(guī)模Web非網頁信息倉儲系統(tǒng)的構建 238
第一節(jié) 網絡資源庫藏相關工作 238
一、Ibiblio 239
二、Internet Archive 240
三、Wikimedia 240
四、中國互聯(lián)網數(shù)字資源財富庫藏 241
第二節(jié) CDAL系統(tǒng)概況 242
第三節(jié) CDAL系統(tǒng)設計 244
一、系統(tǒng)體系結構 244
二、可擴展的存儲組織方案 244
第四節(jié) 網絡資源描述信息獲取 246
一、Ontology概述 247
二、描述信息獲取機制 247
三、改進查詢的方法 248
四、改進排序的方法 249
第五節(jié) 基于局部聚類思想的共現(xiàn)詞匯算法 250
一、基本定義 251
二、FDC共現(xiàn)詞匯算法 251
第六節(jié) 小結 252
第十二章 中文網頁自動分類與聚類 253
第一節(jié) 文檔自動分類算法的類型 253
第二節(jié) 實現(xiàn)中文網頁自動分類的一般過程 254
第三節(jié) 影響分類器性能的關鍵因素分析 256
一、實驗設置 256
二、訓練樣本 258
三、特征選取 262
四、分類算法 265
五、截尾算法 270
六、中文網頁分類器的設計方案 272
第四節(jié) 天網目錄導航服務 272
一、問題的提出 272
二、天網目錄導航服務的體系結構 273
三、天網目錄的運行實例 274
第五節(jié) 文本聚類方法 275
一、文本聚類的一般過程 275
二、文本間相似性的度量 276
三、常用聚類算法 276
四、聚類結果的評估 279
五、搜索引擎返回結果的聚類 280
第六節(jié) 小結 281
第十三章 開放域問答系統(tǒng) 283
第一節(jié) 概述 283
一、問答系統(tǒng)的歷史 283
二、著名開放域問答系統(tǒng)介紹 284
三、開放域問答系統(tǒng)的通用體系結構 285
第二節(jié) 問句的分析 287
一、問句中的指代消解 287
二、問句分類 288
三、問句主題提取 290
第三節(jié) 文檔和段落檢索 290
一、檢索模型的選用 291
二、查詢生成 291
三、查詢結果排序 293
四、增強索引的功能 295
第四節(jié) 答案提取和驗證模塊 295
一、生成候選答案集合 295
二、答案提取 296
第五節(jié) 問答系統(tǒng)的改進方法 299
一、問答系統(tǒng)中外部資源的利用 299
二、尋找特殊類問題的解決方案 301
三、通過系綜方法構建問答系統(tǒng) 302
第六節(jié) 問答系統(tǒng)的評測 303
一、TREC問答系統(tǒng)評測 303
二、問答系統(tǒng)評測指標 304
第七節(jié) 實例：天網開放域問答系統(tǒng) 306
第八節(jié) 小結 308
參考文獻 309
附錄 術語 322
圖表目錄
圖1-1 2012年3月在Google上檢索“伊拉克戰(zhàn)爭”的結果 2
圖1-2 2012年3月在Open Directory上檢索“伊拉克戰(zhàn)爭”的結果 5
圖2-1 搜索引擎示意圖 15
圖2-2 搜索引擎三段式工作流程 16
圖2-3 搜索引擎的體系結構 23
圖3-1 TSE搜索引擎界面 28
圖3-2 TSE查詢結果頁面 29
圖3-3 TSE網頁快照頁面 29
圖3-4 TSE系統(tǒng)結構 30
圖3-5 Web信息的搜集 31
圖3-6 Sockets和端口 35
圖3-7 通過Socket建立連接 36
圖4-1 網頁預處理系統(tǒng)結構 47
圖4-2 原始網頁庫中的記錄格式 48
圖4-3 索引網頁庫算法 49
圖4-4 字符的輸入和顯示流程 57
圖4-5 GB2312，Big5和GBK字符編碼分布 58
圖4-6 正向減字最大匹配算法流程 62
圖4-7 切詞算法流程 63
圖4-8 分析網頁與建立倒排文件流程 65
圖4-9 過濾網頁中非正文信息算法 65
圖4-10 正向索引表記錄格式 65
圖4-11 由正向索引建立反向索引 66
圖5-1 信息查詢的系統(tǒng)結構 68
圖5-2 基本檢索算法 69
圖5-3 動態(tài)摘要算法 71
圖5-4 用戶查詢日志的記錄格式 71
圖6-1 天網系統(tǒng)概貌 76
圖6-2 搜集系統(tǒng)的主控結構 77
圖6-3 協(xié)調進程工作算法 84
圖6-4 分布式Web搜集系統(tǒng)結構 85
圖6-5 負載方差 88
圖6-6 并行搜集系統(tǒng)與集中式搜集系統(tǒng)的性能對比 89
圖6-7 分布式系統(tǒng)效率 89
圖6-8 URL兩階段映射 91
圖6-9 天網分布式搜集系統(tǒng)P_Arthur體系結構 92
圖6-10 人才招聘網站首頁 94
圖7-1 用DocView模型提取的網頁要素 104
圖7-2 凈化后的網頁 104
圖7-3 HTML Tree結構 105
圖7-4 內容塊權值傳遞過程 107
圖7-5 有主題網頁DocView模型生成過程 109
圖7-6 計算網頁特征項權值的算法 109
圖7-7 正文段落識別過程 111
圖7-8 基于anchor text的超鏈選取算法 111
圖7-9 網頁凈化前后分類效果對比 113
圖7-10 查全率隨選取關鍵詞個數(shù)的變化 120
圖8-1 檢索系統(tǒng)集成框架結構 124
圖8-2 天網WWW檢索分布式系統(tǒng)構架 125
圖8-3 倒排索引結構示意圖 129
圖8-4 按塊組織的倒排鏈的結構 130
圖8-5 位置索引的結構 131
圖8-6 CLPS結構示意圖 135
圖8-7 倒排鏈中文檔號之間的d-gaps分布圖 146
圖8-8 不同文檔號分配下平均每個查詢對應文檔號序列的壓縮大小 146
圖8-9 不同壓縮算法對文檔號的解壓速度 147
圖8-10 不同文檔號分配下平均每個查詢對應詞頻序列的壓縮大小 147
圖8-11 不同壓縮算法對詞頻的解壓速度 148
圖8-12 平均每個查詢對應的位置信息需要的存儲空間 149
圖8-13 索引剪枝方法的分類 151
圖8-14 MAXSCORE算法的示例 157
圖8-15 WAND算法選擇候選文檔的過程 159
圖8-16 基于最大塊索引的支點文檔號的選擇示例 161
圖8-17 Interval-Base剪枝方法中文檔子區(qū)間劃分的示例 161
圖8-18 SAAT方法處理查詢處理模式及分數(shù)累加器數(shù)量的變化 164
圖8-19 當前支持高效SR+IR剪枝的索引結構 166
圖8-20 擴展詞典樹結構示例 172
圖8-21 擴展詞典匹配查找算法 173
圖8-22 搜索引擎檢索系統(tǒng)緩存結構 174
圖8-23 文檔數(shù)據訪問對象大小分布 176
圖8-24 I/O與PAGE序列序號—頻度分布 177
圖8-25 I/O與PAGE序列時間間隔分布 177
圖8-26 I/O和PAGE序列中唯一模式串 178
圖9-1 Inktomi提供的幾種搜索引擎技術的比較 185
圖9-2 詞典在系統(tǒng)中的地位 186
圖9-3 新詞學習 187
圖9-4 網頁的互聯(lián)結構示意 191
圖9-5 信息獲取技術評估的“森林 197
圖9-6 查準率和召回率基礎定義圖示 198
圖9-7 查準率和召回率例子 198
圖9-8 “省事的”11點標準召回率例子 199
圖9-9 實踐中召回率例子 200
圖9-10 實際中的44個查詢詞的評價統(tǒng)計表初P-R圖 202
圖9-11 測試集在檢索評估中的角色 208
圖9-12 幫助判斷相關結果頁面的計算機輔助程序人口 211
圖9-13 幫助判斷相關結果頁面的計算機輔助程序操作界面 211
圖10-1 Web InfoMall體系結構 226
圖10-2 網頁數(shù)據的分割 229
圖10-3 Web InfoMall的存儲結構 230
圖10-4 網頁的引用壓縮示意圖 232
圖11-1 CDAL提供的資源訪問方式 243
圖11-2 CDAL系統(tǒng)結構圖 245
圖11-3 基于Ontology的網絡資源描述信息獲取 248
圖11-4 概念的屬性及其詞匯擴展（以電影類資源為例） 249
圖11-5 獲得描述信息的改進排序算法 250
圖11-6 網絡資源描述信息展示 250
圖12-1 自動文檔分類算法的分類 254
圖12-2 中文網頁自動分類的一般過程 255
圖12-3 中文網頁分類器的工作原理圖 256
圖12-4 WebSmart——一個網頁實例集搜集和整理工具 259
圖12-5 一種中文網頁的分類體系 260
圖12-6 Macro-F1值隨樣本數(shù)的變化 261
圖12-7 Micro-F1值隨樣本數(shù)的變化 261
圖12-8 CHI、IG、DF、MI的比較（Macro-F1） 264
圖12-9 CHI、IG、DF、MI的比較（Micro-F1） 264
圖12-10 kNN與NB分類結果的比較 267
圖12-11 是的取值對分類器質量的影響（Marco-F1） 268
圖12-12 忌的取值對分類器質量的影響（Micro-F1） 268
圖12-13 蘭式距離法與歐式距離法對12個不同類別的分類情況 269
圖12-14 基于層次模型的kNN與基本kNN的比較 270
圖12-15 RCut和SCut截尾算法的比較 272
圖12-16 天網目錄的體系結構 274
圖12-17 天網目錄導航服務 274
圖12-18 文本聚類的一般過程 275
圖12-19 層次聚類實例 277
圖12-20 k-均值算法進行文本聚類的過程 278
圖12-21 搜索結果聚類系統(tǒng)Carrot2 281
圖13-1 START系統(tǒng)界面 285
圖13-2 Ask Jeeves查詢結果 285
圖13-3 問答系統(tǒng)的通用體系結構 287
圖13-4 天網開放域系統(tǒng)的體系結構 306
表4-1 網頁索引文件 49
表4-2 URL索引文件 50
表6-1 SOIF數(shù)據描述 78
表6-2 SOIF具體語法 80
表6-3 參照序列，假設節(jié)點數(shù)為2 87
表7-1 類別編號對照表 113
表7-2 消重實驗結果 115
表7-3 當N＝10、δ=0.01時5種算法的查全率和準確率 119
表7-4 考察δ的取值對算法3和4的影響 119
表7-5 分段簽名算法的時間復雜度及性能 120
表7-6 基于關鍵詞的各算法的時間復雜度及性能（N=10，a=0.01） 121
表8-1 MTF對序列<4，4，1，4，2>進行轉換的過程 142
表8-2 對包含100萬詞條的詞典使用不同編碼所需要的空間 144
表8-3 平均每個查詢對應詞頻鏈的空間大小（文檔號按URL序分配） 148
表8-4 不同索引的組織結構及其支持的查詢處理方式 155
表8-5 數(shù)據集基本統(tǒng)計信息 176
表9-1 新詞學習對檢索準確率的影響 188
表9-2 影響權值的HTML標簽 189
表9-3 補償因子定義表 192
表9-4 2004中文Web信息檢索評測提交結果 210
表9-5 主題提取 212
表9-6 導航搜索 212
表9-7 用戶查詢信息類別 215
表10-1 網頁存儲性能（個/秒） 232
表10-2 網頁訪問性能（個/秒） 236
表11-1 幾個網絡資源庫藏系統(tǒng)的特征 238
表11-2 CDAL中的資源分布 243
表12-1 樣本集中類別及實例數(shù)量的分布情況表 258
表12-2 kNN和NB算法的分類質量和分類效率比較 267
表12-3 歐式距離與蘭式距離的比較 269
表12-4 基于層次模型的kNN與基本kNN的比較 270
表12-5 RCut和SCut截尾算法的比較 271
表12-6 一個分類器的設計方案 272
表13-1 問題分類體系結構及TREC問答任務中間題的分布 289
表13-2 天網開放域系統(tǒng)在TREC2005中的表現(xiàn) 307