基于加權層次子樹模型的XML文檔相似度的計算

劉菲

摘 要：XML因其具有的半結構化、可擴展性和自描述性等特點，在互聯網中得到廣泛應用。海量的XML文檔也帶來數據搜索的困難。本文基于加權層次子樹模型，提出模型的相似度計算方法。首先考慮元素的語義信息，將XML文檔的元素語義信息納入計算中，其次考慮到層次的權重問題，靠近根節點層次上的節點比遠離根節點層次上的節點占的比重要大。更加精確了相似度計算，從而達到很好的聚類效果。

關鍵詞：XML文檔;加權層次子樹模型;文檔相似度;計算

中圖分類號：TP391 文獻標識碼：A 文章編號：1671-2064（2019）14-0039-02

1 緒論

XML（eXtensible Markup Language，可擴展標記語言）因其具有的半結構化、可擴展性和自描述性等特點，在互聯網中得到廣泛應用，并逐漸成為數據表示和數據交換的標準。海量的XML文檔也帶來數據搜索的困難，用戶開始發現難以從中快速、便捷的挖掘出有價值的信息。

提高XML文檔相似度計算的速度和準確性對信息檢索結果有直接影響，是對XML文檔進行智能檢索、處理的基礎。本文針對加權層次子樹模型的XML文檔進行研究。加權層次子樹模型以層次結構為基礎，考慮了語義信息及層次權重信息，使表達式內容更加完整。新增的層次權重顯示越靠近根節點的元素對文檔相似度的重要性越大，越遠離根節點的元素對文檔相似度的重要性越小。這樣就可以充分利用層次之間的差距來表示XML文檔的相似度。

本文在文檔相似度計算中將綜合考慮文本語義、結構信息和節點層次權重等因素的影響，并使用K-中心點聚類算法對XML文檔進行聚類分析。

2 元素相似度計算

元素是指文檔中某個開始標簽到相應結束標簽之間的內容。元素是XML文檔的最小單位，也是加權層次子樹模型的基本組成單位。通常用元素名稱來代表元素。元素標簽的語義信息可以直接反映元素的語義，可以通過計算元素的語義信息來更準確的表示文檔相似度。

2.1 元素標簽還原

由于XML元素具有自描述性，所以元素標簽的形式多種多樣，不僅有單詞形式，還有單詞縮寫、用連接符形成的詞組等形式。所以，計算元素相似度時要把元素標簽還原成具有語義信息的單詞或詞組（多個單詞）。

由單詞縮寫構成的元素標簽，可使用常用縮寫、簡寫單詞的對照表將元素標簽還原成有具體含義的單詞集合，如DBA可轉化為{DataBase，Admin}。由連接符構成的元素標簽，刪除連接符構成還原后的單詞集合。如Student_ Name可轉化為{Student，Name}。若元素是由具有實際語義的單詞組成，可將這個單詞單獨看成一個單詞集合。

2.2 計算元素標簽的語義相似度

計算單詞相似度的方法是：（1）根據WordNet的同義網絡關系來判斷兩個單詞的語義是否為相同或相似。（2）如果兩個單詞是同義詞或近義詞，則兩個單詞的相似度為1;如果兩個單詞語義不同，根據字符串編輯距離來計算這兩個單詞之間的相似度。

單詞相似度的計算過程可以表示為：

function wordSim（w1，w2）{

if （w1 and w2 are synonym in WordNet）

return wordSim=1;

else{

wordSim=1-StringEditDistance（w1，w2）/max（|w1|，| w2|）;

if（wordSim >=） //表示單詞的閾值

return wordSim;

else ? ?return 0;

}

}

其中，若兩個單詞的相似度低于閾值，則這兩個單詞的相似度為0;若兩個單詞的高于閾值且不完全相似，則這兩個單詞的相似度為根據字符編輯距離的計算值;若兩個單詞根據WordNet判斷相同或相近，則這兩個單詞的相似度為1。

3 加權層次表達式集合的相似度計算

加權層次表達式集合是加權層次子樹模型的主體，表達式表現了元素之間的父子關系，是與XML文檔對應的父元素和父元素對應的子元素集合。但每條表達式中父元素對應的子元素只表達該父元素的部分子元素，不能表示全部子元素。所以，要對相同父元素的加權層次表達式集合進行合并，這樣的表達式集合才是該父元素的全部子元素集合。隨后對兩篇文檔中擁有相同或相似父元素的加權層次表達式集合進行相似度計算，計算結果即為相同父元素的加權層次表達式集合相似度。

在計算相同父元素的加權層次表達式集合的相似度之前，要先計算單個加權層次達式的相似度。兩個父元素相同的加權層次表達式的相似度看它們含有的子元素集合中的子節點的相似情況。若擁有的子節點相似程度大，則相似度高;反之，相似度低。子節點相似度childSim計算如式（2）所示。

4 加權層次子樹模型的相似度計算

加權層次模型是加權層次表達式的集合，表達式集合的相似度由相同父元素的表達式集合的相似度決定。要計算兩個模型的相似度要先找到兩個模型中父元素相同或相似的表達式集合。將兩個模型中的父元素組成兩個集合，并記錄相似度，選出相似度最大的，將其對應位置存儲為0，避免以后相似的元素對中含有重復的元素。判斷是否有相似的元素，有則繼續存儲。這樣就找到了兩個模型中匹配的父元素相同的表達式集合。

每條層次表達式都有其相對于整個XML文檔的重要性。若某條層次表達式相對于它的XML文檔比較重要，就將此層次表達式的重要性加大;反之，重要性降低。這樣要考慮層次表達式的權重，即越靠近元素根節點的元素的重要性越大，權重也越大;反之權重越小。例如有DOM樹：（1）/books/book/title/（2）/bib/book/title/（3）/books/book/price/。若不考慮各層次的權重，可計算出層次模型的相似度，即累加層次集合相似度再除以最大層次集合的個數。得到，，。但直觀看，DOM樹（1）和DOM樹（3）要比DOM樹（1）和DOM樹（2）更相似，這就需要考慮層次的權重信息。

把層次的權重信息考慮到層次子樹模型中，就構成了加權層次子樹模型。以2i為加權層次子樹模型的權重值，i=0為最底層的葉子節點，每高一層i+1，計算得出的層次集合相似度就是兩個XML文檔中每個父節點的相似度。可把計算得到的層次集合相似度看成是一顆DOM樹各個節點的相似度，乘以各個節點所在層次的權重再除以DOM樹全部節點相似度為1的值，就得到加權層次子樹模型的相似度。加權層次子樹模型的相似度的計算如式（5）所示。

5 結語

加權層次子樹模型考慮了層次信息，以元素之間的關系為主體，將元素所在的層次以及層次的權重納入加權層次表達式中，這樣就更精確的表達了XML文檔的結構，從而為相似度計算打好基礎。在本文提出的基于加權層次子樹模型的相似度計算中考慮了元素的語義信息，文本的結構信息、層次信息以及層次的權重。這樣可以更精確的計算出文檔之間的相似度。

參考文獻

[1] 徐建民，許彩云.基于文本和公式的科技文檔相似度計算[J].數據分析與知識發現，2018，2（10）：103-109.

[2] 李征，李斌.一種基于改進相似度計算的文本聚類方法[J].河南大學學報（自然科學版），2018，48（04）：415-420.

[3] 朱振國，劉民康，趙凱旋.基于用戶聯合相似度的推薦算法[J].計算機系統應用，2018，27（05）：126-132.

[4] 魏小銳.基于整體相似度的文檔主題匹配研究[J].網絡安全技術與應用，2018（03）：44-46.

[5] 吳海濤，郭麗紅，楊潔.基于矩陣存儲的XML相似度檢測算法[J].計算機應用研究，2018，35（07）：2025-2029.