International Journal of Foundations of Computer Science · 1990 · 53 citations · 0 references
ComputingComputer EngineeringComputer ScienceAlgorithmsCompilersData StructuresAbstract Syntax TreesData CompressionData Structure AlgorithmsData Structure DesignCompactionCompressed Data StructuresCompressionCompression AlgorithmsCompression TechniquesLinearizationLinearization TheoryTrie Data Structures
Different methods for compressing trees are surveyed and developed. Tree compression can be seen as a trade-off problem between time and space in which we can choose different strategies depending on whether we prefer better compression results or more efficient operations in the compressed structure. Of special interest is the case where space can be saved while preserving the functionality of the operations; this is called data optimization. The general compression scheme employed here consists of separate linearization of the tree structure and the data stored in the tree. Also some applications of the tree compression methods are explored. These include the syntax-directed compression of program files, the compression of pixel trees, trie compaction and dictionaries maintained as implicit data structures.