本站小編為你精心準備了視覺特征的網頁最優分割算法參考范文，愿這些范文能點燃您思維的火花，激發您的寫作靈感。歡迎深入閱讀并收藏。

《計算機科學雜志》2015年第S1期

1引言

隨著移動通信技術的迅猛發展，人們通過移動終端訪問網頁的活動日漸頻繁。然而，移動終端屏幕尺寸的限制往往造成Web頁面無法正常顯示，給用戶帶來了很大的困擾。為了解決這個問題，早在20世紀90年代，研究人員便開始研究網頁自適應呈現技術，提出了若干算法。這些算法可歸納為3類，即網頁重構、網頁轉碼、網頁分割。其中，網頁分割是實現網頁自適應呈現的主流技術之一。它首先將網頁分割成若干個語義相關的內容段（也稱為內容塊）；然后在內容服務過程中，服務器根據移動終端特征，選擇合適的內容段并推送給用戶，以確保網頁內容在移動終端上得以正常顯示。網頁分割技術具有兩個優點：一方面，它不需要占用大量的計算資源；另一方面，用戶也不需要反復拖動滾動欄查看網頁內容，使網頁內容的服務質量得以保證。近年來，關于網頁分割技術的研究受到了廣泛關注，并且取得了豐富的研究成果。其中經典算法是Cai等研究人員提出的基于視覺的網頁分割技術（Vision－basedPageSegmenta－tionAlgorithm，VIPS）。VIPS根據人的視覺特點，總結出一些網頁分割的規則，然后基于這些規則實現網頁分割。此后，許多研究者在該方法的基礎上提出了許多改進的網頁分割技術，但基于規則的思想沒有本質變化。目前，基于視覺的網頁分割技術主要存在兩方面問題：其一，網頁分割結果過碎，不利于網頁重構；其二，分割規則的總結需要人工參與，規則的好壞也直接影響網頁分割效果。因此，如何劃分網頁分割的粒度，如何能減少分割過程中人工參與，從而降低主觀因素影響，均是需要進一步研究的問題。本文將網頁分割轉化為圖的最優劃分問題，提出一種新穎的網頁最優分割算法（Vision－basedWebOptimalSegmen－tation，VWOS）。VWOS算法首先基于人的視覺特點設計內容相似度計算模型，然后利用網頁結構特征和內容相似度模型，將網頁構造為加權無向連通圖，并將網頁分割轉化為圖的最優劃分問題，最后基于Kruskal算法求解圖的最優劃分問題，實現網頁最優分割。VWOS算法是一種自動算法，不需要人工參與。實驗分析表明，該算法能夠有效地對網頁進行分割，分割效果和算法性能優于VIPS算法。

2相關研究

網頁是一類特殊的文本文件，它具有內容特征、結構特征、布局特征和視覺特征。針對上述4種特征，網頁分割技術可以分為4種類型：基于內容特征的分割技術、基于結構特征的分割技術、基于布局特征的分割技術和基于視覺特征的分割技術。基于內容特征的網頁分割技術主要是基于網頁標簽。20世紀90年代末的手機瀏覽器不支持CSS層疊樣式，也不支持JavaScript，只能訪問簡單的靜態網頁。因此，當時的學者只需基于標簽的類型進行分割，即可達到很好的效果。YanleiDiao等人提出具有自學習功能的Web查詢處理系統［1］，利用有效標簽類型（如〈p〉、〈table〉、〈ul〉、〈h1〉～〈h6〉）進行網頁分割；Wai－chingWong提出標簽檢測算法來檢測具有同類型信息的相似標簽，并定義標簽類型進行網頁分割；EijaKaasinen與OrkutBuyukkokten僅僅利用像〈p〉〈ta－ble〉〈ul〉這樣的簡單標簽進行Web網頁分割?；诮Y構特征的網頁分割技術采用了DOM（DocumentObjectModel，DOM）技術，將網頁表示成DOM樹結構，然后根據各內容塊在DOM樹中的位置對網頁進行分割。文獻均采用的是基于DOM樹的分割技術，RichardRomero［8］在DOM樹的基礎上進行聚類分析，實現網頁分割?；诓季痔卣鞯木W頁分割技術主要包括基于位置的網頁分割技術與基于模板的網頁分割技術兩種。GenHattori提出的基于距離的網頁分割技術，利用標簽的相對位置與層級關系計算內容塊的距離，以此對網頁進行分割。然而HTML中某些特殊標簽具有布局作用，降低了分割的準確率。通過對HTML標簽的研究與分析，GenHattori于2007年提出改進技術：混合分割技術?；旌戏指罴夹g將〈div〉與〈table〉作為布局信息，進行初步分割，之后將標簽間的距離作為內容塊的距離做二次分割。基于模板的網頁分割技術的主要思想是分割前定義好各類模板，通過將欲分割的網頁或內容塊與模板匹配來進行分割。YuChen將網頁分成上、下、左、右和中間5個部分，之后根據這5個部分的特征將網頁的內容提取后納入到定義好的特征模版中，從而實現網頁分割。這種技術適合于結構標準的網頁，對于其他結構的網頁則無法正確分割。文獻將網頁歸類于八大布局模板，之后依據網頁布局（此處考慮的是標簽形成的布局，而非樣式信息形成的布局）與標題塊進行網頁分割?；谝曈X特征的網頁分割技術的原理是標簽本身攜帶內容顯示信息，根據人眼的視覺特征，利用這些顯示信息實現網頁的內容分割。DengCai提出了一種基于視覺特征的網頁分割技術（Vision－basedPageSegmentationAlgorithm，VIPS），該算法具有良好的網頁分割效果。VIPS存在的問題在于需要人工不斷地去總結和調整分割規則，而且當新規則產生后，將影響以前的分割效果?；赩IPS算法，國內外學者提出了一系列的改進技術［14－18］，這些技術在一定程度上優化了VIPS，但上述的本質問題卻沒有解決。此外，這些技術均沒有考慮CSS樣式信息對視覺特征的影響。

3VWOS算法設計

根據網頁的標簽，可以將網頁劃分為許多語義完整的原子內容塊，這些內容塊是網頁內容的最小組成單元。基于網頁視覺特征定義兩個原子內容塊的相似度計算公式，并利用該公式構造原子內容塊相似度矩陣。因此，網頁可以視為由原子內容塊為頂點、相似關系為邊、相似度為權的加權無向連通圖，網頁分割就轉化為圖的最優劃分問題。

3．1網頁最優分割模型為便于表述網頁最優分割模型，對其中包含的重要概念做如下定義。通過解析網頁得到內容塊，并利用內容塊相似度公式計算內容塊兩兩之間相似度，得到相似度矩陣。在此前提下，網頁可以構造為加權無向連通圖。因此，網頁分割轉化為圖的最優劃分問題，其最優化模型如式（1）所示。式（1）的最優化模型具有3個典型性質：最優子結構、重疊子問題與貪心選擇性質。最優子結構指問題的最優解包含子問題的最優解。如果上述問題的最優解包含了原子內容塊n，那么其余原子內容塊一定構成子問題n－1個原子內容塊在組閾值為St－Sn時的最優解。如果最優解不包含原子內容塊n，那么其余原子內容塊一定構成子問題n－1個原子內容塊在組閾值為St時的最優解。重疊子問題指用遞歸算法自頂而下解決上述問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算了多次。貪心選擇性質指所求問題的整體最優解可以通過一系列局部最優解的選擇來達到。若所有原子內容塊構成的集合為V，組內已確定的原子內容塊構成的集合為U，s［u］［v］表示原子內容塊u、v間的相似度。u∈U，v∈V－U，由于U中所有原子內容塊構成一棵相似度最大的生成樹，根據MST性質，V的所有相似度最大的生成樹中一定存在一棵包含邊（u，v）。

3．2VWOS算法網頁最優分割算法VWOS分為4個步驟：第一，根據手機分辨率信息，確定網頁分割閾值St；第二，建立原子內容塊池Pc與相似度池Ps，相似度按值從大到小排序；第三，構建網頁加權無向連通圖G（V，E）；第四，求解圖G（V，E）最優劃分問題。（1）網頁分割閾值確定不同手機的分辨率不同，所能呈現的信息量亦不同。因此網頁分割時，需要設置不同的閾值，以達到在不影響正常顯示與用戶體驗的情況下，子頁所呈現的信息量最大化。網頁分割算法采用像素面積確定分割閾值St。使用諾基亞5800W手機，隨機瀏覽100個手機版網頁，統計分析知，平均每個網頁需要3．51屏顯示；隨機抽取100位大學生手機網民，對“手機版網頁出現幾屏顯示時，會心生埋怨心理”問題進行調查，分析發現其平均值為2．87?？紤]到用戶體驗的重要性，對上述兩個結果以比例1：2進行加權求均值得3．08。因此，可確定最適合手機顯示的網頁大小為手機屏幕的3倍。由于VWOS算法所用的網頁分割算法的特殊性，有時分割形成的子頁結果為所設閾值的2倍。對此，將網頁分割閾值St設為1．5屏，即St＝1．5×水平分辨率×垂直分辨率。（2）原子內容塊池Pc與相似度池Ps的建立為了更有效地實現網頁分割，需要建立原子內容塊池Pc與相似度池Ps。Pc中存放原子內容塊算法獲得的所有內容塊。原子內容塊相似度計算及后期建立連通分支時均從Pc中獲取所需的內容塊。Ps中存放采用基于網頁視覺特征的相似度公式得到的相似度值，并按值從大到小的順序排列。內容相似度基于網頁視覺特征，在此將網頁視覺特征定義為6維向量，根據向量中維度的不同度量屬性，采用不同的計算公式計算各維度相似度值，最后用加權求和的方式計算出最終的內容塊相似度值［19］。Pc存放的內容塊類型為Perfect－Node，而Ps存放的相似度以本文自定義的Similarity類型標識，其類圖如圖1所示。對Ps而言，由于構建連通分支時，以相似度值從大到小的順序連通各分支，因此，Ps中的Similar－ity數據是按值遞減的有序隊列。1Similarity類（3）連通分支構建Pc中含有網頁所有的原子內容塊，Ps中含有兩原子內容塊間的相似度值，并按值從大到小排列。對Pc與Ps采用如下算法構建連通分支，以確保每個分支的相似度權值最大，且每個分支中所有頂點的像素面積和Sk均小于分割閾值St。這樣便實現了網頁分割所需的每個連通分支均可轉換為各個子頁，這些子頁不僅可在手機瀏覽器中正常顯示，而且具有較好的用戶體驗。連通分支構建算法如圖2所示。1）將Pc中n個內容塊看成n個孤立的連通分支，并建立關聯池cr。2）計算各連通分支像素面積和Sk，并與St比較：如果Sk≥St或所有邊都被查看過，則將連通分支中的頂點從Pc中取出存入關聯池cr中；如果Sk＜St，按下述方法連接兩個不同的連通分支：設查看到第s條邊，若該邊兩端點分別是當前兩個不同的連通分支T1和T2中的頂點，則用該邊將T1和T2連成一個連通分支；若該邊兩端點在當前的同一個連通分支中，直接查看第s＋1條邊。3）如果所有邊都被查看過或Pc中已經沒有原子內容塊，則連通分支構建算法結束，否則轉步驟2）。需要特別指出的是，若以是否含有孤立的連通分支或查看邊數是否達到n＋1作為結束算法的條件，雖然可以大幅度減少算法循環次數，但是，卻不能保證最后生成的連通分支不能再合并。而僅僅以判斷所有邊是否被查看過作為結束算法的條件，雖然可以保證Sk在小于St的情況下最大化，然而因需要過多的循環次數導致時間復雜度過大，從而影響VWOS算法的性能。通過分析與測試發現，多數情況下，各連通分支均不能再合并時，有很多邊沒有被查看，對此，連通分支構建算法采用“所有邊都被查看過或Pc中已經沒有原子內容塊”作為算法結束條件，以達到在滿足Sk最大化的同時性能最大化。（4）求解網頁最優分割問題網頁最優分割模型如式（1）所示，基于模型的最優子結構和貪心選擇性質，可采用貪心策略求解該模型。因為，加權無向連通圖G（V，E）可構造為一棵生成樹，使生成樹上各邊權值最大，于是網頁分割可變為在特定閾值St條件下構造子生成樹的過程，每個子生成樹均滿足特定閾值St。采用最優化理論中的Prim算法與Kruskal算法所需的時間復雜度分別為O（n2）與O（eloge），其中e為圖的邊數。當e＝Ω（n2）時，O（n2）＜O（eloge），當e＝O（n2）時，O（n2）＜O（eloge）。因為網頁對應的加權無向連通圖G（V，E）是一張完全圖，即e＝n（n－1）／2＝O（n2），所以用Kruskal算法比用上述其它算法時間復雜度低。因此，本文采用Kruskal算法實現網頁最優分割問題求解。

4實驗與分析

為檢驗VWOS算法的執行效果和性能，設計了一組網頁分割對比實驗。實驗基于Web服務設計，通過移動終端訪問網頁。將VWOS算法和VIPS算法部署在服務器，以國家精品課程站點隨機選取的100個網頁為對象，移動終端采用分辨率為360×640像素的Android2．3手機模擬器，分割閾值St＝1．5×360×640＝3．456×e5。采用3個評價指標：平均分割塊數、語義完整度和平均執行時間。其中語義完整度定義見式（2）。通過網頁在移動終端的呈現結果，比較VWOS算法與VIPS算法在3個指標上的表現，評價算法效果和性能。

結果與分析本節以具體的2個網頁呈現的結果為例，比較兩種算法分割效果和性能，并分析其中的原因。結合專業背景，選取的網頁定為北京師范大學的國家精品教育技術學導論與南京師范大學國家精品課程教育社會學。圖3（a）為北京師范大學的國家精品教育技術學導論經VWOS算法分割的效果。VWOS算法將該網頁分割為兩個子頁，如圖3（b）與圖3（c）所示，圖3（b）為主頁，圖3（c）為子頁。從圖中可以發現，VWOS算法分割該頁面后得到的兩個子頁語義完整且適合手機瀏覽器顯示，具有較好的用戶體驗。圖4為教育技術導論網頁采用VIPS算法的分割結果。

VIPS將該網頁分割為6個子頁。其中只有表格子頁的像素面積與分割閾值接近，而其他5個子頁尺寸均遠小于閾值。VIPS算法之所以將網頁分割得過碎，主要因為其以DOM樹為基礎，對每個內容塊用DoC（DegreeofCoherence）表示緊密程度。按照VIPS的規則，DoC在DOM樹中呈現自頂而下逐漸增大的規律。而VIPS采用自頂而下的方式分割，因此當DOM樹底層的內容塊符合分割閾值時，上層內容塊因DoC小于PDoC（PermittedDegreeofCoherence）而被過度分割。VWOS算法基于最優化理論，將網頁分割看作分組最優化問題，并設計網頁分割算法以自底而上的方式對網頁進行分割，有效地避免了分割過碎問題。由此可以看出在分割后形成子頁數方面，VWOS算法較VIPS算法內容塊語義更完整，也更適合移動設備顯示。圖5為南京師范大學國家精品課程教育社會學分別經VWOS與VIPS分割的效果。采用VWOS算法進行分割后形成兩個子頁，其中圖5（b）所示子頁為原網頁右下角部分。該部分像素面積略大于分割閾值St，按照VWOS算法設計的網頁分割算法，該部分會作為一個完整子頁存在。采用VIPS算法，將頁面分割為3個子頁，如圖5（c）所示，其中黑色方框內的部分為分割后保留下的內容塊。觀察圖5（c）很容易發現丟失了部分內容塊。分析該網頁的代碼可發現，丟失的部分均為樣式信息，該部分的樣式信息存儲在CSS文件中，而非HTML標簽的style屬性中。由此，再一次證明了由于“數據內容－樣式信息”的分離，致使VIPS分割效果無法滿足手機用戶需求的假設，也再一次說明了網頁分割預處理算法的必要性。

VWOS算法充分考慮了〈link〉、〈style〉與HTML標簽style屬性中的樣式信息，并將樣式信息與數據內容融合，以此保證內容塊視覺特征的全面性與精確度。因此可以看出，在分割后形成的內容塊方面，VWOS算法得到的內容塊具有語義完整的特點，而VIPS算法分割過程中，會造成內容塊視覺特征的丟失，甚至會造成部分內容塊的丟失。此外觀察圖5（b）可以發現，分割形成的子頁的像素面積比手機尺寸大，這主要因為該部分采用〈table〉標簽進行布局，而VWOS算法并未對〈table〉標簽的寬高信息進行處理。實驗采用VWOS算法和VIPS算法共對100個精品課程站點網頁進行網頁分割，并在3個性能指標上進行統計對比，結果如表1所列。通過上述實驗，初步證明VWOS算法在內容塊語義完整性和網頁適應性方面，比VIPS算法具有更好的性能。具體而言，VWOS算法比VIPS算法具有以下4點優勢：第一，VWOS算法不需要人工參與，是一種網頁分割自動處理方法；第二，在同樣的分割閾值條件下，VWOS算法生成的子頁數少，因此用戶在各子頁中遍歷瀏覽時，不易迷航；第三，VWOS算法生成的每個子頁的像素面積SP均在［St，2St）區域中，沒有過度分割的子頁；第四，VWOS算法充分利用視覺特征表示內容塊的特征，分割得到的每個內容塊均具有高度的語義完整性。結束語網頁分割技術被廣泛應用于網頁信息獲取和網頁自適應呈現等領域。目前，經典的網頁分割算法仍存在需要人工參與和分割過碎的問題。針對這些問題，綜合視覺特征和網頁結構，將網頁構造為加權無向連通圖，并將網頁分割轉化為圖的最優劃分問題，最后基于經典的最優化算法，結合網頁分割的過程，提出了一種基于視覺特征的網頁最優分割算法VWOS。實驗證明，VWOS算法在語義完整性和網頁適應性方面，性能優于經典分割算法VIPS。與VIPS算法相比，VWOS算法有兩個優點。其一是網頁分割結果沒有過多的內容碎片，較好地保留了內容塊的語義完整性；其二是它屬于自動算法，不需要人工參與。當然，VWOS算法仍存在一些不足之處，集中表現在由于網頁樣式采用技術不同對構造網頁無向連通圖G影響較大，因此該算法的魯棒性存在不足。

下一步研究將從3方面展開。第一，將采用更多的客觀評價指標（如信息檢索領域評價指標），全面對比VWOS和VIPS兩種算法的性能，并以此為依據對VWOS算法做改進。第二，在算法中增加對網頁樣式技術的識別，并做相應的處理，提高算法的魯棒性。第三，將以VWOS算法為核心，研究網頁自適應呈現技術，以期達到Web學習資源移動訪問的目標，提高Web學習資源的利用率，為移動學習服務打下技術基礎。

作者：李文昊 彭紅超 童名文 石俊杰 單位：華中師范大學教育信息技術學院 解放軍63981部隊