Optimal prefix codes with fewer distinct codeword lengths are faster to construct

DOI10.1016/J.IC.2019.104436MaRDI QIDQ2272991zbMATH OpenOpenAlexWikidataFDO

Authors Ahmed A. Belal, Amr Elmasry

Publication date 17 September 2019

Published in Information and Computation (Search for Journal in Brave)

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

zbMATH Keywords

data structuresoutput-sensitiveHuffman treesmedian findingoptimal prefix codes

Mathematics Subject Classification ID

Prefix, length-variable, comma-free codes (94A45) Data structures (68P05) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30)

Abstract: A new method for constructing minimum-redundancy binary prefix codes is described. Our method does not explicitly build a Huffman tree; instead it uses a property of optimal prefix codes to compute the codeword lengths corresponding to the input weights. Let $n$ be the number of weights and $k$ be the number of distinct codeword lengths as produced by the algorithm for the optimum codes. The running time of our algorithm is $O(kcdotn)$. Following our previous work in cite{be}, no algorithm can possibly construct optimal prefix codes in $o(kcdotn)$ time. When the given weights are presorted our algorithm performs $O(9^{k}cdotlo{g}^{2k}n)$ comparisons.

Recommendations

• Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes
• Efficient construction of minimum-redundancy codes for large alphabets
• Optimal prefix free codes with partial sorting
• In-place calculation of minimum-redundancy codes
• A fast algorithm for optimal length-limited Huffman codes

Cites work

• scientific article; zbMATH DE number 3558968 (Why is no real title available?)
• A Method for the Construction of Minimum-Redundancy Codes
• An almost optimal algorithm for unbounded searching
• Design and analysis of dynamic Huffman codes
• Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes
• Efficient construction of minimum-redundancy codes for large alphabets
• In-place calculation of minimum-redundancy codes
• On the maximum length of Huffman codes
• Three space-economical algorithms for calculating minimum-redundancy prefix codes
• Variations on a theme by Huffman
• Verification of minimum-redundancy prefix codes

Cited in

(5)

• A fast algorithm for optimal length-limited Huffman codes
• Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes
• Fixed-prefix encoding of the integers can be Huffman-optimal
• Optimal prefix free codes with partial sorting
• Fast and Compact Prefix Codes

This page was built for publication: Optimal prefix codes with fewer distinct codeword lengths are faster to construct

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