Optimal prefix free codes with partial sorting

DOI10.4230/LIPICS.CPM.2016.29zbMATH Open1380.68460arXiv1602.00023OpenAlexW2964115797MaRDI QIDQ5369564FDOQ5369564

Authors: Jérémy Barbay 

Publication date: 17 October 2017

Abstract: We describe an algorithm computing an optimal prefix free code for $n$ unsorted positive weights in time within $O(n(1+lgalpha))subseteqO(nlgn)$, where the alternation $alphain[\mathrm{1..}n-1]$ measures the amount of sorting required by the computation. 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 size $n$ and alternation $alpha$. Such results refine the state of the art complexity of $Theta(nlgn)$ 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 a multiset depending on the queries on it (known since 1988).

Full work available at URL: https://arxiv.org/abs/1602.00023

Recommendations

• In-place calculation of minimum-redundancy codes
• Optimal prefix codes with fewer distinct codeword lengths are faster to construct
• A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs
• A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs
• Optimum extensions of prefix codes.

zbMATH Keywords

medianHuffmandeferred data structureoptimal prefix free codesvan Leeuwen

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Prefix, length-variable, comma-free codes (94A45) Data structures (68P05) Searching and sorting (68P10) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Algorithms on strings (68W32)

Cited In (5)

• In-place calculation of minimum-redundancy codes
• \(p\)-suffix sorting as arithmetic coding
• Optimal prefix codes with fewer distinct codeword lengths are faster to construct
• Title not available (Why is that?)
• A dynamic programming algorithm for constructing optimal "1"-ended binary prefix-free codes

This page was built for publication: Optimal prefix free codes with partial sorting

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5369564)