2006/12/25 by Paul Vitányi, Paul M. B. Vitanyi, Vitanyi, Paul M. B. +2
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Algorithms and Data Compression #Computational Complexity (cs.CC) #FOS: Computer and information sciences #Genome Rearrangement Algorithms #Information Theory (cs.IT) #cs.CC #cs.IT #math.IT #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.cs/0612133
LaTex 8 pages
arxiv created 2006/12/25 · openalex publication_date 2006/12/25 · arxiv updated 2009/12/01 · openalex created_date 2024/04/11 · openalex updated_date 2026/07/28
We study the new problem of Huffman-like codes subject to individual restrictions on the code-word lengths of a subset of the source words. These are prefix codes with minimal expected code-word length for a random source where additionally the code-word lengths of a subset of the source words is prescribed, possibly differently for every such source word. Based on a structural analysis of properties of optimal solutions, we construct an efficient dynamic programming algorithm for this problem, and for an integer programming problem that may be of independent interest.