閆文剛，常 亮，于莉莉，劉 義，孫淑莉

(佳木斯大學，黑龍江 佳木斯154007)

0 引 言

為了加快XML 文檔的檢索效率，已經出現(xiàn)很多XML 文檔的索引技術，而這些技術的核心是對XML 文檔進行合理的編碼，這在XML 文檔檢索過程中起到了十分重要的作用，對于XML 文檔的索引編碼技術一般分為兩種方式，一種是建立XML文檔樹的路徑索引，這種方式對XML 結構查詢具有較快的響應速度，另一種是對XML 文檔樹中的節(jié)點或邊進行編碼，此種方式可以快速的判斷節(jié)點之間的關系，從而避免對整個XML 文檔的掃描.XML 文檔編碼包括三種類型:基于路徑的編碼、基于節(jié)點序號的編碼和混合編碼方式［1］.

在設計XML 編碼方案時需要考慮的因素包括:

(1)編碼應能夠體現(xiàn)出XML 文檔的結構特征，能夠正確描述判斷節(jié)點間關系，即支持祖先/子孫、雙親/孩子、節(jié)點位置等關系的結構查詢.

(2)插入和刪除操作導致的編碼重置的代價及其算法的復雜度也必須予以考慮.

(3)編碼必須要和采用的數據模型相一致，且編碼的最大長度或平均長度也應加以考慮.

(4)XML 文檔樹的檢索效率也應加以考慮.

考慮到DOM 節(jié)點樹和XXDM 文檔樹中所有的屬性節(jié)點和文本節(jié)點都是葉節(jié)點故進行如下定義.

定義1 XML 文檔樹是一顆樹，且該樹滿足如下條件:

(1)樹中任意一個內部節(jié)點iNode，對應XML文檔中的一個元素，表示為E(iNode);

(2)樹中任意一個外部節(jié)點oNode，對應XML文檔中的一個屬性或文本，當oNode 是一個屬性節(jié)點時表示為A(oNode)，當是一個文本節(jié)點時表示為T(oNode).

該定義的主要特點是將屬性節(jié)點和文本節(jié)點作為外部節(jié)點，這樣就可以更加清晰的描述XML文檔的結構，從而以更加高效的方式組織這些葉子節(jié)點［2］.

1 實驗方案

本實驗的目的在于在發(fā)生動態(tài)更新的XML 文檔中比較SUC 編碼方案與其他編碼方案進行重建編碼的效率.設計思路如下:首先利用DOM 解析器將XML 文檔解析為DOM 文檔樹，然后針對DOM 文檔樹進行編碼，將編碼結果存儲到關系數據庫中.實驗系統(tǒng)體系結構圖如圖1 所示.

圖1 實驗系統(tǒng)體系結構圖

其中SUC 編碼器類包括下列成員函數［3］:

在數據庫中建立兩個表，其中一個描述內部節(jié)點，另外一個描述外部節(jié)點.內部節(jié)點包含4 個屬性.對于外部節(jié)點，因其是用來描述屬性和文本的，而文本可以看做是一個特殊的屬性節(jié)點，故屬性節(jié)點包含兩個屬性:屬性名和屬性值，其中文本作為特殊的屬性節(jié)點，其屬性名固定為“文本”.兩個表單結構模式如下:

內部節(jié)點表nNodeTable(Xno，Level，Parent，Part);

外部節(jié)點表wNodeTable(Wno，Name，Value，Xno);

其中Xno，Level，Parent 為32 位二進制向量;因此在數據庫中和Java 環(huán)境下數據類型皆設置為整型.

為保證每個Part 編碼邏輯塊擁有足夠的空間，將Part 設置成8 個字節(jié)的二進制位，每個Part邏輯塊占8 位二進制位(即一個字節(jié))，因此共有8個Part 編碼邏輯塊.因而Part 在PostgreSQL 中的數據類型為int8，在Java 中數據類型為long.

需要說明的是，以上的數據庫設計不能完全描述實際應用中遇到的所有XML 文檔樹，該描述方法只能描述一顆文檔樹.由于本實驗的主要目的是驗證不同編碼方式在編碼性能和處理插入操作時的時間性能上的區(qū)別，不需要同時管理多顆文檔樹，因此上述數據庫設計可以滿足本實驗的實驗需要.

2 實驗過程及結果

在測試編碼的動態(tài)調整性能時，操作對象為初始化SUC 編碼實驗中用dom4j 解析的XML 文檔樹，在該文檔樹中隨機插入n 個節(jié)點，每個節(jié)點的插入位置在文檔樹中隨機挑選(即隨機選定n 個節(jié)點的Xno 作為待插入節(jié)點的左兄弟節(jié)點的Xno)然后使用DSUCcode()函數確定需要重新編碼的節(jié)點個數，并對這些節(jié)點進行重新編碼，然后將重新編碼后的節(jié)點編碼寫入數據庫中，對每次插入操作重復5 次，取5 次重新編碼所花費的時間的平均值作為其插入時間消耗.

在完成對本文提出的SUC 編碼實驗測試的同時，實驗中還對前綴編碼和Zhang 編碼一并進行了測試.

表1 三種編碼動態(tài)調整性能比較

圖2 M=2 時的時間消耗比

圖3 M=10 時的時間消耗比

在對長度為2M 和10M 的兩個XML 文檔分別進行五次插入試驗后的三種編碼動態(tài)調整過程中重新生成編碼的時間消耗如表1 所示.

為了說明問題，設tp 為前綴編碼動態(tài)調整時間消耗與SUC 編碼動態(tài)調整時間消耗的比值，tz為Zhang 編碼動態(tài)調整時間消耗與SUC 編碼動態(tài)調整時間消耗的比值.

分析表1 結果可知:

(1)XML 文檔較小時(文檔長度小于2M)，當插入結點個數較少時(插入節(jié)點的個數小于10個)，三種編碼方式的動態(tài)調整時間消耗相差不多，但隨著插入結點個數的增加，當插入節(jié)點個數大于100 時，SUC 編碼與前綴編碼和Zhang 編碼相比，其動態(tài)調整時間消耗相差10 倍左右，如圖2 所示.

(2)XML 文檔較大時(文檔長度大于等于10M)，無論插入節(jié)點個數為多少，SUC 編碼與前綴編碼和Zhang 編碼相比，其動態(tài)調整時間消耗相差10 倍之多.如圖3 所示.

因此，本文提出的SUC 編碼方法在進行對XML 文檔做插入操作時在處理XML 文檔插入式編碼時的動態(tài)調整性能具有顯著優(yōu)勢.由于在SUC編碼初始化過程中引入了均衡調整思想，有效地避免了缺位沖突，當出現(xiàn)缺位沖突時采用i 次塊增位調整進行快速編碼，因此并沒有出現(xiàn)隨著插入結點個數大量增加而引起的編碼重構次數的激增.

3 優(yōu)點與不足

SUC 編碼優(yōu)點如下:

(1)編碼的動態(tài)調整性能較好.由實驗結果可知該種編碼方法對XML 文檔的更新具有快速的調整能力.

(2)編碼效率高.SUC 編碼的Part 部分采用位向量的方式定址，其結構與操作系統(tǒng)的段式存儲管理相類似，所有的操作都是基于位運算的，故編碼效率較高.

(3)編碼方式靈活.由于位向量定址方式，每個邏輯塊的二進制位數可以根據XML 文檔的大小動態(tài)調整，因此SUC 編碼方式較為靈活.

不足與需改進的地方如下所述:

SUC 編碼對包含關系的結構連接支持有限，這主要是由于該編碼中不含XML 文檔樹的全局路徑信息，而只含有局部的路徑信息，因此在使用SUC編碼的文檔樹中無法通過編碼判斷節(jié)點間的包含關系.今后將進一步研究在編碼過程中如何合理引入全局路徑信息.

［1］ 周愛武，李孫長，程博，等.XML 數據庫的研究與應用［J］.計算機技術與發(fā)展.2009，9(9):218－224.

［2］ Joe Marini.The Document Object Model［M］.The McGraw－Hill Companies，Inc.2002.

［3］ 閆文剛，李晶.一種XML 文檔樹節(jié)點編碼的動態(tài)調整算法的研究［J］.佳木斯大學學報(自然科學版)，2010，28(3):360－362.