1、00448174 朱磊 本科畢業論文 本科生畢業論文題目：(中文) 大規模網頁模塊識別與信息提取 系統設計與實現 (英文) Design and Implementation of Large Scale Web Template Detection and Information Extraction System姓 名：朱 磊 學 號：00448174 院 系：計算機系 專 業：搜索引擎與互聯網信息挖掘 指導教師：閆宏飛 二二二二二二年二月八日41摘要本文在已有的基于Dom-Tree和啟發式規則的網頁信息提取算法的基礎上，通過為所有符合W3C規范的Html標簽分類，逐個分析各Html標簽所

2、包含的語義信息，細化規則設置，實現了一種自底向上的無信息遺漏的網頁分塊算法，并在此基礎上，利用統計方法得到詳細的概率分布數據，實現了文本相似度比較和Bayes后驗概率估計兩種網頁主題內容信息塊識別算法，并將其求交，提高了主題內容信息塊的識別精確度。上述算法已集成到天網搜索引擎平臺的網頁預處理模塊中，并且在SEWM 2008會議中，以這套算法為框架，組織了主題型網頁識別和網頁主題內容信息塊提取兩個中文Web信息檢索評測項目。在這套算法的基礎上，基于天網文件系統與Map-Reduce計算平臺，實現了分布式的網頁塊級別PageRank算法，命名為QuarkRank算法。實際檢驗表明，該套算法具有很好

3、的適應性與可擴展性，并達到了很高的精度和召回率。關鍵詞：網頁分塊 信息提取 SEWM 評測 PageRankAbstractThis 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 W3C standards, and by analyzing semantic information contained in the Html tags one by o

4、ne, 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 realizes two algorithms of information block recognition, one is text similarity comparison an

5、d 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 integrated into the page pretreatment module of TianWang search engine platform, and in SEWM 2008 me

6、eting, 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 content.In this method, based on TianWang file system and the Map-Reduce computing platform, this paper

7、 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 high precision and recall.Keywords: Web-Page Blocking, SEWM, Information Extraction, Evaluation , PageRank目

8、錄第 1 章序言3第 2 章相關研究工作52.1基于語義的網頁信息提取算法52.2基于視覺的網頁分塊算法62.3Block Level PageRank算法82.3.1Block Level Web Graph82.3.2Block Level PageRank10第 3 章天網搜索引擎Quark模塊113.1網頁分塊算法133.2網頁主題內容提取163.3算法效果演示18第 4 章SEWM2008中文Web信息檢索評測234.1評測任務介紹234.1.1主題型網頁發現任務234.1.2網頁內容信息發現任務244.2評測格式254.3評測結果254.3.1主題型網頁發現任務評測結果264.3.

9、2網頁內容信息發現任務評測結果284.4評測綜述31第 5 章網頁分塊的分布式應用325.1QuarkRank325.2其他應用34第 6 章總結與展望356.1總結356.2展望36第 1 章 序言信息時代，非Web無以制勝。互聯網的高速發展，改變了我們的生活方式，打破了我們的時空界限，重塑著我們的社會形態。經濟、政治、學習、工作、生活、娛樂等等各個層面都在Web網絡中激蕩起伏，深刻地影響著人類的未來。而Web網絡的靈魂，就是流動在其中的無窮無盡的信息。Web2.0的意義就在于網絡內容的提供方從商人和專業人員轉變為網絡上的每一個普通用戶，從而幾何級數地增長了Web的信息量。然而信息量的增大，

10、隨著而來的就是存儲成本的增大和信息提取難度的增大，如何有效的獲取和整合Web信息成為大家面對的共同課題。傳統意義上，整個Web網絡就是由無數的Web頁面而構成，它們是網絡信息存儲和提取的基本單位，獲取了這些Web頁面就相當于獲取了Web信息內容。但是把整個頁面作為最基本的信息處理單位有一些不合理之處。首先是因為Web頁面中信息量的分布非常不均勻，有主題內容，也有廣告，導航欄，版權信息，裝飾信息，以及在大量網頁中重復出現的部分，它們自身的信息含量千差萬別。當網頁瀏覽者剛打開一個新頁面的時候，如果之前沒有瀏覽過類似頁面，就會目不暇接，眼花繚亂，有無所適從的感覺，必須仔細探尋一番才能定位到這個頁面的

11、要害；如果之前瀏覽過類似頁面，比如常上這個網站，那么通常瀏覽者就已經訓練出一種直覺或者說是條件反射，他會立刻定位到他所想要瀏覽的部分，從而忽略掉頁面中的其他部分。其次還因為現在很多Web頁面是動態更新的，比如博客頁面或者論壇討論帖，它們的更新是以一個一個網頁塊的形式進行的，更新時頁面上大部分內容并沒有變化，如果仍然以整個頁面為處理單位，則不可避免地存在效率損失和定義的混淆。這些情況促使我們反思以整個頁面為基本信息單元的做法不僅不盡合理，一定程度上甚至已經損害了網絡瀏覽者的用戶體驗，妨礙了網絡信息提取的效率。解決這個問題的辦法其實有兩種思路。第一種就是從信息的產生方那兒就不再提供網頁式的信息，而

12、改為直接提供網頁塊或者文字段式的信息。最常見的例子就是RSS（聚合內容，Really Simple Syndication），博客或者新聞的提供方省去了瀏覽者訪問網站查看更新的麻煩，直接將精簡后的網頁塊或者文字段發送給RSS的訂閱方。第二種則更為普適，就是細分網頁中的信息單元，也就是給網頁分塊，在網頁分塊的基礎上存儲和提取Web頁面的語義信息。基于網頁分塊的Web頁面的語義信息提取在很多方面都有應用。比如，在常規搜索引擎中，可以以網頁分塊為基礎去除網頁中的噪音信息，識別出網頁中的主題內容信息塊，從而用提取出的主題內容信息來構建對這個頁面的描述，完成網頁分類、網頁消重等應用。還可以憑此改進搜索引

13、擎的索引模塊和檢索模塊的效率，比如改進TF/IDF和PageRank的算法（詳見第五章）。 Web頁面的語義分塊另外一個重要用途在于移動終端訪問互聯網，比如手機和IPod等。因為目前大部分的Web頁面都是針對PC機設計的，要求有相對較大的屏幕。而移動設備通常屏幕較小，計算能力有限，無法直接訪問這些頁面。為了解決這個問題，要么是內容提供商手工編輯專門適用于移動設備的頁面，要么就只有對頁面進行語義分割，并在分割后的頁面中選擇信息量最高的語義塊。除此之外，Web頁面的語義分塊還可能對常規搜索引擎之外的其他信息檢索系統有幫助。比如類似于新聞人物追蹤和歷史新聞檢索等應用，出于節約存儲空間，提高檢索精度，

14、方便更新等目的，可以直接存儲和操作網頁中的主題內容語義塊，而舍棄網頁中其他與系統需求無關的語義塊。在這篇論文中，第二章介紹了本文的相關研究工作，包括常見的網頁分塊和信息提取算法、基于視覺的網頁分塊算法，以及網頁分塊的一個應用Block Level PageRank算法；第三章介紹了我實現的網頁分塊和主題信息提取算法Quark算法；第四章介紹了Quark算法在SEWM2008中文Web信息檢索評測項目中的實際檢驗；第五章介紹了在Quark算法基礎上實現的一個分布式QuarkRank程序。第六章是對本文的總結和工作展望。第 2 章 相關研究工作2.1 基于語義的網頁信息提取算法由于對Web頁面有效

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

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

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

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

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

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

21、因此如果充分的使用Web頁面的視覺信息，模擬人眼識別語義塊的過程，并結合DOM樹結構分析進行頁面分塊，則可以達到更好的效果。微軟亞洲研究院在其2003年的論文VIPS: A vision based page segmentation algorithm4里首次提出了基于視覺的網頁分塊算法VIPS(Vision-based page segmentation)。VIPS算法充分利用了Web頁面的布局特征（見圖1），它有三個主要步驟：首先從DOM樹中以較小的粒度提取出所有可視標簽塊，并且給每個可視標簽塊計算出一個DOC（“一致性程度”，Degree of Coherence）值來描述該塊內部內容

22、的相關性。DOC的值越大，則表明該塊內部的內容之間的聯系越緊密，反之越松散。第二步利用每個可視標簽塊的絕對位置和相對位置信息，檢測出它們之間的所有的分割條，包括水平和垂直方向。最后基于這些分割條，利用更多的諸如顏色等視覺信息，重新構建Web頁面的語義結構。VIPS算法的優點十分明顯，它充分利用了網頁的視覺信息和結構信息，相對于傳統的基于規則的分塊算法來說，大大提高了分塊的精確度。但VIPS算法也有其局限性：首先，提取網頁視覺信息代價很高。因為HTML語言本身并沒有包含足夠的視覺信息，所以網頁真正顯示出來的效果因瀏覽器，因操作系統，甚至因硬件而異。為了得到網頁的完整視覺信息，必須完全下載該網頁所

23、鏈接的CSS文件，JavaScript文件，圖片文件等等，然后調用瀏覽器內核代碼渲染這些網頁文件，最后從瀏覽器內核代碼的接口中得到每個HTML標簽的視覺信息。整個步驟不僅耗時，而且十分依賴于瀏覽器內核代碼。網絡上看到的一些VIPS算法實現都是調用了IE COM接口，而微軟自身的實現是利用單獨優化后的IE內核，他們都是基于Windows編程環境。在Linux編程環境下，可以利用的只有Mozilla（Firefox）瀏覽器的開源代碼。但Mozilla代碼并沒有針對網頁視覺信息提取這一需求給出方便的使用接口，只有在其渲染完網頁之后再截取視覺信息。我們實驗室的毛先領師兄曾經研究Mozilla代碼，完成

24、了這項艱苦的工作，但實驗表明，提取一個網頁的視覺信息所需時間超過1秒鐘，不能滿足搜索引擎等常規應用的使用要求。其次，VIPS算法雖能改進分塊精確度，但算法相對比較復雜，迭代輪數較多，而基于規則的分塊算法卻只用較少的迭代輪數。2.3 Block Level PageRank算法在VIPS算法的分塊基礎上，微軟2004年的論文Block-level Link Analysis5中提出了Block Level PageRank(BLPR)算法。之前的大多數鏈接分析算法都是以一個Web頁面為Web圖中的一個節點，而BLPR算法以網頁中的語義塊為原子節點，從鏈接結構和頁面結構中提取出Page-to-Bl

25、ock，Block-to-Page關系矩陣，構建出新的Web語義圖，并以此計算PageRank。實驗表明，BLPR改進了PageRank的質量。2.3.1 Block Level Web Graph首先定義兩個集合P和B。P為所有網頁的集合，P = p1, p2, , pk，k為網頁總數。B為所有語義塊的集合，B = b1, b2, , bn，n為語義塊總數。對每個語義塊來說，只有一個網頁包含它，bi pj意味著語義塊i包含于網頁j。而每個網頁包含有多個語義塊。然后定義兩個矩陣，block-to-page 矩陣Z和page-to-block矩陣X。在上述兩個矩陣的基礎之上，可以構建兩個web圖

26、模型，即網頁圖GP (VP,EP, WP) 和語義塊圖GB (VB, EB, WB)。對這兩個圖來說，V是節點集合（節點分別是網頁和語義塊），E是連接兩個節點的邊的集合，而W是邊的權值矩陣。 Block-to-Page矩陣塊頁（block-to-page）矩陣Z的維數為nk，定義如下： si是block i所鏈接的網頁總數。Zij可以理解成是用戶從block i鏈接到page j的概率。 Page-to-Block矩陣頁塊（page-to-block）矩陣X的維數為kn，定義如下：si是page i所包含的block總數。上面的公式分配給page i中的每一個blo

27、ck以相同的權值，顯然是過于簡化了，不能區分block的重要程度。在BLPR算法中，采用了一個簡單的block重要度區分的公式，即用block的文字多少和離整個頁面中心點位置的遠近來計算block的重要度。每個block包含的文本長度越大，離頁面中心點越近，則越重要。改進后的X定義如下：其中f函數給page i中的每一個block j賦予一個重要度權值。函數值越大，則block越重要。在BLPR的實現中函數f的定義如下：其中為正規化因子，使得對每個page，fp(b)的總和為1。即fp(b)可以理解為是用戶在瀏覽page p的時候，關注block b的可能性。 Page Grap

28、h傳統的PageRank算法中Page Graph的權值矩陣計算十分簡單，如果從page i到page j有鏈接的話，則WP(i,j)為1，反之為0。然而在BLPR算法中，Page Graph需要體現出不同的語義塊的重要程度的不同。也就是說，當用戶點擊頁面中的超鏈接時，更偏好選擇重要的語義塊中的URL。所以在BLPR中，WP的定義為：即。WP(, )可以理解為是從page 開始，以page 中包含的各語義塊為媒介，跳轉到page 的概率。 Block GraphWB的定義為：即。WB(a,b)可以理解為用戶從block a開始，以包含block b的page 為媒介，跳轉到blo

29、ck b的概率。2.3.2 Block Level PageRankBlock Level PageRank跟PageRank區別的實質在于，PageRank算法基于原始的只有1和0的Page Graph，而BLPR算法基于上面提到的GP。BLPR算法的數學計算公式如下：其中p為結果向量，共n維，每一維代表一個網頁的PageRank值。為適配參數，以1-的概率，用戶在當前頁面中隨機選擇一個超鏈接，跳轉到該鏈接指向的頁面；以的概率，用戶從所有網頁中隨機選擇一個URL并跳轉。所以U為nn的轉換矩陣，它滿足對所有的i，j，Uij = 1/n。而M也是nn的轉換矩陣，它是由上面提到的WP權值矩陣對每一

30、行做歸一化，令每一行的權值之和為1得到的。p向量的值以馬爾科夫鏈的形式循環計算下去，直到算法收斂。Block Level PageRank比單純的PageRank包含了更多的語義信息。因為它的計算基于網頁中各語義塊的重要程度，噪音塊、廣告塊中的超鏈接指向的網頁的重要性顯然不如導航塊、正文塊中的超鏈接所指向的網頁，所以前者會被分配到較少的PageRank值，而后者則被分配到較多的PageRank值。也就是說，網頁中的無關信息區域在PageRank的計算過程中起的作用相對較小，所以BLPR的效果要優于單純的PageRank。第 3 章 天網搜索引擎Quark模塊搜索引擎系統一般包括網頁的抓取、預處

31、理、存儲、索引、檢索等幾個部分，其中預處理部分的作用是分析、處理原始網頁數據如去除網頁噪音，消除重復網頁，計算PageRank，中文切詞等等，并為后繼模塊提供統一的數據訪問接口，規范數據管理，避免重復計算。同時在天網搜索引擎平臺中，基于功能擴展和實驗室內部其他相關研究的需要，必須將對原始網頁的處理部分單獨出來，從而方便模塊復用，統一代碼管理，減少重復勞動。在天網搜索引擎平臺的搭建過程中，也包括了抓取、存儲、分析（預處理）、索引、檢索等模塊，其中的分析模塊接受成批量原始網頁的輸入，然后對每個網頁調用Quark模塊，進行網頁分塊、信息提取等工作，最后將處理后的數據存成TwDocView格式，再提供

32、給下游模塊。我的畢業設計的主要工作，就是圍繞Quark模塊而展開。從上面的介紹中可以看出，天網搜索引擎Quark模塊有兩個比較重要的特點：1、可擴展性。因為搜索引擎是一個比較龐大的系統，并且一直在不停的有新算法，新需求的加入，所以對數據的要求也會一直變化。而基于對原始網頁數據集中處理的原則，為了應對下游模塊可能提取的新的數據訪問需求，Quark模塊必須具備良好的可擴展性，并且提供盡量多的各種類型的數據訪問接口。同時由于實驗室人員的不固定性，代碼的維護十分重要。我自己在剛開始閱讀舊有的天網搜索引擎相關代碼的時候，就常有十分難懂的感覺，無法復用已有代碼，只好自己重新編寫。而正由于Quark模塊的可

33、擴展性要求，所以它的代碼的可閱讀性也十分重要，在編寫的過程中，我盡量注意了這一點，遵守了我們統一的代碼規范。2、獨立性。在我們實驗室內部，除了搜索引擎之外，還有Web數據挖掘，Map-reduce應用等相關工作也可能需要使用對單個網頁的處理和數據提取程序。因此Quark模塊必須能獨立于搜索引擎代碼之外單獨編譯運行，并且方便他人調用這部分代碼。基于上述兩個特點，我初步實現了Quark模塊。該模塊的類結構圖如下：1、圖中右下及中間藍色的部分為Quark模塊的核心功能類，包括QuarkTree、QuarkElement、QuarkRecognizer、QuarkAnalyzer等四個類。QuarkT

34、ree類的作用有兩個，一個是以原始網頁為輸入，建立Html的Dom Tree；另一個是存儲分好的網頁塊（在我們的系統中，每一個網頁塊就叫做一個Quark）并記錄Quark與Quark之間的組織架構。QuarkElement類指代一個Quark,即每個Quark自身就是一個QuarkElement類的對象。QuarkRecognizer類肩負網頁分塊的重任，從網頁中識別出所有語義塊。它依賴于前面的兩個類。QuarkAnalyzer類依賴于QuarkRecognizer類，它在分好的塊的基礎上，判斷各個塊的類型，提取正文信息。這個類是整個Quark模塊最核心的類，目前功能只是初步實現，還有很大的改

35、進空間，將來也可以根據功能將其分割成多個類。2、中上部綠色的部分為Quark模塊的評測和演示類，包括QuarkEvaluation和QuarkHtmlBuilder兩個類。QuarkEvaluation類是評測類，用來評測Quark核心類的實現效果。當前實現的是對網頁正文信息提取的評測，評測需要接受人工標記的網頁或網頁集為輸入。評測算法的細節見后文。QuarkHtmlBuilder類是演示類，用來查看Quark模塊各步驟的實現效果。目前可以查看網頁分塊的效果，也可以查看主題信息提取的效果。3、最上面黃色的部分為Quark模塊的應用類，包括QuarkRank、QuarkDuplicate、Qua

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

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

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

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

40、 Tag，簡稱為D型標簽）：這種標簽數量最多，都是對文字的顯示方式做微幅的調整，如改變字體、顏色、粗細等等。由于它們的存在與否不改變網頁布局，所以不影響網頁分塊。包括：A, ABBR, ACRONYM, AREA, B, BASE, BASEFONT,BDO, BIG, BUTTON, CAPTION, CITE, CODE, DD, 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, TE

41、XTAREA, U, TT, VAR, O:SMARTTAGTYPE5、附屬標簽（Affiliated Tag，簡稱為A型標簽）：這種標簽從屬與上述四種標簽的某一種，同時有些也出現在了前面四種里面。由于它們一般不單獨出現，對網頁布局的影響體現在了其屬主標簽中，所以在QuarkRecognizer算法中也不予考慮。包括：FRAME, INPUT, ISINDEX, LEGEND, LINK, MAP, META, OPTION, OPTGROUP, PARAM, TD, TH, TR, TBODY, TITLE6、定制標簽（Customized Tag，簡稱為C型標簽）：因為不同的應用中，對網頁

42、分塊會有些不同的要求。比如我們實驗室的WebDigest小組在進行新聞網頁的數據挖掘的工作中，需要使用到網頁分塊，但是他們特別需要提取該新聞網頁的發布日期和時間，而這部分內容通常是在新聞標題與新聞正文之間的一小行文字，正常的網頁分塊程序并不會將其單獨提取成一個網頁塊。所以我添加了定制標簽，由用戶指定，它可以是普通的標簽如“TITLE”等，也可以是正則表達式，凡是其內部文字滿足該正則表達式的S型、B型和L型標簽，都將被單獨提取為網頁塊。例如：H1, H2, TITLE在明確了各html標簽的類別之后，利用DomTree中各標簽節點的類別信息和內部文字長度，以及其子標簽節點的類別信息，對DomTr

43、ee自底向上遍歷，在遍歷的過程中不斷判斷出新的網頁塊，并加入網頁塊池中，當遍歷到最上部的html根節點時，算法結束，網頁分塊完畢。QuarkRecognizer算法的核心偽碼如下：_ ALGORITHM QuarkRecognizer (DomTree tree，TagList CType) INPUT : 某單個網頁構建的DomTree，定制標簽(C型)節點列表BEGIN 1 用DomTree的葉子節點，也就是文字節點建立一個當前節點隊列，開始自底向上遍歷。2 取當前節點隊列的第一個節點。3 如果遇到S型節點，則立即將此節點加入網頁塊池。4 如果遇到C型節點，則立即將此節點加入網頁塊池。5

44、如果遇到B型節點，則判斷該節點內部的文字長度是否已超過閾值，或者該節點內部的L型節點比例是否超過閾值，如果滿足上述兩個條件之一，則將此節點加入網頁塊池；否則將其內部文字長度信息和自身信息向父節點傳遞，然后將父節點加入當前節點隊列，回到2。6 如果遇到L型節點，則將其內部文字長度信息和其自身信息向父節點傳遞，然后將父節點加入當前節點隊列，回到2。7 如果遇到D型或A型節點，則將其內部文字長度信息向父節點傳遞，然后將父節點加入當前節點隊列，回到2。8 當前節點隊列為空時，遍歷結束，算法終止。END_ 網頁塊池中的網頁塊是以QuarkElement的格式存儲，而QuarkElement類中包括原來的

45、html子樹的DomTree結構和其他相關信息，同時在上述遍歷的過程中，即使有的網頁塊從html結構上來說包含在更高層的網頁塊之下，但在QuarkElement中也消除了包含關系，所有網頁塊都互相獨立，互不包含。3.2 網頁主題內容提取算法主體在QuarkAnalyzer類中。采用了基于規則和基于Bayes的語義分析相交的方法，也就是分別用基于文本相似度的方法和基于Bayes的方法判斷每個網頁塊的類型（是不是主題塊），然后對它們求交集，只有兩個方法共同認定的主題內容塊才能最終被認定。QuarkAnalyzer算法的核心偽碼如下：_ 第一步，基于文本相似度的方法：1、首先，把所有網頁塊中，文本長

46、度最大的那個網頁塊判定為主題內容塊。2、然后用其余網頁塊逐個與最大的網頁塊比較文本相似度。文本相似度的計算如下： 2.1 將兩個網頁塊分別切詞，去除停用詞后，存儲成token流。 2.2 對兩個token流分別排序。 2.3 對排序后的兩個token流計算token的重復數。 2.4 用token的重復數除以較小的token流中的token個數，得到兩個網頁塊的文本相似度。3、若文本相似度大于一個閾值，則該網頁塊也判定為主題內容塊。第二步，基于Bayes的方法：根據下面列出的7項先驗概率和該網頁塊相對應的這7項特性的（0，1）值，利用Bayes概率的計算公式，計算出每個網頁塊是不是主題內容塊的

47、后驗概率。若該后驗概率大于0.5，則判定該網頁塊為主題內容塊，否則反之。第三步，求交。兩個方法共同判定的主題內容塊即為最后認定的主題內容塊。_ 其中Bayes方法的各先驗概率事先用手工標記的樣本網頁計算得到，結果如下：在該網頁塊為主題內容塊的條件下，# 該塊中包含定制標簽的概率p1_costomizedTag = 0.29;# 該塊中包含常見噪音詞并且文本長度小于100的概率p1_noise = 0.04;# 該塊中每10個字符中的標點符號數大于0.3的概率p1_punctuationScale = 0.85; # 該塊中標點符號總數大于4的概率p1_punctuation = 0.77# 該

48、塊中非錨接文本的長度大于200的概率p1_size = 0.84# 該塊中鏈接數量大于20的概率p1_linkNum = 0.10; # 該塊中錨接文本和非錨接文本的長度之比大于0.3p1_scale = 0.08;在該網頁塊為非主題內容塊的條件下，# 該塊中包含定制標簽的概率p2_costomizedTag = 0.01;# 該塊中包含常見噪音詞并且文本長度小于100的概率p1_noise = 0.45;# 該塊中每10個字符中的標點符號數大于0.3的概率p2_punctuationScale = 0.25; # 該塊中標點符號總數大于4的概率p2_punctuation = 0.34# 該

49、塊中非錨接文本的長度大于200的概率p2_size = 0.06# 該塊中鏈接數量大于20的概率p2_linkNum = 0.71; # 該塊中錨接文本和非錨接文本的長度之比大于0.3p2_scale = 0.85;網頁塊為主題內容塊的概率：p_isContent = 0.16;網頁塊為非主題內容塊的概率：p_isNoise = 1 - p_isContent;3.3 算法效果演示為了檢驗上述算法的效果，除了下一章會提到的評測程序外，還可以用QuarkHtmlBuilder類所編寫的演示程序以及自搭的Apache服務器上的python腳本來查看網頁分塊后和主題信息提取后的效果。限于篇幅，這里就

50、不再詳細介紹算法的細節，但是附有幾張對照圖片，以利說明。第一幅圖：這是用python腳本寫的一個在瀏覽器上查看網頁主題內容提取效果的demo，可以選擇用PageModel的算法（即Quark模塊），也可以選擇用SiteModel的算法，點擊submit按鈕，就可以出現手工標記的主題內容，和程序判斷的主題內容的對比畫面。由于時間關系，該Demo比較粗糙，沒有過多修飾。Submit后的效果圖見后面的第五幅圖。第一幅圖：這是從新浪網上保存的一個新聞網頁。顯然，其主題內容信息塊應該是屏幕中左部的大塊文字內容。在處理這種類型的新聞網頁時，算法的效率很高，但事實上，Quark模塊還可以處理更復雜的網頁類型

51、。第二幅圖：這是網頁分塊之后的示意圖。從圖中可以看出，紅色、綠色、紫色的網頁塊間雜排列，就像地圖一樣，每一種顏色表示一個被識別出的網頁塊。圖中沒有顏色，依舊是藍色的鏈接色的部分是新浪網動態生成的內容，在html源代碼中并不存在，所以沒有被標上字體顏色。第三幅圖：這是網頁正文提取之后的示意圖。圖中紅色的部分為QuarkAnalyzer識別的正文內容，綠色部分為其識別的相關鏈接，其余紫色部分為噪音內容。從圖中可以看出，就這個網頁而言，網頁主題內容的提取基本成功了。第五幅圖：這是第一幅圖所示Demo的結果界面截圖，可見，圖片上方是手工標注的文字內容，共720個字符。圖片下方是程序生成的文字內容，共6

52、28個字符。兩部分內容大致相等，說明網頁主題內容提取成功。第 4 章 SEWM2008中文Web信息檢索評測 4.1 評測任務介紹SEWM中文Web信息檢索評測6是由北京大學網絡實驗室主辦的中文Web檢索評測項目，自2004年起，在SEWM會議中已連續舉辦了五屆，今年（2008年）是第五屆。其目標在于為中文信息檢索領域的研究人員提供一個標準的評測平臺，希望在國內外各個研究小組的共同參與下建立并完善以中文為主的網頁測試集CWT(Chinese Web Test collection)，解決支持中文WEB研究的基礎設施建設和應用中的基本方法與關鍵技術，一起推動中文Web信息檢索技術的發展。SEWM

53、2008中文Web信息檢索評測有三個任務： 主題型網頁發現和網頁內容信息塊發現，非網頁數字資源分類和垃圾郵件過濾，其中前兩個任務主要由何靖師兄設計，由我處理各參賽隊伍提交的數據并給出評測結果。本屆評測采用的數據集是CWT70th。文檔集數據格式參見7。 由于本次評測任務的設計和上文提到的天網Quark模塊關系密切，評測所使用的程序就是天網Quark模塊中QuarkEvaluation類的python版本的代碼，同時天網Quark模塊的一個稍早期版本也參加了第二個任務關于網頁主題內容的評測，所以也可以作為天網Quark模塊的一個實驗結果，檢驗第三章提到的算法的效率。4.1.1 主題型網頁發現任務

54、主題型網頁是指通過文字描述了一件或多件事物，具有一定主題的網頁。如一張具體的新聞網頁就是典型的主題型網頁。下面是對主題型網頁的一個補充定義：1、僅由圖片，flash，網絡視頻等構成主題塊的網頁，除非亦包括獨立成段的文字性描述信息，否則不屬于主題型網頁。2、某些導航型網頁，如同類軟件下載網頁中，雖然對每個鏈接都使用了適量文字來介紹，從而文字比例比較高，但也應該算作非主題型網頁。3、錯誤網頁，空網頁，垃圾網頁，Spam網頁等屬于非主題型網頁。4、論壇、博客網頁屬于主題型網頁，但沒有主貼，只包括無意義回復語句的網頁屬于非主題型網頁。任務評測根據準確度、召回率和Macro-F1三個指標，它們的定義如下：4.1.2 網頁內容信息發現任務在一個主題型的網頁中， 一般會包括主題內容信息，噪音信息，和相關鏈接信息。本項任務的目的在于找出主題型網頁中的主題內容信息。噪音信息定義：a. 與網頁主旨內容不相關的信息b. 由網站提供的內容模板信息c. 廣告信息d. 腳本程序信息相關鏈接定義：指向與本網頁相關網頁的鏈接，如新聞網