【文章內(nèi)容簡介】 。 WP(α, β)可以理解為是從 page α 開始，以 page α 中包含的各語義塊為媒介，? ?iPjf b l o c k j p a g e iijbX ??? ??? 如 果 屬 于 0 否 則? ?P p a g e p b l o c k bf b l o c k bb ?? 中 的 大 小的 中 心 點(diǎn) 到 頁 面 中 心 點(diǎn) 的 距 離? ?Pbpf1b???? ? ? ? ? ?Pbf Z , , W b b P????? ? ? ? ?? ? ??跳轉(zhuǎn)到 page β 的概率。 Block Graph WB 的定義為： 即 BW ZX? 。 WB(a,b)可以理解為 用戶從 block a 開始，以包含 block b 的 page β 為媒介，跳轉(zhuǎn)到 block b 的概率。 Block Level PageRank Block Level PageRank 跟 PageRank 區(qū)別的實(shí)質(zhì)在于， PageRank 算法基于 原始 的 只有 1 和 0 的 Page Graph，而 BLPR 算法基于 上面提到的 GP。 BLPR算法的數(shù)學(xué)計(jì)算公式如下： 其中 p 為結(jié)果向量， 共 n 維，每一 維代表一個(gè) 網(wǎng)頁的 PageRank 值 。 ε為適配參數(shù)， 以 1ε 的概率，用戶在當(dāng)前頁面中隨機(jī)選擇一個(gè)超鏈接，跳轉(zhuǎn)到 該鏈接指向的 頁面；以 ε 的概率，用戶 從所有網(wǎng)頁中隨機(jī)選擇一個(gè) URL并跳轉(zhuǎn)。 所以 U 為 n n 的 轉(zhuǎn)換矩陣 ，它滿足對(duì)所有的 i， j， Uij = 1/n。 而 M也是 n n 的轉(zhuǎn)換矩陣，它是由上面提到的 WP 權(quán)值矩陣對(duì)每一行做歸一化，令每一行的權(quán)值之和為 1 得到的。 p 向量的值以馬爾科夫鏈的形式循環(huán)計(jì)算下去，直到算法收斂。 Block Level PageRank 比單純的 PageRank 包含了更多的語義信息。因?yàn)樗挠?jì)算基于 網(wǎng)頁中各語義塊的重要程度，噪音塊、廣告塊中的超鏈接指向的網(wǎng)頁的重要性顯然不如導(dǎo)航塊、正文塊中的超鏈接所指向的網(wǎng)頁，所以前者會(huì)被分配到較少的 PageRank 值，而后者則被分配到較多的 PageRank 值。也就是說，網(wǎng)頁中的無關(guān)信息區(qū)域在 PageRank 的計(jì)算過程中起的作用相對(duì)較小 ， 所以 BLPR 的效果要優(yōu)于單純的 PageRank。 ? ? ? ? ? ?B a ,b Z a , X b , a ,bWB? ? ? ? ?( 1 ) ) TU M p p?? ? ? ? ?第 3 章 天網(wǎng) 搜索引擎 Quark 模塊 搜索引擎 系統(tǒng) 一般包括 網(wǎng)頁的抓取、預(yù)處理、存儲(chǔ)、索引、檢索等幾個(gè)部分，其中預(yù)處理部分 的作用是 分析、 處理原始網(wǎng)頁數(shù)據(jù)如去除網(wǎng)頁噪音，消除重復(fù)網(wǎng)頁，計(jì)算 PageRank，中文切詞 等 等，并為后繼模塊提供統(tǒng)一的數(shù)據(jù)訪問接口，規(guī)范數(shù)據(jù)管理，避免重復(fù)計(jì)算。同時(shí) 在天網(wǎng)搜索引擎平臺(tái)中，基于功能擴(kuò)展和實(shí)驗(yàn)室內(nèi)部其他相關(guān)研究的需要，必須將對(duì)原始網(wǎng)頁的處理部分單獨(dú)出來，從而方便模塊復(fù)用，統(tǒng)一代碼管理，減少重復(fù)勞動(dòng)。 在天網(wǎng)搜索引擎平臺(tái)的搭建過程中， 也包括了抓取、存儲(chǔ)、分析（預(yù)處理）、索引、檢索等模塊，其中的分析模塊 接受成批量原始網(wǎng)頁的輸入，然后對(duì)每個(gè)網(wǎng)頁調(diào)用 Quark 模塊，進(jìn)行 網(wǎng)頁分塊、信息提取等工作 ，最后將處理后的數(shù)據(jù)存成TwDocView 格式，再提供給下游模塊。 我的畢業(yè)設(shè)計(jì)的 主要工作，就是圍繞 Quark模塊而展開。 從上面的介紹中可以看出，天網(wǎng)搜索引擎 Quark 模塊有兩個(gè)比較重要的特點(diǎn)： 可擴(kuò)展性。 因?yàn)樗阉饕媸且粋€(gè)比較龐大的系統(tǒng)， 并且一直在不停的有新算法，新需求的加入，所以對(duì)數(shù)據(jù)的要求也會(huì)一直變化。而基于對(duì)原始網(wǎng)頁數(shù)據(jù)集中處理的原則，為了應(yīng)對(duì)下游模塊可能提取的新的數(shù)據(jù)訪問需求， Quark 模塊必須具備良好的可擴(kuò)展性 ，并且提供盡量多的各種類型的數(shù)據(jù)訪問接口。 同時(shí)由于實(shí)驗(yàn)室人員的不固定性，代碼的維護(hù)十分重要。我自己在剛開始閱讀舊有的天網(wǎng)搜索引擎相關(guān)代碼的時(shí)候，就常有十分難 懂的感覺，無法復(fù)用已有代碼，只好自己重新編寫。 而正由于 Quark 模塊的可擴(kuò)展性要求，所以它的代碼的可閱讀性也十分重要，在編寫的過程中，我盡量 注意了這一點(diǎn) ，遵守了我們統(tǒng)一的代碼規(guī)范 。 獨(dú)立性。 在我們實(shí)驗(yàn)室內(nèi)部，除了搜索引擎之外，還有 Web 數(shù)據(jù)挖掘， Mapreduce應(yīng)用等相關(guān)工作也可能需要使用對(duì)單個(gè)網(wǎng)頁的處理和數(shù)據(jù)提取程序。 因此Quark 模塊必須能獨(dú)立于搜索引擎代碼之外單獨(dú)編譯運(yùn)行，并且方便他人調(diào)用這部分代碼。 基于上述兩個(gè)特點(diǎn) ，我初步實(shí)現(xiàn)了 Quark 模塊。 該模塊的類結(jié)構(gòu)圖 如下 ： 圖中右下及中間 藍(lán)色的部分為 Quark模塊 的核心功能類，包括 QuarkTree、QuarkElement、 QuarkRecognizer、 QuarkAnalyzer 等四個(gè)類。 QuarkTree 類 的作用 有兩個(gè)，一個(gè)是 以原始網(wǎng)頁為輸入， 建立 Html 的Dom Tree；另一個(gè)是存儲(chǔ) 分好的網(wǎng)頁塊 （在我們的系統(tǒng)中，每一個(gè)網(wǎng)頁塊就叫做一個(gè) Quark） 并記錄 Quark 與 Quark 之間的組織架構(gòu)。 QuarkElement 類指代一個(gè) Quark,即每個(gè) Quark 自身就是一個(gè)QuarkElement 類的對(duì)象。 QuarkRecognizer 類 肩負(fù)網(wǎng)頁分塊的重任，從網(wǎng)頁中識(shí)別出所有語義塊。它依賴于前面的兩個(gè)類。 QuarkAnalyzer 類 依賴于 QuarkRecognizer 類 ， 它在分好的塊的基礎(chǔ)上，判斷各個(gè)塊的類型，提取正文信息。 這個(gè)類是整個(gè) Quark 模塊最核心的類，目前功能只是初步實(shí)現(xiàn)，還有很大的改進(jìn)空間，將來也可以根據(jù)功能將其分割成多個(gè)類。 中上部 綠色的部分為 Quark 模塊的評(píng)測和演示類，包括 QuarkEvaluation和 QuarkHtmlBuilder 兩個(gè)類。 QuarkEvaluation 類 是評(píng)測類 ，用來評(píng)測 Quark 核心類的實(shí)現(xiàn)效果。當(dāng)前實(shí)現(xiàn)的是對(duì)網(wǎng)頁正文信息提取的評(píng)測，評(píng)測需要接受人工標(biāo)記的網(wǎng)頁或網(wǎng)頁集為輸入。評(píng)測算法的細(xì)節(jié)見后文。 QuarkHtmlBuilder類 是 演示類， 用來查看 Quark模塊各步驟的實(shí)現(xiàn)效果。目前 可以查看 網(wǎng)頁分塊的效果，也可以查看主題信息提取的效果。 最上面黃色的部分為 Quark 模塊的應(yīng)用類 ，包括 QuarkRank、QuarkDuplicate、 QuarkClassification 等 ，它們都是利用分好的網(wǎng)頁塊實(shí)現(xiàn)的一些算法，比如基于 Quark 的 PageRank 算法 ，基于 Quark 的網(wǎng)頁消重算法，以及基于 Quark 的網(wǎng)頁分類算法。 左下方灰色的部分 為 Quark 模塊依賴的外部類 接口，包括中文切詞類ChineseTokenizer，以及圖中沒有的編碼轉(zhuǎn)換類 CodeConvert 等等。 中下部紅色的部分為 Quark 模塊直接的下游模塊，包括 TwDocView 類 和TwMd5 類 。 網(wǎng)頁分塊算法 算法 主體在 QuarkRecognizer 類中。 參見在第二章相關(guān)研究里提到的，除了基于視覺的算法之外，大部分基于語義的算法都是利用 html 標(biāo)簽 及其包含的文字信息 的特性 來給網(wǎng)頁 分塊的。 并且由于大多數(shù)論文的著重點(diǎn)在于分塊后的內(nèi)容提取上，所以對(duì)分塊算法本身著墨不多。 綜合各篇論文里提到的分塊方法， 我設(shè)計(jì)實(shí)現(xiàn)了 QuarkRecognizer 算法。 這一算法首先的一大特點(diǎn)就是實(shí)用性強(qiáng)。 所謂實(shí)用性強(qiáng)是指適合在實(shí)際系統(tǒng)中使用，效率高，定義完整。 我詳細(xì)分析了 W3C 制定的 格式規(guī)范，將所有規(guī)范的 Html 標(biāo)簽根據(jù) QuarkRecognizer 算法的需要分類，完整地列出了所有對(duì)網(wǎng)頁分塊起重要作用的標(biāo)簽，而不是像所有已有論文那樣僅僅象征性地列舉出幾個(gè) html 標(biāo)簽。 分類后的詳細(xì) html 標(biāo)簽 清單如下： 超級(jí) 標(biāo)簽 （ Super Tag， 簡稱為 S 型標(biāo)簽） ： 這種標(biāo)簽 可以被直接認(rèn)定是一個(gè)網(wǎng)頁塊的根標(biāo)簽 ，在 算法過程中一旦遇到這種標(biāo)簽，就可以直接將其加入 網(wǎng)頁 塊池。 包括： HEAD, SCRIPT, STYLE, OBJECT, FIELDSET, FRAMESET, IFRAME 大標(biāo)簽（ Big Tag， 簡稱為 B 型標(biāo)簽）： 這種標(biāo)簽 通常都代表一個(gè)網(wǎng)頁塊，只不過有時(shí)其內(nèi)部內(nèi)容過少，需要跟其他節(jié)點(diǎn)合并成一個(gè)網(wǎng)頁塊，或者在特殊情況下其內(nèi)部沒有可見字符。 所以在算法過程中， 遇到這種標(biāo)簽，就判斷其單獨(dú)作為一個(gè)網(wǎng)頁塊的條件是否已經(jīng)成熟，如成熟，則將其加入網(wǎng)頁塊池。 包括： DIV, TD, TABLE, FORM, FIELDSET, CENTER, NOFRAMES, NOSCRIPT, PRE, BODY, HTML 這里需要注意的是像 BODY， HTML 兩個(gè)標(biāo)簽也作為 B 型標(biāo)簽，原因是這樣可以防止分塊之后網(wǎng)頁內(nèi)部文字信息的遺漏，因?yàn)樽罱K即使有遺漏，也會(huì)至少包含在 HTML 這個(gè)最后把關(guān)的門神標(biāo)簽手中。 排版標(biāo)簽（ Layout Tag，簡稱為 L 型標(biāo)簽）： 這種標(biāo)簽 能影響到網(wǎng)頁的顯示效果，改變文字布局。 如果一顆 html 子樹中包含多個(gè) L 型標(biāo)簽，則該子樹單獨(dú)成塊的可能性增加。 包括： P, UL, OL, DL, DIR, LI, DT, BLOCKQUOTE, ADDRESS, BR, HR, COL, COLGROUP, IMG, MENU, SELECT 顯示標(biāo)簽（ Display Tag，簡稱為 D 型標(biāo)簽）： 這種標(biāo)簽 數(shù)量最多，都是對(duì)文字的顯示方式做微幅的調(diào)整，如改變 字體、顏色、粗細(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:SMARTTAGTYPE 附屬標(biāo)簽（ Affiliated Tag， 簡稱為 A 型標(biāo)簽 ） ： 這種標(biāo)簽 從屬與上述四種標(biāo)簽的某一種， 同時(shí)有些也出現(xiàn)在了前面四種里面。由于它們一般不單獨(dú)出現(xiàn)，對(duì)網(wǎng)頁布局的影響體現(xiàn)在了其屬主標(biāo)簽中，所以 在 QuarkRecognizer 算法中也不予考慮。 包括： FRAME, INPUT, ISINDEX, LEGEND, LINK, MAP, META, OPTION, OPTGROUP, PARAM, TD, TH, TR, TBODY, TITLE 定制標(biāo)簽（ Customized Tag，簡稱為 C 型標(biāo)簽）： 因?yàn)椴煌膽?yīng)用中，對(duì)網(wǎng)頁分塊會(huì)有些不同的要求。比如我們實(shí)驗(yàn)室的WebDigest 小組在進(jìn)行新聞網(wǎng)頁的數(shù)據(jù)挖掘的工作中， 需要使用到網(wǎng)頁分塊，但是他們特別需要提取該新聞網(wǎng)頁的發(fā)布日期和時(shí)間，而 這部分內(nèi)容通常是在新聞標(biāo)題 與新聞?wù)闹g的一小行文字，正常的網(wǎng)頁分塊程序并不會(huì)將其單獨(dú)提取成一個(gè)網(wǎng)頁塊。所以我添加了定制標(biāo)簽，由用戶指定，它可以是普通的標(biāo)簽如“ TITLE”等，也可以是正則表達(dá)式，凡是其內(nèi)部文字滿足該正則表達(dá)式的 S 型、 B 型和 L 型標(biāo)簽，都將被單獨(dú)提取為網(wǎng)頁塊。例如： H1, H2, TITLE 在明確了各 html 標(biāo)簽的類別之后， 利用 DomTree 中各標(biāo)簽節(jié)點(diǎn) 的類別信息和內(nèi) 部文字長度 ，以 及 其 子標(biāo)簽節(jié)點(diǎn)的類別信息， 對(duì) DomTree 自底向上遍歷，在遍歷的過程中不斷判斷出新的網(wǎng)頁塊，并 加入網(wǎng)頁塊池中，當(dāng)遍歷到最上部的html 根節(jié)點(diǎn)時(shí)，算法結(jié)束，網(wǎng)頁分塊完畢。 QuarkRecognizer 算法的核心偽碼如下： _________________________________________________________________ ALGORITHM QuarkRecognizer (DomTree tree， TagList CType) INPUT : 某單個(gè)網(wǎng)頁構(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ì)列 ，開始自底向上遍歷。 2 取 當(dāng)前節(jié)點(diǎn) 隊(duì)列 的第一個(gè)節(jié)點(diǎn) 。 3 如果遇到 S 型節(jié)點(diǎn)，則立即將此節(jié)點(diǎn)加入網(wǎng)頁塊池。 4 如果遇