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

1、 本科生畢業(yè)論文題目：(中文) 大規(guī)模網(wǎng)頁模塊識別與信息提取 系統(tǒng)設(shè)計與實現(xiàn) (英文) design and implementation of large scale web template detection and information extraction system姓 名： 學(xué) 號： 院 系：計算機 專 業(yè)：搜索引擎與互聯(lián)網(wǎng)信息挖掘 指導(dǎo)教師： 摘要本文在已有的基于dom-tree和啟發(fā)式規(guī)則的網(wǎng)頁信息提取算法的基礎(chǔ)上，通過為所有符合w3c規(guī)范的html標(biāo)簽分類，逐個分析各html標(biāo)簽所包含的語義信息，細(xì)化規(guī)則設(shè)置，實現(xiàn)了一種自底向上的無信息遺漏的網(wǎng)頁分塊算法，并在此基礎(chǔ)上，利

2、用統(tǒng)計方法得到詳細(xì)的概率分布數(shù)據(jù)，實現(xiàn)了文本相似度比較和bayes后驗概率估計兩種網(wǎng)頁主題內(nèi)容信息塊識別算法，并將其求交，提高了主題內(nèi)容信息塊的識別精確度。上述算法已集成到天網(wǎng)搜索引擎平臺的網(wǎng)頁預(yù)處理模塊中，并且在sewm 2008會議中，以這套算法為框架，組織了主題型網(wǎng)頁識別和網(wǎng)頁主題內(nèi)容信息塊提取兩個中文web信息檢索評測項目。在這套算法的基礎(chǔ)上，基于天網(wǎng)文件系統(tǒng)與map-reduce計算平臺，實現(xiàn)了分布式的網(wǎng)頁塊級別pagerank算法，命名為quarkrank算法。實際檢驗表明，該套算法具有很好的適應(yīng)性與可擴展性，并達(dá)到了很高的精度和召回率。關(guān)鍵詞：網(wǎng)頁分塊 信息提取 sewm 評測

3、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 one, it refines the rules set and achieves a bo

4、ttom-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 and the other is bayes posterior probability est

5、imates, 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 meeting, using these algorithms, we organized tw

6、o 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 reports the distributed block-level pagerank

7、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目錄第 1 章序言3第 2 章相關(guān)研究工作52.1基于語義的網(wǎng)頁信息提取算法52.2基于視覺的

8、網(wǎng)頁分塊算法62.3block level pagerank算法82.3.1block level web graph82.3.2block level pagerank10第 3 章天網(wǎng)搜索引擎quark模塊113.1網(wǎng)頁分塊算法133.2網(wǎng)頁主題內(nèi)容提取163.3算法效果演示18第 4 章sewm2008中文web信息檢索評測234.1評測任務(wù)介紹234.1.1主題型網(wǎng)頁發(fā)現(xiàn)任務(wù)234.1.2網(wǎng)頁內(nèi)容信息發(fā)現(xiàn)任務(wù)244.2評測格式254.3評測結(jié)果254.3.1主題型網(wǎng)頁發(fā)現(xiàn)任務(wù)評測結(jié)果264.3.2網(wǎng)頁內(nèi)容信息發(fā)現(xiàn)任務(wù)評測結(jié)果284.4評測綜述31第 5 章網(wǎng)頁分塊的分布式應(yīng)用325.1

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

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

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

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

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

14、義塊。在這篇論文中，第二章介紹了本文的相關(guān)研究工作，包括常見的網(wǎng)頁分塊和信息提取算法、基于視覺的網(wǎng)頁分塊算法，以及網(wǎng)頁分塊的一個應(yīng)用block level pagerank算法；第三章介紹了我實現(xiàn)的網(wǎng)頁分塊和主題信息提取算法quark算法；第四章介紹了quark算法在sewm2008中文web信息檢索評測項目中的實際檢驗；第五章介紹了在quark算法基礎(chǔ)上實現(xiàn)的一個分布式quarkrank程序。第六章是對本文的總結(jié)和工作展望。第 2 章 相關(guān)研究工作2.1 基于語義的網(wǎng)頁信息提取算法由于對web頁面有效分塊之后可以極大地方便內(nèi)容提取、數(shù)據(jù)挖掘、web結(jié)構(gòu)分析等各項web信息檢索領(lǐng)域的相關(guān)工作，

15、所以早有很多研究人員前赴后繼，就此展開了很多工作。其中，基于語義信息對網(wǎng)頁分塊是最簡便，也最基礎(chǔ)的一種方法。所謂語義信息，通常包括網(wǎng)頁中包含的html標(biāo)簽信息，html dom樹的結(jié)構(gòu)信息，文字內(nèi)容信息，超鏈接信息，以及其他通過統(tǒng)計或?qū)W習(xí)而得到的全局信息等等，也可以理解成為除了網(wǎng)頁中的視覺信息之外的所有可以得到的信息。通?；谡Z義的網(wǎng)頁分塊算法是和后續(xù)的網(wǎng)頁主題內(nèi)容提取結(jié)合在一起的，也就是在網(wǎng)頁分塊的過程中，同時完成了主題內(nèi)容提取的工作，并且主要的注意點是在主題內(nèi)容提取上，因此分塊算法就比較簡單，甚至不顯式地分塊，在此我們統(tǒng)稱它們?yōu)榫W(wǎng)頁信息提取算法。總的來說，網(wǎng)頁信息提取算法可以分為兩類，一類

16、屬于網(wǎng)站級別（site-level），一類屬于網(wǎng)頁級別（page-level），當(dāng)然也有將兩類方法結(jié)合使用的算法。site-level的算法顧名思義，就是分析一個網(wǎng)站或者網(wǎng)頁集內(nèi)部的所有網(wǎng)頁，從中提取反復(fù)出現(xiàn)的模式，而一般來說，在多個網(wǎng)頁里重復(fù)出現(xiàn)的模式（可理解為dom-tree子樹）就是導(dǎo)航欄、廣告等噪音信息了，單個網(wǎng)頁中減去這些信息，剩下的就是主題信息內(nèi)容。關(guān)于site-level的研究一直在繼續(xù)，www2008上就有一篇名為web page sectioning using regex-based template1的論文使用正則表達(dá)式來提取重復(fù)模式，從而更適應(yīng)網(wǎng)頁間的細(xì)微變化，增加了s

17、ite-level的召回率。page-level的算法在處理大型網(wǎng)站的網(wǎng)頁時效率常常不如site-level，但優(yōu)勢在于靈活，不受網(wǎng)頁類型限制。它只利用單個頁面內(nèi)部的信息，當(dāng)然也可能會用到一些全局信息。賓夕法尼亞州立大學(xué)2005年的論文2就是其中的典型。這篇論文提出簡化塊與塊之間的層次結(jié)構(gòu)，直接提取一些原子塊（atomic block），諸如以list, table, link, object, frame, form等為根節(jié)點的html子樹，來完成分塊工作。這一方法雖然簡單而易于實現(xiàn)，但依賴于事先給出的原子塊列表，同時忽略了原子塊之間的嵌套鏈接問題。在分塊之后，它也只是簡單計算了文字長度等幾

18、個變量來決定主題信息塊。合并site-level和page-level的方法也一直有人嘗試。www2007的論文page-level template detection via isotonic smoothing3先利用一個site-level噪音模板提取器來構(gòu)建訓(xùn)練集，然后對所有頁面構(gòu)建dom樹，為各節(jié)點提取分類特征，比如各節(jié)點的文本向量，各節(jié)點中鏈接的平均字?jǐn)?shù)，各節(jié)點中鏈接文字所占比例等，最后利用以上訓(xùn)練集對測試集中每一個dom樹節(jié)點打分，經(jīng)過等壓平滑之后，判定每個dom樹節(jié)點的類型。所以它是典型的先site-level，后page-level的方法。2.2 基于視覺的網(wǎng)頁分塊算法基于

19、語義的網(wǎng)頁分塊算法具有一些無法克服的先天性局限。首先，html語言版本眾多，一直沒有有效統(tǒng)一，而且其語法規(guī)范很松散，一些不符合html規(guī)則的網(wǎng)頁也能被完全識別，所以網(wǎng)頁編寫者在制作網(wǎng)頁時相對隨意，導(dǎo)致web上的很多網(wǎng)頁都沒有完全遵循w3c規(guī)范；其次，ie、firefox等瀏覽器各自為政，對html標(biāo)簽的識別不盡相同，ie甚至還特別為office軟件設(shè)計了特別的html標(biāo)簽以輔助顯示，這些都增加了基于規(guī)則分塊的復(fù)雜性。在實際編程中，就必須得借助一些html規(guī)范工具如tidy等來修正dom樹結(jié)構(gòu)的錯誤，但個別中文網(wǎng)頁仍然存在無法修正的情況。而且dom樹最早引入是為了在瀏覽器中進(jìn)行布局顯示而不是進(jìn)行

20、web頁面的語義結(jié)構(gòu)描述。比如，即使dom樹中兩個結(jié)點具有同一個父結(jié)點，那么這兩個結(jié)點在語義上也不一定就是有聯(lián)系的。反之，兩個在語義上有關(guān)系的結(jié)點卻可能分布在dom樹的不同之處。因此僅僅通過分析dom樹并不能完全獲取web頁面的語義信息，所以依賴于dom樹的啟發(fā)式規(guī)則算法存在先天不足。而基于視覺的網(wǎng)頁分塊算法就彌補了這個不足。它的原理來自于用戶的實際觀察體驗，即用戶并不關(guān)心web頁面的內(nèi)部結(jié)構(gòu)，而是使用一些視覺因素，比如背景顏色、字體顏色和大小、邊框、邏輯塊和邏輯塊之間的間距等等來識別出頁面中的語義塊。因此如果充分的使用web頁面的視覺信息，模擬人眼識別語義塊的過程，并結(jié)合dom樹結(jié)構(gòu)分析進(jìn)行

21、頁面分塊，則可以達(dá)到更好的效果。微軟亞洲研究院在其2003年的論文vips: a vision based page segmentation algorithm4里首次提出了基于視覺的網(wǎng)頁分塊算法vips(vision-based page segmentation)。vips算法充分利用了web頁面的布局特征（見圖1），它有三個主要步驟：首先從dom樹中以較小的粒度提取出所有可視標(biāo)簽塊，并且給每個可視標(biāo)簽塊計算出一個doc（“一致性程度”，degree of coherence）值來描述該塊內(nèi)部內(nèi)容的相關(guān)性。doc的值越大，則表明該塊內(nèi)部的內(nèi)容之間的聯(lián)系越緊密，反之越松散。第二步利用每個可

22、視標(biāo)簽塊的絕對位置和相對位置信息，檢測出它們之間的所有的分割條，包括水平和垂直方向。最后基于這些分割條，利用更多的諸如顏色等視覺信息，重新構(gòu)建web頁面的語義結(jié)構(gòu)。vips算法的優(yōu)點十分明顯，它充分利用了網(wǎng)頁的視覺信息和結(jié)構(gòu)信息，相對于傳統(tǒng)的基于規(guī)則的分塊算法來說，大大提高了分塊的精確度。但vips算法也有其局限性：首先，提取網(wǎng)頁視覺信息代價很高。因為html語言本身并沒有包含足夠的視覺信息，所以網(wǎng)頁真正顯示出來的效果因瀏覽器，因操作系統(tǒng)，甚至因硬件而異。為了得到網(wǎng)頁的完整視覺信息，必須完全下載該網(wǎng)頁所鏈接的css文件，javascript文件，圖片文件等等，然后調(diào)用瀏覽器內(nèi)核代碼渲染這些網(wǎng)頁

23、文件，最后從瀏覽器內(nèi)核代碼的接口中得到每個html標(biāo)簽的視覺信息。整個步驟不僅耗時，而且十分依賴于瀏覽器內(nèi)核代碼。網(wǎng)絡(luò)上看到的一些vips算法實現(xiàn)都是調(diào)用了ie com接口，而微軟自身的實現(xiàn)是利用單獨優(yōu)化后的ie內(nèi)核，他們都是基于windows編程環(huán)境。在linux編程環(huán)境下，可以利用的只有mozilla（firefox）瀏覽器的開源代碼。但mozilla代碼并沒有針對網(wǎng)頁視覺信息提取這一需求給出方便的使用接口，只有在其渲染完網(wǎng)頁之后再截取視覺信息。我們實驗室的毛先領(lǐng)師兄曾經(jīng)研究mozilla代碼，完成了這項艱苦的工作，但實驗表明，提取一個網(wǎng)頁的視覺信息所需時間超過1秒鐘，不能滿足搜索引擎等常

24、規(guī)應(yīng)用的使用要求。其次，vips算法雖能改進(jìn)分塊精確度，但算法相對比較復(fù)雜，迭代輪數(shù)較多，而基于規(guī)則的分塊算法卻只用較少的迭代輪數(shù)。2.3 block level pagerank算法在vips算法的分塊基礎(chǔ)上，微軟2004年的論文block-level link analysis5中提出了block level pagerank(blpr)算法。之前的大多數(shù)鏈接分析算法都是以一個web頁面為web圖中的一個節(jié)點，而blpr算法以網(wǎng)頁中的語義塊為原子節(jié)點，從鏈接結(jié)構(gòu)和頁面結(jié)構(gòu)中提取出page-to-block，block-to-page關(guān)系矩陣，構(gòu)建出新的web語義圖，并以此計算pageran

25、k。實驗表明，blpr改進(jìn)了pagerank的質(zhì)量。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)頁包含有多個語義塊。然后定義兩個矩陣，block-to-page 矩陣z和page-to-block矩陣x。在上述兩個矩陣的基礎(chǔ)之上，可以構(gòu)建兩個web圖模型，即網(wǎng)頁圖gp (vp,ep, wp) 和語義塊圖gb (vb, eb, wb)。對這兩

26、個圖來說，v是節(jié)點集合（節(jié)點分別是網(wǎng)頁和語義塊），e是連接兩個節(jié)點的邊的集合，而w是邊的權(quán)值矩陣。 block-to-page矩陣塊頁（block-to-page）矩陣z的維數(shù)為nk，定義如下： si是block i所鏈接的網(wǎng)頁總數(shù)。zij可以理解成是用戶從block i鏈接到page j的概率。 page-to-block矩陣頁塊（page-to-block）矩陣x的維數(shù)為kn，定義如下：si是page i所包含的block總數(shù)。上面的公式分配給page i中的每一個block以相同的權(quán)值，顯然是過于簡化了，不能區(qū)分block的重要程度。在blpr算法中，采用了一

27、個簡單的block重要度區(qū)分的公式，即用block的文字多少和離整個頁面中心點位置的遠(yuǎn)近來計算block的重要度。每個block包含的文本長度越大，離頁面中心點越近，則越重要。改進(jìn)后的x定義如下：其中f函數(shù)給page i中的每一個block j賦予一個重要度權(quán)值。函數(shù)值越大，則block越重要。在blpr的實現(xiàn)中函數(shù)f的定義如下：其中為正規(guī)化因子，使得對每個page，fp(b)的總和為1。即fp(b)可以理解為是用戶在瀏覽page p的時候，關(guān)注block b的可能性。 page graph傳統(tǒng)的pagerank算法中page graph的權(quán)值矩陣計算十分簡單，如果從page i

28、到page j有鏈接的話，則wp(i,j)為1，反之為0。然而在blpr算法中，page graph需要體現(xiàn)出不同的語義塊的重要程度的不同。也就是說，當(dāng)用戶點擊頁面中的超鏈接時，更偏好選擇重要的語義塊中的url。所以在blpr中，wp的定義為：即。wp(, )可以理解為是從page 開始，以page 中包含的各語義塊為媒介，跳轉(zhuǎn)到page 的概率。 block graphwb的定義為：即。wb(a,b)可以理解為用戶從block a開始，以包含block b的page 為媒介，跳轉(zhuǎn)到block b的概率。2.3.2 block level pagerankblock level

29、pagerank跟pagerank區(qū)別的實質(zhì)在于，pagerank算法基于原始的只有1和0的page graph，而blpr算法基于上面提到的gp。blpr算法的數(shù)學(xué)計算公式如下：其中p為結(jié)果向量，共n維，每一維代表一個網(wǎng)頁的pagerank值。為適配參數(shù)，以1-的概率，用戶在當(dāng)前頁面中隨機選擇一個超鏈接，跳轉(zhuǎn)到該鏈接指向的頁面；以的概率，用戶從所有網(wǎng)頁中隨機選擇一個url并跳轉(zhuǎn)。所以u為nn的轉(zhuǎn)換矩陣，它滿足對所有的i，j，uij = 1/n。而m也是nn的轉(zhuǎn)換矩陣，它是由上面提到的wp權(quán)值矩陣對每一行做歸一化，令每一行的權(quán)值之和為1得到的。p向量的值以馬爾科夫鏈的形式循環(huán)計算下去，直到算法

30、收斂。block level pagerank比單純的pagerank包含了更多的語義信息。因為它的計算基于網(wǎng)頁中各語義塊的重要程度，噪音塊、廣告塊中的超鏈接指向的網(wǎng)頁的重要性顯然不如導(dǎo)航塊、正文塊中的超鏈接所指向的網(wǎng)頁，所以前者會被分配到較少的pagerank值，而后者則被分配到較多的pagerank值。也就是說，網(wǎng)頁中的無關(guān)信息區(qū)域在pagerank的計算過程中起的作用相對較小，所以blpr的效果要優(yōu)于單純的pagerank。第 3 章 天網(wǎng)搜索引擎quark模塊搜索引擎系統(tǒng)一般包括網(wǎng)頁的抓取、預(yù)處理、存儲、索引、檢索等幾個部分，其中預(yù)處理部分的作用是分析、處理原始網(wǎng)頁數(shù)據(jù)如去除網(wǎng)頁噪音，

31、消除重復(fù)網(wǎng)頁，計算pagerank，中文切詞等等，并為后繼模塊提供統(tǒng)一的數(shù)據(jù)訪問接口，規(guī)范數(shù)據(jù)管理，避免重復(fù)計算。同時在天網(wǎng)搜索引擎平臺中，基于功能擴展和實驗室內(nèi)部其他相關(guān)研究的需要，必須將對原始網(wǎng)頁的處理部分單獨出來，從而方便模塊復(fù)用，統(tǒng)一代碼管理，減少重復(fù)勞動。在天網(wǎng)搜索引擎平臺的搭建過程中，也包括了抓取、存儲、分析（預(yù)處理）、索引、檢索等模塊，其中的分析模塊接受成批量原始網(wǎng)頁的輸入，然后對每個網(wǎng)頁調(diào)用quark模塊，進(jìn)行網(wǎng)頁分塊、信息提取等工作，最后將處理后的數(shù)據(jù)存成twdocview格式，再提供給下游模塊。我的畢業(yè)設(shè)計的主要工作，就是圍繞quark模塊而展開。從上面的介紹中可以看出，天

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

33、統(tǒng)一的代碼規(guī)范。2、獨立性。在我們實驗室內(nèi)部，除了搜索引擎之外，還有web數(shù)據(jù)挖掘，map-reduce應(yīng)用等相關(guān)工作也可能需要使用對單個網(wǎng)頁的處理和數(shù)據(jù)提取程序。因此quark模塊必須能獨立于搜索引擎代碼之外單獨編譯運行，并且方便他人調(diào)用這部分代碼。基于上述兩個特點，我初步實現(xiàn)了quark模塊。該模塊的類結(jié)構(gòu)圖如下：1、圖中右下及中間藍(lán)色的部分為quark模塊的核心功能類，包括quarktree、quarkelement、quarkrecognizer、quarkanalyzer等四個類。quarktree類的作用有兩個，一個是以原始網(wǎng)頁為輸入，建立html的dom tree；另一個是存儲分

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

35、類，包括quarkevaluation和quarkhtmlbuilder兩個類。quarkevaluation類是評測類，用來評測quark核心類的實現(xiàn)效果。當(dāng)前實現(xiàn)的是對網(wǎng)頁正文信息提取的評測，評測需要接受人工標(biāo)記的網(wǎng)頁或網(wǎng)頁集為輸入。評測算法的細(xì)節(jié)見后文。quarkhtmlbuilder類是演示類，用來查看quark模塊各步驟的實現(xiàn)效果。目前可以查看網(wǎng)頁分塊的效果，也可以查看主題信息提取的效果。3、最上面黃色的部分為quark模塊的應(yīng)用類，包括quarkrank、quarkduplicate、quarkclassification等，它們都是利用分好的網(wǎng)頁塊實現(xiàn)的一些算法，比如基于quar

36、k的pagerank算法，基于quark的網(wǎng)頁消重算法，以及基于quark的網(wǎng)頁分類算法。4、左下方灰色的部分為quark模塊依賴的外部類接口，包括中文切詞類chinesetokenizer，以及圖中沒有的編碼轉(zhuǎn)換類codeconvert等等。5、中下部紅色的部分為quark模塊直接的下游模塊，包括twdocview類和twmd5類。3.1 網(wǎng)頁分塊算法算法主體在quarkrecognizer類中。參見在第二章相關(guān)研究里提到的，除了基于視覺的算法之外，大部分基于語義的算法都是利用html標(biāo)簽及其包含的文字信息的特性來給網(wǎng)頁分塊的。并且由于大多數(shù)論文的著重點在于分塊后的內(nèi)容提取上，所以對分塊算法

37、本身著墨不多。綜合各篇論文里提到的分塊方法，我設(shè)計實現(xiàn)了quarkrecognizer算法。這一算法首先的一大特點就是實用性強。所謂實用性強是指適合在實際系統(tǒng)中使用，效率高，定義完整。我詳細(xì)分析了w3c制定的html4.01格式規(guī)范，將所有規(guī)范的html標(biāo)簽根據(jù)quarkrecognizer算法的需要分類，完整地列出了所有對網(wǎng)頁分塊起重要作用的標(biāo)簽，而不是像所有已有論文那樣僅僅象征性地列舉出幾個html標(biāo)簽。分類后的詳細(xì)html標(biāo)簽清單如下：1、超級標(biāo)簽（super tag，簡稱為s型標(biāo)簽）：這種標(biāo)簽可以被直接認(rèn)定是一個網(wǎng)頁塊的根標(biāo)簽，在算法過程中一旦遇到這種標(biāo)簽，就可以直接將其加入網(wǎng)頁塊池。

38、包括：head, script, style, object, fieldset, frameset, iframe2、大標(biāo)簽（big tag，簡稱為b型標(biāo)簽）：這種標(biāo)簽通常都代表一個網(wǎng)頁塊，只不過有時其內(nèi)部內(nèi)容過少，需要跟其他節(jié)點合并成一個網(wǎng)頁塊，或者在特殊情況下其內(nèi)部沒有可見字符。所以在算法過程中，遇到這種標(biāo)簽，就判斷其單獨作為一個網(wǎng)頁塊的條件是否已經(jīng)成熟，如成熟，則將其加入網(wǎng)頁塊池。包括：div, td, table, form, fieldset, center, noframes, noscript, pre, body, html這里需要注意的是像body，html兩個標(biāo)簽也作為b

39、型標(biāo)簽，原因是這樣可以防止分塊之后網(wǎng)頁內(nèi)部文字信息的遺漏，因為最終即使有遺漏，也會至少包含在html這個最后把關(guān)的門神標(biāo)簽手中。3、排版標(biāo)簽（layout tag，簡稱為l型標(biāo)簽）：這種標(biāo)簽?zāi)苡绊懙骄W(wǎng)頁的顯示效果，改變文字布局。如果一顆html子樹中包含多個l型標(biāo)簽，則該子樹單獨成塊的可能性增加。包括：p, ul, ol, dl, dir, li, dt, blockquote, address,br, hr, col, colgroup, img, menu, select4、顯示標(biāo)簽（display tag，簡稱為d型標(biāo)簽）：這種標(biāo)簽數(shù)量最多，都是對文字的顯示方式做微幅的調(diào)整，如改變字體、

40、顏色、粗細(xì)等等。由于它們的存在與否不改變網(wǎng)頁布局，所以不影響網(wǎng)頁分塊。包括：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, textarea, u, tt, var, o:smarttagtype5、附屬標(biāo)簽（affil

41、iated tag，簡稱為a型標(biāo)簽）：這種標(biāo)簽從屬與上述四種標(biāo)簽的某一種，同時有些也出現(xiàn)在了前面四種里面。由于它們一般不單獨出現(xiàn)，對網(wǎng)頁布局的影響體現(xiàn)在了其屬主標(biāo)簽中，所以在quarkrecognizer算法中也不予考慮。包括：frame, input, isindex, legend, link, map, meta, option, optgroup, param, td, th, tr, tbody, title6、定制標(biāo)簽（customized tag，簡稱為c型標(biāo)簽）：因為不同的應(yīng)用中，對網(wǎng)頁分塊會有些不同的要求。比如我們實驗室的webdigest小組在進(jìn)行新聞網(wǎng)頁的數(shù)據(jù)挖掘的工作中

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

43、ml根節(jié)點時，算法結(jié)束，網(wǎng)頁分塊完畢。quarkrecognizer算法的核心偽碼如下：_ algorithm quarkrecognizer (domtree tree，taglist ctype) input : 某單個網(wǎng)頁構(gòu)建的domtree，定制標(biāo)簽(c型)節(jié)點列表begin 1 用domtree的葉子節(jié)點，也就是文字節(jié)點建立一個當(dāng)前節(jié)點隊列，開始自底向上遍歷。2 取當(dāng)前節(jié)點隊列的第一個節(jié)點。3 如果遇到s型節(jié)點，則立即將此節(jié)點加入網(wǎng)頁塊池。4 如果遇到c型節(jié)點，則立即將此節(jié)點加入網(wǎng)頁塊池。5 如果遇到b型節(jié)點，則判斷該節(jié)點內(nèi)部的文字長度是否已超過閾值，或者該節(jié)點內(nèi)部的l型節(jié)點比例是否

44、超過閾值，如果滿足上述兩個條件之一，則將此節(jié)點加入網(wǎng)頁塊池；否則將其內(nèi)部文字長度信息和自身信息向父節(jié)點傳遞，然后將父節(jié)點加入當(dāng)前節(jié)點隊列，回到2。6 如果遇到l型節(jié)點，則將其內(nèi)部文字長度信息和其自身信息向父節(jié)點傳遞，然后將父節(jié)點加入當(dāng)前節(jié)點隊列，回到2。7 如果遇到d型或a型節(jié)點，則將其內(nèi)部文字長度信息向父節(jié)點傳遞，然后將父節(jié)點加入當(dāng)前節(jié)點隊列，回到2。8 當(dāng)前節(jié)點隊列為空時，遍歷結(jié)束，算法終止。end_ 網(wǎng)頁塊池中的網(wǎng)頁塊是以quarkelement的格式存儲，而quarkelement類中包括原來的html子樹的domtree結(jié)構(gòu)和其他相關(guān)信息，同時在上述遍歷的過程中，即使有的網(wǎng)頁塊從ht

45、ml結(jié)構(gòu)上來說包含在更高層的網(wǎng)頁塊之下，但在quarkelement中也消除了包含關(guān)系，所有網(wǎng)頁塊都互相獨立，互不包含。3.2 網(wǎng)頁主題內(nèi)容提取算法主體在quarkanalyzer類中。采用了基于規(guī)則和基于bayes的語義分析相交的方法，也就是分別用基于文本相似度的方法和基于bayes的方法判斷每個網(wǎng)頁塊的類型（是不是主題塊），然后對它們求交集，只有兩個方法共同認(rèn)定的主題內(nèi)容塊才能最終被認(rèn)定。quarkanalyzer算法的核心偽碼如下：_ 第一步，基于文本相似度的方法：1、首先，把所有網(wǎng)頁塊中，文本長度最大的那個網(wǎng)頁塊判定為主題內(nèi)容塊。2、然后用其余網(wǎng)頁塊逐個與最大的網(wǎng)頁塊比較文本相似度。文

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

47、法共同判定的主題內(nèi)容塊即為最后認(rèn)定的主題內(nèi)容塊。_ 其中bayes方法的各先驗概率事先用手工標(biāo)記的樣本網(wǎng)頁計算得到，結(jié)果如下：在該網(wǎng)頁塊為主題內(nèi)容塊的條件下，# 該塊中包含定制標(biāo)簽的概率p1_costomizedtag = 0.29;# 該塊中包含常見噪音詞并且文本長度小于100的概率p1_noise = 0.04;# 該塊中每10個字符中的標(biāo)點符號數(shù)大于0.3的概率p1_punctuationscale = 0.85; # 該塊中標(biāo)點符號總數(shù)大于4的概率p1_punctuation = 0.77# 該塊中非錨接文本的長度大于200的概率p1_size = 0.84# 該塊中鏈接數(shù)量大于20的

48、概率p1_linknum = 0.10; # 該塊中錨接文本和非錨接文本的長度之比大于0.3p1_scale = 0.08;在該網(wǎng)頁塊為非主題內(nèi)容塊的條件下，# 該塊中包含定制標(biāo)簽的概率p2_costomizedtag = 0.01;# 該塊中包含常見噪音詞并且文本長度小于100的概率p1_noise = 0.45;# 該塊中每10個字符中的標(biāo)點符號數(shù)大于0.3的概率p2_punctuationscale = 0.25; # 該塊中標(biāo)點符號總數(shù)大于4的概率p2_punctuation = 0.34# 該塊中非錨接文本的長度大于200的概率p2_size = 0.06# 該塊中鏈接數(shù)量大于20的

49、概率p2_linknum = 0.71; # 該塊中錨接文本和非錨接文本的長度之比大于0.3p2_scale = 0.85;網(wǎng)頁塊為主題內(nèi)容塊的概率：p_iscontent = 0.16;網(wǎng)頁塊為非主題內(nèi)容塊的概率：p_isnoise = 1 - p_iscontent;3.3 算法效果演示為了檢驗上述算法的效果，除了下一章會提到的評測程序外，還可以用quarkhtmlbuilder類所編寫的演示程序以及自搭的apache服務(wù)器上的python腳本來查看網(wǎng)頁分塊后和主題信息提取后的效果。限于篇幅，這里就不再詳細(xì)介紹算法的細(xì)節(jié)，但是附有幾張對照圖片，以利說明。第一幅圖：這是用python腳本寫的

50、一個在瀏覽器上查看網(wǎng)頁主題內(nèi)容提取效果的demo，可以選擇用pagemodel的算法（即quark模塊），也可以選擇用sitemodel的算法，點擊submit按鈕，就可以出現(xiàn)手工標(biāo)記的主題內(nèi)容，和程序判斷的主題內(nèi)容的對比畫面。由于時間關(guān)系，該demo比較粗糙，沒有過多修飾。submit后的效果圖見后面的第五幅圖。第一幅圖：這是從新浪網(wǎng)上保存的一個新聞網(wǎng)頁。顯然，其主題內(nèi)容信息塊應(yīng)該是屏幕中左部的大塊文字內(nèi)容。在處理這種類型的新聞網(wǎng)頁時，算法的效率很高，但事實上，quark模塊還可以處理更復(fù)雜的網(wǎng)頁類型。第二幅圖：這是網(wǎng)頁分塊之后的示意圖。從圖中可以看出，紅色、綠色、紫色的網(wǎng)頁塊間雜排列，就像

51、地圖一樣，每一種顏色表示一個被識別出的網(wǎng)頁塊。圖中沒有顏色，依舊是藍(lán)色的鏈接色的部分是新浪網(wǎng)動態(tài)生成的內(nèi)容，在html源代碼中并不存在，所以沒有被標(biāo)上字體顏色。第三幅圖：這是網(wǎng)頁正文提取之后的示意圖。圖中紅色的部分為quarkanalyzer識別的正文內(nèi)容，綠色部分為其識別的相關(guān)鏈接，其余紫色部分為噪音內(nèi)容。從圖中可以看出，就這個網(wǎng)頁而言，網(wǎng)頁主題內(nèi)容的提取基本成功了。第五幅圖：這是第一幅圖所示demo的結(jié)果界面截圖，可見，圖片上方是手工標(biāo)注的文字內(nèi)容，共720個字符。圖片下方是程序生成的文字內(nèi)容，共628個字符。兩部分內(nèi)容大致相等，說明網(wǎng)頁主題內(nèi)容提取成功。第 4 章 sewm2008中文w

52、eb信息檢索評測 4.1 評測任務(wù)介紹sewm中文web信息檢索評測6是由北京大學(xué)網(wǎng)絡(luò)實驗室主辦的中文web檢索評測項目，自2004年起，在sewm會議中已連續(xù)舉辦了五屆，今年（2008年）是第五屆。其目標(biāo)在于為中文信息檢索領(lǐng)域的研究人員提供一個標(biāo)準(zhǔn)的評測平臺，希望在國內(nèi)外各個研究小組的共同參與下建立并完善以中文為主的網(wǎng)頁測試集cwt(chinese web test collection)，解決支持中文web研究的基礎(chǔ)設(shè)施建設(shè)和應(yīng)用中的基本方法與關(guān)鍵技術(shù)，一起推動中文web信息檢索技術(shù)的發(fā)展。sewm2008中文web信息檢索評測有三個任務(wù)： 主題型網(wǎng)頁發(fā)現(xiàn)和網(wǎng)頁內(nèi)容信息塊發(fā)現(xiàn)，非網(wǎng)頁數(shù)字資

53、源分類和垃圾郵件過濾，其中前兩個任務(wù)主要由何靖師兄設(shè)計，由我處理各參賽隊伍提交的數(shù)據(jù)并給出評測結(jié)果。本屆評測采用的數(shù)據(jù)集是cwt70th。文檔集數(shù)據(jù)格式參見7。 由于本次評測任務(wù)的設(shè)計和上文提到的天網(wǎng)quark模塊關(guān)系密切，評測所使用的程序就是天網(wǎng)quark模塊中quarkevaluation類的python版本的代碼，同時天網(wǎng)quark模塊的一個稍早期版本也參加了第二個任務(wù)關(guān)于網(wǎng)頁主題內(nèi)容的評測，所以也可以作為天網(wǎng)quark模塊的一個實驗結(jié)果，檢驗第三章提到的算法的效率。4.1.1 主題型網(wǎng)頁發(fā)現(xiàn)任務(wù)主題型網(wǎng)頁是指通過文字描述了一件或多件事物，具有一定主題的網(wǎng)頁。如一張具體的新聞網(wǎng)頁就是典型

54、的主題型網(wǎng)頁。下面是對主題型網(wǎng)頁的一個補充定義：1、僅由圖片，flash，網(wǎng)絡(luò)視頻等構(gòu)成主題塊的網(wǎng)頁，除非亦包括獨立成段的文字性描述信息，否則不屬于主題型網(wǎng)頁。2、某些導(dǎo)航型網(wǎng)頁，如同類軟件下載網(wǎng)頁中，雖然對每個鏈接都使用了適量文字來介紹，從而文字比例比較高，但也應(yīng)該算作非主題型網(wǎng)頁。3、錯誤網(wǎng)頁，空網(wǎng)頁，垃圾網(wǎng)頁，spam網(wǎng)頁等屬于非主題型網(wǎng)頁。4、論壇、博客網(wǎng)頁屬于主題型網(wǎng)頁，但沒有主貼，只包括無意義回復(fù)語句的網(wǎng)頁屬于非主題型網(wǎng)頁。任務(wù)評測根據(jù)準(zhǔn)確度、召回率和macro-f1三個指標(biāo)，它們的定義如下：4.1.2 網(wǎng)頁內(nèi)容信息發(fā)現(xiàn)任務(wù)在一個主題型的網(wǎng)頁中， 一般會包括主題內(nèi)容信息，噪音信息，和相關(guān)鏈接信息。本項任務(wù)的目的在于找出主題型網(wǎng)頁中的主題內(nèi)容信息。噪音信息定義：a. 與網(wǎng)頁主旨內(nèi)容不相關(guān)的信息b. 由網(wǎng)站提供的內(nèi)容模板信息c. 廣告信息d. 腳本程序信息相關(guān)鏈接定義：指向與本網(wǎng)頁相關(guān)網(wǎng)頁的鏈接，如新聞網(wǎng)頁下方的相關(guān)新聞鏈接。補充定義：1、 新聞網(wǎng)頁的內(nèi)容信息應(yīng)包括出現(xiàn)在頁面里的標(biāo)題，時間，通訊社，記者