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