Compression of random binary data

[Steve D'Aprano]

On Tue, 24 Oct 2017 05:20 pm, Gregory Ewing wrote:

> danceswithnumbers at gmail.com wrote:
>> I did that quite a while ago. 352,954 kb.
> 
> Are you sure? Does that include the size of all the
> code, lookup tables, etc. needed to decompress it?
> 
> But even if you have, you haven't disproved the theorem about
> compressing random data. All you have is a program that
> compresses *that particular* sequence of a million digits.
> 
> To disprove the theorem, you would need to exhibit an
> algorithm that can compress *any* sequence of a million
> digits to less than 415,241 bytes.

Indeed -- but let's give Dancerswithnumbers his due. *IF* he is right (a very
big "if" indeed) about being able to compress the Rand Corporation "Million
Random Digits" in binary form, as given, that alone would be an impressive
trick.

Compressing the digits in text form is not impressive in the least. As Ben
Bacarisse pointed out, most of us will probably already have half a dozen
programs that do that.

 

-- 
Steve
“Cheer up,” they said, “things could be worse.” So I cheered up, and sure
enough, things got worse.