一種基于十六進制的XML前綴編碼方案

楊曉明

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

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

1.概述

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

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

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

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

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

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

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

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

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

3.基于十六進制的XML編碼方案

3.1Dewey編碼和LSDX編碼對比

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

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

3.2基于十六進制的動態(tài)XML編碼方案

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

十六進制前綴編碼示意圖如圖所示：

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

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

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

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

4.小結(jié)

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