【畢業(yè)學(xué)位論文】（Word原稿）一種可擴展的高效鏈接提取模型的實現(xiàn)和驗證-計算機科學(xué)技術(shù)

北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 教師指導(dǎo)意見： 鏈接提取是網(wǎng)頁搜集系統(tǒng)中的一個重要組成部分。蘇杭同學(xué)的畢業(yè)論文工作，是對這一部分的突出貢獻。 論文所涉及的工作包含了對搜索引擎技術(shù)的一般認識。鏈接提取模塊以“容錯性”，“正確性”，“全面性”，“高效性”和“可擴展性”為設(shè)計目標，在充分認識到傳統(tǒng)的鏈接提取方法不足的基礎(chǔ)上，提出新的設(shè)計思路，并且實現(xiàn)。該模塊包括信息提取，信息加工，信息分析和信息存儲四個過程。并成功的運用于“天網(wǎng)”搜索引擎。論文內(nèi)容豐富，所涉及的工作量大，且有較強的系統(tǒng)性，是一篇很有價值的論文。 在畢業(yè)設(shè)計工作的過程中，蘇 杭同學(xué)態(tài)度端正，積極努力，精力集中，表現(xiàn)出很強的進取精神和踏實的工作作風(fēng)，為“天網(wǎng)”的發(fā)展做出了貢獻。 指導(dǎo)教師：閆宏飛 2003年 6月 18日 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 摘要 隨著 來越廣泛的發(fā)展與應(yīng)用，搜索引擎已經(jīng)成為人們從中查找信息的重要工具；在搜索引擎的系統(tǒng)實現(xiàn)中，如何通過鏈接提取發(fā)現(xiàn)更多更廣的 本文總結(jié)了設(shè)計鏈接提取模塊所要求的“容錯性”、“正確性”、“全面性”、“高效性”和“可擴展性”等五個目標，并從這些角度去分析傳統(tǒng)的鏈接提 取方法的不足，并作為改進，提出了一種新的設(shè)計思路。 本文將鏈接提取的過程劃分為信息提取，信息加工，信息分析以及信息儲存四個過程來進行研究。信息的獲取通過 法分析方法從文檔中得到初始據(jù)；信息加工階段通過運用 后在信息分析過程中進一步地篩選與過濾；最后將結(jié)果存儲在一個雙鏈表結(jié)構(gòu)中。 基于上述方法，本文實現(xiàn)了一個新的鏈接提取模型，并將該模型運用于北京大學(xué)天網(wǎng) 索引擎；在獲得足夠的實驗數(shù)據(jù)之后，全面的比 較了這種新的鏈接提取模式與傳統(tǒng)方法在各項指標上的優(yōu)劣。結(jié)果表明該模型有明顯的優(yōu)勢。 關(guān)鍵字：搜索引擎，鏈接提取，統(tǒng)一資源地址 ( 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 s eb is an to on to in a to RL is a in RL of a is is NF is in in is in a On a RL WW to is in 杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 正文目錄 1 研究背景 . 6 2 系統(tǒng)目標 . 7 3 傳統(tǒng)方法 . 9 4 系統(tǒng)實現(xiàn) . 10 計模型概述 . 10 息獲取 . 11 . 11 . 13 設(shè)計 . 15 息加工 . 18 符串規(guī)整 . 18 析 (. 18 相對 . 20 息分析 . 22 確性驗證 (. 23 選器 (. 23 價性判斷 (. 24 息儲存 . 25 5 性能評測 . 26 6 實驗結(jié)果 . 28 7 不足與改進 . 29 附錄 A 錯誤鏈接舉例 . 31 附錄 B . 32 附錄 C 通用的 . 33 參考文獻 . 34 致謝 . 35 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 圖表目錄 圖 1(將要的搜索引擎工作原理示意圖 ). 7 圖 2(舊系統(tǒng)進行鏈接提取的原理模型 ) . 9 圖 3(新的設(shè)計思想的工作原理模型 ) . 4( . 5( . 6(遞歸式過濾注釋嵌 套的方法流程圖 ) . 7(雙鏈表存儲結(jié)構(gòu)示意圖 ) .京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 6頁 1 研究背景 因特網(wǎng) (從誕生開始就以驚人的速度蓬勃地發(fā)展著。當(dāng)今，因特網(wǎng)上的網(wǎng)站數(shù)目不斷的增加，網(wǎng)站之間的鏈接關(guān)系越來越復(fù)雜，所容納的信息量也以指數(shù)爆炸 式地增長著。據(jù)統(tǒng)計，現(xiàn)在 1，每年的增長率突破三千萬 1。如此巨大的信息量和增長速度使得從 了解決這一困難，搜索引擎在 20 世紀 90年代初期應(yīng)運而生。 當(dāng)今最流行的 索引擎，以著名的 們通過網(wǎng)頁搜集系統(tǒng)從 獲取網(wǎng)頁資源，然后將其中的信息索引入庫，并在用戶需要時提供與他們希望查找的內(nèi)容相關(guān)的網(wǎng)頁資源列表。 搜索引擎 由網(wǎng)頁搜集系統(tǒng) ( 索引器 (鏈接提取模塊 (個重要部分組成。其中的鏈接提取模塊，也是本文最為關(guān)心的部分，負責(zé)從網(wǎng)頁資源中提取新的鏈接信息。它的設(shè)計將直接影響整個搜索引擎的效率： 它識別網(wǎng)頁中所包含鏈接的能力會影響搜索引擎的信息覆蓋范圍 2，因為所有網(wǎng)頁資源的鏈接都是通過它分析得到的。如果分析能力有限，則會有相當(dāng)一部分有用信息未被搜索引擎所函蓋，從而降低了其實用性。 它對鏈接識別的準確性將影響搜索引擎的效率。如果它不能準確地判斷網(wǎng)頁中的鏈接信息，而將錯誤的鏈接傳給網(wǎng)頁搜集系統(tǒng)， 會使其在等待錯誤結(jié)果 中浪費大量寶貴的時間，從而大大降低日訪問量。 它本身對鏈接提取的算法代價不能太高，否則會引起搜索引擎的效率瓶頸。 由此可見設(shè)計一個好的鏈接提取模塊的重要性。本文基于上述目的提出一種新的鏈接提取模塊的設(shè)計思想與設(shè)計原理，并將其應(yīng)用于北大天網(wǎng)系統(tǒng) (北京大學(xué)計算機系網(wǎng)絡(luò)與分布式系統(tǒng)實驗室開發(fā)的 索引擎 3)并通過評測證明該模塊是高效的。 準確的數(shù)字為 17,638,2971 2003 這里的搜索引擎指的都是索引式 (索引擎，下同。 錯誤的鏈接往往會使網(wǎng)頁搜集系統(tǒng)得到連接超時的錯誤或者 404錯誤，在等待中浪費很多時間。 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 7頁 2 系統(tǒng)目標 因特網(wǎng)中不同網(wǎng)頁通過超文本鏈接協(xié)議 (相鏈接的結(jié)構(gòu)構(gòu)成一個有向 圖，其中以每個網(wǎng)頁為頂點，網(wǎng)頁之間的鏈接關(guān)系為有向邊。網(wǎng)頁搜集系統(tǒng)從其中一個頂點出發(fā)在圖中進行遍歷，每到達一個新的頂點便會將對應(yīng)網(wǎng)頁的內(nèi)容抓取下來，并通過鏈接提取模塊找到其中包含的新鏈接并提供給網(wǎng)頁搜集系統(tǒng)。網(wǎng)頁搜集系統(tǒng)便可以沿新的有向邊繼續(xù)上述的遍歷過程了。整個過程可以是完全自動化的 (只要提供一個起始的頂點，網(wǎng)頁搜集系統(tǒng)就可以通過不斷獲取新鏈接自動地在因特網(wǎng)中進行遍歷 )，然后索引器將搜集到的資源信息進行索引并存入數(shù)據(jù)庫以備今后查詢使用。 上述過程可以用下面的示意圖來表示： 圖 1中簡要說明了搜索引擎的工 作原理及其各部分間的關(guān)系。從圖中鏈接提取模塊的輸出將直接做為網(wǎng)頁搜集系統(tǒng)的輸入，因此，它對網(wǎng)頁搜集工作的效率與質(zhì)量起著決定性的作用；另外，它的輸出結(jié)果對索引器也有著間接影響，如果網(wǎng)頁中的許多無用鏈接 (如廣告等 )被提取了出來，則索引器也會將這些“噪音”網(wǎng)頁索引入庫，從而降低了數(shù)據(jù)庫中信息的質(zhì)量。 基于上述分析，本文歸納和總結(jié)了設(shè)計鏈接提取模塊的基本原則與目標： “容錯性 (：必須保證在任何情況下不能出現(xiàn)諸如內(nèi)存溢出，內(nèi)存泄露，非法指針，死循環(huán)，或者其他沒有處理的異常錯誤。在網(wǎng)頁搜集系統(tǒng)自 動對因特網(wǎng)進行遍歷并索引網(wǎng)頁時，程序可能會連續(xù)運轉(zhuǎn)幾天甚至幾個星期不停。如果某個模塊在此期間出現(xiàn)了上述的錯誤，可能會導(dǎo)致整個作業(yè)崩潰，甚至當(dāng)機的慘重后果。因此，極好的容錯性是必須的，也是最基本的要求 “正確性 (：要保證提取出來的鏈接都是正確可用的。這并不是說在鏈接提取的過程中就能夠判斷每個鏈接都是可以連接到北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 8頁 主機的，這里的“正確”指的是格式上的正確，即要能夠?qū)⒉粷M足格式要求的錯誤鏈接識別出來并過濾掉。錯誤的鏈接可能是網(wǎng)頁制作時不經(jīng)意的打字錯誤或是使用了無法識別的字符導(dǎo)致的，在附錄 舉了許多常見的錯誤鏈接示例。正確性的優(yōu)劣將直接影響到網(wǎng)頁搜集系統(tǒng)的工作效率。 “全面性 (：鏈接提取模塊要盡可能多地將網(wǎng)頁中所包含的各種鏈接信息提取出來。網(wǎng)頁中包含鏈接信息的形式可能是多樣的，鏈接信息可能出現(xiàn)十分明顯的標志中 (如 )，還可能隱藏在其他信息里，甚至腳本中。因此，模塊必須能準確發(fā)現(xiàn)以各種形式出現(xiàn)的鏈接信息。有些鏈接信息可能是搜索引擎不需要的 (比如圖片鏈接、程序鏈接等 )，但模塊也應(yīng)該能找到它們，為今后系統(tǒng)需求的擴展做準備。全面性的優(yōu)劣直接影響搜索引擎的信息覆蓋率 2。 “高效性 (：鏈接提取算法的時間代價不能太高。圖1中描述的搜索引擎的整體工作的大部分時間花在了網(wǎng)絡(luò)延遲上，也就是等待網(wǎng)頁搜集系統(tǒng)將網(wǎng)頁的內(nèi)容從因特網(wǎng)中抓取下來的時間。其他模塊所消耗的系統(tǒng)時間都是很小的。如果由于算法設(shè)計的不好使得其時間代價過高 (比如超過 O(規(guī)模 )，則鏈接提取的過程就會消耗過多的系統(tǒng)時間，甚至超過了網(wǎng)絡(luò)延遲的時間。這同樣會降低系統(tǒng)對因特網(wǎng)的日訪問量，降低效率。 “可擴展性 (：在設(shè)計的時候應(yīng)該為今后的功能擴充留有余地，這主要 體現(xiàn)在： 可以根據(jù)系統(tǒng)的不同需求得到網(wǎng)頁中不同形式的鏈接資源。比如，可以只提取圖片鏈接，或者只提取 針對新產(chǎn)生的網(wǎng)絡(luò)協(xié)議能夠在不對源程序做大改動的前提下方便地增加對新協(xié)議鏈接資源的支持。 可以適應(yīng)新版本 果新版本的 可以在不對源程序做大改動的前提下實現(xiàn)對這些新形式的識別并從中提取出鏈接信息。 然而，上述這些原則有時很難同時滿足，比如“正確性”和“全面性”本身就存在著某種內(nèi)在的矛盾。有時為了保證“正確性”就不得不放 棄某些“危險的”鏈接，而采取某種相對保守的標準，這樣勢必會丟失一些鏈接信息。例如 圖對腳本程序中隱藏的鏈接信息進行提取就是一種危險的行為。在這種“正確性”與“全面性”相沖突的情況下，“正確性”應(yīng)該優(yōu)先得到滿足。只有這樣，才能使整個搜索引擎高效率無故障地高速運行。 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 9頁 3 傳統(tǒng)方法 傳統(tǒng)的鏈接提取方法中最具代表性的，也是北京大學(xué)天網(wǎng) 3原先所使用的方法，是在網(wǎng)頁中匹配 ”關(guān)鍵字，然后將它們后面的鏈接信息提取出來。這樣做的原理是，在 部分的鏈接 信息都包含在少數(shù)幾種元素 (，比如 , , , 等，而且這些元素基本都是以 ”屬性值來容納鏈接信息的。 下圖中簡要說明了傳統(tǒng)鏈接提取方法的工作流程。 根據(jù)圖 2中的流程，鏈接提取模塊會在網(wǎng)頁中尋找所有出現(xiàn)的 ” ”鍵字，然后將其后的屬性值提取出來作為鏈接信息進行加工。加工的工作主要包括將相對 換為對應(yīng)的絕對 將不滿足系統(tǒng)要求和有重復(fù)的鏈接信 息過濾掉。最后將得到的結(jié)果儲存到一個單鏈表結(jié)構(gòu)中供網(wǎng)頁搜集系統(tǒng)查詢。 從圖中可以很明顯的看出，傳統(tǒng)方法對上一章中提到的幾個目標的實現(xiàn)都存在很大的差距，具體表現(xiàn)為： “正確性”方面：如果所匹配到的諸如 ”關(guān)鍵字不是在是在網(wǎng)頁的正文文字中被提及，或者在注釋中出現(xiàn)，提取出來的就會是錯誤的結(jié)果。 “全面性”方面：很多鏈接信息并不是對少數(shù)關(guān)鍵字的簡單匹配就能夠找到的。比如 ： 。在上例中 ， ”屬性值 ”義這個 元素中包含有重定向的鏈接信息 ， 并在 ”性值里具體給出這個 因此，傳統(tǒng)的方法可能會漏掉大量重要的信息。 “可擴展性”方面：傳統(tǒng)方法很難通過對關(guān)鍵字數(shù)量的擴充來彌補其“全面性”方面的不足。上述 的例子就很好地說明了這一點： ”性取不同的值，后面 ”性值就對應(yīng)北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 10頁 了 不 同 的 含 義 ， 只 有 ”取值為 ”， ”才包含有鏈接信息。所以簡單對關(guān)鍵字進行匹配是無法適應(yīng)這些復(fù)雜情況的。 從上面的分析可以看出，傳統(tǒng)的鏈接提取方法存在著明顯的不足，會嚴重影響整個搜索引擎的質(zhì)量與效率。通過分析也可以看到，圖 2中所闡述的傳統(tǒng)方法的模型本身是存在嚴重缺陷的，根據(jù)這個模型設(shè)計出來的鏈接提取模塊有上述的不足也就在所難免了。因此，要想消除這些問題，就需要在方法模型的層次上重新設(shè)計出一種更加合理的架構(gòu)。 4 系統(tǒng)實現(xiàn) 計模型概述 為了實現(xiàn)一種更加合理與高效的鏈接 提取方法，本文將整個鏈接提取與鏈接分析的過程劃分為四個階段：信息獲取，信息加工，信息分析與信息儲存。 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 11 頁 圖 3中說明了本文提出的可擴展的高效的鏈接提取方法的工作原理，并將全部步驟劃分為上述的四個階段。這四個階段描述了鏈接提取過程中為了實現(xiàn)第二章提出的設(shè)計目標所必須進行的步驟。這四個階段中，前者是后者的條件，后者是對前者的補充，它們?nèi)币徊豢?，并最終將所有滿足條件的鏈接信息提取出來，將不滿足條件的結(jié)果過濾掉。它們對信息加工和處理的層次不斷深入，循序漸進地將提取出來的初始數(shù)據(jù) (范化 (符合 對其進行篩選和過濾，并最終得到正確且有用的結(jié)果，從而提高了鏈接提取模塊的質(zhì)量與搜索引擎的效率。 下面分別就上述四個階段進行剖析與說明。 息獲取 為了能夠更好地對 多、更準確的提取其中的有用信息，不能僅僅將網(wǎng)頁的內(nèi)容看做是簡單的線性文本 (言是符合 4規(guī)范的，因此它是具有自己的文法特征 與文檔結(jié)構(gòu)的。一個標準的 成，在元素間可以存放文本正文 (不同的元素在文檔中有著不同的功能。每個元素都是用 ”括起來的實體(其中以元素名開頭，后面接若干屬性 (不同元素中允許出現(xiàn)的屬性種類也互不相同。有的屬性名后面可以用 ”=”接屬性值，有的屬性則沒有屬性值 (如 無值屬性 )。屬性值可以用雙引號括起 (在值中允許存在單引號 )，可以用單引號括起 (在值中允許存在雙引號 )，也可以不被 引號括起來 (這樣的屬性值中不能有任何種類的引號或空白字符出現(xiàn) )。下面是一個正確的示例： 中， ”a”是元素名， ” ”a”的屬性名， ” ”屬性值， ”文本正文， /a是與 對應(yīng)的結(jié)束標簽 ( 又由于 與網(wǎng)頁相關(guān)的信息 (也包括鏈接信息 )都是作為屬性值出現(xiàn)在不同元素中的 (比如 中的 ，所以可以根據(jù) 取出所有與鏈接信息有關(guān)的屬性 (值 )。 下面是 這個表達式旨在描述提取 值 )的方法。它并不涉及 比如，有些元素必須具有結(jié)束標簽，或者對元素在文檔中出現(xiàn)位置的限制等 )，因為這些文檔結(jié)構(gòu)方面的規(guī)定不能提供有關(guān)鏈接的更多信息。 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 12頁 = *( ) = = “” = “” = *(“=” *( = = *( *( “” *(“” *( = 1*(終結(jié)符的定義： = “ “ | “t” | “n” | “r” “ “n” “” - “” - “” = = “A” | “B” | | “Z” = “a” | “b” | | “z” := 文檔所用字符集 (所有字符的集合 利用上述文法對 頁進行文法分析的工作可以安排給一個單獨的模塊來完成。這個模塊負責(zé)網(wǎng)頁的分析和對其中所有元素及其屬性的提取，并通過向使用者提供接口的方式將這些提取出來的信息反饋給調(diào)用者。因此，可以把這個模塊看做是一個封裝好的 很明顯，上面描述的文法是標準的正則文法 (56，因此可以通過構(gòu)造的方法有窮自動機 (56對其進行分析。 字符串常量被 ”括起； *表示后面的內(nèi)容重復(fù) )；可選項用 括起。 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 13頁 圖 4中完整描述了 值 )的流程。圖中聲明了三個接口，分別用于向調(diào)用者返回網(wǎng)頁中下一個元素的元素名，其屬性名與屬性值。圖 4中的流程圖其實就相當(dāng)于一個有窮自動機的簡化形式，并通過它實現(xiàn)了對前面正則文法的解析。 下面簡要的對圖 4中的工作過程進行說明。圖中左半部分是尋找 (一個元素的結(jié)束標志 )，則說明該元素中沒有聲明屬性，于是直接跳轉(zhuǎn)到最開始，繼續(xù)查找下一個元素；否則，說明有屬性聲明，于是轉(zhuǎn)到圖 4右半部分，開始分析屬性名和屬性值。 如果屬性名后面沒有 =，則說明這個屬性是無值屬性 (類似屬性 )；否則，對 =后面的屬性值進行提取。屬性值可能是被雙引號 (”)或單引號 ()括起來的，也可能沒有被引號括起來，于是分三種情況分別進行提取。得到屬性值之后同樣要判斷后面是否出現(xiàn)元素的結(jié)束標志 ， 如果不是，則說明還有下一個屬性要處理，于是重復(fù)上面的操作，直到處理完所有的屬性。在整個過程中，應(yīng)當(dāng)加入適當(dāng)?shù)漠惓Ｌ幚怼１热?，對屬性值的引號不配對，元素名過長等異常情況進行捕獲，以保證“容錯性”要求。 而，這些信息當(dāng)中的大部分都與鏈接信息沒有關(guān)系。因此，要對 杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 14頁 文法分析引擎提取的信息進行有選擇地處理。為了解決這個問題，我們引入 有些像現(xiàn)在廣 泛提到的插件 (它“插手”某個系統(tǒng)的處理過程，并進行額外的處理工作，從而對系統(tǒng)的功能進行了擴充或修正。 我們引用 它們掛接在 獲提取出來的信息并進行額外的加工分析。每個 圖為 每當(dāng)分析引擎找到了下一個 就會將結(jié)果通過接口傳遞給所有的 些 后，返回分析引擎繼續(xù)查找下一個元素。如此循環(huán)。 每個 定規(guī)則工作。它必須判斷當(dāng)前傳遞進來的是否是它要處理的特定元素。如果是，那么這個后從中獲得有用的信息并進行加工處理。 然后，這個 統(tǒng)會調(diào)用下一個 也會做和上面類似的工作。 圖 5中的示例中注冊了 3個 個 如，圖 5中，它們處理了 ,三種元素，并從這些元素的“ ”性值中析取 從前面的分析可以看出，這種 這種設(shè)計體現(xiàn)了很好的模塊化設(shè)計思想：分析引擎被設(shè)計成一個獨立封裝的完整模塊，每個 們通過接口彼此傳遞信息并相互調(diào)用。這樣做使得每個模塊都可以單獨的進行調(diào)試與擴充而不影響其他模塊，而且它們可以像搭積木一樣隨意地進行拼接。 對“全面性”目標的實現(xiàn)：通過 以將網(wǎng)頁中所有元素所包含的信息沒有疏漏地提取出來而不會漏掉任何有用的信息。 對“可擴展性”目標的實現(xiàn)：很好的模塊化設(shè)計使得每個模塊的改 進都變得很容易。而且通過掛接新的 足新的系統(tǒng)需求，而不用大量修改原有代碼。 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 15頁 設(shè)計 謂的有用信息狹義地講就是指包含 面詳細討論了這些信息在 的出現(xiàn)形式與提取方法。 包含 根據(jù)歸納，一個 息所在的屬性名 備注 a ”性的值也應(yīng)該被提取出來用以指示鏈接目標的字符集及其使用的語言。 素用于重新聲明當(dāng)前網(wǎng)頁的基地址 ( 架目標 嵌框架目標 定 的信息不會被瀏覽器顯示，但它提供了與當(dāng)前網(wǎng)頁相關(guān)的若干重要線索。 性的值為 ”才有效 ) 才包含鏈接信息。 ;字符的后面 (前面是表間隔時間的數(shù)字 )。 許多網(wǎng)頁都只聲明了這樣一個 元素，使得瀏覽這樣的網(wǎng)頁時瀏覽器會自動重定向到其中包含的 應(yīng)該為上表中的每種情況設(shè)計單獨的 而很全面對 此外，利用前面提到的 可以提取文檔中其他的重要信息 (廣義上的有用信息還包括對索引器索引該網(wǎng)頁有幫助的信息 )。這 些重要信息包括文檔的標題 (重要的 網(wǎng)頁所使用的字符集 (語言 (等。附錄 對注釋的處理 作為一種特殊的 釋 ()中的內(nèi)容是必須被忽略的，即使其中包含大量的 有可能是已經(jīng)過期的無用信息。因此，北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 16頁 必須增加一個 之所以使用 注釋過濾掉而不是簡單的將它忽略 (沒有定義專門的理它就相當(dāng)于將它忽略 )， 是由于注釋在文法上的特殊性：在它的開始標志 (”)之間可以存在任意多的 字符，如果不進行特殊處理，分析引擎會將這樣的 判斷為注釋元素的結(jié)束標志，導(dǎo)致分析的錯誤。因此必須設(shè)計一個 另一個值得注意的地方是，注釋是允許嵌套的，不能只是簡單地找到第一個出現(xiàn)的 ”就把它認為是整個注釋的結(jié)束標志。 圖 6中給出了遞歸處理的示意圖。 對腳本程序的處理 與注釋十分類似的還有一個元素，那就是 元素。在 與中間包含著腳本程序，腳本程序可以由不同的腳本語言書寫。它的特殊性在于，在腳本程序中可能隱藏有 息，甚至有些網(wǎng)頁完全由腳本程序生成，其中的鏈接信息也就都包含在腳本程序當(dāng)中了。因此，為了滿足“全面性”的要求，應(yīng)該對腳本程序進行分析，提取出其中隱藏著的 然而，對腳本程序的分析是極其危險的行為，而且論分析程序?qū)懙亩嗝磸?fù)雜，許多隱藏在腳本中的 最為理想的分析程序通過模擬腳本的解釋程序來分析腳本中的相關(guān)信息。然而分析程序與腳本的解釋程序有著本質(zhì)的區(qū)別。 在瀏覽器中，腳本存在著一個運行時環(huán)境 (我們稱其為瀏覽器環(huán)境，這個環(huán)境為腳本的運行提供了必不可少的動態(tài)支持。比如，在動態(tài)網(wǎng)頁 (，腳本可以以變量的形式引用 某些控件的值 (編輯框，復(fù)選框等 )，并使這些變量的值參與計算，得到動態(tài)的結(jié)果進行輸出。這個“動態(tài)”的概念在整個過程中就顯得尤為重要，瀏覽器環(huán)境為北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 17頁 腳本引用這些控件的值提供了支持，于是腳本的解釋程序可以根據(jù)用戶輸入的不同數(shù)據(jù)得到不同的 動態(tài)結(jié)果。 然而，分析程序無法提供上述的環(huán)境。分析程序的輸入是“靜態(tài)”的腳本，分析程序可以對它進行模擬并對其行為作出分析，然而，當(dāng)腳本引用運行時環(huán)境(即瀏覽器環(huán)境 )的動態(tài)數(shù)據(jù)時，分析程序是無法得到動態(tài)結(jié)果的，因為用戶的輸入等動態(tài)信息是不可得的。 因此，無論分析程序設(shè)計得再復(fù)雜再完善，它處理腳本程序?qū)討B(tài)數(shù)據(jù)的引用時就變得一籌莫展。事實證明，在腳本中包含的 如， ”+其中的據(jù)。這樣的情況下，分析程序是無法得知 通過上述分析可以看出，腳本程序中的鏈接信息是無法被 100%地提取出來的，而且在提取的過程中存在著很大的風(fēng)險。如果分析程序做得不夠復(fù)雜與完善，則提取出來的鏈接很有可能是錯誤的。比如上面的例子，很有可能就將鏈接的內(nèi)容提取成了 ”+而這種錯誤恰恰是天網(wǎng)系統(tǒng)中原先使用的鏈接提取模塊所常犯的。這嚴重違反了“正確性”的設(shè)計目標。因此，寧愿跳過腳本程序的分析，也不應(yīng)從中提取出大量的錯誤 鏈接來影響效率。 下面是一組測試，從測試結(jié)果可以看出腳本程序中上述形式的動態(tài)鏈接所占比例之大，以及忽略腳本程序?qū)Α叭嫘浴痹瓌t的損失之小。 測試的數(shù)據(jù)是從天網(wǎng)系統(tǒng)的鏈接數(shù)據(jù)庫中隨機抽樣選取的，測試的結(jié)果是手工統(tǒng)計分析的，并列在下表中： 參加統(tǒng)計的 腳本程序總數(shù) 其中包含的正確有用的錯誤的 沒有價值的232 452 234( 126( 92( 表 1：網(wǎng)頁中腳本程序所包含的 統(tǒng)計 表 1中所謂 “錯誤的 的是與前面例子中類似的通過動態(tài)數(shù)據(jù)計算求得的 沒有價值的 的是一些對索引器 (有價值的者某些彈出小窗口的廣告鏈接。 從測試結(jié)果可以看出，腳本程序中存在相當(dāng)大比例的“危險”的。根據(jù)前面的證明，是無法得到這些 1中的數(shù)據(jù)還說明即使能夠大量準確地提取出腳本程序中包含的正確的鏈接信息，這些正確的鏈接中還會有 28%(92/(234+92)28%)左右是無用的。 由此可以得出結(jié)論，腳本程序中所包含的鏈接有相當(dāng)大的比例是無法提取 這些 的數(shù)目統(tǒng)計中沒有包括那些引用外部腳本文件 (比如 的情況。 北京大學(xué)計算機科學(xué)技術(shù)系蘇杭學(xué)士論文 一種可擴展的高效鏈接提取模型的實現(xiàn)與驗證 第 18頁 的，而且可以提取的鏈接中也有很大一部分是廣告等無意義的鏈接。再根據(jù)第二章中對各個設(shè)計目標的分析，我們采用一種折中的方案，就是完全不對腳本程序進行分析處理。這樣做對“全面性”原則的損失 (從上面的測試結(jié)果可以看出 )是很小的，而且保證了“正確性”。 息加工 通過 而這些信息還是格式極不規(guī)整的初始數(shù)據(jù) (下面，通過“信息加工”的幾個步驟將這些初始 數(shù)據(jù)規(guī)范化 (這些步驟包括： 相對 在進行 兩個步驟之前必須先將得到的 保證在后續(xù)加工過程中的正確性。 規(guī)整的過程包括如下兩個部分： 字符串的首尾可