【畢業(yè)學(xué)位論文】（Word原稿）Maze檢索系統(tǒng)性能優(yōu)化和資源評價

碩士研究生學(xué)位論文 題目： 索系統(tǒng)性能優(yōu)化和資源評價 姓 名： 學(xué) 號： 院 系：信息科學(xué)技術(shù)學(xué)院 專 業(yè)：計算機系統(tǒng)結(jié)構(gòu) 研究方向：計算機網(wǎng)絡(luò)與分布式系統(tǒng) 導(dǎo) 師： 教授 ， 講師 二六 年 五 月 版權(quán)聲明 任何收存和保管本論文各種版本的單位和個人，未經(jīng)本論文作者同意，不得將本論文轉(zhuǎn)借他人，亦不得隨意復(fù)制、抄錄、拍照或以任何方式傳播。否則，引起有礙作者著作權(quán)之問題，將可能承擔(dān)法律責(zé)任。北京大學(xué)碩士學(xué)位論文 - I - 摘 要 統(tǒng)是 基于 內(nèi)容 交換系統(tǒng) ，采用集中式架構(gòu)管理用戶和資源。本文的研究范圍為 索系統(tǒng)以及 統(tǒng)中資源的性質(zhì)。 第一部分 詳細介紹了 索系統(tǒng)的設(shè)計和實現(xiàn)，并針對 索系統(tǒng)的性能問題進行了研究，討論檢索效率的影響 因素，并提出一些改進方法和途徑。這些方法包括改進整數(shù)壓縮編碼、基于 多級 緩沖技術(shù) 等方法。最后對 提出改進方案。 第二部分 研究 統(tǒng)中資源的性質(zhì)。首先提出了根據(jù)文件指紋的搜索方式，利用文件指紋聚合鏡像文件，向用戶提供所需文件的所有可下載源。然后提出 禁用 指紋庫 和 禁用詞表 結(jié)合的 禁用 文件識別方法，控制 絡(luò)中的 禁用 文件的傳播。最后，本文提出 法，利用下載關(guān)系構(gòu)造一個投票模型，評估資源的價值。 法對資源進行全局評價，有助于選擇性索引文件資源和合理排序返回結(jié)果。 關(guān)鍵詞： 索系統(tǒng)，倒排文件，緩沖機制， s i, is a 2P, it In we of In we we do on of of on we to In we of We on is to be to s we a of an to At an is We to a to to in be to to be to - 目 錄 摘 要 . I . 一章 緒論 . 1 究工作的背景和意義 . 1 文研究工作的內(nèi)容 . 3 文的組織 . 4 第二章 索系統(tǒng)基本技術(shù) . 5 言 . 5 統(tǒng)設(shè)計與結(jié)構(gòu) . 6 錄服務(wù)模塊 . 7 引創(chuàng)建模塊 . 7 索服務(wù)模塊 . 8 章小結(jié) . 8 第三章 倒排文件技術(shù)和緩沖技術(shù) . 10 言 . 10 排文件結(jié)構(gòu) . 11 數(shù)壓縮編碼技術(shù) . 12 沖技術(shù)及評估 . 14 排表緩沖 . 14 間對象緩沖 . 15 詢結(jié)果緩沖 . 17 章小結(jié) . 18 第四章 檢索效率的綜合測評 . 19 言 . 19 真實驗設(shè)計 . 19 真實驗結(jié)果 . 20 進前后的性能對比 . 21 北京大學(xué)碩士學(xué)位論文 - 章小結(jié) . 22 第五章 基于文件指紋的搜索和禁用文件控制 . 23 言 . 23 件指紋搜索方式 . 23 用文件識別技術(shù) . 25 統(tǒng)的禁用文件控制機制 . 27 章小結(jié) . 28 第六章 法 . 29 言 . 29 于下載行為的投票模型 . 30 票模型解釋 . 31 票模型的數(shù)學(xué)表示 . 32 票模型中的特殊 構(gòu)和改進 . 32 上傳 . 32 下載 . 33 票閉環(huán)群 . 34 立 . 35 型的改進 . 36 法 . 37 斂性 . 37 源評價的應(yīng)用 . 38 詢結(jié)果排序 . 39 章小結(jié) . 41 第七章 總結(jié)與未來展望 . 42 結(jié) . 42 足與展望 . 43 參考文獻 . 44 致 謝 . 46 北京大學(xué)碩士學(xué)位論文 - 1 - 第一章 緒論 究工作的背景和意義 近年來， 術(shù)的 蓬勃發(fā)展 ，改變了人們使用網(wǎng)絡(luò)的方式。 人們不再只是瀏覽者，而是參與者，平等的交流認(rèn)為最有價值的資源。 如今，在文件交換方面的應(yīng)用， 術(shù)正是炙手可熱。 自從 1999 年 生，它的用戶量迅速增長，在短時間內(nèi)激增到數(shù)千萬人。 2000 年 五大唱片商的對簿公堂，更使 術(shù)成為人們的焦點。而原告之一 司與 成和解 協(xié)議，更證明了數(shù)字方式發(fā)布音樂是不可阻擋的潮流，與其妄圖阻止類似 享軟件的不斷出現(xiàn)，不如將其變成合法的在線音樂銷售渠道。 在 后，基于 術(shù)的內(nèi)容共享軟件層出不窮，如 等。值得一提的是， 2003 發(fā)布，就是因為有 種 技術(shù)，才讓 熱于嘗新的 用戶 們 第一時間 獲 得這樣 龐大的拷貝。如此快捷、自發(fā)而又有序的數(shù)據(jù)傳播方式，在 術(shù)的興起 之 前，可是不可思議的事。至 此， 基于 內(nèi)容共享，因其自由、平等 及 高效等特性，成為人們不可缺少的 數(shù)據(jù)傳播方式。 基于 內(nèi)容共享系統(tǒng)， 架構(gòu)可分三種：集中式、混合式和純分布式。 因其網(wǎng)絡(luò)組織方式不同，其資源的定位算法也截然不同 et 2003。取集中式的架構(gòu)，中央服務(wù)器擁有所有 享資源信息 ； 由中央服務(wù)器負責(zé)定位資源，回應(yīng) 交 尋找資源 的查詢。 混合式架構(gòu)的 統(tǒng)采取不同的策略，如 用部分性能較好的 當(dāng)超級節(jié)點，由它們索引相近的 葉節(jié)點 所共享的 資源；由超級節(jié)點合作定位資源，回應(yīng) 交的尋找資源的查詢。而完全分布式 架構(gòu) 的 享系統(tǒng) 有兩種：一是完全無結(jié)構(gòu)的 ， 資源定位 算法有 泛洪查找、寬度優(yōu)先、和 隨機漫步 等算法； 若 在每個節(jié)點保存一些關(guān)于 其他節(jié)點 資源信息， 則可 采取以上算法的 一些 變種。二是結(jié)構(gòu)化的純分布式 系北京大學(xué)碩士學(xué)位論文 - 2 - 統(tǒng)采取 法建立，所有的操作都基于 ， 由它來處理資源分布 和定位 。 本文的研究對象 統(tǒng)采取集中式架構(gòu)，有一系列的中央服務(wù)器負責(zé)用戶管理 和資源管理。由用戶服務(wù)器負責(zé) 冊、登陸管理；由心跳服務(wù)器負責(zé)用戶狀態(tài)管理；由中央目錄 服務(wù)器 接收 傳的 享 內(nèi)容信息，以建立全局的倒排索引；并有中央檢索服務(wù)器接收和 處理 資源定位請求 ， 并 做 禁用資源控制和 禁用 用戶管理 。 集中式架構(gòu)的 統(tǒng)具有檢索高效、推薦最優(yōu)和系統(tǒng)可控的優(yōu)點。 基于 內(nèi)容共享系統(tǒng)的檢索系統(tǒng) 建立于信息檢索技術(shù)之上 。信息檢索技術(shù)的研究，主要在于 分析信息的結(jié)構(gòu)和組織，研究其存放和檢索，利用各種技術(shù)，以 有效 提高其檢索效率和效果。 非 結(jié)構(gòu)化的文本一直是信息檢索的研究重點，近年來，大規(guī)模搜索引擎因其應(yīng)用廣泛、數(shù)據(jù)規(guī)模大、查詢請求多且實時性要求高，成為了 信息檢索技術(shù)研究的焦點。 對搜索引擎的研究， 在 各個方面都獲得了累累碩果 ，從網(wǎng)頁抓取、 網(wǎng)頁凈化 、鏡像識別到檢索效率和檢索效果，都取得了極大進展。其對 統(tǒng)的檢索系統(tǒng)研究有著極大的借鑒意義。 混合式和純分布式的 統(tǒng)的搜索方式是 式 的，它們的研究熱點集中在網(wǎng)絡(luò)結(jié)構(gòu)組織、資源存儲、資源發(fā)現(xiàn)和查詢請求轉(zhuǎn)發(fā)等方面，與搜索引擎有著極大的不同。 本文研究興趣不在于此，故不作深入闡述。 集中式架構(gòu)的 統(tǒng) ，其檢索系統(tǒng)有著和搜索引擎許多相似的研究 點 。 它們都需要收集分布在 互聯(lián) 網(wǎng) 的 各個地方的資源信息，都需要對所收集資源進行預(yù)處理，識別 禁用 資源和鏡像資源，還 需要對資源進行評價，以求返回給用戶最貼近用戶需求的資源。 它們也存在很多的不同點。首先研究對象不同，搜索引擎 的研究對象 是網(wǎng)頁 ，網(wǎng)頁是半結(jié)構(gòu)化文本，主要需要語言處理技術(shù)；而 統(tǒng)的研究對象是各式各樣的文件，有文本、多媒體文件和各種軟件等等， 可利用信息主要是文件名信息，若需更多的信息則得抓取額外描述信息，或采取多媒體處理技術(shù) 。再者 資源所在站點 性質(zhì)不同， 搜索引擎的資源所在網(wǎng)站是不知中央服務(wù)器存在和只能被動提交資源信息； 統(tǒng)的組成 可知 中央服務(wù)器 存在 ，且具有計算能力， 可自行處理部分?jǐn)?shù)據(jù)。 綜上所述， 集 中式 統(tǒng)的 所需 檢索技術(shù) 可 參考搜索引擎的檢索技術(shù) ，同時 要針對自身特性研究新的檢索技術(shù)。 北京大學(xué)碩士學(xué)位論文 - 3 - 本文主要分析 統(tǒng) 的檢索技術(shù)。 統(tǒng) 是一種 基于 、集中式的內(nèi)容共享 系統(tǒng) ，可從 解 其 基本概況 。 它 的檢索系統(tǒng) 的 設(shè)計實現(xiàn)參考學(xué)習(xí)了天網(wǎng)搜索的檢索技術(shù)， 考慮 文件資源和網(wǎng)頁資源的差異， 并充分 利用 計算能力，采用 針對 性 的技術(shù) ，以打造高效的、可控的 統(tǒng)。 文研究工作的內(nèi)容 本文的研究工作集中在 統(tǒng)的 檢索系統(tǒng)性能的優(yōu)化 和資源評價 ，主要在數(shù)據(jù) 組織 、檢索效率、檢索效果 等方 面進行研究 。 本文從用戶行為、資源分布特性等 方面出發(fā)，研究 統(tǒng)特性，提出以下技術(shù) ： 基于 多級 緩沖技術(shù) 。 統(tǒng)是由自主行為的 成 ； 而 在線與否決定了該 源的可用性。 本文 設(shè)計 基于 多級 緩沖技術(shù)，充分利用 在線屬性，提高緩沖效率。 文件指紋 搜索技術(shù) 。 統(tǒng)中有眾多鏡像文件，它們分布于不同的各鏡像 命名 差異較大 。本文提出提取文件指紋，將分布于不同 同命名的鏡像文件聚合在一塊，提供根據(jù)文件指紋的搜索方式 ， 查 找用戶 所 需 文件 的所有 可下 載源 。 禁用 文件控制技術(shù) 。 統(tǒng)具有眾多 禁用 文件存在，識別它們并控制它們的傳播是 統(tǒng)一項重要任務(wù)。本文提出通過人工提取 禁用詞 ，查找含 禁用詞 的文件，對這些文件進行人工查看 和機器審查 ，進而提取確認(rèn)為 禁用 文件的指紋，組成 禁用 指紋庫 。 統(tǒng)利用禁用 指紋庫 和禁用詞表，合作 進行 對 禁用 文件的控制。 法 。 法利用下載行為評估資源價值。它通過挖掘 下載日志，利用 資源互相 互動關(guān)系，建立投票 模型，刻畫資源的熱門度。利用資源 評價，參與對返回結(jié)果排序 。 北京大學(xué)碩士學(xué)位論文 - 4 - 文的組織 本文第二章 先 圍繞檢索效率和檢索效果，介紹 索系統(tǒng)的結(jié)構(gòu)設(shè)計，再介紹 索系統(tǒng)的組成 模塊 和實現(xiàn)模塊 所需的基本技術(shù)。 第三章先介紹 統(tǒng)的倒排索引文件結(jié)構(gòu)設(shè)計，再介紹采用的索引壓縮編碼，并對該編碼方式進行效果實驗；然后介紹 統(tǒng)采用的對不同緩沖對象各自采用的緩沖機制，并對緩沖的命中率進行分析。 第四章對 統(tǒng)的檢索效率 進行 綜合 測評 。 先對 考察檢索系統(tǒng)在不同負載狀況下的各個性能參數(shù)，對影響檢索系統(tǒng)性能的主要因素進行分析。 然后對運用上述技術(shù)改進前 后的性能進行對比。 第五 章首先提出文件指紋搜索方式，闡述文件指紋搜索方式對于文件名搜索方式的補充作用 ，以及其對深入搜索的意義 。然后提出一種識別 禁用 文件方法，就是結(jié)合 禁用 指紋庫 和 禁用詞 表來發(fā)現(xiàn)禁用文件 ，并且敘述 統(tǒng)中的 禁用文件控制機制 。 第六 章先提出 基于下載行為的投票 模型， 從數(shù)學(xué)、算法和應(yīng)用的方面對投票模型進行詳細解析。 然后 介紹結(jié)果排序所涉及的因素，并 提出 結(jié)果排序算法。 第七 章 先總結(jié) 索系統(tǒng)中的技術(shù)和 區(qū)中資源性質(zhì)的研究，然后闡述現(xiàn)有檢索系統(tǒng)不足和未來可發(fā)展的一些方向。 北京大學(xué)碩士學(xué)位論文 - 5 - 第二章 索系統(tǒng)基本技術(shù) 言 如前所述， 統(tǒng)有三種架構(gòu)：集中式 、混合性、完全分布式。對于資源搜索來說，這三種架構(gòu)各有利弊。 集中式架構(gòu)的 統(tǒng)，具有中央索引服務(wù) ，可快速定位任意資源，具有查詢響應(yīng)時間短的優(yōu)點，而且可控性較好。 但它需要所有用戶向中央服務(wù)器提交資源共享信息，并且中央服務(wù)器索引重建需要一定周期，因此它有不能即時的體現(xiàn) 統(tǒng)內(nèi)共享信息的變化；另外 集中式架構(gòu)的 對 較差 ，整個系統(tǒng)的瓶頸在于中央服務(wù)器的性能 。 混合式和完全分布式的 統(tǒng)，或采用 超級節(jié)點的 分層結(jié)構(gòu)，或采 用法定位資源，具有可擴展性好 的優(yōu)點。但它的資源定位能力較差；雖熱門文件定位迅速，但一般性文件定位至少需要 n） 的時間 代價。此外，它對 資源的控制較差，對 禁用 文件和違規(guī) 能及時進行處理。 綜合考慮上述優(yōu)劣， 統(tǒng)采用集中式架構(gòu) 。 統(tǒng)在中央服務(wù)器上接收用戶共享內(nèi)容列表，索引所有共享內(nèi)容，并對 禁用 文件進行集中控制。 在系統(tǒng)設(shè)計時， 統(tǒng)充分考慮集中式架構(gòu)的優(yōu)點，追求盡可能快的給用戶返回最好的資源信息，并且控制 禁用 文件的傳播，打 造高效的，健康 的網(wǎng)上社區(qū)。另外，考慮到集中 式架構(gòu)的缺點，設(shè)計時盡量 縮短索引重建周期，盡可能快的體現(xiàn)社區(qū)中資源的變化；并且盡可能的增強系統(tǒng)的可擴展性。 統(tǒng)現(xiàn)有 注冊用戶達 400 多萬，索引約 1 億個文件資源。每天活動用戶達 10 萬余人，下載次數(shù)達 110 多萬，每日查詢次數(shù)達 17 萬。 本章以 統(tǒng)為基礎(chǔ)，分析檢索系統(tǒng)的基本技術(shù)和 統(tǒng)的特有技術(shù)。 北京大學(xué)碩士學(xué)位論文 - 6 - 統(tǒng)設(shè)計與結(jié)構(gòu) 索系統(tǒng)的設(shè)計考慮三個因素 ：檢索效率，檢索效果和系統(tǒng)可擴展性。檢索效率是用戶可直接體驗的因 素，一般來說，對查詢請求響應(yīng)時間 要求 在秒級 ，用戶 才沒有等待的感覺。檢索效果是另一 個用戶 可直接體驗的因 素， 主要表現(xiàn)在返回結(jié)果列表中排列在前的結(jié)果與查詢詞 是否 相關(guān)度 高， 并且 易于下載。檢索效率和檢索效果是評價檢索系統(tǒng)的成功與否的兩個主要因素，它們存在競爭，為獲得較好的檢索效果，需要在服務(wù)器做更多的計算，勢必影響到檢索效率。系統(tǒng)可擴展性是指系統(tǒng)適應(yīng)變化能力， 是否能 滿足用戶 數(shù)量 增長、文件資源 增多 后的查詢請求 ；這是集中式架構(gòu)的較弱的環(huán)節(jié)，設(shè)計時要著重考慮 。 這三個要素對 塊的設(shè)計都起了重大影響。 統(tǒng)的設(shè)計目標(biāo)是，將查詢請求相應(yīng)時間控制在秒級前提下，盡可能的提高返回結(jié)果的相 關(guān)度，并且保證系統(tǒng) 具有一定的 可擴展性。 根據(jù)功能 將 索系統(tǒng)分成三 個模塊：文件列表收集模塊，索引建立模塊，檢索服務(wù)模塊；系統(tǒng)結(jié)構(gòu)圖如下所示。 圖 2統(tǒng)架構(gòu)圖 目錄服務(wù)模塊負責(zé)接收 時上傳的共享資源列表，寫入文件。索引建立模塊定時讀取共享資源列表，建立倒排索引文件和相關(guān)文件。檢索服務(wù)模塊讀取北京大學(xué)碩士學(xué)位論文 - 7 - 倒排索引文件和相關(guān)文件， 定時從狀態(tài)服務(wù)器接收 用戶在線狀態(tài) 列表 ，同時接收和處理 交的用戶查詢請求。下面詳細描述各個模塊功能，以及各個模塊為提高性能所采取的技術(shù)。 錄服務(wù) 模塊 目錄服務(wù)模塊負 責(zé)接收 時上傳的資源 列表。 各個 隔設(shè)定時間檢查自身共享內(nèi)容，若未曾有過變化，向目錄服務(wù)器提交時間更新消息，確認(rèn)資源的有效性；若自身共享內(nèi)容發(fā)生變化，則發(fā)送新的資源列表。目錄服務(wù)模塊 根據(jù)收到的消息類型，或 將接收到的資源列表寫入文件，等待索引創(chuàng)建模塊使用 ，或更新該 源列表的有效時間 。 我們在 設(shè)計 資源信息結(jié)構(gòu)時，充分利用了 計算能力，將能在 立計算的所需資源屬性都下放到 計算，以減輕中央服務(wù)器的負載。比如文件資源的指紋計算和 禁用資源 的 部分過濾工作 ，都放在 處 理 。 引創(chuàng)建 模塊 索引創(chuàng)建模塊負責(zé)資源的倒排索引的創(chuàng)建。對 傳的原始資源列表建立倒排文件和其他資源相關(guān)文件 ，以供檢索服務(wù)模塊的使用 。 倒排 索引 的 設(shè)計， 是檢索服務(wù)的基礎(chǔ)， 對檢索系統(tǒng)性能有著巨大影響。為提高檢索系統(tǒng)性能，本文關(guān)注以下內(nèi)容 ： 索引 結(jié)構(gòu)設(shè)計 。 良好的索引結(jié)構(gòu)設(shè)計可以提高解析效率和方便相關(guān)性評價。在所有 的與 索引 相關(guān)的 結(jié)構(gòu) 體 中，都考慮 d 屬性，充分利用 索引壓縮技術(shù)。 索引壓縮的目的是以 算時間換取空間，最終節(jié)約磁盤訪問時間，提高檢索效率 。這是大規(guī)模、多用戶的檢索系統(tǒng)提高性能的重要手段。 禁用 文件控制技術(shù)。利用 禁用 指紋庫 和禁用詞表合作 識別 禁用 文件，阻止禁用 文件的傳播。另外根據(jù)用戶共享的 禁用 文件情況， 對用戶進行審查，記錄 違規(guī) 用戶的 便 對違規(guī) 用戶進行懲罰 ，最終凈化 區(qū) 。 北京大學(xué)碩士學(xué)位論文 - 8 - 索 服務(wù) 模塊 檢索 服務(wù) 是用戶直接參與的過程，也是用戶體驗最明顯的過程。檢索過程分為以下幾個步驟： 解析用戶提交的查詢請求； 查找 與查詢關(guān)鍵詞相關(guān)的資源記錄，考慮 線屬性，對非在線站點資源進行過濾； 根據(jù)查詢請求屬性和 資源屬性過濾 資源 記錄 ； 根據(jù)相關(guān)度和站點 及文件評價對相關(guān)文件列表進行排序 ； 返回相關(guān)文件的描述信息 在檢索過程中，影響效率的最大因素通常是對磁盤的訪問；而影響效果的最大因素是返回結(jié)果的相關(guān)性評價 和 結(jié)果所在 可下載性評價。在 為提高查詢處理效率和檢索效果 ，最終給用戶良好的體驗，我們采用了以下技術(shù)： 緩沖技術(shù)。利用數(shù)據(jù)訪問的局部性， 在內(nèi)存保存使用可能性更高的數(shù)據(jù)，以 減少對磁盤的訪問 。使用緩沖技術(shù)，可以加快查詢處理速度，減少用戶的等待時間 ，也有利于系統(tǒng)的可擴展性 。 術(shù)。利用 區(qū)中的 載行為日志， 建立基于下 載行為的投票模型 ， 評價 資源和 利用這些評價值對返回結(jié)果進行 重要 性評價。 相關(guān)度的綜合評價 技術(shù) 。 綜合查詢詞、資源評價和 價等因素，計算文件的相關(guān)度。根據(jù)相關(guān)度對返回 資源進行排序，將相關(guān)度最高的一些資源返回給用戶。如此，可以減少無 用的記錄返回比例，提升用戶的使用感受。 章小結(jié) 本章 從 索系統(tǒng)的設(shè)計和實現(xiàn)出發(fā)，探討檢索技術(shù)。首先介紹 索系統(tǒng)的設(shè)計目標(biāo)， 索系統(tǒng)的設(shè)計是圍繞效率、效果和可擴展性展開的。接著介紹了 索系統(tǒng) 的架構(gòu)， 索 系統(tǒng) 從功能 可 劃分為 三個模塊： 目北京大學(xué)碩士學(xué)位論文 - 9 - 錄服務(wù)、索引創(chuàng)建、檢索服務(wù)。 最后 對 索系統(tǒng)中 各模塊的功能 進行描述，并對 其中 采用 的各種 檢索 技術(shù)做了粗略介紹。 這些技術(shù)包括索引壓縮技術(shù)、緩沖技術(shù)和相關(guān)度評價技術(shù)， 它們 是 實現(xiàn) 高效檢索系統(tǒng)的保證。 北京大學(xué)碩士學(xué)位論文 - 10 - 第三章 倒排 文件 技術(shù) 和緩沖技術(shù) 言 倒排文件技術(shù)是一種檢索系統(tǒng)常用的數(shù)據(jù)組織技術(shù) 。它 結(jié)構(gòu)簡單， 檢索效率高， 能迅速的定位所需資源的位置 ，是大規(guī)模、高效率的檢索系統(tǒng)的基礎(chǔ) 。 隨著網(wǎng)絡(luò)的發(fā)展，網(wǎng)絡(luò)應(yīng)用的檢索系統(tǒng)索引的數(shù)據(jù)量不斷增大，對查詢響應(yīng)的實時性要求也逐漸提高。如何有效的組織倒排 文件 、優(yōu)化檢索算法 ，一直是研究的熱點 。近年來 ， 頻率和內(nèi)容容量大規(guī)模增長，而磁盤讀寫效率卻相對增長較慢，因此 對 磁盤 上倒排表數(shù)據(jù)的 訪問常成為 檢索系統(tǒng)效率的瓶頸。于是有大量的研究投入到 對倒排表的壓縮上 et 2002，試圖減少對空間的需求，充分的利用 計算能力，進而提高檢索的整體效率。另外 1996提出在壓縮的倒排表中插入同步點，使得可以跳過某些數(shù)據(jù)塊，直接讀取與用戶查詢最相關(guān)的數(shù)據(jù)塊 ，減少讀盤和解壓縮開銷 。 et 1999對海量數(shù)據(jù)管理方法進 行討論，全面的 敘述了各種 壓縮技術(shù)和索引技術(shù)。 本章對 倒排文件的設(shè)計需考慮下列因素 無二義性。只有一種明確的 解析 方式，這是倒排文件可正確使用的前提條件 。 倒排文件規(guī)模小。通過壓縮倒排表， 以增加 算 換取 減少文件占用空間， 于是 減少 了 磁盤訪問開銷，提高整體檢索效率。 結(jié)構(gòu)簡單。簡單的結(jié)構(gòu)有助于快速的定位到最終相關(guān)資源的描述信息， 減少索引服務(wù)解析時間 ，提高檢索效率。 綜合上述思想， 本章 提出用 碼方式壓縮倒排表，減少磁盤訪問開銷；并且按 基本單位組織倒排表，利用 在線屬性，只讀取 可用的倒排表項。 另一方面，緩沖技術(shù)也是檢索系統(tǒng)必不可少的技術(shù)。 隨著檢索系統(tǒng)索引數(shù)據(jù)量和訪問量的增大，提高系統(tǒng)性能和 擴展性至關(guān)重要 。緩沖技術(shù)就是提高系統(tǒng)性北京大學(xué)碩士學(xué)位論文 - 11 - 能和擴展性的重要手段，它在計算機的各個領(lǐng)域得到廣泛應(yīng)用。 緩沖技術(shù)的有效性建立于被緩沖對象的訪問的局部性特征之上。 在 索引擎方面的緩沖技術(shù) 已有很多的 研究 ，如 et 2002, et 2005等 ，而 統(tǒng)中的緩沖技術(shù)研究相對較少。雖然他們一是研究網(wǎng)頁，二是研究文件，但他們存在共性，因為使用者較多關(guān)心的 都是熱門資源。 本文借鑒搜索引擎中對緩沖技術(shù)的研究，考察 統(tǒng)中各種數(shù)據(jù)使用，提出適用于 統(tǒng)的緩沖技術(shù)。 緩沖對象可分為三級：查詢結(jié)果、中間對象、倒排表。 本文根據(jù) 統(tǒng)運行產(chǎn)生的實際數(shù)據(jù)，對各種緩沖對象的局部性特征進行研究，實現(xiàn)對查詢結(jié)果和倒排表的緩沖機制，并設(shè)計基于 中間對象緩沖方法。 本章第 2、 3 節(jié)對倒排文件結(jié)構(gòu)設(shè)計和壓縮算法的應(yīng)用進行闡述。第 4 節(jié)對各種緩沖對象的局部性特征進行研究，第 5 節(jié)著重闡述基于 中間對象緩沖方法，順帶介紹對查詢結(jié)果和倒排表的緩沖方法。 排文件結(jié)構(gòu) 在線屬性是 索系統(tǒng)的一個至關(guān)重要的屬性，它貫穿整個檢索系統(tǒng)的設(shè)計。 不同于 索系統(tǒng)， 中央服務(wù)器不能實時的了解網(wǎng)站的服務(wù)狀態(tài)；而 統(tǒng) 有一個中央狀態(tài)服務(wù)器，可以實時的了解 在線 信息，確定 于一個 文件共享系統(tǒng)， 資源所在 在線是該資源可用的前提 。資源 所在 處于離 線 狀態(tài)，那么這個 資源 就無法 被其他 載 ，也就毫無使用價值 。將無法下載 的資源 返回 給用戶， 浪費了檢索過程中的 內(nèi)存資源 ，更 影響用戶對 檢索 結(jié)果的評價 。 因此，對返回的用戶查詢結(jié)果 ， 必須 利用線信息 進行 過濾。 在 檢索服務(wù) 設(shè)計 時，要盡可能早 的 考慮 在線屬性 的過濾 。 在檢索早期進行 根據(jù) 在線屬性的過濾，能大量減少中間數(shù)據(jù)量和運算量 ，提高檢索效率 。 因此 根據(jù)在線屬性進行 過濾 ，對離線站點資源不予以解壓縮 。 倒排文件分成兩個部分 ，下面詳細講解各個部分的構(gòu)成，及其作用 ： 北京大學(xué)碩士學(xué)位論文 - 12 - 倒排文件頭： 倒排文件頭記錄所有索引詞對應(yīng)的倒排表在倒排文件的起始偏移信息。 索引詞序列號。 索系 統(tǒng)不作切詞，直接采用雙字節(jié)作為索引詞，或為漢字，或為字母和數(shù)字組合 。后一項屬性是指該索引詞對應(yīng)的倒排表在倒排文件的起始偏移。倒排文件 頭 是對倒排文件訪問的入口。 倒排文件主體 ： 倒排文件主體記錄索引詞對應(yīng)的倒排表信息 。倒排文件主體按關(guān)鍵詞順序排列其對應(yīng)的倒排表 ； 在各 關(guān)鍵詞對應(yīng)的 倒排表內(nèi)部，按站點順序排列各站點相關(guān)文件信息 。對于每個資源，在倒排文件中 可提取出 三個屬性：站 點序列號、站內(nèi)文件序列號、索引詞在資源名中的偏移量。 站點序列號信息，標(biāo)識后續(xù)資源 項的站點屬性，方便考察該資源的在線屬性。 站點占位長度標(biāo)識該站點的資源在該索引詞的倒排表占據(jù)的長度，據(jù)此屬性 可略過對離線站點資源的解壓縮。站內(nèi)文件序列號和站點序列號一起表示 一個文件。最后一項屬性是該索引詞在文件名中的偏移，據(jù)此屬性分析文件和查詢短語的相關(guān)度。 檢索時，通過檢索文件頭定位所需索引詞的 對應(yīng) 倒排表在倒排文件的位置，再讀取所需 倒排表，利用資源的站點序列號進行在線屬性過濾 ，得到 與 查詢相關(guān)的文件列表 。 數(shù)壓縮編碼技術(shù) 我們 采用 整數(shù)壓縮編碼技術(shù) 壓縮倒排 文件，