论文部分内容阅读
XML技术出现后,已经逐步成为各种网络应用中数据交换和存储的事实标准。目前,已经有很多大型数据库完全采用了XML格式来表示和存储数据。应用XML格式管理数据面临的最大困难在于XML数据中存在大量的数据冗余。模式和数据混合存储导致模式信息在数据中存在大量重复,这极大地增加了XML数据存储、交换和处理的代价。对XML文档进行压缩可以在一定程度上解决这个问题。但是,现有的XML压缩方法大都只关注单个文档中的信息冗余,而没有考虑利用文档间的相似性来进行压缩。因此,在压缩XML文档集合时不能获得很好的压缩效果。基于此,本文提出了基于聚类的两种不同的XML多文档压缩方法XMdelta和XMcluster。二者能够充分利用文档间的信息冗余来进行压缩,因此,十分适合于压缩XML多文档集合的应用。XMdelta方法的目的是:提高XML文档集合的压缩比,进而更有效地压缩存档大量XML文档的集合。它首先基于改进的pq-gram近似距离进行Single-link层次聚类。这样既保证了同类文档间的较大相似性,又降低了聚类过程的计算复杂度。然后,它根据不同应用场景的具体要求选取四种具有不同特性的增量式压缩策略之一进行压缩。实验结果表明,在真实和生成的XML多文档数据集上,与通用文本压缩器Gzip和面向存储的XML压缩器XMill相比,XMdelta方法有着更高的压缩比和相当的解压缩时间。XMcluster方法的目的是:在解决XML文档集合数据冗余问题的同时,支持压缩数据集上不解压或部分解压的高效查询操作。它同样先基于改进的pq-gram近似距离进行层次聚类以保证每类文档集中较大的相似性。然后,对于同类多文档的结构信息,XMcluster合并其差异,压缩其公共部分。对于同类多文档的数据信息,XMcluster进行全局的信息统计来进行压缩。实验结果表明,在真实和生成的XML多文档数据集上,XMcluster比同样支持查询的XML压缩器XGrind和不采用压缩技术的XML查询器XQilla具有更好的压缩效果和查询效率。