Hucke, Danny: Grammar-based compression for strings and trees. 2019
Inhalt
- Abstract
- Acknowledgements
- Contents
- 1 Introduction
- 2 Preliminaries
- 2.1 Numbers and functions
- 2.2 Words, alphabets and languages
- 2.3 Graphs and trees
- 2.4 Distributions and empirical entropy
- 2.5 Computational models
- 3 Grammar-based string compression
- 3.1 Straight-line programs
- 3.2 Approximation ratio
- 3.3 BiSection
- 3.4 LZ78
- 3.5 Global algorithms
- 3.6 RePair
- 3.7 Greedy
- 3.8 LongestMatch
- 3.9 Universal coding based on SLPs
- 3.10 Conclusion and open problems
- 4 Grammar-based tree compression
- 4.1 Trees and patterns
- 4.2 Tree straight-line programs
- 4.3 Directed acyclic graphs
- 4.4 TreeBiSection
- 4.5 BU-Shrink
- 4.6 Arithmetical circuits
- 4.7 Source coding for unlabeled binary trees
- 4.8 Universal coding based on DAGs
- 4.9 Universal coding based on TSLPs
- 4.10 Conclusion and open problems
- Bibliography