Huffman coding with letter costs: a linear-time approximation scheme

DOI10.1137/100794092MaRDI QIDQ2910857zbMATH OpenOpenAlexFDO

Authors Claire Mathieu, Neal E. Young, Mordecai J. Golin

Publication date 12 September 2012

Published in SIAM Journal on Computing (Search for Journal in Brave)

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

zbMATH Keywords

Huffman coding

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Approximation algorithms (68W25) Prefix, length-variable, comma-free codes (94A45)

Abstract: We give a polynomial-time approximation scheme for the generalization of Huffman Coding in which codeword letters have non-uniform costs (as in Morse code, where the dash is twice as long as the dot). The algorithm computes a (1+epsilon)-approximate solution in time O(n + f(epsilon) log^3 n), where n is the input size.

Recommendations

• Prefix Codes: Equiprobable Words, Unequal Letter Costs
• A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs
• Prefix codes: equiprobable words, unequal letter costs
• scientific article; zbMATH DE number 1305081
• On the Huffman and alphabetic tree problem with general cost functions

Cited in

(6)

• A novel DNA sequence similarity calculation based on simplified pulse-coupled neural network and Huffman coding
• On the Huffman and alphabetic tree problem with general cost functions
• Generalized Huffman coding for binary trees with choosable edge lengths
• A generic top-down dynamic-programming approach to prefix-free coding
• First come first served for online slot allocation and Huffman coding
• Alphabetic coding with exponential costs

This page was built for publication: Huffman coding with letter costs: a linear-time approximation scheme

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