A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs

DOI10.1007/3-540-60084-1_79MaRDI QIDQ4645183zbMATH OpenOpenAlexFDO

Authors Günter Rote, Mordecai J. Golin

Publication date 10 January 2019

Published in Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/3-540-60084-1_79

zbMATH Keywords

dynamic programming algorithmminimum costlevel truncationinternal nodedeep node

Mathematics Subject Classification ID

Formal languages and automata (68Q45) Analysis of algorithms and problem complexity (68Q25) Dynamic programming (90C39)

Recommendations

• A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs
• Faster algorithm for designing optimal prefix-free codes with unequal letter costs
• Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property
• scientific article; zbMATH DE number 1305081
• Prefix Codes: Equiprobable Words, Unequal Letter Costs

Cites work

• scientific article; zbMATH DE number 3118808 (Why is no real title available?)
• scientific article; zbMATH DE number 3162350 (Why is no real title available?)
• scientific article; zbMATH DE number 3657150 (Why is no real title available?)
• scientific article; zbMATH DE number 3518695 (Why is no real title available?)
• Codes: Unequal Probabilities, Unequal Letter Cost
• Efficient Generation of Optimal Prefix Code
• Optimum lopsided binary trees
• Prefix Codes: Equiprobable Words, Unequal Letter Costs
• Tree Structures for Optimal Searching

Cited in

(14)

• Three space-economical algorithms for calculating minimum-redundancy prefix codes
• Algorithms and Data Structures
• Algorithms – ESA 2004
• Optimum extensions of prefix codes.
• More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
• Faster algorithm for designing optimal prefix-free codes with unequal letter costs
• A generic top-down dynamic-programming approach to prefix-free coding
• On the construction of prefix-free and fix-free codes with specified codeword compositions
• Optimal prefix free codes with partial sorting
• More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
• Huffman coding with letter costs: a linear-time approximation scheme
• scientific article; zbMATH DE number 1796977 (Why is no real title available?)
• A dynamic programming algorithm for constructing optimal "1"-ended binary prefix-free codes
• Optimal Prefix-Free Codes for Unequal Letter Costs: Dynamic Programming with the Monge Property

This page was built for publication: A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs

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