Document Open Access Logo

Simple Worst-Case Optimal Adaptive Prefix-Free Coding

Author Travis Gagie

PDF
Thumbnail PDF

File

LIPIcs.ESA.2022.57.pdf
  • Filesize: 0.53 MB
  • 5 pages

Document Identifiers

Author Details

Travis Gagie
  • Faculty of Computer Science, Dalhousie University, Halifax, Canada

Funding

  • Gagie, Travis: Funded by NSERC Discovery Grant RGPIN-07185-2020.

Cite AsGet 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)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Newton Faller. An adaptive system for data compression. In Record of the 7th Asilomar Conference on Circuits, Systems and Computers, pages 593-597, 1973. Google Scholar
  2. 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. Google Scholar
  3. Travis Gagie. Dynamic length-restricted coding. Master’s thesis, University of Toronto, 2003. Google Scholar
  4. Travis Gagie. Dynamic Shannon coding. In Proceedings of the 12th European Symposium on Algorithms (ESA), pages 359-370, 2004. Google Scholar
  5. 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. Google Scholar
  6. Robert Gallager. Variations on a theme by Huffman. IEEE Transactions on Information Theory, 24(6):668-674, 1978. Google Scholar
  7. David A Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098-1101, 1952. Google Scholar
  8. 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. Google Scholar
  9. Marek Karpinski and Yakov Nekrich. A fast algorithm for adaptive prefix coding. Algorithmica, 55(1):29-41, 2009. Google Scholar
  10. Gyula O H Katona and Tibor O H Nemetz. Huffman codes and self-information. IEEE Transactions on Information Theory, 22(3):337-340, 1976. Google Scholar
  11. Donald E Knuth. Dynamic Huffman coding. Journal of Algorithms, 6(2):163-180, 1985. Google Scholar
  12. 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. Google Scholar
  13. Claude Elwood Shannon. A mathematical theory of communication. The Bell System Technical Journal, 27(3):379-423, 1948. Google Scholar
  14. 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. Google Scholar
  15. 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. Google Scholar
  16. Jeffrey Scott Vitter. Design and analysis of dynamic Huffman codes. Journal of the ACM, 34(4):825-845, 1987. Google Scholar
  17. Jeffrey Scott Vitter. Algorithm 673: dynamic Huffman coding. ACM Transactions on Mathematical Software, 15(2):158-167, 1989. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact