XML文檔加權層次子樹模型的建立

王寅

摘要：隨著互聯網的快速發展，具有自描述、半結構化和可擴展特點的XML成為互聯網上數據存儲和數據交換的標準。本文在樹型結構模型和頻繁路徑模型的基礎上，提出針對XML文檔結構聚類的模型——加權層次子樹模型，能夠表示出XML文檔的層次關系和層次信息。通過消除重復元素和重復表達式，用更加簡潔的表達式表示出XML文檔的層次和元素信息，能夠快速、準確分辨出具有相同結構的XML文檔。

關鍵詞：XML文檔;加權層次子樹模型;建立

中圖分類號：TP311 文獻標識碼：A 文章編號：1007-9416（2019）04-0208-02

1 緒論

近年來，隨著互聯網的快速發展，網絡信息量呈幾何級數增長，從海量數據中快速、準確地檢索出用戶所需信息成為研究熱點。具有自描述、半結構化和可擴展特點的XML（eXtensible Markup Language，可擴展標記語言）成為數據表示和數據交換的標準。

在各種XML文檔結構的表示方法中，樹型結構模型和頻繁路徑模型是兩種常用表示模型。其中，樹型結構模型具有直觀、易于理解等特點，但它會隨著文檔規模的增大而變得復雜，處理時間也隨之增加，不能對文檔中的重復元素作出很好的響應。頻繁路徑模型具有表示形式簡單的特點，但它不能完整的描述文檔結構，聚類準確類不高。本文綜合樹型結構模型和頻繁路徑模型的優缺點，提出針對XML文檔結構聚類模型——加權層次子樹模型。

2 加權層次子樹模型的定義

2.1 模型說明

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

每一個含有非空子節點的每一個元素節點都對應加權層次子樹模型中的一條加權層次子樹表達式關系。表達模式即模型中元素之間的父子關系，這一系列父子關系的集合構成加權層次子樹模型的主體。

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

2.2 模型定義

（1）加權層次子樹表達式的定義。加權層次子樹表達式的定義為：r=（ef，ec，l，w）。其中，1）ef是元素與其子元素形成的二層子樹中的父元素，且ef∈E，E表示元素的集合。2）ec是二層子樹中的子元素集合，即二層子樹的葉節點集合，且ec∈E。3）層次l∈N，N表示自然數，是二層子樹中的父元素在整個XML樹型結構文檔中的層次，其中根節點的層次“l”為1，每向下一層“l”加1。4）w∈N是二層子樹中的父元素在整個XML樹型結構文檔中的權重，其中根節點的權重最大

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

（3）加權層次子樹表達式舉例說明。以XML文檔BookInfo.xml為例，介紹加權層次子樹表達式。部分文檔內容如下：

可以看到，加權層次子樹模型由加權層次子樹表達式集合組成，簡潔明了、表達完整，充分體現了元素之間的父子關系。在加權層次子樹表達式中體現了元素父節點所在的層次及該層的權重，這樣構成的模型可以很好提高XML文檔的相似度計算的精確度，從而可以更好的進行XML文檔聚類。

3 加權層次子樹模型的簡化

構造完加權層次子樹的表達式后，父元素構成的二層子樹的子元素集合中可能有重復出現的子元素。加權層次子樹模型考慮的是父元素與子元素的關系，相同的子元素對父元素的影響看作是相同的，所以要去除父元素里包含的相同子元素。XML文檔中會包含著很多這樣重復的節點，隨著XML文檔規模的增大，重復節點也會相應增多，會使表達式顯得冗余，也增加了表達式的數量，導致執行效率降低。所以，為構造一個良好的結構模型需要對模型進行簡化。

3.1 去除重復的元素

去除重復元素即去除由父元素構成的二層子樹的子元素集合中相同子元素，最終只保留一個這樣的子元素。例如，以a為父節點的二層子樹，子樹中子元素集合為{b，c，c，c}，存在重復子元素c，需要進行模型簡化。只保留一個元素c，其余的元素c都刪除，去重后的子元素集合為{b，c}，加權層次子樹表達式為：r=（a，{b，c}，l，w）。

3.2 去除重復的加權層次表達式

重復的加權層次表達式即具有相同的父元素，且在相同父元素下的子元素集也相同，父元素所在的層次和權重也完全相同。多個相同的加權層次表達式會給模型帶來很大的冗余。當XML文檔規模很大時，重復的加權層次表達式會嚴重影響執行效率。

如圖1所示的以a為根節點的加權層次子樹，先去除重復元素。第一層父節點中有重復的子元素c，只保留1個即可。第二層父節點中以c為相同父節點、且具有相同的加權層次表達式的子元素h、j，只保留一個即可。

4 加權層次子樹模型的建立

構造加權層次子樹模型的步驟分2步，首先將XML文檔解析成DOM樹，提取加權層次子樹表達式;隨后精簡提取的表達式，刪除重復的元素和加權層次表達式，得到精簡的加權層次子樹模型。

將XML解析為DOM樹后，從根節點開始遍歷。進行到一個節點，判斷其是否有子節點，若沒有子節點則放棄，若有子節點則將其作為父節點生成相應的加權層次子樹表達式。在子節點集中，判斷每一個子元素是否與現有子元素相同，若相同則不將其添加到子節點集合中;若不同則可添加，并將父節點所在的層次和權重加入表達式。通過對DOM樹遞歸調用就可得到全部的加權層次子樹表達式，并刪除重復元素。刪除重復元素后，進一步去除重復的加權層次表達式。加權層次子樹模型解決了樹型結構模型不易處理、執行效率低的問題，更好的表示了XML文檔中的層次關系，彌補了頻繁路徑模型層次關系表達的欠缺。

5 結語

本文在現有XML文檔模型的基礎上，提出了加權層次子樹模型。模型考慮了層次信息，以元素之間的關系為主體，將元素所在的層次以及層次的權重納入加權層次表達式中，精確表達了XML文檔的結構。

參考文獻

[1] 王大偉，崔婉秋，覃飆.基于XML搜索的相關技術及發展[J].小型微型計算機系統，2018，39（07）：1390-1397.

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

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

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

[5] 陳飛飛.基于DOM4J的XML文檔解析技術研究與應用[J].軟件導刊，2016，15（03）：36-37.