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