附件一：
外文资料翻译译文
XML文件树的高效的存储表示
Giorgio Busattoa, Markus Lohrey, Sebastian Maneth
摘要：加载xml文档和使用DOM访问它们的执行需要大量的存储空间：加载xml文档所需的空间一般是该xml文档大小的好几倍。存储xml文档树结构需要一个相当大的存储空间。在这篇论文中，有一种方法来高效地表示xml文档树结构。这种表示通过压缩xml文档树结构来提高文档的高规律性。正式地，只有一个压缩树来产生上下文无关文法树。 被压缩过后的文档，其基本树的功能性操作依然存在，就像在边缘往复运动一样。 这样允许直接执行解析文档而不需要事先解压。为了压缩文档，无疑这些复杂的计算问题如初始化xml文档类型和测试平衡性都要被考虑进来。
© 2008 Elsevier B.V. 版权所有。
关键字：语法树，压缩，内存中xml表示
1. 引言 (毕业设计)
在很多描述中，使用电脑程序来处理树结构。常常在主存中保存树的表示对加快访问速率是非常有用的。如果被存储的树非常大，使用这种高效的记忆表示方式是非常有用的。最近，一个很著名例子关于用整齐树表示xml文档和一个在主存中实现这种文档具体化的例子都可以评估xml检索性能。后者是用已存在的xml数据模型来实现的，如：DOM标准显示了在主存中的DOM解析空间是普通xml文档的4-5倍多。可以这样理解：form的一个节点<a/>在xml文档中占用4bytes，但是一个树节点至少需要16bytes：一个名字指针需要加上三个节点指针才能指向父亲节点、第一个孩子节点和下一个兄弟节点。有一些改进可以更紧凑的表示这些。如：Galax仅用了原文件的3-4倍多的主存空间。另外，还有一个高效存储xml的数据模型就是二进制树。因此，众所周知的xml查询语言可以通过二进制树模型来评估。
在本章中，我们致力于用一种高效的方式表示二进制树的问题，来使基本树的功能性操作仍被保持。取代压缩，这种方式通常称为数据最优化。有2种方式实现这种小树表示：基于指针的和简洁的小指针。后者是把树包装进一个小的数组，通过贯穿树中的基本导航来识别的方式。最近，在简洁树表示方面有新的进展。基于内存要求的考虑，这种简洁表示比基于指针的表示更有竞争力。
外文(8)
< class="2584
