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

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

0 引 言

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

在設(shè)計(jì)XML 編碼方案時(shí)需要考慮的因素包括:

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

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

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

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

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

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

(1)樹中任意一個(gè)內(nèi)部節(jié)點(diǎn)iNode，對(duì)應(yīng)XML文檔中的一個(gè)元素，表示為E(iNode);

(2)樹中任意一個(gè)外部節(jié)點(diǎn)oNode，對(duì)應(yīng)XML文檔中的一個(gè)屬性或文本，當(dāng)oNode 是一個(gè)屬性節(jié)點(diǎn)時(shí)表示為A(oNode)，當(dāng)是一個(gè)文本節(jié)點(diǎn)時(shí)表示為T(oNode).

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

1 實(shí)驗(yàn)方案

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

圖1 實(shí)驗(yàn)系統(tǒng)體系結(jié)構(gòu)圖

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

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

內(nèi)部節(jié)點(diǎn)表nNodeTable(Xno，Level，Parent，Part);

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

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

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

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

2 實(shí)驗(yàn)過程及結(jié)果

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

在完成對(duì)本文提出的SUC 編碼實(shí)驗(yàn)測(cè)試的同時(shí)，實(shí)驗(yàn)中還對(duì)前綴編碼和Zhang 編碼一并進(jìn)行了測(cè)試.

表1 三種編碼動(dòng)態(tài)調(diào)整性能比較

圖2 M=2 時(shí)的時(shí)間消耗比

圖3 M=10 時(shí)的時(shí)間消耗比

在對(duì)長(zhǎng)度為2M 和10M 的兩個(gè)XML 文檔分別進(jìn)行五次插入試驗(yàn)后的三種編碼動(dòng)態(tài)調(diào)整過程中重新生成編碼的時(shí)間消耗如表1 所示.

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

分析表1 結(jié)果可知:

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

(2)XML 文檔較大時(shí)(文檔長(zhǎng)度大于等于10M)，無(wú)論插入節(jié)點(diǎn)個(gè)數(shù)為多少，SUC 編碼與前綴編碼和Zhang 編碼相比，其動(dòng)態(tài)調(diào)整時(shí)間消耗相差10 倍之多.如圖3 所示.

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

3 優(yōu)點(diǎn)與不足

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

(1)編碼的動(dòng)態(tài)調(diào)整性能較好.由實(shí)驗(yàn)結(jié)果可知該種編碼方法對(duì)XML 文檔的更新具有快速的調(diào)整能力.

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

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

不足與需改進(jìn)的地方如下所述:

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

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

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

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