At 02:27 PM 1/8/2002 -0700, Michael Motyka wrote:
georgemw@speakeasy.net wrote :
On 8 Jan 2002, at 9:51, Michael Motyka wrote:
Eric Cordian <emc@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