【文章內(nèi)容簡(jiǎn)介】 α 開始，以 page α中包含的各語(yǔ)義塊為媒介，? ?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) 到 頁(yè) 面 中 心 點(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)頁(yè)的 PageRank 值 。 ε為適配參數(shù)， 以 1ε的概率，用戶在當(dāng)前頁(yè)面中隨機(jī)選擇一個(gè)超鏈接，跳轉(zhuǎn)到 該鏈接指向的 頁(yè)面；以 ε 的概率，用戶 從所有網(wǎng)頁(yè)中隨機(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ǔ)義信息。因?yàn)樗挠?jì)算基于網(wǎng)頁(yè)中各語(yǔ)義塊的重要程度，噪音塊、廣告塊中的超鏈接指向的網(wǎng)頁(yè)的重要性顯然不如導(dǎo)航塊、正文塊中的超鏈接所指向的網(wǎng)頁(yè)，所以前者會(huì)被分配到較少的 PageRank 值， 而后者則被分配到較多的 PageRank 值。也就是說，網(wǎng)頁(yè)中的無(wú)關(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è)的抓取、預(yù)處理、存儲(chǔ)、索引、檢索等幾個(gè)部分，其中預(yù)處理部分 的作用是 分析、 處理原始網(wǎng)頁(yè)數(shù)據(jù)如去除網(wǎng)頁(yè)噪音，消除重復(fù)網(wǎng)頁(yè)，計(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)頁(yè)的處理部分單獨(dú)出來(lái)，從而方便模塊復(fù)用，統(tǒng)一代碼管理，減少重復(fù)勞動(dòng)。 在天網(wǎng)搜索引擎平臺(tái)的搭建過程中， 也包括了抓取、存儲(chǔ)、分析（預(yù)處理）、索引、檢索等模塊，其中的分析模塊 接受成批量原始網(wǎng)頁(yè)的輸入，然后對(duì)每個(gè)網(wǎng)頁(yè)調(diào)用 Quark 模塊，進(jìn)行 網(wǎng)頁(yè)分塊、信息提取等工作 ，最后將處理后的數(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)頁(yè)數(shù)據(jù)集中處理的原則，為了應(yīng)對(duì)下游模塊可能提取的新的數(shù)據(jù)訪問需求， Quark 模塊必須具備良好的可擴(kuò)展性 ，并且提供盡量多的各種類型的數(shù)據(jù)訪問接口。 同時(shí)由于實(shí)驗(yàn)室人員的不固定性，代碼的維護(hù)十分重要。我自己在剛開始閱讀舊有的天網(wǎng)搜索引擎相關(guān)代碼的時(shí)候，就常有十分難懂的感覺，無(wú)法復(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)頁(yè)的處理和數(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)頁(yè)為輸入， 建立 Html 的Dom Tree；另一個(gè)是存儲(chǔ) 分好的網(wǎng)頁(yè)塊 （在我們的系統(tǒng)中，每一個(gè)網(wǎng)頁(yè)塊就叫做一個(gè) Quark） 并記錄 Quark 與 Quark 之間的組織架構(gòu)。 QuarkElement 類指代一個(gè) Quark,即 每個(gè) Quark 自身 就是一個(gè)QuarkElement 類的對(duì)象。 QuarkRecognizer 類 肩負(fù)網(wǎng)頁(yè)分塊的重任，從網(wǎng)頁(yè)中識(shí)別出所有語(yǔ)義塊。它依賴于前面的兩個(gè)類。 QuarkAnalyzer 類 依賴于 QuarkRecognizer 類 ， 它在分好的塊的基礎(chǔ)上，判斷各個(gè)塊的類型，提取正文信息。 這個(gè)類是整個(gè) Quark 模塊最核心的類，目前功能只是初步實(shí)現(xiàn)，還有很大的改進(jìn)空間，將來(lái)也可以根據(jù)功能將其分割成多個(gè)類。 中上部 綠色的部分為 Quark 模塊的評(píng)測(cè)和演示類，包括 QuarkEvaluation和 QuarkHtmlBuilder 兩個(gè)類。 QuarkEvaluation 類 是評(píng)測(cè)類，用來(lái)評(píng)測(cè) 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è)集為輸入。評(píng)測(cè)算法的細(xì)節(jié)見后文。 QuarkHtmlBuilder類 是 演示類， 用來(lái)查看 Quark模塊各步驟的實(shí)現(xiàn)效果。目前 可以查看 網(wǎng)頁(yè)分塊的效果，也可以查看主題信息提取的效果。 最上面黃色的部分為 Quark 模塊的應(yīng)用類 ，包括 QuarkRank、QuarkDuplicate、 QuarkClassification 等 ，它們都是利用分好的網(wǎng)頁(yè)塊實(shí)現(xiàn)的一些算法，比如基于 Quark 的 PageRank 算法，基于 Quark 的網(wǎng)頁(yè)消重算法，以及基于 Quark 的網(wǎng)頁(yè)分類算法。 左下方灰色的部分 為 Quark 模塊依賴的外部類 接口，包括中文切詞類ChineseTokenizer，以及圖中沒有的編碼轉(zhuǎn)換類 CodeConvert 等等。 中下部紅色的部分為 Quark 模塊直接的下游模塊，包括 TwDocView 類 和TwMd5 類 。 網(wǎng)頁(yè)分塊算法 算法 主體在 QuarkRecognizer 類中。 參見在第二章相關(guān)研究里提到的，除了基于視覺的算法之外，大部分基于語(yǔ)義的算法都是利用 html 標(biāo)簽 及其包含的文字信息 的特性 來(lái)給網(wǎng)頁(yè)分塊的。 并且由于大多數(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)頁(yè)分塊起重要作用的標(biāo)簽，而不是像所有已有論文那樣僅僅象征性地列舉出幾個(gè) html 標(biāo)簽。 分類后的詳細(xì) html 標(biāo)簽清單如下： 超級(jí) 標(biāo)簽 （ Super Tag， 簡(jiǎn)稱為 S 型標(biāo)簽） ： 這種標(biāo)簽 可以被直接認(rèn)定是一個(gè)網(wǎng)頁(yè)塊的根標(biāo)簽 ，在 算法過程中一旦遇到這種標(biāo)簽，就可以直接將其加 入 網(wǎng)頁(yè) 塊池。 包括： HEAD, SCRIPT, STYLE, OBJECT, FIELDSET, FRAMESET, IFRAME 大標(biāo)簽（ Big Tag， 簡(jiǎn)稱為 B 型標(biāo)簽）： 這種標(biāo)簽 通常都代表一個(gè)網(wǎng)頁(yè)塊，只不過有時(shí)其內(nèi)部?jī)?nèi)容過少，需要跟其他節(jié)點(diǎn)合并成一個(gè)網(wǎng)頁(yè)塊，或者在特殊情況下其內(nèi)部沒有可見字符。 所以在算法過程中，遇到這種標(biāo)簽，就判斷其單獨(dú)作為一個(gè)網(wǎng)頁(yè)塊的條件是否已經(jīng)成熟，如成熟，則將其加入網(wǎng)頁(yè)塊池。 包括： DIV, TD, TABLE, FORM, FIELDSET, CENTER, NOFRAMES, NOSCRIPT, PRE, BODY, HTML 這里需要注意的是像 BODY， HTML 兩個(gè)標(biāo)簽也作為 B 型標(biāo)簽，原因是這樣可以防止分塊之后網(wǎng)頁(yè)內(nèi)部文字信息的遺漏，因?yàn)樽罱K即使有遺漏，也會(huì)至少包含在 HTML 這個(gè)最后把關(guān)的門神標(biāo)簽手中。 排版標(biāo)簽（ Layout Tag，簡(jiǎn)稱為 L 型標(biāo)簽）： 這種標(biāo)簽 能影響到網(wǎng)頁(yè)的顯示效果，改變文字布局。 如果一顆 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，簡(jiǎn)稱為 D 型標(biāo)簽）： 這種標(biāo)簽 數(shù)量最多，都是對(duì)文字的顯示方式做微幅的調(diào)整，如改變字體、顏色、粗細(xì)等等。 由于它們的存在與否不改變網(wǎng)頁(yè)布局，所以不影響網(wǎng)頁(yè)分塊。包括： 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)在了前面四種里面。由于它們一般不單獨(dú)出現(xiàn)，對(duì)網(wǎng)頁(yè)布局的影響體現(xiàn)在了其屬主標(biāo)簽中，所以 在 QuarkRecognizer 算法中也不予考慮。 包括： 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ì)有些不同的要求。比如我們實(shí)驗(yàn)室的WebDigest 小組在進(jìn)行新聞網(wǎng)頁(yè)的數(shù)據(jù)挖掘的工作中， 需要使用到網(wǎng)頁(yè)分塊，但是他們特別需要提取該新聞網(wǎng)頁(yè)的發(fā)布日期和時(shí)間，而這部分內(nèi)容通常是在新聞標(biāo)題 與新聞?wù)闹g的一小行文字，正常的網(wǎng)頁(yè)分塊程序并不會(huì)將其單獨(dú)提取成一個(gè)網(wǎng)頁(yè)塊。所以我添加了定制標(biāo)簽，由用戶指定，它可以是普通的標(biāo)簽如“ TITLE”等，也可以是正則表達(dá)式，凡是其內(nèi)部文字滿足該正則表達(dá)式的 S 型、 B 型和 L 型標(biāo)簽，都將 被單獨(dú)提取為網(wǎng)頁(yè)塊。例如： H1, H2, TITLE 在明確了各 html 標(biāo)簽的類別之后， 利用 DomTree 中各標(biāo)簽節(jié)點(diǎn) 的類別信息和內(nèi) 部文字長(zhǎng)度 ，以 及 其 子標(biāo)簽節(jié)點(diǎn)的類別信息， 對(duì) DomTree 自底向上遍歷，在遍歷的過程中不斷判斷出新的網(wǎng)頁(yè)塊，并加入網(wǎng)頁(yè)塊池中，當(dāng)遍歷到最上部的html 根節(jié)點(diǎn)時(shí)，算法結(jié)束，網(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ì)列 ，開始自底向上遍歷。 2 取 當(dāng)前節(jié)點(diǎn) 隊(duì)列 的第一個(gè)節(jié)點(diǎn) 。 3 如果遇到 S 型節(jié)點(diǎn)，則立即將此節(jié)點(diǎn)加入網(wǎng)頁(yè)塊池。 4 如果遇到 C 型節(jié)點(diǎn)，則立即將 此節(jié)點(diǎn)加入網(wǎng)頁(yè)塊池。 5 如果遇到 B 型節(jié)點(diǎn)