楊曉明

摘要：對原有的XML前綴編碼方案進(jìn)行改進(jìn)，通過引入十六進(jìn)制數(shù)，實(shí)現(xiàn)了ML文檔在任意節(jié)點(diǎn)間的插入，有效地支持了XML數(shù)據(jù)更新，提出了一種基于十六進(jìn)制的XML前綴編碼方案。

關(guān)鍵詞：前綴編碼；十六進(jìn)制；數(shù)據(jù)更新

1.概述

XML（eXtensible Markup Language，可擴(kuò)展標(biāo)記語言胙為互聯(lián)網(wǎng)上一種功能強(qiáng)大的標(biāo)記語言，已經(jīng)成為數(shù)據(jù)表示和交換的一個(gè)主要標(biāo)準(zhǔn)，受到越來越多業(yè)內(nèi)人士的關(guān)注。為了有效支持XML查詢，特別是結(jié)構(gòu)查詢，國內(nèi)外學(xué)者已經(jīng)提出了許多針對XML文檔的編碼方案。但是實(shí)際應(yīng)用中由于XML文檔的頻繁數(shù)據(jù)更新，多數(shù)方案都需要花費(fèi)很大代價(jià)重新編碼，嚴(yán)重影響了XML查詢的效率。因此，對XML動(dòng)態(tài)編碼方案的研究成為當(dāng)前亟待解決的熱點(diǎn)問題。

本文針對目前XML編碼中的主要問題進(jìn)行分析，在現(xiàn)有的前綴編碼方案中的基礎(chǔ)上，提出一種基于十六進(jìn)制數(shù)的新的前綴編碼方案，支持?jǐn)?shù)據(jù)的動(dòng)態(tài)更新，以及任意位置的節(jié)點(diǎn)插入。無需二次編碼，執(zhí)行效率高。

2.國內(nèi)外研究現(xiàn)狀

目前，國內(nèi)外學(xué)者針對XML數(shù)據(jù)編碼問題已經(jīng)進(jìn)行了一系列的研究，常用的兩類XML編碼方案分別是基于前綴的編碼方案和基于區(qū)間的編碼方案。基于區(qū)間的編碼方案無法從根本上解決節(jié)點(diǎn)插入時(shí)的重新編碼問題，因此有研究者使用基于前綴的編碼方案，并通過一些精心的設(shè)計(jì)來解決節(jié)點(diǎn)插入的重新編碼問題。

Dewey編碼是最早提出的前綴編碼方案，該編碼將雙親結(jié)點(diǎn)的編碼直接作為自己編碼的前綴，可以保留整個(gè)文檔的位置信息以及結(jié)點(diǎn)間的關(guān)系，但不支持?jǐn)?shù)據(jù)更新，屬于靜態(tài)前綴編碼。LSDX編碼是以nx.y為編碼格式，其中數(shù)字n表示該結(jié)點(diǎn)所在的層次，字母x表示當(dāng)前父結(jié)點(diǎn)的編碼，字母y表示其為孩子結(jié)點(diǎn)，該編碼能夠支持文檔的動(dòng)態(tài)更新，但是在進(jìn)行各種關(guān)系的判斷時(shí)需要對字符進(jìn)行比較，查詢效率要差于利用數(shù)字進(jìn)行編碼的編碼方式。

IPEU編碼對Dewey編碼進(jìn)行了擴(kuò)展，取消了Dewey編碼中各層的點(diǎn)號分隔符，改用數(shù)字標(biāo)識各層，整個(gè)編碼由字母、整數(shù)、點(diǎn)組成，縮短了編碼長度，可支持在兩個(gè)相鄰位置的兄弟結(jié)點(diǎn)之間插入新結(jié)點(diǎn)；在結(jié)點(diǎn)的最左孩子結(jié)點(diǎn)之前插入新結(jié)點(diǎn)；在結(jié)點(diǎn)的最右孩子結(jié)點(diǎn)之后插入新結(jié)點(diǎn)；給葉子結(jié)點(diǎn)的孩子插入新結(jié)點(diǎn)四種插入操作。該編碼不需要預(yù)留空間，有效地解決了更新操作所造成的重新編碼問題。但是只能完成以上四種特定情況的插入，沒有考慮在新插入的兩個(gè)結(jié)點(diǎn)之間再次插入結(jié)點(diǎn)的情況。

DPEF編碼提出一種基于分?jǐn)?shù)的動(dòng)態(tài)前綴編碼DPEF。利用分?jǐn)?shù)的無限擴(kuò)展性實(shí)現(xiàn)了對XML文檔的更新操作。但是由于分?jǐn)?shù)在編碼中難以表示，需要對分?jǐn)?shù)進(jìn)行FC編碼，將分母的數(shù)字轉(zhuǎn)換為字母，如157/13表示為BFHl3。運(yùn)算不夠簡單，編碼也不直觀。

FPES編碼將分?jǐn)?shù)引入到LSDX前綴編碼中，提出了一種分?jǐn)?shù)前綴編碼方案（FPES），根據(jù)2個(gè)分?jǐn)?shù)間可插人無窮多個(gè)分?jǐn)?shù)的理論，來支持XML節(jié)點(diǎn)數(shù)據(jù)的無限更新。FPES編碼的每個(gè)節(jié)點(diǎn)用一個(gè)二元組來表示，與LSDX相比，查詢效率得到了提高，與分?jǐn)?shù)編碼相比，編碼及插入節(jié)點(diǎn)的時(shí)間減少了。但結(jié)點(diǎn)間關(guān)系及結(jié)點(diǎn)層次不夠直觀，需要進(jìn)行一系列的判斷，影響查詢效率。

以上算法雖然在查詢效率以及節(jié)省存儲空間上做了一定的改進(jìn)，但是效果都不是很理想，字母比較以及分隔符存儲需要大量的運(yùn)行時(shí)間和存儲空間，因此，面對目前Internet上海量數(shù)據(jù)的存儲和交換，國內(nèi)外研究者的主要研究方向仍是動(dòng)態(tài)XML編碼，以適應(yīng)數(shù)據(jù)的不斷更新。XML動(dòng)態(tài)編碼方案的設(shè)計(jì)仍然是需要進(jìn)一步深入研究的課題。

3.基于十六進(jìn)制的XML編碼方案

3.1Dewey編碼和LSDX編碼對比

Dewey編碼方案和LSDX編碼如圖1所示。

Dewey編碼方案中，節(jié)點(diǎn)“1.2”是節(jié)點(diǎn)“1.2.2”的前綴，分隔符“.”只差1個(gè)，所以很容易確定他們之間的父子關(guān)系，但當(dāng)有新節(jié)點(diǎn)插入時(shí)，兩個(gè)相鄰兄弟之間無法插入新的節(jié)點(diǎn)，因此需要重新編碼。LSDX編碼方案標(biāo)識了節(jié)點(diǎn)所在層次，能快速準(zhǔn)確的判斷XML文檔結(jié)構(gòu)樹中任意兩個(gè)節(jié)點(diǎn)之間的父子、祖先/子孫以及兄弟關(guān)系，但是需要進(jìn)行字符之間的比較，運(yùn)算比較復(fù)雜。

3.2基于十六進(jìn)制的動(dòng)態(tài)XML編碼方案

以Dewey編碼為原型，結(jié)合LSDX編碼對結(jié)點(diǎn)所在層次的標(biāo)識，引入十六進(jìn)制數(shù)以及移位運(yùn)算進(jìn)行編碼方案的改進(jìn)，提出了一種基于十六進(jìn)制數(shù)的XML前綴編碼方案。該編碼方案具有Dewey編碼保留結(jié)點(diǎn)關(guān)系的良好特性。

十六進(jìn)制前綴編碼示意圖如圖所示：

1）對結(jié)點(diǎn)所在層次進(jìn)行標(biāo)識，如：00表示第一層根節(jié)點(diǎn)，010a表示第二層結(jié)點(diǎn)，020aOa、020ala表示第三層結(jié)點(diǎn)，并且互為兄弟結(jié)點(diǎn)，是OlOa結(jié)點(diǎn)的子節(jié)點(diǎn)，既能快速準(zhǔn)確的判斷XML文檔結(jié)構(gòu)樹中任意兩個(gè)節(jié)點(diǎn)之間的父子、祖先/子孫以及兄弟關(guān)系，又可簡化運(yùn)算過程，提高效率。

2）同時(shí)以十六進(jìn)制數(shù)代替十進(jìn)制數(shù)及字符進(jìn)行編碼，給每一層的最左孩子的左邊和最右孩子的右邊預(yù)留空間，如：O10a左邊預(yù)留了0100到0109的編碼，Olla右邊預(yù)留了O11b到0111f的編碼，這樣可方便給最左孩子插入左兄弟以及最右孩子插入右兄弟，既能使操作簡化，又考慮到各種情況的插入操作。

3）考慮在新插入的兩個(gè)結(jié)點(diǎn)之間再次插人結(jié)點(diǎn)的情況，該編碼方案通過取中間值的方法進(jìn)行了改進(jìn)，在結(jié)點(diǎn)020aOa、020ala之間插入結(jié)點(diǎn)時(shí)，新節(jié)點(diǎn)編碼為020a12，在結(jié)點(diǎn)020aOa左邊插入結(jié)點(diǎn)時(shí)，新節(jié)點(diǎn)編碼為020a05，在020ala右邊插入結(jié)點(diǎn)時(shí)，新節(jié)點(diǎn)編碼為020a2a。不僅能在最左孩子左邊和最右孩子右邊插入兄弟，以及在兩個(gè)結(jié)點(diǎn)之間插人結(jié)點(diǎn)，還可通過再次取中間值的方法實(shí)現(xiàn)在新插入的兩個(gè)結(jié)點(diǎn)之間再次插入結(jié)點(diǎn)。

4）該編碼方案同時(shí)采用十六進(jìn)制移位運(yùn)算的方法來完成運(yùn)算問題，十六進(jìn)制數(shù)左移、右移1位即可完成乘2、除2操作，左移、右移4位即可完成乘16、除16的操作，例如：OxlOaOaO<<4就是OxlOaOa00，OxlOaOaO>>4就是OxlOaOaO，這樣在給最左孩子插人左兄弟以及最右孩子插入右兄弟時(shí)可以預(yù)留空間。同時(shí)通過十六進(jìn)制取中間值的方法可實(shí)現(xiàn)在新插入的兩個(gè)結(jié)點(diǎn)之間再次插入結(jié)點(diǎn)，例如：在結(jié)點(diǎn)020aOa、020ala之間插入結(jié)點(diǎn)時(shí)，新節(jié)點(diǎn)編碼為020a12，在結(jié)點(diǎn)020aOa左邊插人結(jié)點(diǎn)時(shí)，新節(jié)點(diǎn)編碼為020a05，在020ala右邊插入結(jié)點(diǎn)時(shí)，新節(jié)點(diǎn)編碼為020a2a。解決了以往XML編碼中無法對這幾種特定情況進(jìn)行編碼的問題。

4.小結(jié)

該編碼方案結(jié)合Dewey、LSDX以及IPEU編碼方案的算法思想及優(yōu)點(diǎn)，以十六進(jìn)制數(shù)代替十進(jìn)制數(shù)和字符，保留了節(jié)點(diǎn)的層次關(guān)系，同時(shí)考慮到在節(jié)點(diǎn)的各個(gè)位置插入新節(jié)點(diǎn)的情況，不僅能快速準(zhǔn)確的判斷XML文檔結(jié)構(gòu)樹中任意兩個(gè)節(jié)點(diǎn)之間的父子、祖先/子孫以及兄弟關(guān)系，而且能夠支持XML文檔在任意位置進(jìn)行結(jié)點(diǎn)插入，有效地支持XML文檔更新，有利于XML的查詢、存儲。