compressing randomly-generated numbers

[Travis H.]

Hey,

I was mulling over some old emails about randomly-generated numbers
and realized that if I had an imperfectly random source (something
less than 100% unpredictable), that compressing the output would
compress it to the point where it was nearly so.  Would there be any
reason to choose one algorithm over another for this application?

I recall talking to a CS prof once who said that LZW compression was
"optimal", which seemed and still seems really odd to me because
optimal compression would generate a null output file.  So surely he
meant asymptotically optimal, or e-close to optimal, or something like
that... anyone know?

Obviously I will avoid any fixed-content headers and "magic numbers"
by using a "raw" implementation of the algorithm, not reusing, say,
gzip.  Plus, I will be running as though the RNG was providing me with
an infinitely long string, not reading everything into memory and
trying to compress.

It seems as though the Burroughs-Wheeler Transform (bzip2 et. al.)
gets the best compression of the standard utilities... is it suitable
for infinite length strings?  Is there anything better?
-- 
"If you're not part of the solution, you're part of the precipitate."
Unix "guru" for rent or hire -><- http://www.lightconsulting.com/~travis/
GPG fingerprint: 9D3F 395A DAC5 5CCC 9066  151D 0A6B 4098 0C55 1484

---------------------------------------------------------------------
The Cryptography Mailing List
Unsubscribe by sending "unsubscribe cryptography" to majordomo at metzdowd.com