论文部分内容阅读
作为半结构化数据的典型代表,XML已成为Web上数据表示和交换的标准。但它的自描述和半结构化特性使得XML中存在大量的数据冗余,极大地增加了数据存储、交换和处理的代价,严重阻碍了XML数据库更深入更广泛的应用。因此,对XML数据进行压缩变得十分必要。针对生物XML数据中可压缩子结构高频重复出现的特点,我们设计了适于生物XML数据的压缩方法SCSC(Schema based Compressible Substructure Compressing)。首先,我们根据XML Schema提供的丰富结构信息建立XML扩充结构树,并从中提取用于压缩的子结构,包括极大可压缩子结构和完全可压缩子结构。然后解析XML文档,将其分离为结构数据和内容数据,且把内容数据归到不同的内容容器中。最后根据提取的可压缩子结构对结构数据进行压缩,并对不同类型的内容容器采用相应的压缩方法。理论分析和实验结果表明,在生物数据的压缩上,SCSC比已有的方法XMill具有更好的压缩性能。此外,SCSC不仅适合生物XML数据,也可扩展到其他具有高频重复子结构的XML数据。针对大多数XML压缩方法不能支持Twig查询的问题,我们提出了一种能够支持Twig查询的XML压缩算法XCTwig(XML Compression supporting Twig)。该方法主要包含两大部分—XML数据压缩方法和压缩XML数据上的Twig查询处理方法。首先,我们给出了XCTwig压缩算法的框架,设计了XML结构树的构建算法以及XML文档的压缩算法。然后,我们给出了压缩XML数据上进行Twig查询的框架,并给出了压缩数据上Twig查询操作算法。XCTwig压缩算法的基本思想是把具有相同路径的内容数据划分到同一组进行存储。在压缩XML数据上进行Twig查询处理时,首先把Twig查询模式分解为多个路径查询表达式,在压缩数据中依次执行并返回匹配的结果,且将先驱路径的中间结果用作当前路径查询中的过滤条件。实验证明,虽然XCTwig的压缩比低于XMill和gzip,却明显高于XGrind,且由于采用了路径存储的独特形式,其上Twig查询操作仍然具有很好的性能。