Are there any good DEFLATE-like compression algorithms that are additive and immutable?

I need to add more things onto a stacklike structure, but compress them additively such that addition of new data results in the expected compression gain, but new chunks are still stored as compressed data without altering any of the past data chunks.

So in other words, it must preserve the additive property over successive compressed chunks. If f() is the ‘adding another chunk’ function, I need the following to hold for all chunks ‘x’:

\sum_{i=1}^{n}f(x_i)=f(\sum_{i=1}^{n}x_i)

>Solution :

Sure. Deflate does this, if you just keep it running and terminate each chunk at a byte boundary, e.g. with Z_SYNC_FLUSH, so that it can be written to file up to and including that chunk.

So long as your chunks are large enough, you will get the same compression gain.

Leave a Reply