Fixed point compression algorithm currently used widely

Question

I was wondering if today there is a general compression algorithm containing a fixed point, i.e. an identification file.

To explain, call C : byte[] -> byte[] function that represents a compression algorithm. I want to know if there exists (and what it is, if it is possible to determine within a reasonable time) a file f , such that

C(f) = f

That is, a file that, when compressed using a suitable well-known compression algorithm, will now be used as the result.

Do you know about this phenomenon?

Answer 1

Yes! This is an option for the quine problem.

• An example that gzip uses is: http://groups.google.com/group/comp.compression/browse_thread/thread/c57c322e15c782aa/350d9fb166fdf11f

• An example that uses zip / unzip : http://www.steike.com/code/useless/zip-file-quine/

Answer 2

Warning: rather a pedantic answer.

There are many cases where D (f) = f (D is defined as decompression). However, compression is not well defined. For most compression algorithms, different implementations of the compression algorithm will produce different output files (of different sizes). Consider two programs: 1 and 2. For complete interoperability, it is necessary that D1 (F) be equal to D2 (F) for all real F. Similarly, it is necessary that D2 (C2 (f)) == D2 (C1 (F)) = = D1 (C1 (F)) == D1 (C2 (F)), for all real F. However, it is absolutely not necessary that C1 (F) == C2 (F), and this is actually a rare case.

Thus, you are unlikely to be able to, if you are actually compressing such quines to get the same file, if you are not using the same program as for creating it (which is unlikely, since such quines are usually manual, and C (F) never tested).

While it is possible (indeed, trivial!) To create a program for which C (F) == F for some F, most people tend to instead indicate as quines a more clearly defined case where D (F) == F (because D1 (F) == D2 (F) for all valid, compatible decompressions of format F, if F is valid).

So, there are likely cases where C (F) == F, but this is usually the wrong question, and you should ask for cases where D (F) == F ... which are other people who answered the question.