Could you please describe or refer to an algorithm that would enable a
universal, general purpose program to compress any stream of random
data? It would be a plus if this could be implemented on a Turing
Machine, or failing that, a Windows PC.

---

Request for Question Clarification by answerguru-ga on 11 Jan 2004 19:42 PST

Hi there,

Have you tried Huffman codings? This is the same technology used to
"zip" files...if you are interested I can dig up some more information
on this for you :)

answerguru-ga

It is mathematically impossible to have an algorithm that can compress
any input without loss.  For a discussion, see:

http://www.faqs.org/faqs/compression-faq/part1/section-8.html

--efn

you have a turing machine? hehe, wow.

check this guy out, he's got turing and compression written all over
his site. if he's real or not i'm not sure

http://www.geocities.com/malbrain/

The Lempel-Ziv algorithm is a universal lossless compression algorithm
that is asymptotically optimal, that is as the sequence grows longer
you get a compression ration that approaches the best that can be done
. This algorithm is actually used in the various versions of zip
(gzip, winzip etc.)

It is quite easy to implemet.
See http://www.data-compression.com/lossless.html
Also Section 12.10 of Cover and Thomas "Elements of Information
Theory" for a slightly different description and proof of optimality.