Document Open Access Logo

Optimal Prefix Free Codes with Partial Sorting

Author Jérémy Barbay

PDF
Thumbnail PDF

File

LIPIcs.CPM.2016.29.pdf
  • Filesize: 0.5 MB
  • 13 pages

Document Identifiers

Author Details

Jérémy Barbay

Cite As Get BibTex

Jérémy Barbay. Optimal Prefix Free Codes with Partial Sorting. In 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 54, pp. 29:1-29:13, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016) https://doi.org/10.4230/LIPIcs.CPM.2016.29

Abstract

We describe an algorithm computing an optimal prefix free code for n unsorted positive weights in less time than required to sort them on many large classes of instances, identified by a new measure of difficulty for this problem, the alternation alpha.  This asymptotical complexity is within a constant factor of the optimal in the algebraic decision tree computational model, in the worst case over all instances of fixed size n and alternation alpha.  Such results refine the state of the art complexity in the worst case over instances of size n in the same computational model, a landmark in compression and coding since 1952, by the mere combination of van Leeuwen's algorithm to compute optimal prefix free codes from sorted weights (known since 1976), with Deferred Data Structures to partially sort multisets (known since 1988).

Subject Classification

Keywords
  • Deferred Data Structure
  • Huffman
  • Median
  • Optimal Prefix Free Codes
  • van Leeuwen.

Metrics

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

References

  1. Jérémy Barbay. Optimal prefix free codes with partial sorting. arXiv preprint arXiv:1602.00023, 2016. URL: http://arxiv.org/1602.00023.
  2. Jérémy Barbay, Ankur Gupta, Seungbum Jo, Srinivasa Rao Satti, and Jonathan Sorenson. Theory and implementation of online multiselection algorithms. In Proceedings of the Annual European Symposium on Algorithms (ESA), 2013. Google Scholar
  3. Jérémy Barbay, Ankur Gupta, S. Srinivasa Rao, and Jonathan Sorenson. Dynamic online multiselection in internal and external memory. In Proceedings of the International Workshop on Algorithms and Computation (WALCOM), 2014. Google Scholar
  4. Ahmed A. Belal and Amr Elmasry. Distribution-sensitive construction of minimum-redundancy prefix codes. CoRR, abs/cs/0509015, 2005. Version of Tue, 21 Dec 2010 14:22:41 GMT, with downgraded results from the ones in the conference version [5]. Google Scholar
  5. Ahmed A. Belal and Amr Elmasry. Distribution-sensitive construction of minimum-redundancy prefix codes. In Bruno Durand and Wolfgang Thomas, editors, Proceedings of the International Symposium on Theoretical Aspects of Computer Science (STACS), volume 3884 of Lecture Notes in Computer Science, pages 92-103. Springer, 2006. URL: http://dx.doi.org/10.1007/11672142_6.
  6. Ahmed A. Belal and Amr Elmasry. Verification of minimum-redundancy prefix codes. IEEE Transactions on Information Theory (TIT), 52(4):1399-1404, 2006. URL: http://dx.doi.org/10.1109/TIT.2006.871578.
  7. Yu-Tai Ching, Kurt Mehlhorn, and Michiel H.M. Smid. Dynamic deferred data structuring. Information Processing Letters (IPL), 35(1):37-40, June 1990. Google Scholar
  8. Shimon Even and Guy Even. Graph Algorithms, Second Edition. Cambridge University Press, 2012. Google Scholar
  9. Paolo Ferragina, Raffaele Giancarlo, Giovanni Manzini, and Marinella Sciortino. Boosting textual compression in optimal linear time. Journal of the ACM, 52(4):688-713, 2005. URL: http://dx.doi.org/10.1145/1082036.1082043.
  10. Yijie Han. Deterministic sorting in o(nlog log n) time and linear space. Journal of Algorithms, 50(1):96-105, 2004. URL: http://dx.doi.org/10.1016/j.jalgor.2003.09.001.
  11. David A. Huffman. A method for the construction of minimum-redundancy codes. Proceedings of the Institute of Radio Engineers (IRE), 40(9):1098-1101, September 1952. Google Scholar
  12. Kanela Kaligosi, Kurt Mehlhorn, J. Ian Munro, and Peter Sanders. Towards optimal multiple selection. In Proceedings of the International Conference on Automata, Languages, and Programming (ICALP), pages 103-114, 2005. URL: http://dx.doi.org/10.1007/11523468_9.
  13. R. Karp, R. Motwani, and P. Raghavan. Deferred data structuring. SIAM Journal of Computing (SJC), 17(5):883-902, 1988. URL: http://dx.doi.org/10.1137/0217055.
  14. J. Van Leeuwen. On the construction of Huffman trees. In Proceedings of the International Conference on Automata, Languages, and Programming (ICALP), pages 382-410, Edinburgh University, 1976. Google Scholar
  15. Ruy Luiz Milidiú, Artur Alves Pessoa, and Eduardo Sany Laber. A space-economical algorithm for minimum-redundancy coding. Technical report, Departamento de Informática, PUC-RJ, Rio de, 1998. Google Scholar
  16. Ruy Luiz Milidiú, Artur Alves Pessoa, and Eduardo Sany Laber. Three space-economical algorithms for calculating minimum-redundancy prefix codes. IEEE Transactions on Information Theory (TIT), 47(6):2185-2198, September 2001. URL: http://dx.doi.org/10.1109/18.945242.
  17. Alistair Moffat and Andrew Turpin. Efficient construction of minimum-redundancy codes for large alphabets. IEEE Transactions on Information Theory (TIT), pages 1650-1657, 1998. Google Scholar
  18. E. Moura, G. Navarro, N. Ziviani, and R. Baeza-Yates. Fast and flexible word searching on compressed text. ACM Transactions on Information Systems (TOIS), 18(2):113-139, 2000. Google Scholar
  19. Jop F. Sibeyn. External selection. Journal of Algorithms (JALG), 58(2):104-117, 2006. URL: http://dx.doi.org/10.1016/j.jalgor.2005.02.002.
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 About DROPS Imprint Privacy Contact