【畢業(yè)學位論文】（Word原稿）搜索引擎檢索系統(tǒng)的效率優(yōu)化與效果評估研究(V2.0)-計算機網絡技術博士論文

北京大學博士研究生學位論文 題目：搜索引擎檢索系統(tǒng)的效率優(yōu)化與效果評估研究 姓 名：彭波 學 號： 10108808 院 系：計算機科學技術系 專 業(yè)：計算機系統(tǒng)結構 研究方向：計算機網絡與分布式系統(tǒng) 導 師：李曉明 教授 2004 年 5 月 in of or y o ( I 2004 版權聲明 任何收存和保管本論文各種版本的單位和個人，未經本論文作者同意，不得將本論文轉 借他人，亦不得隨意復制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權之問題，將可能承擔法律責任。 i 摘 要 本文研究工作是國家重點基礎研究發(fā)展規(guī)劃項目“網絡環(huán)境下海量信息組織與處理的理論與方法研究”的一部分；針對 索引擎應用背景，以構建大規(guī)模、高性能搜索引擎的檢索系統(tǒng)為目標，系統(tǒng)地研究了檢索系統(tǒng)的效率問題和效果評估問題，提出了若干關鍵技術，在大量實驗和真實數據分析的基礎上，得到了如下研究成果和結論： 1）提出了一種混合索引技術。該技術針對中文信息檢索索引詞選擇的問題，通過結合中文自動分詞與未 登錄詞識別技術，把基本分詞結果與在識別生成的擴展詞典上的分詞結果都選擇作為索引詞。通過在實際系統(tǒng)的應用實踐，表明該技術能有效提高短語檢索效率。 2）提出了一種倒排文件分塊組織方法，它兼顧了文檔編號序列和文檔權值序列在檢索系統(tǒng)性能中的不同作用，為綜合優(yōu)化系統(tǒng)性能提供了一個可操作的框架。和已有相關工作相比，這一研究基于搜索引擎應用背景，通過搜索引擎系統(tǒng)的實際數據，建立了一個檢索性能模型，在此模型基礎上研究分塊組織策略對性能的影響和分塊參數的優(yōu)選。研究結果表明，這一分塊組織策略可以有效提高檢索效率。 3）倒排文件 緩存是檢索系統(tǒng)效率優(yōu)化的重要技術。結合到大規(guī)模檢索過程中磁盤 I/O 以及操作系統(tǒng)頁面調度的特點，本文研究了倒排文件緩存優(yōu)化設計中的性能指標選擇、替換算法、頁面大小和倒排文件組織方式對緩存性能影響等問題。研究結果為倒排文件緩存優(yōu)化設計提供了指導。 4）針對搜索引擎檢索系統(tǒng)效果評估中的若干問題，設計并實現了一個搜索引擎檢索系統(tǒng)檢索效果評估的實驗環(huán)境?；谒阉饕娴挠脩舨樵內罩?，按查詢類別構建了用戶查詢集合。對不同搜索引擎搜集系統(tǒng)搜集網頁集合的差異、評測員結果之間的差異對評估實驗的穩(wěn)定性、連續(xù)性的相關度評分分值以及 對應的評估指標、查詢集合大小對評估實驗的穩(wěn)定性等問題進行了研究，結果對于進行有效的檢索評估實驗有重要指導意義。 5）基于對搜索引擎用戶點擊日志數據的分析，提出了一種自動構建評估實驗相關結果集合與進行自動評估實驗的方法。實驗顯示這一自動方法得到的結果和人工評估實驗結果保持一致，并且對不同查詢集合保持穩(wěn)定。這一方法為解決大規(guī)模數據集上檢索系統(tǒng)評估的可擴展性問題提供了一條有效的途徑。 關鍵詞 ：萬維網，搜索引擎，信息檢索，檢索效率，性能，評估 is an of In we of of on 1. A is By we of on on of as of is in 2. A of is It of to of A of on by on of 3. is an We in of of of a of 4. at in of in we an We a of eb h of on of 5. An is on of of on of on to is a of on eb v 目錄 摘 要 . i . 錄 . v 圖示 . 格 . 1 章 引言 . 1 究工作的背景和意義 . 1 文研究工作的內容 . 2 文的主要貢獻 . 3 合索引技術 . 3 排文件分塊組織技術 . 3 排文件索引的緩存優(yōu)化技術 . 4 索引擎檢索效果評估方法 . 4 于用戶點擊日志的自動評估方法 . 4 文組織 . 4 第 2 章 搜索引擎檢索系統(tǒng)基本技術 . 6 言 . 6 統(tǒng)設計與結構 . 6 引創(chuàng)建 . 10 引詞選擇 . 10 頁預處理 . 11 引創(chuàng)建算法 . 12 索過程 . 12 引壓縮 . 13 機訪問的索引組織 . 13 要索引詞單獨索引 . 14 章小結 . 14 第 3 章 混合索引技術 . 15 言 . 15 合索引原理 . 15 合索引的實現 . 18 登錄詞識別 . 18 展詞典組織與分詞 . 19 章小結 . 20 第 4 章 倒排文件分塊組織技術 . 21 言 . 21 排索引的檢索性能模型 . 22 檔模型 . 22 戶查詢模型 . 24 算機系統(tǒng)性能參數 . 26 塊索引項的組織策略 . 26 排文件基本組織方式與檢索算法 . 26 排文件分塊組織方式與檢索算法 . 28 驗設計 . 29 法仿真 . 29 題分析 . 30 真實驗和結果 . 31 R|與 k 比較 . 31 (Q)以及分塊因子 對 T(Q)的影響 . 33 章小結 . 35 第 5 章 倒排文件索引緩存機制 . 36 言 . 36 排文件緩存 . 37 系結構 . 37 載數據 . 38 載特性 . 39 列中對象的時間間隔分布 . 40 列的重復模式 . 41 驗設計 . 41 題分析 . 41 驗設計 . 44 真實驗結果 . 45 擊 時間間隔 . 72 擊 過程具有自相似性特征 . 74 擊 聚類分析 . 75 動評估實驗 . 77 章小結 . 80 第 8 章 總結和未來工作展望 . 81 參考文獻 . 85 北京大學學位論文原創(chuàng)性聲明和使用授權說明 . 94 致謝 . 95 博士期間錄用和提交的論文 . 96 圖示 圖 2索系統(tǒng)集成框架結構 . 7 圖 2網 索分布式系統(tǒng)構架 . 9 圖 3展詞典樹結構示例 . 20 圖 3展詞典匹配查找算法 . 20 圖 4序號 . 24 圖 4戶查詢詞個數分布 . 25 圖 4引詞區(qū)間上的查詢分布 . 25 圖 4排文件基本檢索算法 . 27 圖 4塊組織倒排文件的檢索算法 . 28 圖 4R| 與 K 比較的仿真結果 . 32 圖 4塊檢 索 I/O 訪問比例 . 32 圖 4詞區(qū)間均勻分塊下的 T(Q) . 34 圖 4幾何級數區(qū)間分塊下的 T(Q) . 34 圖 5索引 擎檢索系統(tǒng)緩存結構 . 37 圖 5檔數據訪問對象大小分布 . 40 圖 5（ 4列替換算法比較 . 46 圖 5緩存性能 . 46 圖 5面對齊方式下緩存性能與頁面大小的關系 . 48 圖 6關度評測環(huán)境 . 56 圖 6測人員每組評測平均花費時間 . 59 圖 6測人員評分差異 . 59 圖 6同評估人員與評估指標下結果比較 . 60 圖 6詢集合大小對評估穩(wěn)定性影響 . 62 圖 7同 數量遵從 . 68 x 圖 7擊 頻度頻級關系 . 68 圖 7點擊 序號 . 70 圖 7始索引文檔庫中網頁的大小分布 . 70 圖 7引庫中與點擊頁面大小的比較 . 71 圖 7面大小與點擊次數關系 . 71 圖 7擊 現的時間間隔 . 73 圖 7時間間隔在 60 秒內點擊 特征 . 73 圖 7擊 列的自相似性 . 75 圖 7同的 數與對應查詢詞序號關系圖 . 78 表格 表 4檔模型參數 . 23 表 4戶查詢模型參數 . 24 表 4算機性能參數 . 26 表 5據集基本統(tǒng)計信息 . 39 表 5面對齊方式和順序方式的性能比較 . 47 表 6戶查詢分類類別 . 53 表 6戶查詢類別分布 . 53 表 6詢集說明及示例 . 53 表 6索引擎覆蓋率比較 . 58 表 6估人員與指標比較實驗結果 . 61 表 6航型查詢評估結果 . 63 表 6航型查詢評估結果顯著性和錯誤率 . 63 表 6務型查詢評估結果 . 64 表 7網用戶點擊日志記錄格式 . 67 表 7網 2003 年 9 月 點擊日志基本情況 . 67 表 7擊 應頁面的類別 . 72 表 7于 較的自動評估結果 . 78 表 7于 較的相關判別結果統(tǒng)計 . 79 表 7于站點判別的自動評估結果 . 79 表 7于站點判別的相關結果統(tǒng)計 . 79 表 7于站點判別的自動評估實驗錯誤率 . 80 第 1 章 引言 1 第 1章 引言 究工作的背景和意義 我們 正處在一個新時代的起點。 活和工作等各個方面，它們的影響力已經開始滲透到社會的各個層面。而這一切才剛剛開始。 1945 年提出的 945代表了人類長久以來的一個夢想：讓每個人都可以十分容易的訪問人類積累下來的知識并且十分容易的共享自己的見解。 描述成一個存放了無數本書籍的書桌，這些書籍的內容被超鏈接互相連接起來，同時其它形式的知識載體，如圖片、聲音錄音等也被放進來。人們可以通過鏈接在 瀏覽，也可以通過簡單的界面，比如口頭的命令來搜索和查詢。人們還可以共享自己對書籍閱讀的注解。 出現使 再僅僅是一個夢想。萬維網（ 記為 源于 1989 年歐洲粒子物理研究室 初計 劃是由物理學家 1989 年 3 月提出，在 1993 年 2 月，隨著第一個圖形界面 發(fā)布而開始迅速發(fā)展 et 1994。據估計每年 量增加 100%001，每天增加大約100 萬的新網頁 et 1999。到 2004 年 4 月， 稱提供對 4,285,199,774 個網頁提供 檢索服務 但這還只是 已有網頁中很小的一部分 999, 核心技術是超文本和超媒體，它通過將文本、圖形、圖像、音頻、視頻等信息的有機結合，給人們提供了豐富的信息表示空間。同時 得信息發(fā)布 變得前所未有的簡單，也讓信息瀏覽十分方便。整個 當于一個巨大的知識庫，越來越多的文本、書籍被數字化提供在線服務，越來越多的文字以數字化的形式創(chuàng)建和存儲。 模的迅速增長和內容不斷豐富，也給人們進行有效訪問帶來了困難。人們需要 有 那樣理想的搜索和查詢的功能，以幫助自己快速、準確的在信息的海洋中找到自己需要的內容。搜索引擎正是由這樣一種需求推動而得到快速發(fā)展的信息服務形式。根據統(tǒng)計，約 85%的用戶使用搜索引擎去定位他們需要的信息，并且，幾個著名的通用搜索引擎一直都穩(wěn)定的處于全球訪問 量最大的 50 個網站之列。搜索引擎已經成為第 1 章 引言 2 了人們進行信息獲取的一個基礎設施。 搜索引擎的檢索系統(tǒng)建立在信息檢索技術之上。廣義的信息檢索是研究信息的結構、分析、組織、存貯和檢索的學科。其中，非結構化的文本信息檢索是信息檢索領域研究的重點，當前搜索引擎的檢索系統(tǒng)就是這一類的信息檢索系統(tǒng)。信息檢索從 1960 年代開始，一直堅持采用統(tǒng)計的方法處理語言和文本數據，強調評估方法和評估實驗，逐步建立了大規(guī)模的測試數據集和評估環(huán)境，取得了豐碩的研究成果。 索是信息檢索研究的多種信息獲取類型中的一種， 的用戶查詢是多 種用戶信息需求類型中很重要的一部分，搜索引擎可以從信息檢索領域研究成果中選取成熟的技術。同時， 索本身的特點也為信息檢索研究帶來了新的研究問題，比如 索下的巨大數據規(guī)模和用戶數量， 據的超文本結構，索下用戶短查詢的特點等等。 隨著 日益重要， 索成為計算機學科多個領域研究的對象和中心，包括信息檢索、數據庫、自然語言處理、數據挖掘等。眾多研究方法、技術的融合、互相促進是這一方向的特點。 文研究工作的內容 本文研究工作集中在搜索引擎檢索系統(tǒng)的性能和評估，主要圍繞如何更有效 的組織數據，如何高效檢索，如何對檢索系統(tǒng)的檢索效率和效果進行評估等幾個方面。具體體現在研究海量 息的高性能檢索技術， 容如下： 1. 混合索引技術：中文全文索引技術中索引詞選擇直接影響檢索系統(tǒng)性能。本文提出了一種基于自動識別新詞技術上的混合索引技術。與常用的其它幾種索引詞選擇技術相比，這一技術能夠有效提高搜索引擎檢索效率，同時不會導致檢索效果下降。 2. 分塊索引組織技術：對倒排文件索引項數據訪問的開銷是影響檢索系統(tǒng)性能的重要因素。本文針對搜索引擎用戶查詢的統(tǒng)計特性，提出了一種分塊組織 倒排文件的方法及其查詢匹配操作算法。該方法兼顧了文檔編號序列和文檔權值序列在檢索系統(tǒng)性能中的不同作用，為綜合優(yōu)化系統(tǒng)性能提供了一個可操作的框架。 3. 索引緩存技術：緩存技術是提高系統(tǒng)效率的重要技術。本文通過分析數據訪問序列的局部性特性，和基于用戶查詢日志數據的緩存仿真實第 1 章 引言 3 驗，探討了倒排文件緩存優(yōu)化設計中的性能指標選擇問題、替換算法選擇、頁面大小和倒排文件組織方式對緩存性能影響等問題。 4. 檢索系統(tǒng)效果評估：檢索系統(tǒng)效果評估是信息檢索研究的重要內容。本文建立了搜索引擎檢索系統(tǒng)效果評估的工具和評估實驗環(huán)境，對索環(huán) 境下的檢索效果評估中的若干問題進行研究，包括用戶查詢類別問題、數據規(guī)模和數據集不一致問題、連續(xù)型相關性分值與評估標準選擇問題、評估評估人員差異對實驗的穩(wěn)定性問題、查詢集合大小對實驗的穩(wěn)定性問題等。 5. 點擊日志分析：本文對搜索引擎用戶點擊日志進行統(tǒng)計分析，包括用戶點擊的基本分布特征分析、局部性特征分析和聚類分析。結果用于指導對檢索系統(tǒng)設計和對用戶搜索行為的研究。 6. 自動評估方法：自動評估是解決傳統(tǒng)檢索系統(tǒng)評估的可擴展性問題的一種方法。本文基于用戶點擊日志分析，提出了一種自動構建評估實驗相關結果集合的方法。實驗結果 表明這一方法的有