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