Wyszukiwarka
Abstrakt
Compression schemes for advanced data structures have become the challenge of today. Information theory has traditionally dealt with conventional data such as text, image, or video. In contrast, most data available today is multitype and context-dependent. To meet this challenge, we have recently initiated a systematic study of advanced data structures such as unlabeled graphs [1]. In this paper, we continue this program by considering trees with statistically correlated vertex names. Trees come in many forms, but here we deal with binary plane trees (where order of subtrees matters) and their non-plane version. Furthermore, we assume that each symbol of a vertex name depends in a Markovian sense on the corresponding symbol of the parent vertex name. We first evaluate the entropy for both types of trees. Then we propose two compression schemes COMPRESSPTREE for plane trees with correlated names, and COMPRESSNPTREE for non-plane trees. We prove that the former scheme achieves the lower bound within two bits, while the latter is within 1% of the optimal compression.
Cytowania
-
5
CrossRef
-
0
Web of Science
-
6
Scopus
Autorzy (3)
Cytuj jako
Pełna treść
pełna treść publikacji nie jest dostępna w portalu
Słowa kluczowe
Informacje szczegółowe
- Kategoria:
- Aktywność konferencyjna
- Typ:
- publikacja w wydawnictwie zbiorowym recenzowanym (także w materiałach konferencyjnych)
- Tytuł wydania:
- 2016 IEEE International Symposium on Information Theory strony 1 - 5
- ISSN:
- 2157-8117
- Język:
- angielski
- Rok wydania:
- 2016
- Opis bibliograficzny:
- Manager A., Turowski K., Szpankowski W.: Lossless Compression of Binary Trees with Correlated Vertex Names // 2016 IEEE International Symposium on Information Theory / Barcelona: Information Theory (ISIT) 2016 IEEE International Symposoum on, 2016, s.1-5
- DOI:
- Cyfrowy identyfikator dokumentu elektronicznego (otwiera się w nowej karcie) 10.1109/isit.2016.7541492
- Weryfikacja:
- Politechnika Gdańska
wyświetlono 141 razy
Publikacje, które mogą cię zainteresować
Detecting coupling directions with transcript mutual information: A comparative study
- J. Amigó,
- B. Graff,
- G. Graff
- + 2 autorów
Computing algebraic transfer entropy and coupling directions via transcripts
- J. Amigó,
- R. Monetti,
- B. Graff
- + 1 autorów