On the construction of prefix-free and fix-free codes with specified codeword compositions

DOI10.1016/J.DAM.2011.08.003zbMATH Open1233.94012arXiv1002.0097OpenAlexW2104932738MaRDI QIDQ765325FDOQ765325

Authors: A. Kakhbod, Morteza Zadimoghaddam 

Publication date: 19 March 2012

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Abstract: We investigate the construction of prefix-free and fix-free codes with specified codeword compositions. We present a polynomial time algorithm which constructs a fix-free code with the same codeword compositions as a given code for a special class of codes called distinct codes. We consider the construction of optimal fix-free codes which minimizes the average codeword cost for general letter costs with uniform distribution of the codewords and present an approximation algorithm to find a near optimal fix-free code with a given constant cost.

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

Recommendations

• Complete variable-length ``fix-free codes
• Faster algorithm for designing optimal prefix-free codes with unequal letter costs
• A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs
• A dynamic programming algorithm for constructing optimal prefix-free codes for unequal letter costs
• Algorithms and Data Structures

zbMATH Keywords

approximation algorithmpolynomial-time algorithmfix-free codeprefix-free code

Mathematics Subject Classification ID

Prefix, length-variable, comma-free codes (94A45)

Cites Work

• A Method for the Construction of Minimum-Redundancy Codes
• More Efficient Algorithms and Analyses for Unequal Letter Cost Prefix-Free Coding
• Codes: Unequal Probabilities, Unequal Letter Cost
• Conjectures on uniquely decipherable codes (Corresp.)
• Some basic properties of fix-free codes
• A dynamic programming algorithm for constructing optimal prefix-free codes with unequal letter costs

Cited In (5)

• Algorithms and Data Structures
• Some basic properties of fix-free codes
• Efficient and compact representations of some non-canonical prefix-free codes
• Necessary and sufficient conditions of commutatively prefix codes and every-layer-extensible codes
• Complete variable-length ``fix-free codes

This page was built for publication: On the construction of prefix-free and fix-free codes with specified codeword compositions

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