Abstract | ||
---|---|---|
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 min imal 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, a nd for an integer programming problem that may be of independent interest. |
Year | Venue | Keywords |
---|---|---|
2006 | Clinical Orthopaedics and Related Research | computational complexity,structure analysis,information theory,prefix code,dynamic programming algorithm |
Field | DocType | Volume |
Dynamic programming,Discrete mathematics,Theoretical computer science,Prefix,Huffman coding,Integer programming,Prefix code,Mathematics | Journal | abs/cs/061 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Paul Vitányi | 1 | 2130 | 287.76 |
Zvi Lotker | 2 | 1000 | 79.68 |