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

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