公开/公告号CN103116654A
专利类型发明专利
公开/公告日2013-05-22
原文格式PDF
申请/专利权人 同方知网(北京)技术有限公司;
申请/专利号CN201310070566.7
申请日2013-03-06
分类号G06F17/30;
代理机构北京天奇智新知识产权代理有限公司;
代理人刘黎明
地址 100084 北京市海淀区清华园清华大学36区华业大厦B1410、1412、1414室
入库时间 2024-02-19 18:53:05
法律状态公告日
法律状态信息
法律状态
2016-08-24
授权
授权
2013-06-19
实质审查的生效 IPC(主分类):G06F17/30 申请日:20130306
实质审查的生效
2013-05-22
公开
公开
技术领域
本发明涉及数据库领域,尤其涉及一种简单易用的XML数据节 点编码压缩方法。
背景技术
随着XML逐渐成为广泛应用的数据表现形式,如何对XML数 据进行高效的管理也成为一个重要的问题。对于需要大量管理XML 数据的数据库管理系统来说,为了有效支持XML查询,特别是结构 查询,研究者已经提出了XML数据节点的各种编码方案。所谓XML 编码指的是使用特定的编码策略对XML文档树中的元素、属性和其 他语义实体赋予一个唯一的编码。对XML数据进行有效编码,可以 迅速确定XML文档树中任意节点间的结构关系,例如:父子关系、 祖先关系及文档顺序等,不需遍历XML文档树,从而提高了结构查 询的效率。
对现有的技术文献检索发现,XML数据的主要编码方案包括 Dewey编码等。Dewey编码方法把XML数据看作树模型,树中节点 根据Dewey编码标注,每个节点赋予Dewey标签作为唯一的ID。例 如,设树T的一个节点的Dewey编码为c(u),则节点u的孩子节 点v的Dewey编码c(v)=c(u).n,这里n记录的是节点v在u中 所有孩子节点中的序号,利用符号“.”将c(u)与n进行连接。编码 时,从根节点开始为每个节点编排Dewey标签,如DeweyID为0.2.3 的节点是节点0.2的第4个子节点,即Dewey编码直接将父节点的 编码作为子节点的前缀。该编码方式能反映节点间的兄弟及继承关 系,有效地支持了结构关系计算。但动态更新XML数据后需要重新 编码,且编码没有采用压缩方式存储,造成了存储空间浪费。
Patrick O’Neil在论文“ORDPATHs:Insert-Firendly XML Node Labels”中提出的ORDPATH编码是一种扩展的Dewey编码。逻辑涵 义上,ORDPATH的每个节点对应编码的一部分,如节点编码为1的 三个子节点分别编码为1.1、1.3与1.5,以此类推。实际表示时,它 采用二进制的形式对编码进行了压缩,其结构由Li/Oi比特串构成, 且一个Li/Oi对应于ORDPATH编码中的一部分,Li表示紧跟其后的 Oi的比特数,使用前缀编码方式表示,Oi存储的是相对该比特数所 在区间开始值的差值。ORDPATH编码也是一种前缀编码,可通过比 较前缀反映节点的兄弟、继承关系,且其采用压缩方法存储,具有较 高的压缩比,但相应的压缩规则复杂,因此存在解压缩过程复杂的缺 点,不利于在大规模XML数据的结构查询中进行快速的节点编码操 作。
发明内容
为解决上述技术中存在的问题与缺陷,本发明提供了一种XML 数据节点编码压缩方法。所述技术方案如下:
一种XML数据节点编码压缩方法,包括:
将XML数据生成XML文档树;
对XML文档树中的每个节点进行编码;
对节点编码进行压缩存储。
本发明提供的技术方案的有益效果是:
是一种无损的压缩方法,具有简单易用的特点,编码及其编码压 缩规则简单,便于理解和编程实现,能够快速解压,利于编码操作。
在压缩时依然保持了编码的结构信息,因此无需解压便可直接比 较比特串来判断节点间的特定结构关系,并且采用分段压缩,编码的 各个整数互不影响,在进行解压操作时,不需全部解压比特串,可按 所需顺序分段解压,提高了编码操作的性能。
附图说明
图1是XML数据节点编码压缩方法流程图;
图2是XML文档树结构示意图。
具体实施方式
为使本发明的目的、技术方案和优点更加清楚,下面将结合附图 对本发明实施方式作进一步地详细描述:
如图1所示,提供了XML数据节点编码压缩方法流程,包括:
步骤10将XML数据生成XML文档树;
在生成上述文档树的过程中不区分元素节点、属性节点和文本节 点。为形象说明该过程,例如下面的XML文档:
对其构件的XML文档树结构如图2所示。
步骤20对XML文档树中的每个节点进行编码;
进行编码前首先对文档树的每个节点分配一个整数,分配方法如 下:
(1)如果节点为根节点则分配整数1。
(2)如果节点不是叶子节点则为其子节点自左到右分配整数1、 3、5…,初始时分配的是正奇数,偶数保留。
按照上述方法遍历一遍文档树即可完成节点整数的分配并连接, 然后对每个节点进行编码,编码规则为从根节点到某节点的路径上的 所有整数以符号“.”进行连接作为该节点的编码;即若节点不为根 节点,则节点编码由其父节点编码与代表该节点在父节点的所有子节 点中的位置的整数以“.”进行连接构成;若节点为根节点则编码直 接为其分配整数。如图2所示节点BOOK为根节点则其编码为“1”, 节点ISBN是根节点的第一个子节点则其编码为1.1。
步骤30对节点编码进行压缩存储。
存储方式采用二进制比特串的形式,如若直接存储编码中的整 数,会存在很多冗余的比特位,造成物理存储空间浪费,因而采用压 缩方式存储,存储时按编码中整数的先后顺序分段压缩为二进制串, 但忽略连接符号“.”不存储。编码的二进制存储形式为:L0B0L1B1…, 其中一对LB表示一个整数,L表示紧跟其后的比特串的位数,L的设 定为形如比特串“(1)n0”表示紧跟其后的整数B的位数为n+7,n表示 比特1的个数,B表示编码中整数的二进制串,之所以加7是因为实 际应用中编码后的整数的位数大多为8位,利于数据编码在内存中按 字节对齐。L的各种比特串以及其表示的B的位数和范围如表1所示:
表1
例如,图2中的节点CAPTION的编码为“1.3.5.1”,整数1、3、5 的范围都在[1,127]范围内,则L的比特串为0,紧跟其后的整数的比特 串B为7位,则编码“1.3.5.1”的二进制串为:“0000000100000011 0000010100000001”。
以上所述仅为本发明的较佳实施例,并不用以限制本发明,凡在 本发明的精神和原则之内,所作的任何修改、等同替换、改进等,均 应包含在本发明的保护范围之内。
机译: XML数据的编码方法,已编码的XML数据的解码方法,XML数据的编码系统,已编码的XML数据的解码系统,程序和记录介质
机译: XML数据的编码方法,XML数据的编码方法,XML数据的编码系统,XML数据的编码系统,程序和记录介质
机译: XML数据压缩设备,XML数据压缩方法和XML数据压缩程序