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

DOI10.1109/18.705558zbMath0980.94009MaRDI QIDQ4701156

Günter Rote, Mordecai J. Golin

Publication date: 21 November 1999

Published in: IEEE Transactions on Information Theory (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/1187358d4738f6448c91a5863cba4e536fc8d102

zbMATH Keywords

dynamic programming; optimal code; Huffman code; prefix-free codes of minimum cost

Mathematics Subject Classification ID

90C39: Dynamic programming

94A45: Prefix, length-variable, comma-free codes

Related Items

More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding, On the construction of prefix-free and fix-free codes with specified codeword compositions, Dynamic Shannon coding, Trees with exponentially growing costs, The \(S\)-digraph optimization problem and the greedy algorithm, Optimal point-to-point broadcast algorithms via lopsided trees, Generalized Huffman coding for binary trees with choosable edge lengths, Speeding up the AIFV-2 dynamic programs by two orders of magnitude using range minimum queries