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.
Worst-case prediction
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.
Last updated December 2008