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