【正文】 es 的語(yǔ)義分析相交的方法，也就是分別用基于文本相似 度的方法和基于 Bayes 的方法判斷每個(gè)網(wǎng)頁(yè)塊的類型（是不是主題塊），然后對(duì)它們求交集，只有兩個(gè)方法共同認(rèn)定的主題內(nèi)容塊才能最終被認(rèn)定。 END _________________________________________________________________ 網(wǎng)頁(yè)塊池中的網(wǎng)頁(yè)塊是以 QuarkElement 的格式存儲(chǔ)，而 QuarkElement 類中包括原來(lái)的 html 子樹(shù)的 DomTree 結(jié)構(gòu)和其他相關(guān)信息，同時(shí)在上述遍歷的過(guò)程中，即使有的網(wǎng)頁(yè)塊從 html 結(jié)構(gòu)上來(lái)說(shuō)包含在更高層的網(wǎng)頁(yè)塊之下，但在QuarkElement 中也消除了包含關(guān)系，所有網(wǎng)頁(yè)塊都互相獨(dú)立，互不包含。 7 如果遇到 D 型或 A 型節(jié)點(diǎn)，則將其內(nèi)部文字長(zhǎng)度信息向父節(jié)點(diǎn)傳遞，然后將父節(jié)點(diǎn)加入當(dāng)前節(jié)點(diǎn)隊(duì)列，回到 2。 5 如果遇到 B 型節(jié)點(diǎn)，則判斷 該節(jié)點(diǎn)內(nèi)部的文字長(zhǎng)度是否已超過(guò)閾值，或者該節(jié)點(diǎn)內(nèi) 部的 L 型節(jié)點(diǎn)比例是否超過(guò)閾值，如果滿足上述兩個(gè)條件之一，則將此節(jié)點(diǎn)加入網(wǎng)頁(yè)塊池 ；否則將其內(nèi)部文字長(zhǎng)度信息和自身信息向父節(jié)點(diǎn)傳遞，然后將父節(jié)點(diǎn)加入當(dāng)前節(jié)點(diǎn)隊(duì)列，回到 2。 3 如果遇到 S 型節(jié)點(diǎn)，則立即將此節(jié)點(diǎn)加入網(wǎng)頁(yè)塊池。 QuarkRecognizer 算法的核心偽碼如下： _________________________________________________________________ ALGORITHM QuarkRecognizer (DomTree tree， TagList CType) INPUT : 某單個(gè)網(wǎng)頁(yè)構(gòu)建的 DomTree，定制標(biāo)簽 (C 型 )節(jié)點(diǎn)列表 BEGIN 1 用 DomTree 的葉子節(jié)點(diǎn)，也就是文字節(jié)點(diǎn) 建立 一個(gè) 當(dāng)前 節(jié)點(diǎn) 隊(duì)列 ，開(kāi)始自底向上遍歷。所以我添加了定制標(biāo)簽，由用戶指定，它可以是普通的標(biāo)簽如“ TITLE”等，也可以是正則表達(dá)式，凡是其內(nèi)部文字滿足該正則表達(dá)式的 S 型、 B 型和 L 型標(biāo)簽，都將 被單獨(dú)提取為網(wǎng)頁(yè)塊。 包括： FRAME, INPUT, ISINDEX, LEGEND, LINK, MAP, META, OPTION, OPTGROUP, PARAM, TD, TH, TR, TBODY, TITLE 定制標(biāo)簽（ Customized Tag，簡(jiǎn)稱為 C 型標(biāo)簽）： 因?yàn)椴煌膽?yīng)用中，對(duì)網(wǎng)頁(yè)分塊會(huì)有些不同的要求。包括： 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:SMARTTAGTYPE 附屬標(biāo)簽（ Affiliated Tag， 簡(jiǎn)稱為 A 型標(biāo)簽 ） ： 這種標(biāo)簽 從屬與上述四種標(biāo)簽的某一種， 同時(shí)有些也出現(xiàn)在了前面四種里面。 包括： P, UL, OL, DL, DIR, LI, DT, BLOCKQUOTE, ADDRESS, BR, HR, COL, COLGROUP, IMG, MENU, SELECT 顯示標(biāo)簽（ Display Tag，簡(jiǎn)稱為 D 型標(biāo)簽）： 這種標(biāo)簽 數(shù)量最多，都是對(duì)文字的顯示方式做微幅的調(diào)整，如改變字體、顏色、粗細(xì)等等。 排版標(biāo)簽（ Layout Tag，簡(jiǎn)稱為 L 型標(biāo)簽）： 這種標(biāo)簽 能影響到網(wǎng)頁(yè)的顯示效果，改變文字布局。 所以在算法過(guò)程中，遇到這種標(biāo)簽，就判斷其單獨(dú)作為一個(gè)網(wǎng)頁(yè)塊的條件是否已經(jīng)成熟，如成熟，則將其加入網(wǎng)頁(yè)塊池。 分類后的詳細(xì) html 標(biāo)簽清單如下： 超級(jí) 標(biāo)簽 （ Super Tag， 簡(jiǎn)稱為 S 型標(biāo)簽） ： 這種標(biāo)簽 可以被直接認(rèn)定是一個(gè)網(wǎng)頁(yè)塊的根標(biāo)簽 ，在 算法過(guò)程中一旦遇到這種標(biāo)簽，就可以直接將其加 入 網(wǎng)頁(yè) 塊池。 所謂實(shí)用性強(qiáng)是指適合在實(shí)際系統(tǒng)中使用，效率高，定義完整。 綜合各篇論文里提到的分塊方法， 我設(shè)計(jì)實(shí)現(xiàn)了 QuarkRecognizer 算法。 參見(jiàn)在第二章相關(guān)研究里提到的，除了基于視覺(jué)的算法之外，大部分基于語(yǔ)義的算法都是利用 html 標(biāo)簽 及其包含的文字信息 的特性 來(lái)給網(wǎng)頁(yè)分塊的。 中下部紅色的部分為 Quark 模塊直接的下游模塊，包括 TwDocView 類 和TwMd5 類 。 最上面黃色的部分為 Quark 模塊的應(yīng)用類 ，包括 QuarkRank、QuarkDuplicate、 QuarkClassification 等 ，它們都是利用分好的網(wǎng)頁(yè)塊實(shí)現(xiàn)的一些算法，比如基于 Quark 的 PageRank 算法，基于 Quark 的網(wǎng)頁(yè)消重算法，以及基于 Quark 的網(wǎng)頁(yè)分類算法。 QuarkHtmlBuilder類 是 演示類， 用來(lái)查看 Quark模塊各步驟的實(shí)現(xiàn)效果。當(dāng)前實(shí)現(xiàn)的是對(duì)網(wǎng)頁(yè)正文信息提取的評(píng)測(cè)，評(píng)測(cè)需要接受人工標(biāo)記的網(wǎng)頁(yè)或網(wǎng)頁(yè)集為輸入。 中上部 綠色的部分為 Quark 模塊的評(píng)測(cè)和演示類，包括 QuarkEvaluation和 QuarkHtmlBuilder 兩個(gè)類。 QuarkAnalyzer 類 依賴于 QuarkRecognizer 類 ， 它在分好的塊的基礎(chǔ)上，判斷各個(gè)塊的類型，提取正文信息。 QuarkRecognizer 類 肩負(fù)網(wǎng)頁(yè)分塊的重任，從網(wǎng)頁(yè)中識(shí)別出所有語(yǔ)義塊。 QuarkTree 類 的作用 有兩個(gè)，一個(gè)是 以原始網(wǎng)頁(yè)為輸入， 建立 Html 的Dom Tree；另一個(gè)是存儲(chǔ) 分好的網(wǎng)頁(yè)塊 （在我們的系統(tǒng)中，每一個(gè)網(wǎng)頁(yè)塊就叫做一個(gè) Quark） 并記錄 Quark 與 Quark 之間的組織架構(gòu)。 基于上述兩個(gè)特點(diǎn) ，我初步實(shí)現(xiàn)了 Quark 模塊。 在我們實(shí)驗(yàn)室內(nèi)部，除了搜索引擎之外，還有 Web 數(shù)據(jù)挖掘， Mapreduce應(yīng)用等相關(guān)工作也可能需要使用對(duì)單個(gè)網(wǎng)頁(yè)的處理和數(shù)據(jù)提取程序。 而正由于 Quark 模塊的可擴(kuò)展性要求，所以它的代碼的可閱讀性也十分重要，在編寫的過(guò)程中，我盡量 注意了這一點(diǎn) ，遵守 了我們統(tǒng)一的代碼規(guī)范 。 同時(shí)由于實(shí)驗(yàn)室人員的不固定性，代碼的維護(hù)十分重要。 因?yàn)樗阉饕媸且粋€(gè)比較 龐大的系統(tǒng)， 并且一直在不停的有新算法，新需求的加入，所以對(duì)數(shù)據(jù)的要求也會(huì)一直變化。 我的畢業(yè)設(shè)計(jì)的主要工作，就是圍繞 Quark模塊而展開(kāi)。同時(shí) 在天網(wǎng)搜索引擎平臺(tái)中，基于功能擴(kuò)展和實(shí)驗(yàn)室內(nèi)部其他相關(guān)研究的需要， 必須將對(duì)原始網(wǎng)頁(yè)的處理部分單獨(dú)出來(lái)，從而方便模塊復(fù)用，統(tǒng)一代碼管理，減少重復(fù)勞動(dòng)。也就是說(shuō)，網(wǎng)頁(yè)中的無(wú)關(guān)信息區(qū)域在 PageRank 的計(jì)算過(guò)程中起的作用相對(duì)較小 ， 所以 BLPR 的效果要優(yōu)于單純的 PageRank。 Block Level PageRank 比單純的 PageRank 包含了更多的語(yǔ)義信息。 而 M也是 n n 的轉(zhuǎn)換矩陣，它是由上面提到的 WP權(quán)值矩陣對(duì)每一行做歸一化，令每一行的權(quán)值之和為 1 得到的。 ε為適配參數(shù)， 以 1ε的概率，用戶在當(dāng)前頁(yè)面中隨機(jī)選擇一個(gè)超鏈接，跳轉(zhuǎn)到 該鏈接指向的 頁(yè)面；以 ε 的概率，用戶 從所有網(wǎng)頁(yè)中隨機(jī) 選擇一個(gè) URL并跳轉(zhuǎn)。 Block Level PageRank Block Level PageRank 跟 PageRank 區(qū)別的實(shí)質(zhì)在于， PageRank 算法基于 原始 的 只有 1 和 0 的 Page Graph，而 BLPR 算法基于 上面提到的 GP。 Block Graph WB的定義為： 即 BW ZX? 。所以在 BLPR 中， WP的定義為： 即 PW XZ? 。然而在 BLPR 算法中， Page Graph需要體現(xiàn)出不同的語(yǔ)義塊的重要程度的不同。 即 fp(b)可以理解為是用戶在瀏覽 page p 的時(shí)候，關(guān)注 block b 的可能性。函數(shù)值越大，則 block 越重要。每個(gè) block包含的文本長(zhǎng)度越大， 離 頁(yè)面中心點(diǎn)越近，則越重要。上面的公式分配給 page i 中的每一個(gè)block 以相同的權(quán)值，顯然是過(guò)于簡(jiǎn)化了，不能區(qū)分 block 的重要程度。 Zij可以理解成是用戶從 block i 鏈接到page j 的概率。對(duì)這兩個(gè)圖來(lái)說(shuō)， V 是節(jié)點(diǎn)集合（節(jié)點(diǎn)分別是網(wǎng)頁(yè)和語(yǔ)義塊）， E 是連接兩個(gè)節(jié)點(diǎn)的邊的集合，而 W 是邊的權(quán)值矩陣。 然后定義兩個(gè)矩陣， blocktopage 矩陣 Z 和pagetoblock 矩陣 X。對(duì)每個(gè)語(yǔ)義塊來(lái)說(shuō)，只有一個(gè)網(wǎng)頁(yè)包含它， bi ∈ pj 意味著語(yǔ)義塊 i 包含于網(wǎng)頁(yè) j。 P 為所有網(wǎng)頁(yè)的集合， P = {p1, p2, …, pk}， k 為網(wǎng)頁(yè)總數(shù)。實(shí)驗(yàn)表明， BLPR改進(jìn)了 PageRank的質(zhì)量。 Block Level PageRank 算法 在 VIPS 算法的分塊基礎(chǔ)上，微軟 2021 年的論文 Blocklevel Link Analysis[5]中提出了 Block Level PageRank(BLPR)算法。 我們實(shí)驗(yàn)室的毛先領(lǐng)師兄曾經(jīng) 研究 Mozilla 代碼，完成了這項(xiàng)艱苦的工作，但實(shí)驗(yàn)表明，提取一個(gè)網(wǎng)頁(yè)的視覺(jué)信息所需時(shí)間超過(guò) 1 秒鐘，不能 滿足搜索引擎等常規(guī)應(yīng)用的使用要求。在 Linux 編程環(huán)境下，可以利用的只有 Mozilla（ Firefox）瀏覽器 的開(kāi)源代碼。 整個(gè)步 驟不僅耗時(shí)，而且十分依賴于瀏覽器內(nèi)核代碼。因?yàn)?HTML 語(yǔ)言本身并沒(méi)有包含足夠的視覺(jué)信息，所以網(wǎng)頁(yè)真正顯示出來(lái)的效果因?yàn)g覽器，因操作系統(tǒng)，甚至因硬件而異。 VIPS 算法的優(yōu)點(diǎn)十分明顯，它充分利用了網(wǎng)頁(yè)的視覺(jué)信息和結(jié)構(gòu)信息，相對(duì)于傳統(tǒng)的基于規(guī)則的分塊算法來(lái)說(shuō)，大大提高了分塊的精確度。 第二步利用每個(gè)可視標(biāo)簽塊 的絕對(duì) 位置 和相對(duì)位置信息 ， 檢測(cè)出它們之間的所有的分割條，包括水平和垂直方向。 VIPS 算法充分利用了 Web 頁(yè)面的布局特征 （見(jiàn)圖 1） ， 它 有三個(gè)主要步驟： 首先從 DOM 樹(shù)中 以較小的粒度 提取出 所有可視標(biāo)簽塊 ， 并且給每個(gè)可視標(biāo)簽塊計(jì)算出一個(gè) DOC（“ 一致性程度 ”， Degree of Coherence） 值來(lái)描述該塊內(nèi)部?jī)?nèi)容的相關(guān)性。因此如果充分的使用 Web 頁(yè)面的視覺(jué) 信息 ， 模擬人眼識(shí)別語(yǔ)義塊的過(guò)程， 并結(jié)合 DOM 樹(shù) 結(jié)構(gòu)分析進(jìn)行 頁(yè)面 分塊，則可以 達(dá)到更好的效果。 而基于視覺(jué)的網(wǎng)頁(yè)分塊算法就彌補(bǔ)了這個(gè)不足。反之，兩個(gè)在語(yǔ)義上有關(guān)系的結(jié)點(diǎn)卻可能分布在 DOM 樹(shù)的不同之處。而且 DOM 樹(shù)最早引入是為了在瀏覽器中進(jìn)行布局顯示而不是進(jìn)行 Web 頁(yè)面的語(yǔ)義結(jié)構(gòu)描述。首先， HTML語(yǔ)言版本眾多，一直沒(méi)有有效統(tǒng)一，而且其語(yǔ)法規(guī)范很松散，一些不符合 HTML規(guī)則的網(wǎng)頁(yè)也能被完全識(shí)別，所以網(wǎng)頁(yè)編寫者在制作網(wǎng)頁(yè)時(shí)相對(duì)隨意，導(dǎo)致 Web上的很多網(wǎng)頁(yè)都沒(méi)有完全遵循 W3C 規(guī)范；其次， IE、 Firefox 等瀏覽器各自為政，對(duì) HTML 標(biāo)簽的識(shí)別不盡相同， IE 甚至還特別為 Office 軟件設(shè)計(jì)了特別的 html標(biāo)簽 以輔助顯示，這些都增加了基于規(guī)則分塊的復(fù)雜性。所以它是典型的先 SiteLevel，后PageLevel 的方法。 合并 SiteLevel 和 PageLevel 的方法也一直有人嘗試。 這一方法雖然簡(jiǎn)單而易于實(shí)現(xiàn)，但 依賴于事先給出的原子塊列表，同時(shí)忽略了原子塊之間的嵌套鏈接問(wèn)題。 賓夕法尼亞州立大學(xué) 2021 年的論文 [2]就是其中的典型。 PageLevel 的算法在處理大型網(wǎng)站的網(wǎng)頁(yè)時(shí)效率常常不如 SiteLevel，但優(yōu)勢(shì)在于靈 活，不受網(wǎng)頁(yè)類型限制。 SiteLevel 的算法顧名思義，就是分析 一個(gè)網(wǎng)站或者網(wǎng)頁(yè)集內(nèi)部的所有網(wǎng)頁(yè)，從中提取反復(fù)出現(xiàn)的 模式 ， 而一 般來(lái)說(shuō)，在多個(gè)網(wǎng)頁(yè)里重復(fù)出現(xiàn)的模式（可理解為 DomTree 子樹(shù)） 就是導(dǎo)航欄、廣告等噪音信息了，單個(gè)網(wǎng)頁(yè)中減去這些信息，剩下的就是主題信息內(nèi)容。 通 常基于語(yǔ)義的網(wǎng)頁(yè)分塊算法是和后續(xù)的網(wǎng)頁(yè)主題內(nèi)容提取結(jié)合在一起的，也就是在網(wǎng)頁(yè)分塊的過(guò)程中，同時(shí)完成了主題內(nèi)容提取的工 作，并且主要的注意點(diǎn)是在主題內(nèi)容提取上，因此分塊算法就比較簡(jiǎn)單，甚至不顯式地分塊， 在此我們統(tǒng)稱它們?yōu)榫W(wǎng)頁(yè)信息提取算法。其中，基于語(yǔ)義信息對(duì)網(wǎng)頁(yè)分塊是最簡(jiǎn)便 ， 也最基礎(chǔ)的一種方法。 第六章是對(duì)本文的 總結(jié)和工作展望。比如類似于新聞人物追蹤和歷史新聞檢索等應(yīng)用，出于節(jié)約存儲(chǔ)空間，提高檢索精度，方 便更新等目的，可以直接存儲(chǔ)和操作網(wǎng)頁(yè)中的主題內(nèi)容語(yǔ)義塊，而舍棄網(wǎng)頁(yè)中其他與系統(tǒng)需求無(wú)關(guān)的語(yǔ)義塊。 為了解決這個(gè)問(wèn)題，要么是內(nèi)容提供商手工編輯專門適用于移動(dòng)設(shè)備的頁(yè)面，要么就只有對(duì)頁(yè)面 進(jìn)行語(yǔ)義分割，并在分割后的頁(yè)面中選擇信息量最高的語(yǔ)義塊。 因?yàn)槟壳?大部分