Random Data Compressed 100:1 (Guffaw)

Steve Schear schear at lvcm.com
Tue Jan 8 15:35:19 PST 2002


At 02:27 PM 1/8/2002 -0700, Michael Motyka wrote:
>georgemw at speakeasy.net wrote :
> >
> >On 8 Jan 2002, at 9:51, Michael Motyka wrote:
> >
> >> Eric Cordian <emc at artifact.psychedelic.net> wrote :
> >> >Someone else needs to read the comp.compression FAQ.



>What exactly is random data? Does it have to appear to be random? Does
>it have to pass some set of statistical tests to be random? If a string
>or bits from a radiation source spells "Merry Christmas and a Happy New
>Year" in ASCII is it non-random - a message from above? If a string of
>bits from a natural source ( decay etc ) matches a string of bits from
>some PRNG is it somehow disqualified as truly random data?
>
>I think the classification random does not rule out the presence of
>local patterns however obscure. If a substring of data happens to match
>what is generated by some PRNG then that substring can be "compressed"
>to {generator, seed, count}. The geological timescale might be involved
>in matching generator outputs to input data sections or deriving
>generators for subsections of data.

I came up with a similar approach in the late '80s (I may have even 
discussed it on the list a year or so back).  I was interested in 
compressing image data, which has quite a bit of inter-pixel 
correlation.  My approach was to run a Hilbert space filling curve through 
the image (it looks like a tightly wound maze).  This allows one to 
maintain most of the pixel correlation while transforming from an array to 
line.  Then I analyzed the auto correlation of the runs of various lengths 
and attempted to create generators which could produce the required 
combinations/permutations and auto correlations to code for the runs.  I 
say attempted, because I was never able to find acceptable algorithms to 
satisfy my requirement.  I still believe these algorithms exist, it was 
just my limitations in identifying the underlying math needed.

steve





More information about the cypherpunks-legacy mailing list