Algorithmic height compression of unordered trees.

Area of Science:

• Computer Science
• Data Structures
• Algorithms

Background:

• Tree structures often contain redundant sub-parts, motivating compression techniques.
• Existing methods merge isomorphic subtrees into directed acyclic graphs (DAGs), preserving tree height but limiting compression.
• Further height compression is challenging due to nested, non-isomorphic substructures.

Purpose of the Study:

• To address the limitation of existing tree compression methods by further reducing the height of directed acyclic graphs (DAGs).
• To introduce a novel concept of quasi-isomorphism for detecting and merging non-exactly isomorphic, nested substructures.
• To achieve minimal structural compression by removing redundancy in both width and height.

Main Methods:

• Introduced the concept of quasi-isomorphism to identify similar patterns along tree paths.
• Developed an algorithm to detect these quasi-isomorphic patterns within nested substructures.
• Proposed merging these patterns to create DAGs augmented with return edges.

Main Results:

• The proposed algorithm successfully compresses DAGs by reducing their height.
• Achieved minimal structural compression by removing redundancy in both width and height.
• Demonstrated the algorithm's effectiveness on compressing plant-like structures.

Conclusions:

• Quasi-isomorphism enables effective compression of tree structures beyond traditional methods.
• The developed algorithm achieves significant structural compression by addressing nested redundancies.
• This approach offers a powerful tool for optimizing complex tree-based data representations.