Lossless Compression of Binary Trees with Correlated Vertex Names

Area of Science:

• Data Compression
• Information Theory
• Graph Theory

Background:

• Traditional information theory focuses on conventional data types like text and video.
• Modern data is increasingly multitype and context-dependent, posing challenges for compression.
• Advanced data structures, such as unlabeled graphs and trees, require new compression strategies.

Purpose of the Study:

• To systematically study compression schemes for advanced data structures, specifically trees with statistically correlated vertex names.
• To analyze and develop optimal compression algorithms for both binary plane trees and non-plane trees.
• To evaluate the entropy and demonstrate the analytical tractability of compression for these tree structures.

Main Methods:

• Developed a model for trees with statistically correlated vertex names, incorporating horizontal independence and vertical Markovian dependency.
• Analyzed the entropy of binary plane trees and non-plane trees under the specified statistical model.
• Designed and evaluated compression schemes, proving their optimality and efficiency for both tree types.

Main Results:

• Derived analytical solutions for entropy and optimal compression in the studied tree models.
• Demonstrated that a simple two-stage compression scheme is optimal and efficient for plane trees (with or without vertex names).
• Presented efficient and optimal compression algorithms for the more complex non-plane trees.

Conclusions:

• Compression and entropy analysis for trees with statistically correlated vertex names are analytically tractable in this natural setting.
• The proposed compression schemes provide efficient and optimal solutions for both binary plane and non-plane trees.
• This work advances the field of data compression for complex, context-dependent data structures.