Algorithm Using Expanded LZ Compression Scheme for Compressing Tree Structured Data

摘要

Due to the rapid growth of information technologies, the use of electronic data such as XML/HTML documents, which are a form of tree structured data, has been rapidly increasing. We have developed an algorithm for effectively compressing tree structured data and one for decompressing a compressed tree that are based on the Lempel-Ziv compression scheme. Next, we have implemented both compression and decompression algorithms by applying our algorithms for the Xmill compressor and Xdemill decompressor presented by Liefke and Suciu. Then, testing using synthetic large ordered trees and real-world tree structured data demonstrated the effectiveness and efficiency of our algorithms.