A pattern in random data

[CompressMaster]

A pattern in random data - there is ALWAYS some pattern, problem is, how to express it using less information (bytes) than original...

[Shelwien]

Enumerate all possible data strings with specific pattern, then encode the index of given string in the list.

[compgt]

The algorithm i described here is an attack on random data; it assumes or best for random data:

https://encode.su/threads/3024-Best-...ental-integers

If i remember it right, my gr32 program in the Miscellany page of "The Data Compression Guide" is designed for random data in mind. Somehow, when things got complicated, i just opted for repetition i/o codes. That's why i decided to write a decoder. It's like a failed BPE, with very miniscule compression.

https://sites.google.com/site/dataco...ide/miscellany

Random Data quips here:

https://grtamayoblog.blogspot.com/20...ndom-data.html

Random data compression is futile unless, perhaps, you start from the most basic of information unit that is bits.

[pklat]

but such a 'compressor', if it exists, would then enlarge 'nonrandom data'? I don't see how that could be useful.

[Shelwien]

Actually it would - switching codecs requires 1 bit.

Problem is, too many of possible data strings are random.
I'd say, only something like 2^(n/log(n)) of 2^n strings (where n is the length of a binary string) are compressible.
So it would be hard to encode all random strings (ie not compressible) with less than n bits.

[pklat]

perhaps there is finite amount of information in universe, if good enough compression/deduplication/whatever is used. that theory of everything or something.

[compgt]

perhaps there is finite amount of information in universe, if good enough compression/deduplication/whatever is used. that theory of everything or something.

Pklat, your "information" = data; "theory" = (set of) functions, or equations.

The space of all possible pictures in a 640x480 picture, for example, is clearly finite with respect to "infinity". If you can somehow brute-force or generate all these pictures, there are finite set/s of very interesting pictures that have enough very high "information" such as pictures that show you when you were a child or ten years old, and even up to what you are doing at the present moment. However, that is only theoretical or logical play of mind. You cannot catch up with this theoretical machine or this "camera in infinite time," but perhaps find this set of functions for the camera that would only show "the most important" events in your life.

[compgt]

A pattern in random data - there is ALWAYS some pattern, problem is, how to express it using less information (bytes) than original...

One slow early approach is to guess the pattern or symbol. Just try to guess the input byte in < 32 tries, to output just 5 bits. (You can do this by randomly setting bits of a dummy byte on or off and compare it with the input byte.) If not guessed, output 00000 and then 8-bit byte. How would you initialize the dummy byte? Maybe by context; crude LZP like. What else? Build on this. Improve this.