-2

The title says it all, basically.

Are there any deterministic compression algorithms - that is, an algorithm which, given identical input, will always produce identical output?

As far as I know, all widely-used compression algoritms are "adaptive" and will vary their output based on whatever heuristic they happen to be using at the moment.

  • 4
    You seem to make a wrong assumption here (see answer below), or you mean something different than what you wrote. Please clarify. – Doc Brown Aug 18 '15 at 7:49
10

Most compression algorithms are deterministic. Being "adaptive" in no way contradicts being "deterministic": it only means varying behavior based on input, so if the input is the same, so will be the output.

You can easily verify this by compressing the same file several times using an algorithm of your choice (zip, gzip, bzip2, 7z, etc.) and comparing the outputs. For example on linux, you can run this command several times to compress the file /etc/fstab and compare if its checksum is the same each time: gzip < /etc/fstab | md5sum -.

  • though the algorithm itself is indeed deterministic, the implementation will sometimes store additionnal information (file permissions, timestamps etc) which can make it look like the output is not deterministic. adding a touch on the file between the compress and decompress can generate a different zip even though the file's content did not change. That being said, it's still deterministic once all parameters are factored in. – Newtopian Sep 27 '16 at 15:19

Not the answer you're looking for? Browse other questions tagged or ask your own question.