走進搜索引擎

第1章 引言
1.1 搜索引擎概述
1.1.1 目錄式搜索引擎
1.1.2 全文搜索引擎
1.1.3 元搜索引擎（Meta-Search Engine）
1.2 搜索引擎的主要需求
1.2.1 快
1.2.2 全
1.2.3 準
1.2.4 穩
1.2.5 省
1.3 搜索引擎的4大系統
1.3.1 搜索引擎的體系結構
第2章 搜索引擎的下載系統
2.1 爬蟲的發展歷史
2.1.1 世界上第1個爬蟲
2.1.2 爬蟲的發展歷程
2.2 萬維網及其網頁分析
2.2.1 蝴蝶結型的萬維網
2.2.2 萬維網的直徑
2.2.3 萬維網的規模及變化特征
2.2.4 網頁的特征
2.3 有關爬蟲的基本概念
2.3.1 爬蟲
2.3.2 種子站點
2.3.3 URL
2.3.4 Backlinks
2.4 網頁抓取原理
2.4.1 telnet和wget
2.4.2 從種子站點開始逐層抓取
2.4.3 不重復抓取策略
2.4.4 網頁抓取優先策略
2.4.5 網頁重訪策略
2.4.6 Robots協議
2.4.7 其他應該注意的禮貌性問題
2.4.8 重要性網頁優先抓取策略
2.4.9 抓取提速策略（合作抓取策略）
2.5 網頁庫
2.6 下載系統回顧及未來發展
參考文獻
第3章 搜索引擎的分析系統
3.1 知識準備
3.1.1 HTML語言
3.1.2 錨文本（anchor text）
3.1.3 半結構化數據（semi-structured data）
3.2 信息抽取及網頁信息結構化
3.2.1 網頁結構化的目標
3.2.2 建立HTML標簽樹
3.2.3 通過投票方法得到正文
3.2.4 網頁結構化過程回顧
3.3 網頁查重
3.3.1 網頁查重技術發展歷史
3.3.2 網頁查重實現方法
3.4 中文分詞
3.4.1 什麼是中文分詞
3.4.2 通過字典實現分詞
3.4.3 基于統計的分詞方法
3.5 PageRank
3.5.1 PageRank的來由
3.5.2 PageRank的基本想法
3.5.3 PageRank的計算公式
3.5.4 PageRank的計算方法
3.6 分析系統結構圖
參考文獻
第4章 搜索引擎的索引系統
4.1 知識準備
4.1.1 信息
4.1.2 索引
4.1.3 倒排索引、倒排表、臨時倒排文件、最終倒排文件
4.1.4 其他概念
4.2 全文檢索
4.3 文檔編號
4.3.1 編號的本質
4.3.2 文檔編號的方法
4.3.3 游程編碼
4.4 倒排索引
4.4.1 經典的倒排索引
4.4.2 正排索引（前向索引）
4.4.3 倒排索引
4.5 數據規模的估計
4.5.1 齊普夫法則
4.5.2 布爾檢索模型下的索引規模估計
4.6 涉及存儲規模的一些計算
4.6.1 正排表與倒排表的合並
4.6.2 多個臨時倒排文件的歸並
4.6.3 倒排索引分布式存儲
4.6.4 倒排文件緩存
4.6.5 倒排索引詞典統計信息的計算
4.7 倒排索引文件的創建過程
4.7.1 創建倒排表
4.7.2 計算統計信息
參考文獻
第5章 搜索引擎的查詢系統
5.1 知識準備
5.1.1 什麼是信息熵
5.1.2 檢索和查詢的區別
5.1.3 檢索詞和查詢詞的區別
5.1.4 自動文本摘要（Automatic Text Summarization）
5.2 網頁信息檢索
5.2.1 早期的檢索模型
5.2.2 向量空間模型（Vector Space Models）
5.2.3 關鍵詞權重的量化方法TF/IDF
5.2.4 搜索引擎采用的檢索模型
5.2.5 多文檔列表求交計算
5.2.6 檢索結果排序
5.2.7 堆排序
5.3 中文自動摘要
5.3.1 自動摘要的發展歷史
5.3.2 自動摘要的含義和實現
5.4 生成搜索結果頁
5.4.1 生成搜索結果頁
5.5 搜索結果頁的緩存
5.6 推測用戶查詢意圖
5.6.1 查詢分類
5.6.2 推測信息類、事物類的查詢意圖
5.7 查詢系統的當前熱點和發展方向
5.7.1 查詢系統的當前熱點
5.7.2 查詢系統的發展方向
參考文獻
第6章 搜索引擎日志分析
6.1 簡介
6.1.1 人機交互的記錄——日志
6.1.2 分析搜索引擎日志的意義
6.1.3 本章的主要內容
6.2 知識準備
6.2.1 二分圖模型（Bipartite Model）
6.2.2 圖模型（graphical model）
6.2.3 LDA（Latent Dirichlet Allocation）模型
6.2.4 隨機游走（Random Walk）
6.2.5 小結
6.3 查詢日志分析
6.3.1 查詢日志的內容
6.3.2 查詢詞頻統計
6.3.3 查詢串提示（Suggestion）
6.3.4 命名實體（Named Entity）類別識別
6.3.5 小結
6.4 點擊日志分析
6.4.1 點擊日志的內容
6.4.2 查詢串提示（Suggestion）再分析
6.4.3 查詢和結果類別屬性傳遞
6.4.4 搜索結果相似性度量
6.4.5 查詢結果排序
6.4.6 點擊數據的稀疏性
6.4.7 小結
6.5 隱私問題
6.5.1 日志的兩面性
6.5.2 日志的安全使用
6.5.3 小結
6.6 本章總結
參考文獻
第7章 排序學習（Learning to Rank）
7.1 排序概述
7.2 傳統的排序模型
7.2.1 查詢相關的排序模型
7.2.2 查詢無關的排序模型
7.3 排序學習簡介以及研究現狀
7.3.1 排序學習簡介
7.3.2 排序學習問題的研究現狀
7.4 排序學習模型的應用實例
7.5 排序學習方法的框架
7.5.1 參數設置
7.5.2 排序學習方法的框架
7.6 評測數據集
7.6.1 LETOR數據集
7.6.2 Microsoft Learning to Rank數據集
7.6.3 Yahoo Webscope數據集
7.7 排序學習模型簡介
7.7.1 實例
7.7.2 Pointwise方法
7.7.3 Pairwise方法
7.7.4 Listwise方法
7.7.5 3種排序方法的對比
7.8 排序學習模型性能比較
7.8.1 評測方法
7.8.2 排序模型性能的比較
7.9 排序學習的研究方向
7.9.1 標準標注的自動構建
7.9.2 排序特征
7.9.3 半監督學習/主動學習
7.9.4 查詢相關的排序模型
7.9.5 利用用戶行為特征
7.10 總結
參考文獻
第8章 搜索引擎的性能調優
8.1 系統調優概述
8.2 瓶頸識別
8.3 涉及CPU的優化方法
8.3.1 上下文切換問題（context switching）
8.3.2 中斷和輪詢
8.3.3 CPU的Affinity問題
8.3.4 流水線問題
8.4 涉及內存的優化方法
8.4.1 概述
8.4.2 對換區
8.4.3 cache line
8.4.4 false sharing問題
8.4.5 內存的鎖問題
8.4.6 內存庫的使用
8.5 涉及磁盤的優化方法
8.5.1 磁盤IO的調度
8.5.2 其他常見磁盤參數調優
8.5.3 磁盤讀寫方式
8.5.4 文件緩存問題
8.5.5 5分鐘法則
8.6 涉及網絡的優化方法
8.6.1 搜索首頁，結果頁提速方法
8.6.2 Web Server的架構選擇
參考文獻

本書第1版出版到現在已經3年了。在這段不長的時光里，搜索引擎技術有了進一步的發展。其中比較突出的是，隨著數據規模進一步增大，為提升用戶體驗，搜索引擎性能進一步優化；在更廣泛的用戶參與下，增強了基于用戶行為進行效果改進的能力。這也使得本書有了改版以適應這些重大變化的必要。

基于此，本書第2版增加了搜索引擎性能調優、搜索引擎日志分析，以及基于學習進行排序優化三方面的內容，希望能讓讀者跟上搜索技術的發展潮流，在這一領域的前沿真切地感受到它的勃勃生機。

當前，搜索技術已經不再局限于搜索引擎本身，它所建立的一套駕馭互聯網級別海量數據的架構和理念正日益擴展到整個信息技術領域。而隨著世界的日益信息化、數字化、網絡化，這些理念的深遠影響還會進一步顯現。這又將是一次新的科技浪潮。

時光流逝，卻有如輪回。信息技術產業，甚至整個科技界，正是在這樣的浪潮更迭中不斷進步。從AT＆T的有線電話到IBM的大型機，到Apple的PC機，到Intel的CPU，到MotOfola的無線通信，到Microsoft的操作系統，到Cisco的路由器，到Google的搜索引擎，概莫能外。一次次浪潮，一個個產業巨擘，終將隨自己的時代而去，但它們所帶來的影響卻將投射在人類文明的歷史上，永不消逝。

至于搜索的浪潮究竟將持續多長時間，在整個1T史上留下怎樣的一筆，只有時間才能告訴人們答案。此時此刻，置身其中，讓我們打開書本，接受浪潮之巔的洗禮，走進搜索引擎。

關于本書作者

作者潘雪峰，畢業于中國科學院計算技術研究所，工學博士。研究興趣包括多媒體內容分析、機器學習和互聯網數據挖掘，現從事搜索引擎領域相關工作。

作者花貴春，目前在清華大學信息科學與技術國家實驗室攻讀博士學位，研究興趣包括機器學習及其在搜索領域的應用。

作者梁斌，目前在清華大學信息科學與技術國家實驗室攻讀博士學位，研究興趣包括大規模數據處理、搜索引擎和軟件工程等。

致謝

筆者首先要特別感謝他們的妻子，感謝她們在繁忙的工作和學習之余，包攬了家里家外大大小小的事務，還在筆者們有所懈怠的時候，從精神上給予莫大的支持和鼓勵。正是她們無私的支持，才使本書得以面世。

感謝電子工業出版社計算機圖書出版分社孫學瑛女士和鄧彩屏女士，她們除了參與了此書的創作過程，還為筆者提供了有關圖書市場的寶貴信息，使得本書更加面向讀者，面向市場。

感謝本書參考文獻的作者們、搜索引擎研究界的學者們，以及為此書提出寶貴技術意見的業界同行，正是你們杰出的成就和無私的幫助，才使得本書有了寫作的基礎和必要。

由于筆者水平有限，加之搜索領域的發展日新月異，書中不足及錯誤之處在所難免，敬請專家和讀者給予批評指正。

潘雪峰、花貴春、梁斌
2011年2月