Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:59
jwashbur@whittman-hart.com
Fri, 21 Aug 1998 08:52:13 -0500
RE: Compressing random data.
In general the "compressed" result is larger than the original.
The broad information theory behind compression is:
Given a a universe of text patterns (think files); if an algorithim can map
some text patterns to a smaller patterns then there exist other text
patterns that must map to larger patterns. In other words, if you can
compress some files, then there are other files that are incompressible.
By incompressible I mean the result from the compression engine is larger
than the input.
Humans use only a small fraction of the text patterns available. That is
why such text is so compressible. Your test of random data through
compression provides only a necessary test. All random data is
incompressible, but not all incompressible data is necessarily random. It
could be that the patterns in your data are unrecognized by the compression
engine. Thus not compressed.
Roughly speaking, PKZip, by design, is optimized to compress text,
executable binaries and pictures. PKZip sides steps this incompressibliity
issue by simply storing those patterns which are incomressible. The result
is a file larger than the original. The extra bytes are the 3 PKZip
headers (File Header, Central Directory header, and Archive Header) stored
with the original compressed data. With most files the savings in
compression more than offsets the overhead added by the PKZip file format.
For every gory detail on the PKZip file format see:
http://src.doc.ic.ac.uk/public/public/packages/zip/doc/appnote-970531-pk.zi
p.
I digress. Compressibility as a test of randomness is not correct. The
fact that a file is incompressible says nothing
about its "randomness".
In Liberty
John Washburn
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:59