【文章內(nèi)容簡介】 α 開始，以 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ù)學(xué)計算公式如下： 其中 p 為結(jié)果向量， 共 n 維，每一維代表一個 網(wǎng)頁的 PageRank 值 。 ε為適配參數(shù)， 以 1ε的概率，用戶在當(dāng)前頁面中隨機選擇一個超鏈接，跳轉(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)頁的重要性顯然不如導(dǎo)航塊、正文塊中的超鏈接所指向的網(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)頁的抓取、預(yù)處理、存儲、索引、檢索等幾個部分，其中預(yù)處理部分 的作用是 分析、 處理原始網(wǎng)頁數(shù)據(jù)如去除網(wǎng)頁噪音，消除重復(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 模塊，進行 網(wǎng)頁分塊、信息提取等工作 ，最后將處理后的數(shù)據(jù)存成TwDocView 格式，再提供給下游模塊。 我的畢業(yè)設(shè)計的主要工作，就是圍繞 Quark模塊而展開。 從上面的介紹中可以看出，天網(wǎng)搜索引擎 Quark模塊有兩個比較重要的特點： 可擴展性。 因為搜索引擎是一個比較 龐大的系統(tǒng)， 并且一直在不停的有新算法，新需求的加入，所以對數(shù)據(jù)的要求也會一直變化。而基于對原始網(wǎng)頁數(shù)據(jù)集中處理的原則，為了應(yīng)對下游模塊可能提取的新的數(shù)據(jù)訪問需求， Quark 模塊必須具備良好的可擴展性 ，并且提供盡量多的各種類型的數(shù)據(jù)訪問接口。 同時由于實驗室人員的不固定性，代碼的維護十分重要。我自己在剛開始閱讀舊有的天網(wǎng)搜索引擎相關(guān)代碼的時候，就常有十分難懂的感覺，無法復(fù)用已有代碼，只好自己重新編寫。 而正由于 Quark 模塊的可擴展性要求，所以它的代碼的可閱讀性也十分重要，在編寫的過程中，我盡量 注意了這一點 ，遵守 了我們統(tǒng)一的代碼規(guī)范 。 獨立性。 在我們實驗室內(nèi)部，除了搜索引擎之外，還有 Web 數(shù)據(jù)挖掘， Mapreduce應(yīng)用等相關(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)效果。當(dāng)前實現(xiàn)的是對網(wǎng)頁正文信息提取的評測，評測需要接受人工標(biāo)記的網(wǎng)頁或網(wǎng)頁集為輸入。評測算法的細節(jié)見后文。 QuarkHtmlBuilder類 是 演示類， 用來查看 Quark模塊各步驟的實現(xiàn)效果。目前 可以查看 網(wǎng)頁分塊的效果，也可以查看主題信息提取的效果。 最上面黃色的部分為 Quark 模塊的應(yīng)用類 ，包括 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 標(biāo)簽 及其包含的文字信息 的特性 來給網(wǎng)頁分塊的。 并且由于大多數(shù)論文的著重點在于分塊后的內(nèi)容提取上，所以對分塊算法本身著墨不多。 綜合各篇論文里提到的分塊方法， 我設(shè)計實現(xiàn)了 QuarkRecognizer 算法。 這一算法首先的一大特點就是實用性強。 所謂實用性強是指適合在實際系統(tǒng)中使用，效率高，定義完整。 我詳細分析了 W3C 制定的 格式規(guī)范，將所有規(guī)范的 Html 標(biāo)簽根據(jù) QuarkRecognizer 算法的需要分類，完整地列出了所有對網(wǎng)頁分塊起重要作用的標(biāo)簽，而不是像所有已有論文那樣僅僅象征性地列舉出幾個 html 標(biāo)簽。 分類后的詳細 html 標(biāo)簽清單如下： 超級 標(biāo)簽 （ Super Tag， 簡稱為 S 型標(biāo)簽） ： 這種標(biāo)簽 可以被直接認定是一個網(wǎng)頁塊的根標(biāo)簽 ，在 算法過程中一旦遇到這種標(biāo)簽，就可以直接將其加 入 網(wǎng)頁 塊池。 包括： HEAD, SCRIPT, STYLE, OBJECT, FIELDSET, FRAMESET, IFRAME 大標(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 型標(biāo)簽，原因是這樣可以防止分塊之后網(wǎng)頁內(nèi)部文字信息的遺漏，因為最終即使有遺漏，也會至少包含在 HTML 這個最后把關(guān)的門神標(biāo)簽手中。 排版標(biāo)簽（ Layout Tag，簡稱為 L 型標(biāo)簽）： 這種標(biāo)簽 能影響到網(wǎng)頁的顯示效果，改變文字布局。 如果一顆 html 子樹中包含多個 L 型標(biāo)簽，則該子樹單獨成塊的可能性增加。 包括： 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ù)量最多，都是對文字的顯示方式做微幅的調(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 附屬標(biāo)簽（ Affiliated 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, TITLE 定制標(biāo)簽（ Customized Tag，簡稱為 C 型標(biāo)簽）： 因為不同的應(yīng)用中，對網(wǎng)頁分塊會有些不同的要求。比如我們實驗室的WebDigest 小組在進行新聞網(wǎng)頁的數(shù)據(jù)挖掘的工作中， 需要使用到網(wǎng)頁分塊，但是他們特別需要提取該新聞網(wǎng)頁的發(fā)布日期和時間，而這部分內(nèi)容通常是在新聞標(biāo)題 與新聞?wù)闹g的一小行文字，正常的網(wǎng)頁分塊程序并不會將其單獨提取成一個網(wǎng)頁塊。所以我添加了定制標(biāo)簽，由用戶指定，它可以是普通的標(biāo)簽如“ TITLE”等，也可以是正則表達式，凡是其內(nèi)部文字滿足該正則表達式的 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)遍歷到最上部的html 根節(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é)點