啟發式多特徵規則集網頁分塊方法與流程
2023-04-30 01:47:26
本發明涉及一種頁面分塊方法,具體地,涉及一種啟發式多特徵規則集網頁分塊方法。
背景技術:
近年來,移動通信技術和網際網路技術的發展和廣泛應用,對人們的生活方式產生巨大影響。移動通信技術使人與人之間能夠隨時隨地進行溝通,而網際網路的發展使人們能迅速、快捷地獲取豐富的信息資源。兩種技術的結合使人們無論何時何地能通過移動終端自由地訪問網際網路的信息資源。目前絕大部分Web(網頁)頁面是為傳統個人電腦而設計的,包括桌上型電腦和筆記本電腦,它們具有較大的屏幕和高解析度。然而由於屏幕大小的物理局限、內存大小和無線網絡帶寬等因素的限制,移動終端直接訪問已有的Web頁面難以正常顯示頁面,Web頁面的二維布局不適合移動終端屏幕顯示。目前通常通過兩種手段來解決這種問題:通過伺服器進行頁面轉換或者使用網頁縮略圖。前者首先將用戶訪問的頁面進行分頁和轉換,然後將分頁的結果提交給行動裝置;後者則是將整個Web頁面生成縮略圖,整個頁面被分割為數目不等的區域,用戶如果對特定區域感興趣,則可以再次訪問該區域的內容。通過這兩個策略,基本可以完成移動終端訪問網際網路的內容,但是核心內容就是對頁面進行語義分割。
如何對Web頁面進行有效的分頁,目前提出的VIPS(基於視覺信息的網頁分塊)算法,充分利用了頁面的布局特點並從語義層次對頁面進行劃分,將視覺提示信息和DOM(文檔對象模塊)結合起來推斷出可視化的內容結構。該算法以預定義的PDoC(頁面預先定義的內聚度閥值,Permitted DegreeofCoherence)值作為迭代的終止條件,當各塊的內聚度值大於PDoC值是迭代終止,預定義的終止條件影響了分塊的效果。
技術實現要素:
針對現有技術中的缺陷,本發明的目的是提供一種啟發式多特徵規則集網頁分塊方法,其不需要事先定義PDoC值,方法簡單可靠,網頁分塊效果好,便於伺服器進行頁面轉換或使用網頁縮略圖,使移動端訪問網際網路的內容,並且在分塊過程中獲取了每個塊的結構信息和內容信息,便於後續進行Web頁面信息的提取和頁面內容的重組。
根據本發明的一個方面,提供啟發式多特徵規則集網頁分塊方法,其特徵在於,其包括以下步驟:
步驟一,調用VIPS算法將待操作的網頁生成頁面的塊結構樹;
步驟二,根據啟發式多特徵規則集對結構樹進行裁剪;
步驟三,生成語義獨立的塊列表;
步驟二包括以下判斷過程:
過程一,根據塊間語義距離的推理規則確定當前塊是否要繼續分隔;
過程二,若過程一的結果為否,繼續按照分割流程來判斷是否繼續分割;
過程三,將不需要分割的節點納入塊列表,需要分割的塊對它的子節點同樣進行檢查;
推理規則包括:
規則一,兩個節點所對應塊的語義距離初始為零;
規則二,如果兩個頁面塊的距離越遠,則兩個頁面塊的語義關係越不緊密;
規則三,如果兩個頁面塊的背景色不同,但兩個頁面塊相鄰且兩個頁面塊的寬度相差不超過30%且上面塊的面積大於下面塊的面積的一百倍,那麼兩個頁面塊間語義距離保持不變;
規則四,如果兩個頁面塊的背景色不同且不是規則三的情況,那麼兩個頁面塊的語義關係不緊密,兩個頁面塊間語義距離值加一;
規則五,如果兩個頁面塊的字體大小不同且兩個頁面塊不是上下相鄰,那麼兩個頁面塊間語義距離值加一;
規則六,如果兩個頁面塊的字體不同,兩個頁面塊上下相鄰,上面塊的面積的一百倍小於下面塊的面積,上面塊的字體小於下面塊的字體,那麼兩個頁面塊間語義距離值加一;
規則七,如果兩個頁面塊的字體不同,兩個頁面塊上下相鄰,上面塊的面積大於下面塊的面積,那麼兩個頁面塊間語義距離值加一;
規則八,如果兩個頁面塊的字體大小不同,兩個頁面塊上下相鄰且上面塊的面積和下面塊的面積相差不超過30%,那麼兩個頁面塊間語義距離值加一;
規則九,如果兩個頁面塊的字體重量不同且兩個頁面塊不是上下相鄰,那麼兩個頁面塊間語義距離值加一;
規則十,如果兩個頁面塊的字體重量不同,兩個頁面塊上下相鄰,上面塊的面積的一百倍小於下面塊的面積,上面塊的字體重量小於下面塊的字體重量,那麼兩個頁面塊間語義距離值加一;
規則十一,如果兩個頁面塊的字體重量不同,兩個頁面塊上下相鄰,上面塊的面積大於下面塊的面積,那麼兩個頁面塊間語義距離值加一;
規則十二,如果兩個頁面塊的字體重量不同,兩個頁面塊上下相鄰且上面塊的面積和下面塊的面積相差不超過30%,那麼兩個頁面塊間語義距離值加一;
規則十三,如果兩個頁面塊不是兄弟塊且其中一個塊的父節點與另外一塊為兄弟節點,那麼兩個頁面塊間語義距離等於父節點與其的塊間語義距離加上父塊與兄弟塊間的語義距離;
分割流程包括:
流程一,若該塊的內聚度為十一,則表明該塊已經是葉子節點,不需要繼續分割,否則進入流程二;
流程二,若該塊是一個列表類型,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程三;
流程三,若該塊是一個橫向滾動條列表類型,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程四;
流程四,若該塊的所有孩子節點的內聚度都是十一,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程五;
流程五,若該塊的孩子節點是左右相鄰的,則該塊需要繼續分割,否則進入流程六;
流程六,若該塊的內聚度與其所有孩子節點的內聚度一致,表明父塊內部結構的緊密程度與子塊類似,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程七;
流程七,若該塊有兩個孩子,其中一個孩子節點的DoC值為十一,另一個孩子節點的DoC值與當前塊值一致,且該孩子節點的孩子不是左右相鄰的,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程八;
流程八,若上述流程中的條件都不滿足,則該塊需要繼續分割,遍歷其孩子節點,繼續判斷。
優選地,所述步驟三在生成語義獨立的塊列表的過程中獲取每個塊的結構信息和內容信息。
與現有技術相比,本發明具有如下的有益效果:本發明不需要事先定義PDoC值,方法簡單可靠,網頁分塊效果好,便於伺服器進行頁面轉換或使用網頁縮略圖,使移動端訪問網際網路的內容,並且在分塊過程中獲取了每個塊的結構信息和內容信息,便於後續進行Web頁面信息的提取和頁面內容的重組。本發明方便伺服器進行頁面轉換或是使用網頁縮略圖,從而完成移動終端訪問網際網路內容。
附圖說明
通過閱讀參照以下附圖對非限制性實施例所作的詳細描述,本發明的其它特徵、目的和優點將會變得更明顯:
圖1為本發明的步驟流程圖。
圖2為本發明判斷塊節點是否需要分割的流程圖。
圖3為本發明耦合度隨分割層次的變化曲線圖。
圖4為本發明內聚度隨分割層次的變化曲線圖。
圖5為本發明J值隨分割層次的變化曲線圖。
具體實施方式
下面結合具體實施例對本發明進行詳細說明。以下實施例將有助於本領域的技術人員進一步理解本發明,但不以任何形式限制本發明。應當指出的是,對本領域的普通技術人員來說,在不脫離本發明構思的前提下,還可以做出若干變形和改進。這些都屬於本發明的保護範圍。
如圖1所示,本發明啟發式多特徵規則集網頁分塊方法包括以下步驟:
步驟一,調用VIPS算法將待操作的網頁生成頁面的塊結構樹,將頁面內聚度PDoC值設置為允許的最大值;
步驟二,根據啟發式多特徵規則集對結構樹進行裁剪;
步驟三,生成語義獨立的塊列表;
步驟二包括以下判斷過程:
過程一,根據塊間語義距離的推理規則確定當前塊是否要繼續分隔;
過程二,若過程一的結果為否,繼續按照分割流程來判斷是否繼續分割;
過程三,將不需要分割的節點納入塊列表,需要分割的塊對它的子節點同樣進行檢查;
調用VIPS算法後,每個頁面由樹表示,樹的每個節點對應於一個塊,每個塊由其結構信息、內容信息和內聚度組成,深度遍歷塊結構樹,根據啟發式多特徵規則集對結構樹進行裁剪,在每次迭代中,檢查結構樹當前層的每個塊節點,確定它是否需要繼續分割,如果能,則對它的子節點進行同樣的檢查,如果不能,則裁剪掉以該節點為父節點的子樹;
推理規則包括以下規則:
規則一,兩個節點所對應塊的語義距離初始為零;
規則二,如果兩個頁面塊的距離越遠,則兩個頁面塊的語義關係越不緊密,假設兩個頁面塊間的距離為distance,故兩個頁面塊間的語義距離增加distanc/l,其中1是規範因子,是整個頁面的對角線長度;
規則三,如果兩個頁面塊的背景色不同,但兩個頁面塊相鄰且兩個頁面塊的寬度相差不超過30%且上面塊的面積大於下面塊的面積的一百倍,那麼兩個頁面塊間語義距離保持不變;
規則四,如果兩個頁面塊的背景色不同且不是規則三的情況,那麼兩個頁面塊的語義關係不緊密,兩個頁面塊間語義距離值加一;
規則五,如果兩個頁面塊的字體大小不同且兩個頁面塊不是上下相鄰,那麼兩個頁面塊間語義距離值加一;
規則六,如果兩個頁面塊的字體不同,兩個頁面塊上下相鄰,上面塊的面積的一百倍小於下面塊的面積,上面塊的字體小於下面塊的字體,那麼兩個頁面塊間語義距離值加一;
規則七,如果兩個頁面塊的字體不同,兩個頁面塊上下相鄰,上面塊的面積大於下面塊的面積,那麼兩個頁面塊間語義距離值加一;
規則八,如果兩個頁面塊的字體大小不同,兩個頁面塊上下相鄰且上面塊的面積和下面塊的面積相差不超過30%,那麼兩個頁面塊間語義距離值加一;
規則九,如果兩個頁面塊的字體重量不同且兩個頁面塊不是上下相鄰,那麼兩個頁面塊間語義距離值加一;
規則十,如果兩個頁面塊的字體重量不同,兩個頁面塊上下相鄰,上面塊的面積的一百倍小於下面塊的面積,上面塊的字體重量小於下面塊的字體重量,那麼兩個頁面塊間語義距離值加一;
規則十一,如果兩個頁面塊的字體重量不同,兩個頁面塊上下相鄰,上面塊的面積大於下面塊的面積,那麼兩個頁面塊間語義距離值加一;
規則十二,如果兩個頁面塊的字體重量不同,兩個頁面塊上下相鄰且上面塊的面積和下面塊的面積相差不超過30%,那麼兩個頁面塊間語義距離值加一;
規則十三,如果兩個頁面塊不是兄弟塊且其中一個塊的父節點與另外一塊為兄弟節點,那麼兩個頁面塊間語義距離等於父節點與其的塊間語義距離加上父塊與兄弟塊間的語義距離;
分割流程包括以下流程:
流程一,若該塊的內聚度為十一,則表明該塊已經是葉子節點,不需要繼續分割,否則進入流程二;
流程二,若該塊是一個列表類型,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程三;
流程三,若該塊是一個橫向滾動條列表類型,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程四;
流程四,若該塊的所有孩子節點的內聚度都是十一,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程五;
流程五,若該塊的孩子節點是左右相鄰的,則該塊需要繼續分割,否則進入流程六;
流程六,若該塊的內聚度與其所有孩子節點的內聚度一致,表明父塊內部結構的緊密程度與子塊類似,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程七;
流程七,若該塊有兩個孩子,其中一個孩子節點的DoC值為十一,另一個孩子節點的DoC值與當前塊值一致,且該孩子節點的孩子不是左右相鄰的,則停止分割,以該節點為父節點的子樹被裁減掉,否則進入流程八;
流程八,若上述流程中的條件都不滿足,則該塊需要繼續分割,遍歷其孩子節點,繼續判斷。
塊間的耦合度可以根據塊間語義距離來確定,耦合度的計算公式如下式(1):
公式(1)中,DoCL是塊間的耦合度,SD是塊間的語義距離。塊間的語義距離用來衡量兩個頁面塊之間的語義相關性,距離越大,說明兩個頁面塊語義上越不相關。耦合度用來衡量頁面塊間語義的緊密關係。與塊間語義距離塊相反,塊間語義距離越大,塊間的耦合度就越小。
如圖3至圖4所示,當塊較大的時候,由於塊包含的主題較多,與其他塊的語義有部分重疊,故塊間的耦合度比較大,隨著塊的分割,每個塊的語義越來越單一,與其他塊的語義重疊部分較少,使得塊間的耦合度不斷地減少,但是如果塊分割的過細,就會破壞語義的完整性,使得塊間的耦合度增大,因此,隨著分割層次的增加,當前葉子節點對應塊之間的平均耦合度會不斷地減少,直到達到最小值,然後會隨著分割層次的增加不斷地增大。內聚度是用來衡量塊內部結構緊密性的,子塊的內聚度總是大於或等於父塊的內聚度,內聚度總是隨著塊的分割不斷地增大,當塊分割到一定的程度,其內聚度達到允許的最大值,因此,葉子節點對應塊的平均內聚度則會隨著分割層次的增加不斷地增大,直到達到最大值。
根據耦合度和內聚度的變化趨勢可以看出對於頁面分割而言,當塊與其他塊的耦合度值較低,同時塊的內聚度比較高的時候,頁面的分割最好,因此根據內聚度高,耦合度低的原則,進行最大化下面的目標函數J,如下式(2):
公式(2)中,avg_DoCL是所有節點所對應塊間的耦合度的平均值,如下式(3):
在一個有k個節點的集合塊裡,兩兩配對且不重複,則第1個節點與它配對的有k-1個塊,第2個節點與它配對的有k-2個塊,依次類推,則第k-1個節點與它配對的只有1個塊,即第k個節點,所以一共有1+2+3+……k-1=k(k-1)/2對組合,而DoCL(i,j)代表集合塊裡節點i和節點j間的耦合度,∑i=1..k∑j≠i DoCL(i,j)表示所有配對塊之間的耦合度值的總和,所以所有節點所對應塊間的耦合度的平均值就是耦合度值的總和除以塊間配對組合數,即公式(3)的表達。
avg_Doc是指所有節點所對應塊的內聚度的平均值,如下式(4):
在一個有k個節點的集合塊裡,DoC(i)表示集合塊裡第i個節點的內聚度值,Σi=i..k DoC(i)表示所有k個節點內聚度值的總和,而集合裡共有k個節點,所以所有節點所對應塊的內聚度的平均值就是內聚度值的總和除以節點的個數,即公式(4)的表達。
目標函數J值的變化趨勢如圖5所示,對塊結構樹的每個節點進行檢查,將分割前的J值Jbefore與分割後的J值Jafter進行比較,每次比較只考慮分割帶來的局部影響,即某節點分割後對其兄弟節點的影響。假設有兩個頁面塊集合A和B,A為某節點與其兄弟節點,B為某節點的子節點與該節點的兄弟節點,|A|表示集合A的大小,|B|表示集合B的大小,Jbefore是集合A中所有塊的J值Jafter是集合B中所有塊的J值,如果Jbefore≥Jafter,則該節點停止分割,以該節點為父節點的子樹被裁減掉。
所述步驟三在生成語義獨立的塊列表的過程中獲取每個塊的結構信息和內容信息,這樣便於後續進行Web頁面信息的提取和頁面內容的重組。
VIPS算法對頁面進行劃分,是通過預先定義的閥值PDoC控制分塊的粒度。當PDoC值較大,頁面塊分的很細,當PDoC較小時,頁面塊分的很細。但對於不同的頁面,採用同一PDoC值,會導致部頁面塊分得過細,而部分頁面塊分得過粗。而本發明不需要事先定義PDoC值,並且能夠取得近似於或好於取最佳PDoC值的VIPS劃分效果。
本發明在分塊的過程中會獲取每個塊的結構信息:,和內容信息:<圖片數,圖片大小,連結數,連結文字樹,總文字,總文字長度,標籤文字>,以便後續進行Web頁面信息提取和頁面內容重組。
以上對本發明的具體實施例進行了描述。需要理解的是,本發明並不局限於上述特定實施方式,本領域技術人員可以在權利要求的範圍內做出各種變形或修改,這並不影響本發明的實質內容。