【計算機專業(yè)畢業(yè)論文】大規(guī)模網(wǎng)頁模塊識別與信息提取系統(tǒng)設計與實現(xiàn)

《【計算機專業(yè)畢業(yè)論文】大規(guī)模網(wǎng)頁模塊識別與信息提取系統(tǒng)設計與實現(xiàn)》由會員分享，可在線閱讀，更多相關《【計算機專業(yè)畢業(yè)論文】大規(guī)模網(wǎng)頁模塊識別與信息提取系統(tǒng)設計與實現(xiàn)（43頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1、 本科生畢業(yè)論文 題目：(中文) 大規(guī)模網(wǎng)頁模塊識別與信息提取 系統(tǒng)設計與實現(xiàn) (英文) Design and Implementation of Large Scale Web Template Detection and Information Extraction System 姓 名： 學 號： 院 系：計算機 專 業(yè)：搜索引擎與互聯(lián)網(wǎng)信息挖掘 指導教師： 41

2、 摘要 本文在已有的基于Dom-Tree和啟發(fā)式規(guī)則的網(wǎng)頁信息提取算法的基礎上，通過為所有符合W3C規(guī)范的Html標簽分類，逐個分析各Html標簽所包含的語義信息，細化規(guī)則設置，實現(xiàn)了一種自底向上的無信息遺漏的網(wǎng)頁分塊算法，并在此基礎上，利用統(tǒng)計方法得到詳細的概率分布數(shù)據(jù)，實現(xiàn)了文本相似度比較和Bayes后驗概率估計兩種網(wǎng)頁主題內容信息塊識別算法，并將其求交，提高了主題內容信息塊的識別精確度。 上述算法已集成到天網(wǎng)搜索引擎平臺的網(wǎng)頁預處理模塊中，并且在SEWM 2008會議中，以這套算法為框架，組織了主題型網(wǎng)頁識別和網(wǎng)頁主題內容信息塊提取兩個中文Web信息檢索評測項目。在這套算法的基礎上

3、，基于天網(wǎng)文件系統(tǒng)與Map-Reduce計算平臺，實現(xiàn)了分布式的網(wǎng)頁塊級別PageRank算法，命名為QuarkRank算法。實際檢驗表明，該套算法具有很好的適應性與可擴展性，并達到了很高的精度和召回率。 關鍵詞：網(wǎng)頁分塊 信息提取 SEWM 評測 PageRank Abstract This paper has been based on the Dom-Tree and heuristic rules of the Web information extraction method, by classifying all the Html tags in line with

4、W3C standards, and by analyzing semantic information contained in the Html tags one by one, it refines the rules set and achieves a bottom-up page block algorithm without information missing. On this basis, with the probability distribution of data getting from statistical methods, this paper

5、realizes two algorithms of information block recognition, one is text similarity comparison and the other is Bayes posterior probability estimates, and the final result comes from their intersection, which improves the accuracy of information theme block recognition. These algorithms have been in

6、tegrated into the page pretreatment module of TianWang search engine platform, and in SEWM 2008 meeting, using these algorithms, we organized two Chinese Web Information Retrieval Evaluation Project, Which two are theme-based Web page identification and block extraction of the information theme con

7、tent. In this method, based on TianWang file system and the Map-Reduce computing platform, this paper reports the distributed block-level PageRank algorithm, named QuarkRank algorithm here. The actual test showed that these algorithms are good at adaptability and scalability, and reach a very hig

8、h precision and recall. Keywords: Web-Page Blocking, SEWM, Information Extraction, Evaluation , PageRank 目錄 第 1 章 序言 3 第 2 章 相關研究工作 5 2.1 基于語義的網(wǎng)頁信息提取算法 5 2.2 基于視覺的網(wǎng)頁分塊算法 6 2.3 Block Level PageRank算法 8 2.3.1 Block Level Web Graph 8 2.3.2 Block Level PageRank 10 第 3 章 天網(wǎng)搜索引擎Quark模塊 11

9、 3.1 網(wǎng)頁分塊算法 13 3.2 網(wǎng)頁主題內容提取 16 3.3 算法效果演示 18 第 4 章 SEWM2008中文Web信息檢索評測 23 4.1 評測任務介紹 23 4.1.1 主題型網(wǎng)頁發(fā)現(xiàn)任務 23 4.1.2 網(wǎng)頁內容信息發(fā)現(xiàn)任務 24 4.2 評測格式 25 4.3 評測結果 25 4.3.1 主題型網(wǎng)頁發(fā)現(xiàn)任務評測結果 26 4.3.2 網(wǎng)頁內容信息發(fā)現(xiàn)任務評測結果 28 4.4 評測綜述 31 第 5 章 網(wǎng)頁分塊的分布式應用 32 5.1 QuarkRank 32 5.2 其他應用 34 第 6 章 總結與展望 35 6.1 總結 35

10、 6.2 展望 36 第 1 章 序言 信息時代，非Web無以制勝?；ヂ?lián)網(wǎng)的高速發(fā)展，改變了我們的生活方式，打破了我們的時空界限，重塑著我們的社會形態(tài)。經(jīng)濟、政治、學習、工作、生活、娛樂等等各個層面都在Web網(wǎng)絡中激蕩起伏，深刻地影響著人類的未來。而Web網(wǎng)絡的靈魂，就是流動在其中的無窮無盡的信息。Web2.0的意義就在于 網(wǎng)絡內容的提供方從商人和專業(yè)人員轉變?yōu)榫W(wǎng)絡上的每一個普通用戶，從而幾何級數(shù)地增長了Web的信息量。然而信息量的增大，隨著而來的就是存儲成本的增大和信息提取難度的增大，如何有效的獲取和整合Web信息成為大家面對的共同課題。 傳統(tǒng)意義上，整個Web

11、網(wǎng)絡就是由無數(shù)的Web頁面而構成，它們是網(wǎng)絡信息存儲和提取的基本單位，獲取了這些Web頁面就相當于獲取了Web信息內容。但是把整個頁面作為最基本的信息處理單位有一些不合理之處。首先是因為Web頁面中信息量的分布非常不均勻，有主題內容，也有廣告，導航欄，版權信息，裝飾信息，以及在大量網(wǎng)頁中重復出現(xiàn)的部分，它們自身的信息含量千差萬別。當網(wǎng)頁瀏覽者剛打開一個新頁面的時候，如果之前沒有瀏覽過類似頁面，就會目不暇接，眼花繚亂，有無所適從的感覺，必須仔細探尋一番才能定位到這個頁面的要害；如果之前瀏覽過類似頁面，比如常上這個網(wǎng)站，那么通常瀏覽者就已經(jīng)訓練出一種直覺或者說是條件反射，他會立刻定位到他所想要瀏覽

12、的部分，從而忽略掉頁面中的其他部分。 其次還因為現(xiàn)在很多Web頁面是動態(tài)更新的，比如博客頁面或者論壇討論帖，它們的更新是以一個一個網(wǎng)頁塊的形式進行的，更新時頁面上大部分內容并沒有變化，如果仍然以整個頁面為處理單位，則不可避免地存在效率損失和定義的混淆。這些情況促使我們反思以整個頁面為基本信息單元的做法不僅不盡合理，一定程度上甚至已經(jīng)損害了網(wǎng)絡瀏覽者的用戶體驗，妨礙了網(wǎng)絡信息提取的效率。 解決這個問題的辦法其實有兩種思路。第一種就是從信息的產(chǎn)生方那兒就不再提供網(wǎng)頁式的信息，而改為直接提供網(wǎng)頁塊或者文字段式的信息。最常見的例子就是RSS（聚合內容，Really Simple Syndi

13、cation），博客或者新聞的提供方省去了瀏覽者訪問網(wǎng)站查看更新的麻煩，直接將精簡后的網(wǎng)頁塊或者文字段發(fā)送給RSS的訂閱方。第二種則更為普適，就是細分網(wǎng)頁中的信息單元，也就是給網(wǎng)頁分塊，在網(wǎng)頁分塊的基礎上存儲和提取Web頁面的語義信息。 基于網(wǎng)頁分塊的Web頁面的語義信息提取在很多方面都有應用。比如，在常規(guī)搜索引擎中，可以以網(wǎng)頁分塊為基礎去除網(wǎng)頁中的噪音信息，識別出網(wǎng)頁中的主題內容信息塊，從而用提取出的主題內容信息來構建對這個頁面的描述，完成網(wǎng)頁分類、網(wǎng)頁消重等應用。還可以憑此改進搜索引擎的索引模塊和檢索模塊的效率，比如改進TF/IDF和PageRank的算法（詳見第五章）。 W

14、eb頁面的語義分塊另外一個重要用途在于移動終端訪問互聯(lián)網(wǎng)，比如手機和IPod等。因為目前大部分的Web頁面都是針對PC機設計的，要求有相對較大的屏幕。而移動設備通常屏幕較小，計算能力有限，無法直接訪問這些頁面。 為了解決這個問題，要么是內容提供商手工編輯專門適用于移動設備的頁面，要么就只有對頁面進行語義分割，并在分割后的頁面中選擇信息量最高的語義塊。 除此之外，Web頁面的語義分塊還可能對常規(guī)搜索引擎之外的其他信息檢索系統(tǒng)有幫助。比如類似于新聞人物追蹤和歷史新聞檢索等應用，出于節(jié)約存儲空間，提高檢索精度，方便更新等目的，可以直接存儲和操作網(wǎng)頁中的主題內容語義塊，而舍棄網(wǎng)頁中其他與系統(tǒng)需

15、求無關的語義塊。 在這篇論文中，第二章介紹了本文的相關研究工作，包括常見的網(wǎng)頁分塊和信息提取算法、基于視覺的網(wǎng)頁分塊算法，以及網(wǎng)頁分塊的一個應用Block Level PageRank算法；第三章介紹了我實現(xiàn)的網(wǎng)頁分塊和主題信息提取算法——Quark算法；第四章介紹了Quark算法在SEWM2008中文Web信息檢索評測項目中的實際檢驗；第五章介紹了在Quark算法基礎上實現(xiàn)的一個分布式QuarkRank程序。第六章是對本文的總結和工作展望。 第 2 章 相關研究工作 2.1 基于語義的網(wǎng)頁信息提取算法 由于對Web頁面有效分塊之后可以

16、極大地方便內容提取、數(shù)據(jù)挖掘、Web結構分析等各項Web信息檢索領域的相關工作，所以早有很多研究人員前赴后繼，就此展開了很多工作。其中，基于語義信息對網(wǎng)頁分塊是最簡便，也最基礎的一種方法。所謂語義信息，通常包括網(wǎng)頁中包含的HTML標簽信息，HTML DOM樹的結構信息，文字內容信息，超鏈接信息，以及其他通過統(tǒng)計或學習而得到的全局信息等等，也可以理解成為除了網(wǎng)頁中的視覺信息之外的所有可以得到的信息。 通常基于語義的網(wǎng)頁分塊算法是和后續(xù)的網(wǎng)頁主題內容提取結合在一起的，也就是在網(wǎng)頁分塊的過程中，同時完成了主題內容提取的工作，并且主要的注意點是在主題內容提取上，因此分塊算法就比較簡單，甚至不顯式

17、地分塊，在此我們統(tǒng)稱它們?yōu)榫W(wǎng)頁信息提取算法。總的來說，網(wǎng)頁信息提取算法可以分為兩類，一類屬于網(wǎng)站級別（Site-Level），一類屬于網(wǎng)頁級別（Page-Level），當然也有將兩類方法結合使用的算法。 Site-Level的算法顧名思義，就是分析一個網(wǎng)站或者網(wǎng)頁集內部的所有網(wǎng)頁，從中提取反復出現(xiàn)的模式，而一般來說，在多個網(wǎng)頁里重復出現(xiàn)的模式（可理解為Dom-Tree子樹）就是導航欄、廣告等噪音信息了，單個網(wǎng)頁中減去這些信息，剩下的就是主題信息內容。關于Site-Level的研究一直在繼續(xù)，WWW2008上就有一篇名為Web page sectioning using regex-bas

18、ed template[1]的論文使用正則表達式來提取重復模式，從而更適應網(wǎng)頁間的細微變化，增加了Site-Level的召回率。 Page-Level的算法在處理大型網(wǎng)站的網(wǎng)頁時效率常常不如Site-Level，但優(yōu)勢在于靈活，不受網(wǎng)頁類型限制。它只利用單個頁面內部的信息，當然也可能會用到一些全局信息。賓夕法尼亞州立大學2005年的論文[2]就是其中的典型。這篇論文提出簡化塊與塊之間的層次結構，直接提取一些原子塊（Atomic Block），諸如以list, table, link, object, frame, form等為根節(jié)點的html子樹，來完成分塊工作。這一方法雖然簡單而易于實

19、現(xiàn)，但依賴于事先給出的原子塊列表，同時忽略了原子塊之間的嵌套鏈接問題。在分塊之后，它也只是簡單計算了文字長度等幾個變量來決定主題信息塊。 合并Site-Level和Page-Level的方法也一直有人嘗試。WWW2007的論文Page-level template detection via isotonic smoothing[3]先利用一個Site-Level噪音模板提取器來構建訓練集，然后對所有頁面構建DOM樹，為各節(jié)點提取分類特征，比如各節(jié)點的文本向量，各節(jié)點中鏈接的平均字數(shù)，各節(jié)點中鏈接文字所占比例等，最后利用以上訓練集對測試集中每一個DOM樹節(jié)點打分，經(jīng)過等壓平滑之后，判

20、定每個DOM樹節(jié)點的類型。所以它是典型的先Site-Level，后Page-Level的方法。 2.2 基于視覺的網(wǎng)頁分塊算法 基于語義的網(wǎng)頁分塊算法具有一些無法克服的先天性局限。首先，HTML語言版本眾多，一直沒有有效統(tǒng)一，而且其語法規(guī)范很松散，一些不符合HTML規(guī)則的網(wǎng)頁也能被完全識別，所以網(wǎng)頁編寫者在制作網(wǎng)頁時相對隨意，導致Web上的很多網(wǎng)頁都沒有完全遵循W3C規(guī)范；其次，IE、Firefox等瀏覽器各自為政，對HTML標簽的識別不盡相同，IE甚至還特別為Office軟件設計了特別的html標簽以輔助顯示，這些都增加了基于規(guī)則分塊的復雜性。在實際編程中，就必須得借助一些HTML

21、規(guī)范工具如tidy等來修正DOM樹結構的錯誤，但個別中文網(wǎng)頁仍然存在無法修正的情況。而且DOM樹最早引入是為了在瀏覽器中進行布局顯示而不是進行Web頁面的語義結構描述。比如，即使DOM樹中兩個結點具有同一個父結點，那么這兩個結點在語義上也不一定就是有聯(lián)系的。反之，兩個在語義上有關系的結點卻可能分布在DOM樹的不同之處。因此僅僅通過分析DOM樹并不能完全獲取Web頁面的語義信息，所以依賴于DOM樹的啟發(fā)式規(guī)則算法存在先天不足。 而基于視覺的網(wǎng)頁分塊算法就彌補了這個不足。它的原理來自于用戶的實際觀察體驗，即用戶并不關心Web頁面的內部結構，而是使用一些視覺因素，比如背景顏色、字體顏色和大小、

22、邊框、邏輯塊和邏輯塊之間的間距等等來識別出頁面中的語義塊。因此如果充分的使用Web頁面的視覺信息，模擬人眼識別語義塊的過程，并結合DOM樹結構分析進行頁面分塊，則可以達到更好的效果。 微軟亞洲研究院在其2003年的論文VIPS: A vision based page segmentation algorithm[4]里首次提出了基于視覺的網(wǎng)頁分塊算法VIPS(Vision-based page segmentation)。VIPS算法充分利用了Web頁面的布局特征（見圖1），它有三個主要步驟：首先從DOM樹中以較小的粒度提取出所有可視標簽塊，并且給每個可視標簽塊計算出一個DOC（“一致

23、性程度”，Degree of Coherence）值來描述該塊內部內容的相關性。DOC的值越大，則表明該塊內部的內容之間的聯(lián)系越緊密，反之越松散。第二步利用每個可視標簽塊的絕對位置和相對位置信息，檢測出它們之間的所有的分割條，包括水平和垂直方向。最后基于這些分割條，利用更多的諸如顏色等視覺信息，重新構建Web頁面的語義結構。 VIPS算法的優(yōu)點十分明顯，它充分利用了網(wǎng)頁的視覺信息和結構信息，相對于傳統(tǒng)的基于規(guī)則的分塊算法來說，大大提高了分塊的精確度。但VIPS算法也有其局限性： 首先，提取網(wǎng)頁視覺信息代價很高。因為HTML語言本身并沒有包含足夠的視覺信息，所以網(wǎng)頁真正顯示出來的效果因瀏

24、覽器，因操作系統(tǒng)，甚至因硬件而異。為了得到網(wǎng)頁的完整視覺信息，必須完全下載該網(wǎng)頁所鏈接的CSS文件，JavaScript文件，圖片文件等等，然后調用瀏覽器內核代碼渲染這些網(wǎng)頁文件，最后從瀏覽器內核代碼的接口中得到每個HTML標簽的視覺信息。整個步驟不僅耗時，而且十分依賴于瀏覽器內核代碼。網(wǎng)絡上看到的一些VIPS算法實現(xiàn)都是調用了IE COM接口，而微軟自身的實現(xiàn)是利用單獨優(yōu)化后的IE內核，他們都是基于Windows編程環(huán)境。在Linux編程環(huán)境下，可以利用的只有Mozilla（Firefox）瀏覽器的開源代碼。但Mozilla代碼并沒有針對網(wǎng)頁視覺信息提取這一需求給出方便的使用接口，只有在其渲

25、染完網(wǎng)頁之后再截取視覺信息。我們實驗室的毛先領師兄曾經(jīng)研究Mozilla代碼，完成了這項艱苦的工作，但實驗表明，提取一個網(wǎng)頁的視覺信息所需時間超過1秒鐘，不能滿足搜索引擎等常規(guī)應用的使用要求。 其次，VIPS算法雖能改進分塊精確度，但算法相對比較復雜，迭代輪數(shù)較多，而基于規(guī)則的分塊算法卻只用較少的迭代輪數(shù)。 2.3 Block Level PageRank算法 在VIPS算法的分塊基礎上，微軟2004年的論文Block-level Link Analysis[5]中提出了Block Level PageRank(BLPR)算法。之前的大多數(shù)鏈接分析算法都是以一個Web頁面為Web圖中

26、的一個節(jié)點，而BLPR算法以網(wǎng)頁中的語義塊為原子節(jié)點，從鏈接結構和頁面結構中提取出Page-to-Block，Block-to-Page關系矩陣，構建出新的Web語義圖，并以此計算PageRank。實驗表明，BLPR改進了PageRank的質量。 2.3.1 Block Level Web Graph 首先定義兩個集合P和B。P為所有網(wǎng)頁的集合，P = {p1, p2, …, pk}，k為網(wǎng)頁總數(shù)。B為所有語義塊的集合，B = {b1, b2, …, bn}，n為語義塊總數(shù)。對每個語義塊來說，只有一個網(wǎng)頁包含它，bi ∈pj意味著語義塊i包含于網(wǎng)頁j。而每個網(wǎng)頁包含有多個語義塊。然后定義兩

27、個矩陣，block-to-page 矩陣Z和page-to-block矩陣X。在上述兩個矩陣的基礎之上，可以構建兩個web圖模型，即網(wǎng)頁圖GP (VP,EP, WP) 和語義塊圖GB (VB, EB, WB)。對這兩個圖來說，V是節(jié)點集合（節(jié)點分別是網(wǎng)頁和語義塊），E是連接兩個節(jié)點的邊的集合，而W是邊的權值矩陣。 2.3.1.1 Block-to-Page矩陣 塊頁（block-to-page）矩陣Z的維數(shù)為nk，定義如下： si是block i所鏈接的網(wǎng)頁總數(shù)。Zij可以理解成是用戶從block i鏈接到page j的概率。 2.3.1.2 Page-to-Bl

28、ock矩陣 頁塊（page-to-block）矩陣X的維數(shù)為kn，定義如下： si是page i所包含的block總數(shù)。上面的公式分配給page i中的每一個block以相同的權值，顯然是過于簡化了，不能區(qū)分block的重要程度。在BLPR算法中，采用了一個簡單的block重要度區(qū)分的公式，即用block的文字多少和離整個頁面中心點位置的遠近來計算block的重要度。每個block包含的文本長度越大，離頁面中心點越近，則越重要。改進后的X定義如下： 其中f函數(shù)給page i中的每一個block j賦予一個重要度權值。函數(shù)值越大，則block越重要。

29、在BLPR的實現(xiàn)中函數(shù)f的定義如下： 其中β為正規(guī)化因子，使得對每個page，fp(b)的總和為1。即 fp(b)可以理解為是用戶在瀏覽page p的時候，關注block b的可能性。 2.3.1.3 Page Graph 傳統(tǒng)的PageRank算法中Page Graph的權值矩陣計算十分簡單，如果從page i到page j有鏈接的話，則WP(i,j)為1，反之為0。然而在BLPR算法中，Page Graph需要體現(xiàn)出不同的語義塊的重要程度的不同。也就是說，當用戶點擊頁面中的超鏈接時，更偏好選擇重要的語義塊中的URL。所以在BLPR中，WP的定義

30、為： 即。 WP(α, β)可以理解為是從page α 開始，以page α中包含的各語義塊為媒介，跳轉到page β的概率。 2.3.1.4 Block Graph WB的定義為： 即。 WB(a,b)可以理解為用戶從block a開始，以包含block b的page β為媒介，跳轉到block b的概率。 2.3.2 Block Level PageRank Block Level PageRank跟PageRank區(qū)別的實質在于，PageRank算法基于原始的只有1和0的Page Graph，而BLPR算法基于上面提到的GP。BLPR

31、算法的數(shù)學計算公式如下： 其中p為結果向量，共n維，每一維代表一個網(wǎng)頁的PageRank值。ε為適配參數(shù)，以1-ε的概率，用戶在當前頁面中隨機選擇一個超鏈接，跳轉到該鏈接指向的頁面；以ε的概率，用戶從所有網(wǎng)頁中隨機選擇一個URL并跳轉。所以U為nn的轉換矩陣，它滿足對所有的i，j，Uij = 1/n。而M也是nn的轉換矩陣，它是由上面提到的WP權值矩陣對每一行做歸一化，令每一行的權值之和為1得到的。p向量的值以馬爾科夫鏈的形式循環(huán)計算下去，直到算法收斂。 Block Level PageRank比單純的PageRank包含了更多的語義信息。因為它的計算基于網(wǎng)頁中各語義塊

32、的重要程度，噪音塊、廣告塊中的超鏈接指向的網(wǎng)頁的重要性顯然不如導航塊、正文塊中的超鏈接所指向的網(wǎng)頁，所以前者會被分配到較少的PageRank值，而后者則被分配到較多的PageRank值。也就是說，網(wǎng)頁中的無關信息區(qū)域在PageRank的計算過程中起的作用相對較小，所以BLPR的效果要優(yōu)于單純的PageRank。 第 3 章 天網(wǎng)搜索引擎Quark模塊 搜索引擎系統(tǒng)一般包括網(wǎng)頁的抓取、預處理、存儲、索引、檢索等幾個部分，其中預處理部分的作用是分析、處理原始網(wǎng)頁數(shù)據(jù)如去除網(wǎng)頁噪音，消除重復網(wǎng)頁，計算PageRank，中文切詞等等，并為后繼模塊提供統(tǒng)一的數(shù)據(jù)訪問接口，規(guī)范數(shù)據(jù)管理，避免重復計

33、算。同時在天網(wǎng)搜索引擎平臺中，基于功能擴展和實驗室內部其他相關研究的需要，必須將對原始網(wǎng)頁的處理部分單獨出來，從而方便模塊復用，統(tǒng)一代碼管理，減少重復勞動。 在天網(wǎng)搜索引擎平臺的搭建過程中，也包括了抓取、存儲、分析（預處理）、索引、檢索等模塊，其中的分析模塊接受成批量原始網(wǎng)頁的輸入，然后對每個網(wǎng)頁調用Quark模塊，進行網(wǎng)頁分塊、信息提取等工作，最后將處理后的數(shù)據(jù)存成TwDocView格式，再提供給下游模塊。我的畢業(yè)設計的主要工作，就是圍繞Quark模塊而展開。 從上面的介紹中可以看出，天網(wǎng)搜索引擎Quark模塊有兩個比較重要的特點： 1、可擴展性。 因為搜索引擎是一個比較

34、龐大的系統(tǒng)，并且一直在不停的有新算法，新需求的加入，所以對數(shù)據(jù)的要求也會一直變化。而基于對原始網(wǎng)頁數(shù)據(jù)集中處理的原則，為了應對下游模塊可能提取的新的數(shù)據(jù)訪問需求，Quark模塊必須具備良好的可擴展性，并且提供盡量多的各種類型的數(shù)據(jù)訪問接口。同時由于實驗室人員的不固定性，代碼的維護十分重要。我自己在剛開始閱讀舊有的天網(wǎng)搜索引擎相關代碼的時候，就常有十分難懂的感覺，無法復用已有代碼，只好自己重新編寫。而正由于Quark模塊的可擴展性要求，所以它的代碼的可閱讀性也十分重要，在編寫的過程中，我盡量注意了這一點，遵守了我們統(tǒng)一的代碼規(guī)范。 2、獨立性。 在我們實驗室內部，除了搜索引擎之外，還有W

35、eb數(shù)據(jù)挖掘，Map-reduce應用等相關工作也可能需要使用對單個網(wǎng)頁的處理和數(shù)據(jù)提取程序。因此Quark模塊必須能獨立于搜索引擎代碼之外單獨編譯運行，并且方便他人調用這部分代碼。 基于上述兩個特點，我初步實現(xiàn)了Quark模塊。該模塊的類結構圖如下： 1、圖中右下及中間藍色的部分為Quark模塊的核心功能類，包括QuarkTree、QuarkElement、QuarkRecognizer、QuarkAnalyzer等四個類。 QuarkTree類的作用有兩個，一個是以原始網(wǎng)頁為輸入，建立Html的Dom Tree；另一個是存儲分好的網(wǎng)頁塊（在我們的系統(tǒng)中

36、，每一個網(wǎng)頁塊就叫做一個Quark）并記錄Quark與Quark之間的組織架構。 QuarkElement類指代一個Quark,即每個Quark自身就是一個QuarkElement類的對象。 QuarkRecognizer類肩負網(wǎng)頁分塊的重任，從網(wǎng)頁中識別出所有語義塊。它依賴于前面的兩個類。 QuarkAnalyzer類依賴于QuarkRecognizer類，它在分好的塊的基礎上，判斷各個塊的類型，提取正文信息。這個類是整個Quark模塊最核心的類，目前功能只是初步實現(xiàn)，還有很大的改進空間，將來也可以根據(jù)功能將其分割成多個類。 2、中上部綠色的部分為Quark模塊的

37、評測和演示類，包括QuarkEvaluation和QuarkHtmlBuilder兩個類。 QuarkEvaluation類是評測類，用來評測Quark核心類的實現(xiàn)效果。當前實現(xiàn)的是對網(wǎng)頁正文信息提取的評測，評測需要接受人工標記的網(wǎng)頁或網(wǎng)頁集為輸入。評測算法的細節(jié)見后文。 QuarkHtmlBuilder類是演示類，用來查看Quark模塊各步驟的實現(xiàn)效果。目前可以查看網(wǎng)頁分塊的效果，也可以查看主題信息提取的效果。 3、最上面黃色的部分為Quark模塊的應用類，包括QuarkRank、QuarkDuplicate、QuarkClassification等，它們都是利用分好的網(wǎng)頁

38、塊實現(xiàn)的一些算法，比如基于Quark的PageRank算法，基于Quark的網(wǎng)頁消重算法，以及基于Quark的網(wǎng)頁分類算法。 4、左下方灰色的部分為Quark模塊依賴的外部類接口，包括中文切詞類ChineseTokenizer，以及圖中沒有的編碼轉換類CodeConvert等等。 5、中下部紅色的部分為Quark模塊直接的下游模塊，包括TwDocView類和TwMd5類。 3.1 網(wǎng)頁分塊算法 算法主體在QuarkRecognizer類中。參見在第二章相關研究里提到的，除了基于視覺的算法之外，大部分基于語義的算法都是利用html標簽及其包含的文字信息的特性來給網(wǎng)頁分塊的

39、。并且由于大多數(shù)論文的著重點在于分塊后的內容提取上，所以對分塊算法本身著墨不多。綜合各篇論文里提到的分塊方法，我設計實現(xiàn)了QuarkRecognizer算法。 這一算法首先的一大特點就是實用性強。所謂實用性強是指適合在實際系統(tǒng)中使用，效率高，定義完整。我詳細分析了W3C制定的HTML4.01格式規(guī)范，將所有規(guī)范的Html標簽根據(jù)QuarkRecognizer算法的需要分類，完整地列出了所有對網(wǎng)頁分塊起重要作用的標簽，而不是像所有已有論文那樣僅僅象征性地列舉出幾個html標簽。分類后的詳細html標簽清單如下： 1、超級標簽（Super Tag，簡稱為S型標簽）： 這種標簽可以被直

40、接認定是一個網(wǎng)頁塊的根標簽，在算法過程中一旦遇到這種標簽，就可以直接將其加入網(wǎng)頁塊池。包括： "HEAD", "SCRIPT", "STYLE", "OBJECT", "FIELDSET", "FRAMESET", "IFRAME" 2、大標簽（Big Tag，簡稱為B型標簽）： 這種標簽通常都代表一個網(wǎng)頁塊，只不過有時其內部內容過少，需要跟其他節(jié)點合并成一個網(wǎng)頁塊，或者在特殊情況下其內部沒有可見字符。所以在算法過程中，遇到這種標簽，就判斷其單獨作為一個網(wǎng)頁塊的條件是否已經(jīng)成熟，如成熟，則將其加入網(wǎng)頁塊池。包括： "DIV", "TD", "TABLE", "FORM",

41、"FIELDSET", "CENTER", "NOFRAMES", "NOSCRIPT", "PRE", "BODY", "HTML" 這里需要注意的是像BODY，HTML兩個標簽也作為B型標簽，原因是這樣可以防止分塊之后網(wǎng)頁內部文字信息的遺漏，因為最終即使有遺漏，也會至少包含在HTML這個最后把關的門神標簽手中。 3、排版標簽（Layout Tag，簡稱為L型標簽）： 這種標簽能影響到網(wǎng)頁的顯示效果，改變文字布局。如果一顆html子樹中包含多個L型標簽，則該子樹單獨成塊的可能性增加。包括： "P", "UL", "OL", "DL", "DIR", "LI", "DT",

42、 "BLOCKQUOTE", "ADDRESS", "BR", "HR", "COL", "COLGROUP", "IMG", "MENU", "SELECT" 4、顯示標簽（Display Tag，簡稱為D型標簽）： 這種標簽數(shù)量最多，都是對文字的顯示方式做微幅的調整，如改變字體、顏色、粗細等等。由于它們的存在與否不改變網(wǎng)頁布局，所以不影響網(wǎng)頁分塊。包括： "A", "ABBR", "ACRONYM", "AREA", "B", "BASE", "BASEFONT", "BDO", BIG", "BUTTON", "CAPTION", "CITE", "CODE", "DD

43、", "DEL", "DFN", "EM", "FONT", "H1", "H2", "H3", "H4", "H5", "H6", "I", "INS", "KBD", "LABLE", "SMALL", "STRIKE", "STRONG", "SUB", "SUP", "Q", "S", "SAMP", "SPAN", "THEAD", "TFOOT", "TEXTAREA", "U", "TT", "VAR", "O:SMARTTAGTYPE" 5、附屬標簽（Affiliated Tag，簡稱為A型標簽）： 這種標簽從屬與上述四種標簽的某一種，同時有些也出現(xiàn)在了前面四種里面。由

44、于它們一般不單獨出現(xiàn)，對網(wǎng)頁布局的影響體現(xiàn)在了其屬主標簽中，所以 在QuarkRecognizer算法中也不予考慮。包括： "FRAME", "INPUT", "ISINDEX", "LEGEND", "LINK", "MAP", "META", "OPTION", "OPTGROUP", "PARAM", "TD", "TH", "TR", "TBODY", "TITLE" 6、定制標簽（Customized Tag，簡稱為C型標簽）： 因為不同的應用中，對網(wǎng)頁分塊會有些不同的要求。比如我們實驗室的WebDigest小組在進行新聞網(wǎng)頁的數(shù)據(jù)挖掘的工作中，需要使用到網(wǎng)頁分塊，但

45、是他們特別需要提取該新聞網(wǎng)頁的發(fā)布日期和時間，而這部分內容通常是在新聞標題與新聞正文之間的一小行文字，正常的網(wǎng)頁分塊程序并不會將其單獨提取成一個網(wǎng)頁塊。所以我添加了定制標簽，由用戶指定，它可以是普通的標簽如“TITLE”等，也可以是正則表達式，凡是其內部文字滿足該正則表達式的S型、B型和L型標簽，都將被單獨提取為網(wǎng)頁塊。例如： "H1", "H2", "TITLE" 在明確了各html標簽的類別之后，利用DomTree中各標簽節(jié)點的類別信息和內部文字長度，以及其子標簽節(jié)點的類別信息，對DomTree自底向上遍歷，在遍歷的過程中不斷判斷出新的網(wǎng)頁塊，并加入網(wǎng)頁塊池中，當遍歷到最上部的

46、html根節(jié)點時，算法結束，網(wǎng)頁分塊完畢。QuarkRecognizer算法的核心偽碼如下： _________________________________________________________________ ALGORITHM QuarkRecognizer (DomTree tree，TagList CType) INPUT : 某單個網(wǎng)頁構建的DomTree，定制標簽(C型)節(jié)點列表 BEGIN 1 用DomTree的葉子節(jié)點，也就是文字節(jié)點建立一個當前節(jié)點隊列，開始自底向上遍歷。 2 取當前節(jié)點隊列的第一個節(jié)點。 3 如果遇到S型節(jié)點，則立即

47、將此節(jié)點加入網(wǎng)頁塊池。 4 如果遇到C型節(jié)點，則立即將此節(jié)點加入網(wǎng)頁塊池。 5 如果遇到B型節(jié)點，則判斷該節(jié)點內部的文字長度是否已超過閾值，或者該節(jié)點內部的L型節(jié)點比例是否超過閾值，如果滿足上述兩個條件之一，則將此節(jié)點加入網(wǎng)頁塊池；否則將其內部文字長度信息和自身信息向父節(jié)點傳遞，然后將父節(jié)點加入當前節(jié)點隊列，回到2。 6 如果遇到L型節(jié)點，則將其內部文字長度信息和其自身信息向父節(jié)點傳遞，然后將父節(jié)點加入當前節(jié)點隊列，回到2。 7 如果遇到D型或A型節(jié)點，則將其內部文字長度信息向父節(jié)點傳遞，然后將父節(jié)點加入當前節(jié)點隊列，回到2。 8 當前節(jié)點隊列為空時，遍歷結束，算法終止。 END

48、 _________________________________________________________________ 網(wǎng)頁塊池中的網(wǎng)頁塊是以QuarkElement的格式存儲，而QuarkElement類中包括原來的html子樹的DomTree結構和其他相關信息，同時在上述遍歷的過程中，即使有的網(wǎng)頁塊從html結構上來說包含在更高層的網(wǎng)頁塊之下，但在QuarkElement中也消除了包含關系，所有網(wǎng)頁塊都互相獨立，互不包含。 3.2 網(wǎng)頁主題內容提取 算法主體在QuarkAnalyzer類中。采用了基于規(guī)則和基于Bayes的語義分析相交的方法，也就是分別用基

49、于文本相似度的方法和基于Bayes的方法判斷每個網(wǎng)頁塊的類型（是不是主題塊），然后對它們求交集，只有兩個方法共同認定的主題內容塊才能最終被認定。 QuarkAnalyzer算法的核心偽碼如下： _________________________________________________________________ 第一步，基于文本相似度的方法： 1、首先，把所有網(wǎng)頁塊中，文本長度最大的那個網(wǎng)頁塊判定為主題內容塊。 2、然后用其余網(wǎng)頁塊逐個與最大的網(wǎng)頁塊比較文本相似度。文本相似度的計算如下： 2.1 將兩個網(wǎng)頁塊分別切詞，去除停用詞后，存儲成token流。

50、 2.2 對兩個token流分別排序。 2.3 對排序后的兩個token流計算token的重復數(shù)。 2.4 用token的重復數(shù)除以較小的token流中的token個數(shù)，得到兩個網(wǎng)頁塊的文本相似度。 3、若文本相似度大于一個閾值，則該網(wǎng)頁塊也判定為主題內容塊。 第二步，基于Bayes的方法： 根據(jù)下面列出的7項先驗概率和該網(wǎng)頁塊相對應的這7項特性的（0，1）值，利用Bayes概率的計算公式，計算出每個網(wǎng)頁塊是不是主題內容塊的后驗概率。若該后驗概率大于0.5，則判定該網(wǎng)頁塊為主題內容塊，否則反之。 第三步，求交。 兩個方法共同判定的主題內容塊即為最后認定的主題

51、內容塊。 _________________________________________________________________ 其中Bayes方法的各先驗概率事先用手工標記的樣本網(wǎng)頁計算得到，結果如下： 在該網(wǎng)頁塊為主題內容塊的條件下， # 該塊中包含定制標簽的概率 p1_costomizedTag = 0.29; # 該塊中包含常見噪音詞并且文本長度小于100的概率 p1_noise = 0.04; # 該塊中每10個字符中的標點符號數(shù)大于0.3的概率 p1_punctuationScale = 0.85; # 該塊中標點符號總數(shù)

52、大于4的概率 p1_punctuation = 0.77 # 該塊中非錨接文本的長度大于200的概率 p1_size = 0.84 # 該塊中鏈接數(shù)量大于20的概率 p1_linkNum = 0.10; # 該塊中錨接文本和非錨接文本的長度之比大于0.3 p1_scale = 0.08; 在該網(wǎng)頁塊為非主題內容塊的條件下， # 該塊中包含定制標簽的概率 p2_costomizedTag = 0.01; # 該塊中包含常見噪音詞并且文本長度小于100的概率 p1_noise = 0.45; # 該塊中每10個字符中的標

53、點符號數(shù)大于0.3的概率 p2_punctuationScale = 0.25; # 該塊中標點符號總數(shù)大于4的概率 p2_punctuation = 0.34 # 該塊中非錨接文本的長度大于200的概率 p2_size = 0.06 # 該塊中鏈接數(shù)量大于20的概率 p2_linkNum = 0.71; # 該塊中錨接文本和非錨接文本的長度之比大于0.3 p2_scale = 0.85; 網(wǎng)頁塊為主題內容塊的概率： p_isContent = 0.16; 網(wǎng)頁塊為非主題內容塊的概率： p_isNoise = 1 - p_isCo

54、ntent; 3.3 算法效果演示 為了檢驗上述算法的效果，除了下一章會提到的評測程序外，還可以用QuarkHtmlBuilder類所編寫的演示程序以及自搭的Apache服務器上的python腳本來查看網(wǎng)頁分塊后和主題信息提取后的效果。限于篇幅，這里就不再詳細介紹算法的細節(jié)，但是附有幾張對照圖片，以利說明。 第一幅圖： 這是用python腳本寫的一個在瀏覽器上查看網(wǎng)頁主題內容提取效果的demo，可以選擇用PageModel的算法（即Quark模塊），也可以選擇用SiteModel的算法，點擊submit按鈕，就可以出現(xiàn)手工標記的主題內容，和程序判斷的主題內容的對比畫

55、面。由于時間關系，該Demo比較粗糙，沒有過多修飾。Submit后的效果圖見后面的第五幅圖。 第一幅圖：這是從新浪網(wǎng)上保存的一個新聞網(wǎng)頁。顯然，其主題內容信息塊應該是屏幕中左部的大塊文字內容。在處理這種類型的新聞網(wǎng)頁時，算法的效率很高，但事實上，Quark模塊還可以處理更復雜的網(wǎng)頁類型。 第二幅圖：這是網(wǎng)頁分塊之后的示意圖。從圖中可以看出，紅色、綠色、紫色的網(wǎng)頁塊間雜排列，就像地圖一樣，每一種顏色表示一個被識別出的網(wǎng)頁塊。圖中沒有顏色，依舊是藍色的鏈接色的部分是新浪網(wǎng)動態(tài)生成的內容，在html源代碼中并不存在，所以沒有被標上字體顏色。 第三幅圖：這是網(wǎng)頁正文提取之

56、后的示意圖。圖中紅色的部分為QuarkAnalyzer識別的正文內容，綠色部分為其識別的相關鏈接，其余紫色部分為噪音內容。從圖中可以看出，就這個網(wǎng)頁而言，網(wǎng)頁主題內容的提取基本成功了。 第五幅圖：這是第一幅圖所示Demo的結果界面截圖，可見，圖片上方是手工標注的文字內容，共720個字符。圖片下方是程序生成的文字內容，共628個字符。兩部分內容大致相等，說明網(wǎng)頁主題內容提取成功。 第 4 章 SEWM2008中文Web信息檢索評測 4.1 評測任務介紹 SEWM中文Web信息檢索評測[6]是由北京大學網(wǎng)絡實驗室主辦的中文Web檢索評測項目

57、，自2004年起，在SEWM會議中已連續(xù)舉辦了五屆，今年（2008年）是第五屆。其目標在于為中文信息檢索領域的研究人員提供一個標準的評測平臺，希望在國內外各個研究小組的共同參與下建立并完善以中文為主的網(wǎng)頁測試集CWT(Chinese Web Test collection)，解決支持中文WEB研究的基礎設施建設和應用中的基本方法與關鍵技術，一起推動中文Web信息檢索技術的發(fā)展。 SEWM2008中文Web信息檢索評測有三個任務： 主題型網(wǎng)頁發(fā)現(xiàn)和網(wǎng)頁內容信息塊發(fā)現(xiàn)，非網(wǎng)頁數(shù)字資源分類和垃圾郵件過濾，其中前兩個任務主要由何靖師兄設計，由我處理各參賽隊伍提交的數(shù)據(jù)并給出評測結果。本屆評測采用

58、的數(shù)據(jù)集是CWT70th。文檔集數(shù)據(jù)格式參見[7]。 由于本次評測任務的設計和上文提到的天網(wǎng)Quark模塊關系密切，評測所使用的程序就是天網(wǎng)Quark模塊中QuarkEvaluation類的python版本的代碼，同時天網(wǎng)Quark模塊的一個稍早期版本也參加了第二個任務關于網(wǎng)頁主題內容的評測，所以也可以作為天網(wǎng)Quark模塊的一個實驗結果，檢驗第三章提到的算法的效率。 4.1.1 主題型網(wǎng)頁發(fā)現(xiàn)任務 主題型網(wǎng)頁是指通過文字描述了一件或多件事物，具有一定主題的網(wǎng)頁。如一張具體的新聞網(wǎng)頁就是典型的主題型網(wǎng)頁。 下面是對主題型網(wǎng)頁的一個補充定義： 1、僅由圖片，flash，網(wǎng)絡視頻等

59、構成主題塊的網(wǎng)頁，除非亦包括獨立成段的文字性描述信息，否則不屬于主題型網(wǎng)頁。 2、某些導航型網(wǎng)頁，如同類軟件下載網(wǎng)頁中，雖然對每個鏈接都使用了適量文字來介紹，從而文字比例比較高，但也應該算作非主題型網(wǎng)頁。 3、錯誤網(wǎng)頁，空網(wǎng)頁，垃圾網(wǎng)頁，Spam網(wǎng)頁等屬于非主題型網(wǎng)頁。 4、論壇、博客網(wǎng)頁屬于主題型網(wǎng)頁，但沒有主貼，只包括無意義回復語句的網(wǎng)頁屬于非主題型網(wǎng)頁。 任務評測根據(jù)準確度、召回率和Macro-F1三個指標，它們的定義如下： 4.1.2 網(wǎng)頁內容信息發(fā)現(xiàn)任務 在一個主題型的網(wǎng)頁中， 一般會包括主題內容信息，噪音信息，和相關鏈接信息。本項任務

60、的目的在于找出主題型網(wǎng)頁中的主題內容信息。 噪音信息定義： a. 與網(wǎng)頁主旨內容不相關的信息 b. 由網(wǎng)站提供的內容模板信息 c. 廣告信息 d. 腳本程序信息 相關鏈接定義： 指向與本網(wǎng)頁相關網(wǎng)頁的鏈接，如新聞網(wǎng)頁下方的相關新聞鏈接。 補充定義： 1、 新聞網(wǎng)頁的內容信息應包括出現(xiàn)在頁面里的標題，時間，通訊社，記者名等信息。 2、一個網(wǎng)頁中的內容信息不一定只有一塊，可能有多塊，甚至可能是零散分布的文字段。 3、無意義的論壇回帖（如”頂”等）不屬于內容信息，但有一定內容的論壇回帖屬于內容信息。 4、相關鏈接不算內容信息。 任務評測根據(jù)準確度、召回率和Mac

61、ro-F1三個指標，它們的定義如下： 4.2 評測格式 評測要求參加評測單位以一定的格式提交，每個評測任務接受參加者的一到二組檢索結果。具體要求如下： 主題型網(wǎng)頁發(fā)現(xiàn)：提交一個純文本文件，包含所有找到的主題網(wǎng)頁，每個網(wǎng)頁的編號占一行。如： CWTquark080103-00000010 CWTquark080103-00000019 網(wǎng)頁內信息塊發(fā)現(xiàn)：只需要把正文內容找出來即可， 一個網(wǎng)頁可能包括多個彼此不連續(xù)的正文內容， 正文內容可以包括包含內容標簽， 也可以不包含內容標簽。 結果的格式如下： Document-Num

62、ber Start-Position Length三元組 其中Document-Number是網(wǎng)頁的編號，Start-Position是某段正文內容在原網(wǎng)頁文檔中的開始位置（網(wǎng)頁的起始位置從0開始計算）， Length是該段正文內容的長度。 一個網(wǎng)頁可以有多個正文內容段， 因此可以有類似下面的情況： CWTquark080103-00000001 200 300 // 該網(wǎng)頁中的第一段正文內容 CWTquark080103-00000001 450 500 // 該網(wǎng)頁中的第二段正文內容 4.3 評測結果 本次評測任務最終共有七支參賽隊伍，提交了12組結果。 1、大連理

63、工大學信息檢索實驗室 DLUT1 DLUT2 2、四川大學計算機學院數(shù)據(jù)庫與知識工程研究所 SCU1 SCU2 3、華南理工大學廣東省計算機網(wǎng)絡重點實驗室一隊 SCUT1 SCUT2 4、華南理工大學廣東省計算機網(wǎng)絡重點實驗室二隊 SCUT3 SCUT4 5、山東大學信息檢索實驗室 SDU1 SDU2 6、人民大學信息學院 RUC 7、北京大學網(wǎng)絡實

64、驗室 PKU 4.3.1 主題型網(wǎng)頁發(fā)現(xiàn)任務評測結果 在數(shù)據(jù)集CWT70th中的所有71502個網(wǎng)頁中，有71281個不重復URL。 在這71281個網(wǎng)頁中，隨機抽取了300個URL，人工判斷其類型。為了消除對主題型網(wǎng)頁認定上的分歧，在300個URL中去除了部分混合型以及不易判別類型的網(wǎng)頁，共得到227個確定類型的網(wǎng)頁，其中包括138個主題型網(wǎng)頁，89個非主題型網(wǎng)頁，主題型網(wǎng)頁數(shù)目/非主題型網(wǎng)頁數(shù)目 = 1.5505618，經(jīng)驗證，大致符合原網(wǎng)頁集中的類型分布。利用該227個網(wǎng)頁，評測各組參賽數(shù)據(jù)。 雖然我們的樣本數(shù)偏少，但由于樣本中的類型分布大致符合原網(wǎng)頁集

65、中的類型分布，所以評測結果基本反映了各組的實際分類質量，只不過沒有形成明顯差距。華南理工一隊和大連理工的分類質量相對最佳，而人民大學和山東大學提交的三個結果，分別將71502個網(wǎng)頁中的66498、56509、55111個判斷為了主題型網(wǎng)頁，過高地估計了主題型網(wǎng)頁的比例，從而大大降低了精度，但值得一提的是，山東大學提交的結果2獲得了最高的召回率。 評測結果如下： TEAM Macro-Precision Macro-Recall Macro-F1 DLUT1 0.888888888889 0.869565217391 0.879120879121 DLUT2 0.895

66、52238806 0.869565217391 0.882352941176 SCU1 0.846153846154 0.876811594203 0.861209964413 SCU2 0.840277777778 0.876811594203 0.858156028369 SCUT1 0.883211678832 0.876811594203 0.88 SCUT2 0.889705882353 0.876811594203 0.883211678832 SCUT3 0.82119205298 0.898550724638 0.858131487889 SCUT4 0.794871794872 0.898550724638 0.843537414966 SDU1 0.78125 0.905797101449 0.838926174497 SDU2 0.774566473988 0.971014492754 0.861736334405 RUC 0.670103092784 0.942028985507