Dror Baron -
Worst-case constraints in compression and prediction
Andy Singer
and I developed an interest in lossless compression
systems where the output length is constrained not
to exceed the input length by more than Delta bits
(inputs are of length N and the output no more than N+Delta).
Our first result in this arena was to show that modified
Huffman codes that satisfy such constraints have a slightly higher
average coding length than regular Huffman codes, yet this extra
redundancy decays
exponentially with Delta.
D. Baron and
A. C. Singer,
"On the Cost of Worst-Case Coding Length Constraints,"
IEEE Transactions on Information Theory,
vol. 47, no.7, pp. 3088-3090, November 2001
(pdf).
Next, we considered the cost of these
constraints when ideal coding lengths based on
probability assignments are considered.
The main idea, as illustrated, is that the constraint modifies
the probability mass function (PMF) such that large probabilities
above some threshold are decreased, while small probabilities
are increased to all have the constrained (smallest allowed) value.
D. Baron,
A. C. Singer,
and R. G. Baraniuk,
"Probability Assignments with Worst-Case Coding Length Constraints,"
Proceedings of 38th Annual Conference on Information Sciences and
Systems (CISS2004), Princeton, NJ, March 2004
(pdf).
Last updated December 2008