劉菲

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

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

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

1 緒論

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

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

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

2 元素相似度計(jì)算

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

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

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

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

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

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

單詞相似度的計(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;

}

}

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

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

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

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

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

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

每條層次表達(dá)式都有其相對(duì)于整個(gè)XML文檔的重要性。若某條層次表達(dá)式相對(duì)于它的XML文檔比較重要，就將此層次表達(dá)式的重要性加大;反之，重要性降低。這樣要考慮層次表達(dá)式的權(quán)重，即越靠近元素根節(jié)點(diǎn)的元素的重要性越大，權(quán)重也越大;反之權(quán)重越小。例如有DOM樹：（1）/books/book/title/（2）/bib/book/title/（3）/books/book/price/。若不考慮各層次的權(quán)重，可計(jì)算出層次模型的相似度，即累加層次集合相似度再除以最大層次集合的個(gè)數(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é)點(diǎn)，每高一層i+1，計(jì)算得出的層次集合相似度就是兩個(gè)XML文檔中每個(gè)父節(jié)點(diǎn)的相似度。可把計(jì)算得到的層次集合相似度看成是一顆DOM樹各個(gè)節(jié)點(diǎn)的相似度，乘以各個(gè)節(jié)點(diǎn)所在層次的權(quán)重再除以DOM樹全部節(jié)點(diǎn)相似度為1的值，就得到加權(quán)層次子樹模型的相似度。加權(quán)層次子樹模型的相似度的計(jì)算如式（5）所示。

5 結(jié)語

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

參考文獻(xiàn)

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

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

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

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

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