一种基于十六进制的XML前缀编码方案

杨晓明

摘要：对原有的XML前缀编码方案进行改进，通过引入十六进制数，实现了ML文档在任意节点间的插入，有效地支持了XML数据更新，提出了一种基于十六进制的XML前缀编码方案。

关键词：前缀编码；十六进制；数据更新

1.概述

XML（eXtensible Markup Language，可扩展标记语言胙为互联网上一种功能强大的标记语言，已经成为数据表示和交换的一个主要标准，受到越来越多业内人士的关注。为了有效支持XML查询，特别是结构查询，国内外学者已经提出了许多针对XML文档的编码方案。但是实际应用中由于XML文档的频繁数据更新，多数方案都需要花费很大代价重新编码，严重影响了XML查询的效率。因此，对XML动态编码方案的研究成为当前亟待解决的热点问题。

本文针对目前XML编码中的主要问题进行分析，在现有的前缀编码方案中的基础上，提出一种基于十六进制数的新的前缀编码方案，支持数据的动态更新，以及任意位置的节点插入。无需二次编码，执行效率高。

2.国内外研究现状

目前，国内外学者针对XML数据编码问题已经进行了一系列的研究，常用的两类XML编码方案分别是基于前缀的编码方案和基于区间的编码方案。基于区间的编码方案无法从根本上解决节点插入时的重新编码问题，因此有研究者使用基于前缀的编码方案，并通过一些精心的设计来解决节点插入的重新编码问题。

Dewey编码是最早提出的前缀编码方案，该编码将双亲结点的编码直接作为自己编码的前缀，可以保留整个文档的位置信息以及结点间的关系，但不支持数据更新，属于静态前缀编码。LSDX编码是以nx.y为编码格式，其中数字n表示该结点所在的层次，字母x表示当前父结点的编码，字母y表示其为孩子结点，该编码能够支持文档的动态更新，但是在进行各种关系的判断时需要对字符进行比较，查询效率要差于利用数字进行编码的编码方式。

IPEU编码对Dewey编码进行了扩展，取消了Dewey编码中各层的点号分隔符，改用数字标识各层，整个编码由字母、整数、点组成，缩短了编码长度，可支持在两个相邻位置的兄弟结点之间插入新结点；在结点的最左孩子结点之前插入新结点；在结点的最右孩子结点之后插入新结点；给叶子结点的孩子插入新结点四种插入操作。该编码不需要预留空间，有效地解决了更新操作所造成的重新编码问题。但是只能完成以上四种特定情况的插入，没有考虑在新插入的两个结点之间再次插入结点的情况。

DPEF编码提出一种基于分数的动态前缀编码DPEF。利用分数的无限扩展性实现了对XML文档的更新操作。但是由于分数在编码中难以表示，需要对分数进行FC编码，将分母的数字转换为字母，如157/13表示为BFHl3。运算不够简单，编码也不直观。

FPES编码将分数引入到LSDX前缀编码中，提出了一种分数前缀编码方案（FPES），根据2个分数间可插人无穷多个分数的理论，来支持XML节点数据的无限更新。FPES编码的每个节点用一个二元组来表示，与LSDX相比，查询效率得到了提高，与分数编码相比，编码及插入节点的时间减少了。但结点间关系及结点层次不够直观，需要进行一系列的判断，影响查询效率。

以上算法虽然在查询效率以及节省存储空间上做了一定的改进，但是效果都不是很理想，字母比较以及分隔符存储需要大量的运行时间和存储空间，因此，面对目前Internet上海量数据的存储和交换，国内外研究者的主要研究方向仍是动态XML编码，以适应数据的不断更新。XML动态编码方案的设计仍然是需要进一步深入研究的课题。

3.基于十六进制的XML编码方案

3.1Dewey编码和LSDX编码对比

Dewey编码方案和LSDX编码如图1所示。

Dewey编码方案中，节点“1.2”是节点“1.2.2”的前缀，分隔符“.”只差1个，所以很容易确定他们之间的父子关系，但当有新节点插入时，两个相邻兄弟之间无法插入新的节点，因此需要重新编码。LSDX编码方案标识了节点所在层次，能快速准确的判断XML文档结构树中任意两个节点之间的父子、祖先/子孙以及兄弟关系，但是需要进行字符之间的比较，运算比较复杂。

3.2基于十六进制的动态XML编码方案

以Dewey编码为原型，结合LSDX编码对结点所在层次的标识，引入十六进制数以及移位运算进行编码方案的改进，提出了一种基于十六进制数的XML前缀编码方案。该编码方案具有Dewey编码保留结点关系的良好特性。

十六进制前缀编码示意图如图所示：

1）对结点所在层次进行标识，如：00表示第一层根节点，010a表示第二层结点，020aOa、020ala表示第三层结点，并且互为兄弟结点，是OlOa结点的子节点，既能快速准确的判断XML文档结构树中任意两个节点之间的父子、祖先/子孙以及兄弟关系，又可简化运算过程，提高效率。

2）同时以十六进制数代替十进制数及字符进行编码，给每一层的最左孩子的左边和最右孩子的右边预留空间，如：O10a左边预留了0100到0109的编码，Olla右边预留了O11b到0111f的编码，这样可方便给最左孩子插入左兄弟以及最右孩子插入右兄弟，既能使操作简化，又考虑到各种情况的插入操作。

3）考虑在新插入的两个结点之间再次插人结点的情况，该编码方案通过取中间值的方法进行了改进，在结点020aOa、020ala之间插入结点时，新节点编码为020a12，在结点020aOa左边插入结点时，新节点编码为020a05，在020ala右边插入结点时，新节点编码为020a2a。不仅能在最左孩子左边和最右孩子右边插入兄弟，以及在两个结点之间插人结点，还可通过再次取中间值的方法实现在新插入的两个结点之间再次插入结点。

4）该编码方案同时采用十六进制移位运算的方法来完成运算问题，十六进制数左移、右移1位即可完成乘2、除2操作，左移、右移4位即可完成乘16、除16的操作，例如：OxlOaOaO<<4就是OxlOaOa00，OxlOaOaO>>4就是OxlOaOaO，这样在给最左孩子插人左兄弟以及最右孩子插入右兄弟时可以预留空间。同时通过十六进制取中间值的方法可实现在新插入的两个结点之间再次插入结点，例如：在结点020aOa、020ala之间插入结点时，新节点编码为020a12，在结点020aOa左边插人结点时，新节点编码為020a05，在020ala右边插入结点时，新节点编码为020a2a。解决了以往XML编码中无法对这几种特定情况进行编码的问题。

4.小结

该编码方案结合Dewey、LSDX以及IPEU编码方案的算法思想及优点，以十六进制数代替十进制数和字符，保留了节点的层次关系，同时考虑到在节点的各个位置插入新节点的情况，不仅能快速准确的判断XML文档结构树中任意两个节点之间的父子、祖先/子孙以及兄弟关系，而且能够支持XML文档在任意位置进行结点插入，有效地支持XML文档更新，有利于XML的查询、存储。