动态有序树存储模型与实现方法  

Storage Model and Implementation of the Dynamic Ordered Tree

作　　者：特日根[1] 李巍[1] 李雄飞[1] 

机构地区：[1]符号计算与知识工程教育部重点实验室(吉林大学),长春130012

出　　处：《计算机研究与发展》2013年第5期969-985,共17页Journal of Computer Research and Development

基　　金：国家科技支撑计划基金项目(2006BAK01A33);吉林省科技发展计划基金项目(20090704)

摘　　要：XML作为半结构化数据模型的代表,其文档较大,存储动态有序树时需要较多空间成为其明显的缺点,对XML文档进行二进制的编码压缩可以有效地减少存储空间.提出了一种不仅可以对有序树进行空间高效存储,又可以实现有序树的动态化操作的封装包结构.此结构通过将有序树的二进制编码段分段处理的方法,减少了修改量.并通过三重定位的方法快速选定要修改的封装包.针对有序树动态化后出现的节点意义丢失的问题,提出了对树进行辅助描述的高效节点序号表,通过节点序号表可以记录每个节点的内容及意义,进而补充了二进制编码只能表示树结构的缺点.并通过建立有效的序号修改表对其进行快速高效的更新.通过设计对动态树的各种常用操作,并计算出各种操作的空间及时间复杂度,表明了通过此结构可以实现动态有序树的空间高效存储.XML, as the representative of the semi-structured data model, has a large number of documentation. It needs more space in storage of ordered sequential trees. That is one of its obvious shortcomings. One of the methods of reducing the storage space is using binary encoding to compress XML＇s documentation. A packet structure is proposed, which can not only store the ordered tree space-efficiently, but also realize its dynamic operation. This structure can reduce the amount of modification by separating the binary coded segments of the ordered tree. It can select the modified package rapidly by the triple positioning. For the missing of nodes＇ significance after the dynamic operation of the ordered tree, the efficient node number table is presented, which describes the tree indirectly. And it can record the contents and significance of each node by this structure. It also can make up for the short coming that the binary encoding can only express the tree structure. And by establishing an effective ordinal modification table, the table is updated efficiently. It is proved that this structure can realize the space efficient storage of the ordered tree by designing a variety of common operations of the ordered tree and by calculating the various operations of the space and time complexity.

关 键 词：动态有序树 XML压缩 查询处理 二进制编码 树更新算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]