LIPIcs.ESA.2022.57.pdf
- Filesize: 0.53 MB
- 5 pages
Document
Simple Worst-Case Optimal Adaptive Prefix-Free Coding
Author
Travis Gagie 
-
Part of:
Volume:
30th Annual European Symposium on Algorithms (ESA 2022)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: European Symposium on Algorithms (ESA) - License:
Creative Commons Attribution 4.0 International license
- Publication Date: 2022-09-01
File
Document Identifiers
Author Details
Cite As Get BibTex
Travis Gagie. Simple Worst-Case Optimal Adaptive Prefix-Free Coding. In 30th Annual European Symposium on Algorithms (ESA 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 244, pp. 57:1-57:5, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.ESA.2022.57
Abstract
We give a new and simple worst-case optimal algorithm for adaptive prefix-free coding that matches Gagie and Nekrich’s (2009) bounds except for lower-order terms, and uses no data structures more complicated than a lookup table.
Subject Classification
ACM Subject Classification
- Theory of computation → Design and analysis of algorithms
Keywords
- Adaptive prefix-free coding
- Shannon coding
- Lookup tables
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Newton Faller. An adaptive system for data compression. In Record of the 7th Asilomar Conference on Circuits, Systems and Computers, pages 593-597, 1973.
-
Michael L Fredman and Dan E Willard. Surpassing the information theoretic bound with fusion trees. Journal of Computer and System Sciences, 47(3):424-436, 1993.
-
Travis Gagie. Dynamic length-restricted coding. Master’s thesis, University of Toronto, 2003.
-
Travis Gagie. Dynamic Shannon coding. In Proceedings of the 12th European Symposium on Algorithms (ESA), pages 359-370, 2004.
-
Travis Gagie and Yakov Nekrich. Worst-case optimal adaptive prefix coding. In Proceedings of the 11th Symposium on Algorithms and Data Structures (WADS), pages 315-326, 2009.
-
Robert Gallager. Variations on a theme by Huffman. IEEE Transactions on Information Theory, 24(6):668-674, 1978.
-
David A Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098-1101, 1952.
-
Marek Karpinski and Yakov Nekrich. A fast algorithm for adaptive prefix coding. In Proceedings of the International Symposium on Information Theory (ISIT), pages 592-596, 2006.
-
Marek Karpinski and Yakov Nekrich. A fast algorithm for adaptive prefix coding. Algorithmica, 55(1):29-41, 2009.
-
Gyula O H Katona and Tibor O H Nemetz. Huffman codes and self-information. IEEE Transactions on Information Theory, 22(3):337-340, 1976.
-
Donald E Knuth. Dynamic Huffman coding. Journal of Algorithms, 6(2):163-180, 1985.
-
Ruy Luiz Milidiú, Eduardo Sany Laber, and Artur Alves Pessoa. Bounding the compression loss of the FGK algorithm. Journal of Algorithms, 32(2):195-211, 1999.
-
Claude Elwood Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(3):379-423, 1948.
-
Jan van Leeuwen. On the construction of Huffman trees. In Proceedings of the 3rd International Colloquium on Automata, Languages and Programming (ICALP), pages 382-410, 1976.
-
Jeffrey Scott Vitter. Design and analysis of dynamic Huffman coding. In Proceedings of the 26th Symposium on Foundations of Computer Science (FOCS), pages 293-302, 1985.
-
Jeffrey Scott Vitter. Design and analysis of dynamic Huffman codes. Journal of the ACM, 34(4):825-845, 1987.
-
Jeffrey Scott Vitter. Algorithm 673: dynamic Huffman coding. ACM Transactions on Mathematical Software, 15(2):158-167, 1989.