XML文檔加權(quán)層次子樹(shù)模型的建立

王寅

摘要：隨著互聯(lián)網(wǎng)的快速發(fā)展，具有自描述、半結(jié)構(gòu)化和可擴(kuò)展特點(diǎn)的XML成為互聯(lián)網(wǎng)上數(shù)據(jù)存儲(chǔ)和數(shù)據(jù)交換的標(biāo)準(zhǔn)。本文在樹(shù)型結(jié)構(gòu)模型和頻繁路徑模型的基礎(chǔ)上，提出針對(duì)XML文檔結(jié)構(gòu)聚類(lèi)的模型——加權(quán)層次子樹(shù)模型，能夠表示出XML文檔的層次關(guān)系和層次信息。通過(guò)消除重復(fù)元素和重復(fù)表達(dá)式，用更加簡(jiǎn)潔的表達(dá)式表示出XML文檔的層次和元素信息，能夠快速、準(zhǔn)確分辨出具有相同結(jié)構(gòu)的XML文檔。

關(guān)鍵詞：XML文檔;加權(quán)層次子樹(shù)模型;建立

中圖分類(lèi)號(hào)：TP311 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1007-9416（2019）04-0208-02

1 緒論

近年來(lái)，隨著互聯(lián)網(wǎng)的快速發(fā)展，網(wǎng)絡(luò)信息量呈幾何級(jí)數(shù)增長(zhǎng)，從海量數(shù)據(jù)中快速、準(zhǔn)確地檢索出用戶所需信息成為研究熱點(diǎn)。具有自描述、半結(jié)構(gòu)化和可擴(kuò)展特點(diǎn)的XML（eXtensible Markup Language，可擴(kuò)展標(biāo)記語(yǔ)言）成為數(shù)據(jù)表示和數(shù)據(jù)交換的標(biāo)準(zhǔn)。

在各種XML文檔結(jié)構(gòu)的表示方法中，樹(shù)型結(jié)構(gòu)模型和頻繁路徑模型是兩種常用表示模型。其中，樹(shù)型結(jié)構(gòu)模型具有直觀、易于理解等特點(diǎn)，但它會(huì)隨著文檔規(guī)模的增大而變得復(fù)雜，處理時(shí)間也隨之增加，不能對(duì)文檔中的重復(fù)元素作出很好的響應(yīng)。頻繁路徑模型具有表示形式簡(jiǎn)單的特點(diǎn)，但它不能完整的描述文檔結(jié)構(gòu)，聚類(lèi)準(zhǔn)確類(lèi)不高。本文綜合樹(shù)型結(jié)構(gòu)模型和頻繁路徑模型的優(yōu)缺點(diǎn)，提出針對(duì)XML文檔結(jié)構(gòu)聚類(lèi)模型——加權(quán)層次子樹(shù)模型。

2 加權(quán)層次子樹(shù)模型的定義

2.1 模型說(shuō)明

對(duì)XML文檔結(jié)構(gòu)進(jìn)行研究，需要首先建立XML文檔的結(jié)構(gòu)表示模型，并考慮表示信息完整、結(jié)構(gòu)簡(jiǎn)潔、易于理解和操作等要求。加權(quán)層次子樹(shù)模型描述的是元素與元素之間的層次關(guān)系，以每一個(gè)具體元素為中心，凡具有孩子節(jié)點(diǎn)的元素都可以形成一個(gè)二層子樹(shù)，在XML文檔樹(shù)中，每個(gè)二層子樹(shù)都可以描述其父子關(guān)系。這樣表述出來(lái)的模型就很清楚、很簡(jiǎn)潔的描述了父子關(guān)系及兄弟關(guān)系。

每一個(gè)含有非空子節(jié)點(diǎn)的每一個(gè)元素節(jié)點(diǎn)都對(duì)應(yīng)加權(quán)層次子樹(shù)模型中的一條加權(quán)層次子樹(shù)表達(dá)式關(guān)系。表達(dá)模式即模型中元素之間的父子關(guān)系，這一系列父子關(guān)系的集合構(gòu)成加權(quán)層次子樹(shù)模型的主體。

與元素層次模型和元素內(nèi)容模型不同，加權(quán)層次子樹(shù)模型是一種元素內(nèi)容模型。元素內(nèi)容模型由元素及其子元素構(gòu)成，元素之間的父子關(guān)系是其主要描述內(nèi)容，其子元素是該父元素的全部子元素。由于元素內(nèi)容模型在表示XML文檔模式方面具有優(yōu)勢(shì)，它經(jīng)常被用來(lái)進(jìn)行XML模式的抽取研究。與元素內(nèi)容模型相似，元素層次模型描述的也是元素之間的父子關(guān)系，但其中某個(gè)父元素所在的二層子樹(shù)中包含的子元素集合可能只是這個(gè)父元素的所有子元素的一部分，父元素要求有很多元素層次表達(dá)式才能全部描述其子元素的集合。

2.2 模型定義

（1）加權(quán)層次子樹(shù)表達(dá)式的定義。加權(quán)層次子樹(shù)表達(dá)式的定義為：r=（ef，ec，l，w）。其中，1）ef是元素與其子元素形成的二層子樹(shù)中的父元素，且ef∈E，E表示元素的集合。2）ec是二層子樹(shù)中的子元素集合，即二層子樹(shù)的葉節(jié)點(diǎn)集合，且ec∈E。3）層次l∈N，N表示自然數(shù)，是二層子樹(shù)中的父元素在整個(gè)XML樹(shù)型結(jié)構(gòu)文檔中的層次，其中根節(jié)點(diǎn)的層次“l(fā)”為1，每向下一層“l(fā)”加1。4）w∈N是二層子樹(shù)中的父元素在整個(gè)XML樹(shù)型結(jié)構(gòu)文檔中的權(quán)重，其中根節(jié)點(diǎn)的權(quán)重最大

（2）加權(quán)層次子樹(shù)模型的定義。加權(quán)層次子樹(shù)模型的定義為：M=（E，R）。其中，1）E表示XML文檔元素的集合，由元素e組成。2）R是加權(quán)層次子樹(shù)表達(dá)式的集合，r∈R。

（3）加權(quán)層次子樹(shù)表達(dá)式舉例說(shuō)明。以XML文檔BookInfo.xml為例，介紹加權(quán)層次子樹(shù)表達(dá)式。部分文檔內(nèi)容如下：

可以看到，加權(quán)層次子樹(shù)模型由加權(quán)層次子樹(shù)表達(dá)式集合組成，簡(jiǎn)潔明了、表達(dá)完整，充分體現(xiàn)了元素之間的父子關(guān)系。在加權(quán)層次子樹(shù)表達(dá)式中體現(xiàn)了元素父節(jié)點(diǎn)所在的層次及該層的權(quán)重，這樣構(gòu)成的模型可以很好提高XML文檔的相似度計(jì)算的精確度，從而可以更好的進(jìn)行XML文檔聚類(lèi)。

3 加權(quán)層次子樹(shù)模型的簡(jiǎn)化

構(gòu)造完加權(quán)層次子樹(shù)的表達(dá)式后，父元素構(gòu)成的二層子樹(shù)的子元素集合中可能有重復(fù)出現(xiàn)的子元素。加權(quán)層次子樹(shù)模型考慮的是父元素與子元素的關(guān)系，相同的子元素對(duì)父元素的影響看作是相同的，所以要去除父元素里包含的相同子元素。XML文檔中會(huì)包含著很多這樣重復(fù)的節(jié)點(diǎn)，隨著XML文檔規(guī)模的增大，重復(fù)節(jié)點(diǎn)也會(huì)相應(yīng)增多，會(huì)使表達(dá)式顯得冗余，也增加了表達(dá)式的數(shù)量，導(dǎo)致執(zhí)行效率降低。所以，為構(gòu)造一個(gè)良好的結(jié)構(gòu)模型需要對(duì)模型進(jìn)行簡(jiǎn)化。

3.1 去除重復(fù)的元素

去除重復(fù)元素即去除由父元素構(gòu)成的二層子樹(shù)的子元素集合中相同子元素，最終只保留一個(gè)這樣的子元素。例如，以a為父節(jié)點(diǎn)的二層子樹(shù)，子樹(shù)中子元素集合為{b，c，c，c}，存在重復(fù)子元素c，需要進(jìn)行模型簡(jiǎn)化。只保留一個(gè)元素c，其余的元素c都刪除，去重后的子元素集合為{b，c}，加權(quán)層次子樹(shù)表達(dá)式為：r=（a，{b，c}，l，w）。

3.2 去除重復(fù)的加權(quán)層次表達(dá)式

重復(fù)的加權(quán)層次表達(dá)式即具有相同的父元素，且在相同父元素下的子元素集也相同，父元素所在的層次和權(quán)重也完全相同。多個(gè)相同的加權(quán)層次表達(dá)式會(huì)給模型帶來(lái)很大的冗余。當(dāng)XML文檔規(guī)模很大時(shí)，重復(fù)的加權(quán)層次表達(dá)式會(huì)嚴(yán)重影響執(zhí)行效率。

如圖1所示的以a為根節(jié)點(diǎn)的加權(quán)層次子樹(shù)，先去除重復(fù)元素。第一層父節(jié)點(diǎn)中有重復(fù)的子元素c，只保留1個(gè)即可。第二層父節(jié)點(diǎn)中以c為相同父節(jié)點(diǎn)、且具有相同的加權(quán)層次表達(dá)式的子元素h、j，只保留一個(gè)即可。

4 加權(quán)層次子樹(shù)模型的建立

構(gòu)造加權(quán)層次子樹(shù)模型的步驟分2步，首先將XML文檔解析成DOM樹(shù)，提取加權(quán)層次子樹(shù)表達(dá)式;隨后精簡(jiǎn)提取的表達(dá)式，刪除重復(fù)的元素和加權(quán)層次表達(dá)式，得到精簡(jiǎn)的加權(quán)層次子樹(shù)模型。

將XML解析為DOM樹(shù)后，從根節(jié)點(diǎn)開(kāi)始遍歷。進(jìn)行到一個(gè)節(jié)點(diǎn)，判斷其是否有子節(jié)點(diǎn)，若沒(méi)有子節(jié)點(diǎn)則放棄，若有子節(jié)點(diǎn)則將其作為父節(jié)點(diǎn)生成相應(yīng)的加權(quán)層次子樹(shù)表達(dá)式。在子節(jié)點(diǎn)集中，判斷每一個(gè)子元素是否與現(xiàn)有子元素相同，若相同則不將其添加到子節(jié)點(diǎn)集合中;若不同則可添加，并將父節(jié)點(diǎn)所在的層次和權(quán)重加入表達(dá)式。通過(guò)對(duì)DOM樹(shù)遞歸調(diào)用就可得到全部的加權(quán)層次子樹(shù)表達(dá)式，并刪除重復(fù)元素。刪除重復(fù)元素后，進(jìn)一步去除重復(fù)的加權(quán)層次表達(dá)式。加權(quán)層次子樹(shù)模型解決了樹(shù)型結(jié)構(gòu)模型不易處理、執(zhí)行效率低的問(wèn)題，更好的表示了XML文檔中的層次關(guān)系，彌補(bǔ)了頻繁路徑模型層次關(guān)系表達(dá)的欠缺。

5 結(jié)語(yǔ)

本文在現(xiàn)有XML文檔模型的基礎(chǔ)上，提出了加權(quán)層次子樹(shù)模型。模型考慮了層次信息，以元素之間的關(guān)系為主體，將元素所在的層次以及層次的權(quán)重納入加權(quán)層次表達(dá)式中，精確表達(dá)了XML文檔的結(jié)構(gòu)。

參考文獻(xiàn)

[1] 王大偉，崔婉秋，覃飆.基于XML搜索的相關(guān)技術(shù)及發(fā)展[J].小型微型計(jì)算機(jī)系統(tǒng)，2018，39（07）：1390-1397.

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

[3] 趙震，馬宗民.模糊XML文檔與模糊DTD相似性研究[J].東北大學(xué)學(xué)報(bào)（自然科學(xué)版），2017，38（02）：200-204.

[4]? 張沛朋，李杰.基于多層次技術(shù)的XML數(shù)據(jù)挖掘研究[J].蘭州文理學(xué)院學(xué)報(bào)（自然科學(xué)版），2016，30（03）：60-63.

[5] 陳飛飛.基于DOM4J的XML文檔解析技術(shù)研究與應(yīng)用[J].軟件導(dǎo)刊，2016，15（03）：36-37.