基于加權(quán)層次子樹模型的XML文檔相似度的計算

劉菲

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

關(guān)鍵詞：XML文檔;加權(quán)層次子樹模型;文檔相似度;計算

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

1 緒論

XML（eXtensible Markup Language，可擴展標(biāo)記語言）因其具有的半結(jié)構(gòu)化、可擴展性和自描述性等特點，在互聯(lián)網(wǎng)中得到廣泛應(yīng)用，并逐漸成為數(shù)據(jù)表示和數(shù)據(jù)交換的標(biāo)準。海量的XML文檔也帶來數(shù)據(jù)搜索的困難，用戶開始發(fā)現(xiàn)難以從中快速、便捷的挖掘出有價值的信息。

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

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

2 元素相似度計算

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

2.1 元素標(biāo)簽還原

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

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

2.2 計算元素標(biāo)簽的語義相似度

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

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

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;若兩個單詞的高于閾值且不完全相似，則這兩個單詞的相似度為根據(jù)字符編輯距離的計算值;若兩個單詞根據(jù)WordNet判斷相同或相近，則這兩個單詞的相似度為1。

3 加權(quán)層次表達式集合的相似度計算

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

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

4 加權(quán)層次子樹模型的相似度計算

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

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

把層次的權(quán)重信息考慮到層次子樹模型中，就構(gòu)成了加權(quán)層次子樹模型。以2i為加權(quán)層次子樹模型的權(quán)重值，i=0為最底層的葉子節(jié)點，每高一層i+1，計算得出的層次集合相似度就是兩個XML文檔中每個父節(jié)點的相似度?？砂延嬎愕玫降膶哟渭舷嗨贫瓤闯墒且活wDOM樹各個節(jié)點的相似度，乘以各個節(jié)點所在層次的權(quán)重再除以DOM樹全部節(jié)點相似度為1的值，就得到加權(quán)層次子樹模型的相似度。加權(quán)層次子樹模型的相似度的計算如式（5）所示。

5 結(jié)語

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

參考文獻

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

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

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

[4] 魏小銳.基于整體相似度的文檔主題匹配研究[J].網(wǎng)絡(luò)安全技術(shù)與應(yīng)用，2018（03）：44-46.

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