Universal Tree Source Coding Using Grammar-Based Compression
| Autor: | Moses Ganardi, Markus Lohrey, Louisa Seelbach Benkner, Danny Hucke |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Pointwise
Discrete mathematics Source code Binary tree media_common.quotation_subject Zhàng 020206 networking & telecommunications 02 engineering and technology Library and Information Sciences Directed acyclic graph Upper and lower bounds Computer Science Applications Redundancy (information theory) 0202 electrical engineering electronic engineering information engineering Natural class Information Systems Mathematics media_common |
| Zdroj: | IEEE Transactions on Information Theory. 65:6399-6413 |
| ISSN: | 1557-9654 0018-9448 |
| DOI: | 10.1109/tit.2019.2919829 |
| Popis: | The problem of universal source coding for binary trees is considered. Zhang, Yang, and Kieffer derived upper bounds on the average-case redundancy of codes based on directed acyclic graph (DAG) compression for binary tree sources with certain properties. In this paper, a natural class of binary tree sources is presented such that the demanded properties are fulfilled. Moreover, for both subclasses considered in the paper of Zhang, Yang, and Kieffer, their result is improved by deriving bounds on the maximal pointwise redundancy (or worst-case redundancy) instead of the average-case redundancy. Finally, using context-free tree grammars instead of DAGs, upper bounds on the maximal pointwise redundancy for certain binary tree sources are derived. This yields universal codes for new classes of binary tree sources. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|