Document Open Access Logo

Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings

Authors Shashwat Banchhor, Rishikesh Gajjala, Yogish Sabharwal, Sandeep Sen

PDF
Thumbnail PDF

File

LIPIcs.FSTTCS.2021.8.pdf
  • Filesize: 0.89 MB
  • 23 pages

Document Identifiers

Author Details

Shashwat Banchhor
  • Department of Computer Science, Indian Institute of Technology, New Delhi, India
Rishikesh Gajjala
  • Indian Institute of Science, Bangalore, India
  • Department of Computer Science, Indian Institute of Technology, New Delhi, India
Yogish Sabharwal
  • IBM Research, New Delhi, India
Sandeep Sen
  • Department of Computer Science, Shiv Nadar University, Uttar Pradesh, India
  • Department of Computer Science, Indian Institute of Technology, New Delhi, India

Acknowledgements

We are grateful to an anonymous reviewer for suggesting the use of Monge property and simplifying the proofs of Theorem 1 and Theorem 2 in a previous version of this manuscript.

Cite AsGet BibTex

Shashwat Banchhor, Rishikesh Gajjala, Yogish Sabharwal, and Sandeep Sen. Generalizations of Length Limited Huffman Coding for Hierarchical Memory Settings. In 41st IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 213, pp. 8:1-8:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)
https://doi.org/10.4230/LIPIcs.FSTTCS.2021.8

Abstract

In this paper, we study the problem of designing prefix-free encoding schemes having minimum average code length that can be decoded efficiently under a decode cost model that captures memory hierarchy induced cost functions. We also study a special case of this problem that is closely related to the length limited Huffman coding (LLHC) problem; we call this the soft-length limited Huffman coding problem. In this version, there is a penalty associated with each of the n characters of the alphabet whose encodings exceed a specified bound D(≤ n) where the penalty increases linearly with the length of the encoding beyond D. The goal of the problem is to find a prefix-free encoding having minimum average code length and total penalty within a pre-specified bound P. This generalizes the LLHC problem. We present an algorithm to solve this problem that runs in time O(nD). We study a further generalization in which the penalty function and the objective function can both be arbitrary monotonically non-decreasing functions of the codeword length. We provide dynamic programming based exact and PTAS algorithms for this setting.

Subject Classification

ACM Subject Classification
  • Theory of computation → Data compression
Keywords
  • Approximation algorithms
  • Hierarchical memory
  • Prefix free codes

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Alok Aggarwal, Maria M. Klawe, Shlomo Moran, Peter W. Shor, and Robert E. Wilber. Geometric applications of a matrix-searching algorithm. Algorithmica, 2:195-208, 1987. URL: https://doi.org/10.1007/BF01840359.
  2. Alok Aggarwal, Baruch Schieber, and Takeshi Tokuyama. Finding a minimum-weightk-link path in graphs with the concave monge property and applications. Discrete & Computational Geometry, 12(3):263-280, 1994. Google Scholar
  3. M.B. Baer. Source coding for quasiarithmetic penalties. IEEE Transactions on Information Theory, 52(10):4380-4393, 2006. URL: https://doi.org/10.1109/TIT.2006.881728.
  4. Shashwat Banchhor, Rishikesh R. Gajjala, Yogish Sabharwal, and Sandeep Sen. Decode efficient prefix codes. CoRR, abs/2010.05005v2, 2020. URL: http://arxiv.org/abs/2010.05005v2.
  5. Shashwat Banchhor, Rishikesh R. Gajjala, Yogish Sabharwal, and Sandeep Sen. Decode-efficient prefix codes for hierarchical memory models. In Data Compression Conference, DCC 2020, page 360. IEEE, 2020. URL: https://doi.org/10.1109/DCC47342.2020.00077.
  6. Shashwat Banchhor, Rishikesh R. Gajjala, Yogish Sabharwal, and Sandeep Sen. Efficient algorithms for decode efficient prefix codes. In Ali Bilgin, Michael W. Marcellin, Joan Serra-Sagristà, and James A. Storer, editors, 31st Data Compression Conference, DCC 2021, Snowbird, UT, USA, March 23-26, 2021, page 338. IEEE, 2021. URL: https://doi.org/10.1109/DCC50243.2021.00080.
  7. Thomas Boutell. PNG (portable network graphics) specification ver 1.0. RFC, 2083:1-102, 1997. URL: https://doi.org/10.17487/RFC2083.
  8. Vladimir Britanak. A survey of efficient MDCT implementations in MP3 audio coding standard: Retrospective and state-of-the-art. Signal Process., 91(4):624-672, 2011. URL: https://doi.org/10.1016/j.sigpro.2010.09.009.
  9. Rainer E. Burkard, Bettina Klinz, and Rüdiger Rudolf. Perspectives of monge properties in optimization. Discrete Applied Mathematics, 70(2):95-161, 1996. URL: https://doi.org/10.1016/0166-218X(95)00103-X.
  10. M. Burrows and D. J. Wheeler. A block-sorting lossless data compression algorithm. Technical report, Digital Systems Research Centre, 1994. Google Scholar
  11. LL Campbell. Definition of entropy by means of a coding problem. Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete, 6(2):113-118, 1966. Google Scholar
  12. Peter Deutsch. DEFLATE compressed data format specification ver 1.3. RFC, 1951:1-17, 1996. URL: https://doi.org/10.17487/RFC1951.
  13. Hiroshi Fujiwara and Tobias Jacobs. On the huffman and alphabetic tree problem with general cost functions. Algorithmica, 69(3):582-604, 2014. URL: https://doi.org/10.1007/s00453-013-9755-6.
  14. M. R. Garey. Optimal binary search trees with restricted maximal depth. SIAM J. Comput., 3(2):101-110, 1974. URL: https://doi.org/10.1137/0203008.
  15. Edgar N. Gilbert. Codes based on inaccurate source probabilities. IEEE Trans. Inf. Theory, 17(3):304-314, 1971. URL: https://doi.org/10.1109/TIT.1971.1054638.
  16. M. Golin and Y. Zhang. A dynamic programming approach to length-limited huffman coding: Space reduction with the monge property. IEEE Trans. on Information Theory, 56(8):3918-3929, 2010. URL: https://doi.org/10.1109/TIT.2010.2050947.
  17. Mordecai J. Golin, Claire Kenyon, and Neal E. Young. Huffman coding with unequal letter costs. In John H. Reif, editor, Proceedings on 34th Annual ACM Symposium on Theory of Computing, May 19-21, 2002, Montréal, Québec, Canada, pages 785-791. ACM, 2002. URL: https://doi.org/10.1145/509907.510020.
  18. Song Han, Huizi Mao, and William J. Dally. Deep compression: Compressing deep neural networks with pruning, trained quantization and huffman coding. ICLR 2016, 2015. URL: http://arxiv.org/abs/1510.00149.
  19. TC Hu and KC Tan. Path length of binary search trees. SIAM Journal on Applied Mathematics, 22(2):225-234, 1972. Google Scholar
  20. D. A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the IRE, 40(9):1098-1101, 1952. URL: https://doi.org/10.1109/JRPROC.1952.273898.
  21. Richard M. Karp. Minimum-redundancy coding for the discrete noiseless channel. IRE Trans. Inf. Theory, 7(1):27-38, 1961. URL: https://doi.org/10.1109/TIT.1961.1057615.
  22. Lawrence Larmore and Teresa Przytycka. Constructing huffman trees in parallel. SIAM Journal on Computing, 24, July 1998. URL: https://doi.org/10.1137/S0097539792233245.
  23. Lawrence L. Larmore. Height restricted optimal binary trees. SIAM J. Comput., 16(6):1115-1123, 1987. URL: https://doi.org/10.1137/0216070.
  24. Lawrence L. Larmore and Daniel S. Hirschberg. A fast algorithm for optimal length-limited huffman codes. J. ACM, 37(3):464-473, 1990. URL: https://doi.org/10.1145/79147.79150.
  25. Lawrence L. Larmore and Teresa M. Przytycka. A parallel algorithm for optimum height-limited alphabetic binary trees. J. Parallel Distributed Comput., 35(1):49-56, 1996. URL: https://doi.org/10.1006/jpdc.1996.0067.
  26. A. Moffat and A. Turpin. On the implementation of minimum redundancy prefix codes. IEEE Transactions on Communications, 45(10):1200-1207, 1997. Google Scholar
  27. Baruch Schieber. Computing a minimum weightk-link path in graphs with the concave monge property. J. Algorithms, 29(2):204-222, 1998. URL: https://doi.org/10.1006/jagm.1998.0955.
  28. G. K. Wallace. The jpeg still picture compression standard. IEEE Transactions on Consumer Electronics, 38(1):xviii-xxxiv, 1992. Google Scholar
  29. Robert Wilber. The concave least-weight subsequence problem revisited. J. Algorithms, 9(3):418-425, September 1988. URL: https://doi.org/10.1016/0196-6774(88)90032-6.
  30. Justin Zobel and Alistair Moffat. Adding compression to a full-text retrieval system. Softw. Pract. Exp., 25(8):891-903, 1995. URL: https://doi.org/10.1002/spe.4380250804.
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