I wish to estimate the compression ratio of a stream of bytes. Specifically, I'm interested in DEFLATE compression. I'm looking for some algorithm/heuristic that can estimate roughly the compressibility (more quickly than just deflating the stream).
My main interest is not on the absolute value of the compression (though it would also be useful) but on comparison: given two streams, guess which will be better compressed.
Another nice-to-have feature: be able to update the estimation incrementally.
For the record: just estimating the zero-order entropy, by computing the frequencies of each byte value, does not perform well enough for me.