I have a file containing ordered binary numbers from $0$ to $2^n - 1$:00000000000000000001000000001000000000110000000100...11111111117z did not compress this file very efficiently (for n = 20, 22 MB were compressed to 300 kB).Are there algorithms that can recognize very simple structure of data and compress file to several bytes? Also I want to know what area of CS or information theory studies such smart algorithms. AI would be too broad, please suggest more concrete keywords.Notion of symmetry should play fundamental role in data compression, but search queries symmetry in data compression and group theory in data compression surprisingly return almost nothing relevant.
Efficient compression of simple binary data
information theory;data compression
This seems to be a clear use case for delta compression. If $n$ is known a priori this is trivial: store the first number verbatim, and for each next number store only the difference to the previous. In your case, this will give01111...This can then with simple run-length encoding be stored in $\mathcal{O}(n)$ space, as there are only $\mathcal{O}(1)$ groups (namely, two) of different deltas.If $n$ is not known, the simplest thing would be a brute-force search for the word-size for which this delta/run-length representation comes out shortest. Perhaps only do this search for randomly-chosen, $\sqrt{N}$-sized chunks, to amortize the overhead of finding $n$ while retaining good reliability.Unlike D.W.'s all or nothing proposal, delta compression with run-length encoding can actually give sensible compression ratios for some simple real-world kinds of content, like low-resolution audio. (It is thus suitable for low-quality, very low-latency and low-power audio compression.)