【畢業(yè)學(xué)位論文】（Word原稿）搜索引擎的日志分析-方法、技術(shù)和應(yīng)用-計算機(jī)系網(wǎng)絡(luò)與分布式系統(tǒng)

北京大學(xué)學(xué)士學(xué)位論文 第 1 頁 論 文 摘 要 本文首先介紹了 迅速發(fā)展?fàn)顩r，分析了 息資源的特點(diǎn)。在介紹已有的搜索引擎之后，分析了這些搜索引擎的特點(diǎn)。 隨后，本文對“天網(wǎng)”搜索引擎系統(tǒng)進(jìn)行了介紹，給出了該系統(tǒng)的總體結(jié)構(gòu)、技術(shù)特征，并分析了該系統(tǒng)的性能。 然后，文章介紹了“天網(wǎng)”系統(tǒng)中的信息統(tǒng)計子系統(tǒng)。信息統(tǒng)計子系統(tǒng)是為系統(tǒng)管理人員評估系統(tǒng)性能、維護(hù)系統(tǒng)效率、更好滿足用戶的查詢要求而設(shè)計實(shí)現(xiàn)的。本文給出了信息統(tǒng)計子系統(tǒng)的總體結(jié)構(gòu)，并詳細(xì)介紹了該子系統(tǒng)的 兩個重要部分，數(shù)據(jù)庫信息處理和日志文件信息處理的設(shè)計目標(biāo)和實(shí)現(xiàn)算法，并介紹了如何讓機(jī)器自動學(xué)習(xí)新詞。 關(guān)鍵詞 ： 搜索引擎、信息統(tǒng)計、機(jī)器學(xué)習(xí)新詞 北京大學(xué)學(xué)士學(xué)位論文 第 2 頁 目 錄 目 錄 . 2 第一章 背景介紹 . 3 發(fā)展與現(xiàn)狀 . 3 索引擎技術(shù)的發(fā)展與現(xiàn)狀 . 5 第二章 系統(tǒng)概述 . 6 統(tǒng)的總體結(jié)構(gòu) . 6 統(tǒng)技術(shù)特征 . 6 體性能 . 8 第三章 信息統(tǒng)計子系統(tǒng) . 10 統(tǒng)的改進(jìn)需求 . 10 息統(tǒng)計子系統(tǒng)的總體結(jié)構(gòu) . 10 行條件 . 11 用界面 . 11 第四章 數(shù)據(jù)庫信息處理的實(shí)現(xiàn) . 14 計目標(biāo) . 14 據(jù)庫處理 . 14 用次數(shù)排行表 . 15 . 16 計各個域內(nèi)的主機(jī)數(shù)目 . 18 機(jī)情況查詢 . 19 第五章 日志文件信息處理的實(shí)現(xiàn) . 20 計目標(biāo) . 20 件處理 . 20 詞學(xué)習(xí) . 22 致謝 . 25 參考文獻(xiàn) . 26 北京大學(xué)學(xué)士學(xué)位論文 第 3 頁 第一章 背景介紹 發(fā)展與現(xiàn)狀 一個規(guī)模巨大、自治性強(qiáng)、發(fā)展變化快，用戶訪問頻繁的國際互聯(lián)網(wǎng)絡(luò)。 前身是 60 年代末， 70 年代初美國國防部高級研究計劃署的實(shí)驗性網(wǎng)絡(luò) 建 最初原因是當(dāng)時計算機(jī)的價格非常昂貴，所以科研工作者們想通過網(wǎng)絡(luò)進(jìn)行遠(yuǎn)程計算。后來，人們才逐漸認(rèn)識到它作為通訊手段的好處。 1983 年后， 有關(guān)軍事的部分被隔離為 后， 1986年誕生的美國國家科學(xué)基金會 發(fā)展起了劃時代的作用。 90 年代初到現(xiàn)在，是 長最迅速的時期。 1993 年， 增長速度是 341%。截止到 1996 年 7 月， 連接了 134336 個網(wǎng)絡(luò)，入網(wǎng)主機(jī) 1228 萬臺，以及數(shù)以億計的用戶。 的信息資源隨著 信息量大而且分散 自治性強(qiáng) 信息資源多種多樣 信息變化快 不一致和不完整性 這些特點(diǎn)對網(wǎng)絡(luò)軟件的性能提出了很高的要求。 全球性的網(wǎng)絡(luò)信息系統(tǒng)。一九八九年，位于瑞士的先開始了 研究工作。隨后，許多其它的研究機(jī)構(gòu)、大學(xué)和公司也加入 究者的行列，并相繼開發(fā)出各自的 件。這些 件的運(yùn)行平臺覆蓋了目前主流的計算機(jī)硬件和操作系統(tǒng)。在此過程中， 不斷完善和發(fā)展。同時，為了保證不同 件之間的互操作性，一系列 議和標(biāo)準(zhǔn)也正在使用和完善之中。 基于超文本（ 超媒體 (分布式信息系統(tǒng)。超文本和超媒體是信息的一種組織形式，如圖 示： 北京大學(xué)學(xué)士學(xué)位論文 第 4 頁 在超文本文件中，包含有許多指針，這些指針被稱為超文本鏈 (每一個超文本鏈都指向其它的超文本信息。這些超文本信息可能存放在同一臺計算機(jī)中，也可能存放在 息系統(tǒng)的其它計算機(jī)中。讀者并不關(guān)心這些超文本信息存放在何處，如果他們想了解這些信息，他們就可以通過超文本鏈得到。超媒體是對超文本的擴(kuò)展。在超媒體系統(tǒng)中，超媒體鏈可以指向 任何媒體信息，包括圖象、音頻、視頻等等。超文本和超媒體為用戶進(jìn)行信息檢索提供了極大的方便。 . . . 圖 京大學(xué)學(xué)士學(xué)位論文 第 5 頁 索引擎技術(shù)的發(fā)展與現(xiàn)狀 隨著 迅速發(fā)展， 出現(xiàn)了 息查詢服務(wù)，它們通常被稱作搜索引擎。這些搜索引擎一般是預(yù)先由程序自動地在網(wǎng)上遞歸地訪問 訪問的信息存入數(shù)據(jù)庫。然后將數(shù)據(jù)庫中的信息建立索引，并提供給用戶 查詢界面。搜索引擎根據(jù)用戶的請求查詢數(shù)據(jù)庫，并將結(jié)果按相關(guān)程度排序后輸出給用戶。 目前的搜索引擎大致可分為三大類：分類編目搜索引擎 (機(jī)器人搜索引擎 (元搜索引擎（ 分類編目搜索引擎以 代表，機(jī)器人搜索引擎以 司的 代表 , 元搜索引擎以 國外搜索引擎起步較早，功能全面，性能良好，但是它們的共同缺點(diǎn)是都不能很好地支持中文信息的發(fā)現(xiàn)和查詢。雖然 搜索引擎在 1998年上 半年宣布支持中文，但在對中文信息的處理上尚存在很多不足，如不能準(zhǔn)確切詞，不能在上下文環(huán)境中理解語義等等。 北京大學(xué)學(xué)士學(xué)位論文 第 6 頁 第二章 系統(tǒng)概述 統(tǒng)的總體結(jié)構(gòu) “天網(wǎng)（ 中英文搜索引擎系統(tǒng)是為滿足用戶對中國教育科研計算機(jī)網(wǎng)（ 的信息資源的檢索和查找需要而研制開發(fā)的。本系統(tǒng)的研制列入 用系統(tǒng)課題項目，其目標(biāo)是建立 能廣泛應(yīng)用的 源索引與查找系統(tǒng)。它符合相關(guān)的 準(zhǔn)，能夠自 動對 時建立 源索引數(shù)據(jù)庫，以滿足遠(yuǎn)程 覽器的交互式查詢請求，并將查詢的結(jié)果以 件的形式返回給用戶。 本系統(tǒng)主要由 息存取和分析子系統(tǒng)、 息收集控制子系統(tǒng)、 源索引數(shù)據(jù)庫、信息檢索子系統(tǒng)、管理和監(jiān)控子系統(tǒng)等幾個部分組成。其總體結(jié)構(gòu)如圖 示。 統(tǒng)技術(shù)特征 本系統(tǒng)有以下技術(shù)特征： 1 信息收集符合 相關(guān)協(xié)議和標(biāo)準(zhǔn)。 因為本系統(tǒng)收集的主要是 的信息，所以在設(shè)計開發(fā)時把對有 關(guān)協(xié)議和標(biāo)準(zhǔn)的支持 作為一個重要的目標(biāo)。這些協(xié)議和標(biāo)準(zhǔn)包括： 議、言、 準(zhǔn)、 議。 2 實(shí)用、高效的信息分析方法。 本系統(tǒng)主要根據(jù) 不同的 分頁面中各個部分信息內(nèi)容在文章中的重要性和所處的位置，并結(jié)合使用中文分詞、詞頻統(tǒng)計和一定的自然語言理解技術(shù)，智能化地提取該頁面的關(guān)鍵詞和摘要。 3 高度智能性和適應(yīng)性的信息發(fā)現(xiàn)方法 我們在本系統(tǒng)中主要使用程序方式自動收集 息，即 器人方式。在該方式中，有一個能自動在 中獲取信息并進(jìn)行漫游的程序根據(jù) 檔中 的超鏈，自動收集和索引 息這種方式速度快、基本不需人工干預(yù)。 北京大學(xué)學(xué)士學(xué)位論文 第 7 頁 務(wù)器 取分析 存取分析 存取分析 部接口 部接口 部接口 主控模塊 索服務(wù)器 索引數(shù)據(jù) 庫 口處理 口處理 子郵件 瀏覽器 檔 圖 京大學(xué)學(xué)士學(xué)位論文 第 8 頁 4 中文信息處理技術(shù) 中文信息處理與英文存在很大不同，這是因為中文信息處理具有很多自己 的特點(diǎn)，這使中文信息的詞語切分 (切詞 )成為漢語信息處理的第一道關(guān)口，也是建立中文信息發(fā)現(xiàn)和檢索系統(tǒng)的關(guān)鍵性技術(shù)之一。我們使用 以帶詞類標(biāo)記的詞典為基礎(chǔ)、以切詞與標(biāo)注相結(jié)合的方法處理中文信息， 較好地解決了漢語的切詞問題。 5 可伸縮的分布式結(jié)構(gòu) 本系統(tǒng)主要由信息收集子系統(tǒng)和信息檢索子系統(tǒng)兩部分組成。這兩個子系統(tǒng)之間既相互聯(lián)系，又相互獨(dú)立，可以分布在不同的主機(jī)上分別運(yùn)行。 6 基于詞的大型、高效的信息索引數(shù)據(jù)庫和快速、準(zhǔn)確的檢索方法。 本系統(tǒng)主要采用基于詞的索引，以達(dá)到較快的速度和較高的準(zhǔn)確性，同時減少索引信息對磁盤空間 的占用。 在索引庫中采用分級的優(yōu)化索引結(jié)構(gòu)和多級索引技術(shù)，將較小的一級索引駐留內(nèi)存，檢索操作過程大部分在內(nèi)存中進(jìn)行，盡量減少對硬盤文件的訪問。因而大大提高了檢索的響應(yīng)速度。索引庫支持增量修改和索引。以減少數(shù)據(jù)復(fù)制時產(chǎn)生的網(wǎng)絡(luò)流量，提高索引速度。 7智能化、多功能的用戶檢索接口。 用戶可以通過瀏覽器直接訪問本系統(tǒng)，還可以使用 詢接口。 體性能 存 引數(shù)據(jù)庫和檢索數(shù)據(jù)庫分開等先進(jìn) 、 有效的技術(shù)，使得系統(tǒng)占用資源少、信息收集 速度快、用戶查詢響應(yīng)時間快（系統(tǒng)對 上的查詢可在 1秒鐘之內(nèi)作出響應(yīng)）、查準(zhǔn)率和查全率較高，基本達(dá)到了實(shí)用化程度。 系統(tǒng)在設(shè)計和實(shí)現(xiàn)過程中，充分考慮到了用戶和管理員的使用習(xí)慣，提供了瀏覽器、電子郵件、中英文用戶接口和方便易用、功能豐富的管理工具，因而有很好的可用性和易用性。 天網(wǎng)從 1997年 10月在 到了用戶的歡迎和好評。 統(tǒng)計數(shù)字表明了系統(tǒng)的使用情況： 北京大學(xué)學(xué)士學(xué)位論文 第 9 頁 時間 1998 年 1999 年 3 月 1999 年 4 月 平均每天訪問人次 2200 10113 15333 由于天網(wǎng)功能全面、性能突出，軟件世界雜志年第 7期將天網(wǎng)評價為國內(nèi)最好的中英文搜索引擎。 北京大學(xué)學(xué)士學(xué)位論文 第 10 頁 第三章 信息統(tǒng)計子系統(tǒng) 統(tǒng)的改進(jìn)需求 經(jīng)過測試和改進(jìn)，到 1998 年，天網(wǎng)搜索引擎已經(jīng)可以很好地為廣大網(wǎng)絡(luò)用戶服務(wù)了。在 ，平均每天有幾千人次訪問天網(wǎng)搜索引擎。許多研究人員、教師都把天網(wǎng)搜索引擎作為他們工作中的重要工具。為數(shù)眾多的大中院校學(xué)生每天通過天網(wǎng)搜索引擎查詢專業(yè)信息，了解社會動態(tài)，和娛樂消遣。 隨著系統(tǒng)的 廣泛使用，對索引數(shù)據(jù)庫以及用戶查詢記錄進(jìn)行處理，從中提取出有用的信息，幫助系統(tǒng)管理人員評估系統(tǒng)性能、維護(hù)系統(tǒng)效率、更好滿足用戶的查詢要求，成為一個急待解決的問題。信息統(tǒng)計子系統(tǒng)就是為這個目的而設(shè)計的。 該子系統(tǒng)通過處理索引數(shù)據(jù)庫產(chǎn)生關(guān)于網(wǎng)上頁面、主機(jī)狀況的信息，如頁面的平均長度、頁面的被引用情況、頁面的編碼類型、主機(jī)上的頁面數(shù)等等；通過處理用戶查詢記錄文件產(chǎn)生關(guān)于用戶需求的信息，如用戶的訪問次數(shù)、訪問類型、常查詢的詞語，并可以自動學(xué)習(xí)新詞。 息統(tǒng)計子系統(tǒng)的總體結(jié)構(gòu) 界面程序 數(shù)據(jù)庫信息 處理程序 日志信息 處理程序 用戶查詢 日志文件 索引 數(shù)據(jù)庫 結(jié)果文件 圖 求 結(jié)果 調(diào)用 調(diào)用 北京大學(xué)學(xué)士學(xué)位論文 第 11 頁 信息統(tǒng)計子系統(tǒng)的總體結(jié)構(gòu)如圖 示。 信息統(tǒng)計子系統(tǒng)主要分為三大模塊。第一部分是數(shù)據(jù)庫信息處理程序，它啟動運(yùn)行后，從索引數(shù)據(jù)庫中讀取數(shù)據(jù)，統(tǒng)計出信息，寫在結(jié)果文件中。這部分內(nèi)容又可分為統(tǒng)計頁面信息和統(tǒng)計主機(jī)信息兩部分。第二部分是日志處理程序，它讀取用戶查詢?nèi)罩疚募?，處理得到的信息也記錄在幾個結(jié)果文件中。第三部分是使用界面程序，它根據(jù)使用者的要求啟動數(shù)據(jù)庫信息處理程序、日志信息處理程序、或是顯示某些查詢結(jié)果。 行條件 本子系統(tǒng)與主系統(tǒng)一樣，硬件平臺選用的是 作站。整個程序是在 境下用 C 語言開發(fā)的。程序中使用了一些 C 語言的庫函數(shù)，數(shù)據(jù)庫統(tǒng)計部分采用 嵌入式數(shù)據(jù)庫查詢語言。 用界面 界面部分使用網(wǎng)絡(luò)研究室自己開發(fā)的 C 語言圖形編輯函數(shù)庫，采用 主菜單的形式如下： 菜單：脫機(jī)啟動各統(tǒng)計程序。 菜單：清除以前的統(tǒng)計記錄，使 得以后運(yùn)行各統(tǒng)計程序得到的結(jié)果并不在這之前的記錄上累加。 菜單：查詢與用戶查詢情況有關(guān)的信息。 菜單：查詢與數(shù)據(jù)庫內(nèi)頁面有關(guān)的信息。 菜單：查詢與數(shù)據(jù)庫內(nèi)主機(jī)有關(guān)的信息。 菜單：退出主菜單。 單的形式如下： 京大學(xué)學(xué)士學(xué)位論文 第 12 頁 項：啟動統(tǒng)計頁面情況的程序。 項：啟動統(tǒng)計主機(jī)情況的程序。 項：啟動統(tǒng)計用戶日志情況的程序。 單的形 式如下： 項：刪除以前統(tǒng)計的詞的查詢頻率的記錄。 項：刪除以前統(tǒng)計的新詞頻率記錄。 項：清空所有的查詢次數(shù)計數(shù)器。 單的形式如下： 項：查詢次數(shù)和種類的統(tǒng)計信息。 項：顯示近期內(nèi)的查詢統(tǒng)計信息。 菜單：查詢詞語的出現(xiàn)頻率。 菜單：查詢學(xué)習(xí)到的新詞。 單的形式如下： 項：查詢各編碼類型的頁面數(shù)。 項：查詢與頁面長度有關(guān)的信息。 項：顯示被引用次數(shù)最高的一百個頁面。 項：顯示總頁面數(shù)。 單的形式如下： 項：顯示主機(jī)總數(shù)。 項：顯 示每個域的主機(jī)數(shù)。 項：查詢有關(guān)某個主機(jī)的信息。 北京大學(xué)學(xué)士學(xué)位論文 第 13 頁 單的形式如下： 項：顯示被查詢次數(shù)在 5 到 10 次之間的詞。 項：顯示被查詢次數(shù)在 10 到 20 次之間的詞。 項：顯示被查詢次數(shù)在 20 到 50 之間的詞。 項：顯示被查詢次數(shù)在 50 到 100 之間的詞。 項：顯示被查詢次數(shù)在 100 以 上的詞。 單的形式如下： 項：顯示學(xué)習(xí)到的長度為 2 的詞。 項：顯示學(xué)習(xí)到的長度為 3 的詞。 項：顯示學(xué)習(xí)到的長度在 4 以上的詞。 北京大學(xué)學(xué)士學(xué)位論文 第 14 頁 第四章 數(shù)據(jù)庫信息處理的實(shí)現(xiàn) 計目標(biāo) 1 統(tǒng)計數(shù)據(jù)庫中一共有多少個頁面，這樣可以幫助估計數(shù)據(jù)庫的規(guī)模和系統(tǒng)的服務(wù)能力。 2 統(tǒng)計數(shù)據(jù)庫中一 共有多少個主機(jī)。 3 統(tǒng)計各種編碼類型的頁面各有多少，這樣可以知道大部分用戶查詢需要怎樣被處理，從而估計影響系統(tǒng)效率的關(guān)鍵因素。 4 統(tǒng)計被引用次數(shù)最多的 100 個頁面，這可以反映出網(wǎng)上比較受歡迎的信息。 5 統(tǒng)計數(shù)據(jù)庫中各個長度范圍的頁面數(shù)和頁面的平均長度，用來估計系統(tǒng)所占用的空間。 6 統(tǒng)計各個域內(nèi)的主機(jī)數(shù)目，反映網(wǎng)上的主機(jī)分布情況。 7 查詢某個主機(jī)是否在索引數(shù)據(jù)庫中收錄，如果被收錄，它的上面有多少頁面被收錄到索引數(shù)據(jù)庫內(nèi)。 據(jù)庫處理 功能示意圖如下： 索引 數(shù)據(jù)庫 讀數(shù)據(jù)庫 函數(shù) 中間文件 全局變量 圖 京大學(xué)學(xué)士學(xué)位論文 第 15 頁 對索引數(shù)據(jù)庫的處理分為 兩部分，一部分是對頁面的統(tǒng)計，主要是對據(jù)庫中的 中的數(shù)據(jù)進(jìn)行處理，提取出關(guān)于頁面的有用信息；另一部分是對主機(jī)的統(tǒng)計，主要是對 據(jù)庫中的 中的數(shù)據(jù)進(jìn)行統(tǒng)計，提取出關(guān)于主機(jī)的有用信息。 由于索引數(shù)據(jù)庫中的信息量很大，共有一百多萬頁面，七千多個站點(diǎn)，對數(shù)據(jù)庫內(nèi)的數(shù)據(jù)如果完全用 句處理，會使統(tǒng)計的速度非常慢。因此，采用的算法是只通過一遍掃描，將數(shù)據(jù)庫中有用的信息存在一些中間文件和 后用雙鏈表等手段處理這些中間文件，得到 結(jié)果文件。 為保證系統(tǒng)的效率，程序中只用了一條最簡單的 句。 頁面統(tǒng)計程序中，每從數(shù)據(jù)庫中讀取一個信息，都要進(jìn)行如下處理： 將該頁面的網(wǎng)址寫在一個文件中。 將該頁面所在的主機(jī)的信息插入 ，并在 相應(yīng)的項的域中記錄該頁面的網(wǎng)址在上一文件中的位置。 頁面數(shù)計數(shù)器加 1。 增加頁面總長度。 該頁面長度所在的范圍的計數(shù)器加 1。 該文件所屬的編碼類型的計數(shù)器加 1。 將該頁面的網(wǎng)址、標(biāo)題、引用次數(shù)寫入一個文件。 主機(jī)統(tǒng)計程序中，每從數(shù)據(jù)庫中讀取一個信息，都要進(jìn)行如下處理： 主機(jī)數(shù)計數(shù)器加 1。 找到 該主機(jī)所在的域，并將該域的計數(shù)器加 1。 用次數(shù)排行表 將所有頁面的引用次數(shù)都記錄在一個文件中后，要對該文件進(jìn)行處理，從中找出引用次數(shù)最高的 100 項。 因為數(shù)據(jù)庫中有一百多萬個頁面，所以該文件的數(shù)據(jù)量很大，必須采用高效的算法。又因為最終只要產(chǎn)生前 100 項就可以了，所以不必將文件中的數(shù)據(jù)全部排序。 北京大學(xué)學(xué)士學(xué)位論文 第 16 頁 經(jīng)過比較，我采用了下面的算法： 1 將中間文件中的前 100 項用插入排序法加入雙鏈表。 2. 讀中間文件后面的項，如果某一項的引用次數(shù)小于當(dāng)前雙鏈表中的最后一項，直接將它略去；否則，將它插入雙鏈表，并將最后一項除去， 保證雙鏈表中只有 100 項。 算法效率評估： 該算法只需要一遍掃描文件，剛開始時，雙鏈表的內(nèi)容變換比較頻繁，但處理過一些數(shù)據(jù)之后，雙鏈表中的 100 項的引用次數(shù)就會高于文件中的大多數(shù)項。這時，很多項都不需要插入雙鏈表。 在 100 項的雙鏈表中插入一項的平均比較次數(shù)是 50 次，在雙鏈表中插入和刪除一項時，并不需要移動別的項。 如果文件中有 N 項，該算法所需的比較次數(shù)遠(yuǎn)小于 50N 次。所以，該算法的時間復(fù)雜度為 O(N)，效率較高。 該算法所占用的空間僅為 100 項的雙鏈表所需的空間，空間代價也較低。 存放各主機(jī)上的頁面信息。 1 的結(jié)構(gòu)如下： 表中共有 99991 項，每一項是一個記錄，該記錄的結(jié)構(gòu)是： 內(nèi) 容 類 型 主機(jī) 址 字符串 主機(jī)上的頁面數(shù) 整數(shù) 主機(jī)上的頁面總長度 雙精度浮點(diǎn)數(shù) 各編碼類型的頁面數(shù) 整數(shù)數(shù)組 存放頁面地址鏈表中的最末項位置 整數(shù) 下一表項的指針 指針 存放頁面地址的鏈表 指針 北京大學(xué)學(xué)士學(xué)位論文 第 17 頁 2 數(shù)如下： 將 址看作以 256 為基數(shù)的整數(shù)，將它除以 99991 的余數(shù)作為散列地址。 為防止計算整數(shù)時溢出，采用如下方法： （ 1） 先計算 256 的 N 次方除以 99991 的余數(shù)，放在一個數(shù)組中。流程圖如下： （ 2） 址中的每一位，如果是數(shù)字，就把該位看作是該數(shù)字表示的數(shù)，如果是 .，就把該位看作 10。計算余數(shù)的流程如圖 示。 3 每處理一個頁面，就調(diào)用一次 數(shù)，如果該頁面所在的主機(jī)沒有被插入 ，就插入該主機(jī)的信息；否則，修改 中記錄的該主機(jī)的頁面數(shù)和頁面總長度，并把中間文件中存 放該頁面網(wǎng)址的位置加入結(jié)構(gòu)體的最后一項所表示的鏈表。 第一項 = 1 第二項 = 256 第三項 = （ 256*256） %99991 j 16 ? 第 j 項 = （第 *第 1 項） % 99991 j = j+1 j = 3 結(jié)束 no 京大學(xué)學(xué)士學(xué)位論文 第 18 頁 4 因為共要處理一百多萬個頁面，所以如果存放頁面地址鏈表中的每一項只放一個地址，就會耗盡系統(tǒng)的存儲空間。解決方法是將鏈表中的一項定義成一個數(shù)組，再用一個整數(shù)表示該鏈表的最后一項所指的數(shù)組中最后一項的位置。 計各個域內(nèi)的主機(jī)數(shù)目 每個域各有一個碼字和一個域標(biāo)號，對任何一個主機(jī)，如果某個域的碼字取反，在與該主機(jī)的 址相交，得到的是這個域的域標(biāo)號，那么該主機(jī)屬于這個域。 設(shè)數(shù)據(jù)庫內(nèi)共有 N 個主機(jī)，有 n 個域，該算法的時間代價為 O( j = 0 地址 = 0 中的第 j 位 為結(jié)束標(biāo)志 地址 =地址 +第 j 為表示的數(shù) *余數(shù)數(shù)組的 第 j 位 j = j+1 地址 =地址 % 99991 結(jié)束 no 京大學(xué)學(xué)士學(xué)位論文 第 19 頁 機(jī)情況查詢 在將 的內(nèi)容寫入結(jié)果文件時，每將一個主機(jī)的信息寫入文件，同時按照存放頁面地址的鏈表，將該主機(jī)上的所有頁面的網(wǎng)址從中間文件中找到，并拷貝到結(jié)果文件中。 這樣得到兩個文件： 在一個文件中可以查到主機(jī) 址，主機(jī)上的頁面數(shù)，主機(jī)上的頁面網(wǎng)址在另一頁面上的起始位置。在另一文件上，每個主機(jī)上的頁面都存放在一起。根據(jù)起始位置和頁面數(shù)，就可以順序讀取該主機(jī)上所有頁面的網(wǎng)址 。 用戶查詢時，可以輸入主機(jī)的 址或主機(jī)域名，程序會自動將域名轉(zhuǎn)化為 址，然后根據(jù) 址從第一個文件中找到該主機(jī)的項，再根據(jù)第一個文件中的起始位置和頁面數(shù)，從第二個文件中找到該主機(jī)上的所有頁面。 第一個文件只有幾千項，查找時間較短。第二個文件雖然有一百多萬項，但可以直接定位，順序地讀所有需要的項。所以，該算法的時間代價不高，可以滿足實(shí)時查詢的需要。 主機(jī) 起始位置 m 頁面數(shù) n m m+n 文件 1 文件 2 圖 京大學(xué)學(xué)士學(xué)位論文 第 20 頁 第五章 日志文件信息處理的實(shí)現(xiàn) 計目標(biāo) 1 統(tǒng)計總查詢次數(shù)，反映用戶的使用情況。 2 統(tǒng)計 中率，反映系統(tǒng)的 運(yùn)行效率。如果 中率過小，說明系統(tǒng)的效率需要改進(jìn)。 3 統(tǒng)計 中的查詢所需要的總時間，和從數(shù)據(jù)庫中得到查詢結(jié)果的操作所需要的總時間。用來反映 效率如何，如果需要，可以以此數(shù)據(jù)為基礎(chǔ)，變換 大小。這兩個數(shù)據(jù)也反映了系統(tǒng)的平均查詢時間，即對用戶要求的反映速度。 4 統(tǒng)計 作和 作的總次數(shù)，表明用戶操作的類型，可以幫助估計系統(tǒng)處理的關(guān)鍵操作是什么，把提高系統(tǒng)性能的關(guān)鍵放在優(yōu)化處理關(guān)鍵操作的算法上，較少出現(xiàn)的情況不必投入太多的精力。 5 統(tǒng)計最近一個月內(nèi)每天用戶查詢的次數(shù)，本年 內(nèi)每月的用戶查詢次數(shù)，去年的用戶查詢次數(shù)，和今年的用戶查詢次數(shù)。通過這組數(shù)據(jù)來反映系統(tǒng)近期內(nèi)的使用情況，以便及時了解用戶的動態(tài)，更好地滿足用戶的要求。 6 統(tǒng)計數(shù)據(jù)庫內(nèi)的詞語被查詢的次數(shù)，并按照查詢頻率的不同范圍分類，在各類內(nèi)排序。了解詞庫的使用情況。 7 自動學(xué)習(xí)新詞語，并按照詞語的出現(xiàn)頻率將詞語排序。每過一段時間，提交給系統(tǒng)管理員一份新詞表，系統(tǒng)管理員經(jīng)過篩選，可以將部分詞語加入詞庫。使得系統(tǒng)管理員可以隨時根據(jù)用戶的需求調(diào)整詞庫的內(nèi)容。 件處理 有一個日志文件編輯程序，用來處理日志文件。 首先，它先 打開一個配置文件，從該配置文件中讀取要處理的日志文件名。配置文件中可以有一個或多個日志文件名。如果有多個，就會順序處理這些文件。 打開要處理的日志文件后，一行一行地讀文件。每讀出一行，就分析該行的北京大學(xué)學(xué)士學(xué)位論文 第 21 頁 內(nèi)容。日志文件中關(guān)于一次查詢的內(nèi)容如圖 示。 6 15:27:53 1998 :367 :P : : :葡萄品種 : : :1 :126 * 圖 據(jù)每行開始的內(nèi)容，可以轉(zhuǎn)而進(jìn)行不同的處理。情況如下： 第一個詞是 行時間處理，如果進(jìn)行查詢時的時間是在本月內(nèi)，當(dāng)天的查詢次數(shù)加 1。如果是在本年內(nèi)，當(dāng)月的查詢次數(shù)加 1，并且本年的查詢次數(shù)加 1。如果是在去年，去年的查詢記錄加 1。 第一個詞是 種情況統(tǒng)計查詢次數(shù)。 前兩個詞是 行查詢內(nèi)容處理。 前兩個詞是 種情況 統(tǒng)計查詢次數(shù)。 前兩個詞是 種情況統(tǒng)計查詢所用的總時間。 第一個字符是 * 、 -，或者第一個詞是 者前兩個詞是 接處理下一行。 其他情況，進(jìn)行錯誤處理。 查詢內(nèi)容處理進(jìn)行的操作如下： 北京大學(xué)學(xué)士學(xué)位論文 第 22 頁 1 調(diào)用分詞程序，將用戶提交的查詢信息分成單個的詞。 如： “阿聯(lián)酋是一個國家” “阿 聯(lián) 酋 是 一 個 國家” 2 將分出的詞逐個加入 ，統(tǒng)計詞的出現(xiàn)頻率。 3 用另一個 進(jìn)行新詞學(xué)習(xí)。 詞學(xué)習(xí) 用戶的查詢語句中很可能會出現(xiàn)一些詞庫中沒有的詞，碰到這種情況，系統(tǒng)會調(diào)用分詞程序，將這些詞分成幾個的詞。 如： “紅樓夢” “紅 樓 夢” “信息化” “信息 化” 系統(tǒng)為檢索這樣的信息，就要進(jìn)行多次匹配，如上面的“紅樓夢”就要匹配三次，而“紅”，“樓”，“夢”等單字詞的出現(xiàn)頻率是很高的，所以這樣的查詢會需要較長的時間。如果要系統(tǒng)管理員自己人工學(xué)習(xí)這些新詞，將是一個很繁重的工作，而且系統(tǒng)管理員無法去了解 所有的領(lǐng)域，找出所有的社會熱點(diǎn)。如果系統(tǒng)能夠根據(jù)用戶的查詢信息，將這些經(jīng)常出現(xiàn)在用戶的查詢要求中，但詞庫中又沒有收錄的漢字組合整理出來，提交給系統(tǒng)管理員，系統(tǒng)管理員只要稍稍修改，就可以直接加入詞庫。這將是一種比較方便和高效的算法。新詞學(xué)習(xí)程序的任務(wù)就是發(fā)現(xiàn)這些新詞。 新詞學(xué)習(xí)程序的處理過程是： 調(diào)用分詞程序之后，用戶一次提交的查詢內(nèi)容被分為單詞，如： “阿聯(lián)酋是一個國家” “阿 聯(lián) 酋 是 一 個 國家” 從第一個單 詞開始，將詞的組合插入 ，直到組合的長度大于 8 為止。 如上例中，得到： 阿聯(lián)、阿聯(lián)酋、阿聯(lián)酋是、阿聯(lián)酋是一、阿聯(lián)酋是一個、阿聯(lián)酋是一個國家 很明顯，這樣得到的組合中，很多都是不可能作為一個詞的， 如： 阿聯(lián)酋是、阿聯(lián)酋是一、阿聯(lián)酋是一個、阿聯(lián)酋是一個國家 我們可以作這樣的改進(jìn)?！笆恰?，“的”，“了”等詞在句子中出現(xiàn)時，大多北京大學(xué)學(xué)士學(xué)位論文 第 23 頁 數(shù)情況下，并不會與其它的字組成詞，而是用來連接別的詞。所以，我們可以在碰到這些詞的時候，就停止處理。 在系統(tǒng)中有一個禁用 詞文件，所有該文件中的詞，在分詞后都有一個特殊的返回碼。我們可以簡單地通過返回碼來判斷是否停止處理。 經(jīng)過這樣的改進(jìn)之后，“ 阿聯(lián)酋是”、“阿聯(lián)酋是一”、“阿聯(lián)酋是一個”、 “阿聯(lián)酋是一個國家”，就不會被插入 了。 然后，再從第二個詞開始尋找組合，以此類推。 因為用戶提交的查詢一般都不會太長，所以該算法的時間代價不會超過 O（ N）。 在處理完日志文件后，所有的新詞組合都被插入 。把這些新詞從寫到一個文件中，寫入時，將出現(xiàn)頻率太低的組合都舍去