License: Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.CPM.2016.29
URN: urn:nbn:de:0030-drops-60635
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2016/6063/
Go to the corresponding LIPIcs Volume Portal

Barbay, Jérémy

Optimal Prefix Free Codes with Partial Sorting

pdf-format:
LIPIcs-CPM-2016-29.pdf (0.5 MB)

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).

BibTeX - Entry

@InProceedings{barbay:LIPIcs:2016:6063,
  author =	{J{\'e}r{\'e}my Barbay},
  title =	{{Optimal Prefix Free Codes with Partial Sorting}},
  booktitle =	{27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)},
  pages =	{29:1--29:13},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-012-5},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{54},
  editor =	{Roberto Grossi and Moshe Lewenstein},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6063},
  URN =		{urn:nbn:de:0030-drops-60635},
  doi =		{10.4230/LIPIcs.CPM.2016.29},
  annote =	{Keywords: Deferred Data Structure, Huffman, Median, Optimal Prefix Free Codes, van Leeuwen.}
}

Keywords: Deferred Data Structure, Huffman, Median, Optimal Prefix Free Codes, van Leeuwen.
Collection: 27th Annual Symposium on Combinatorial Pattern Matching (CPM 2016)
Issue Date: 2016
Date of publication: 27.06.2016

DROPS-Home | Fulltext Search | Imprint | Privacy Published by LZI