Efficient compression of simple binary data

Question

I have a file containing ordered binary numbers from $0$ to $2^n - 1$:

0000000000
0000000001
0000000010
0000000011
0000000100
...
1111111111

7z 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.

Answer 1

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 give

0
1
1
1
1
...

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.)

Answer 2

Sure, of course there are algorithms. Here is my algorithm:

1. First, check if the file contains ordered binary numbers from $0$ to $2^n-1$, for some $n$. If so, write out a 0 bit followed by $n$ one bits followed by a 0 bit.

2. If not, write out a 1 bit, then write out the 7z-compression of the file.

This is extremely efficient for files of that particular structure.

The point is: there is no free lunch in data compression. You might be able to build a compression algorithm that compresses one type of file well, at the cost of compressing others worse. But, if you know a priori something about the nature of the files you will be compressing, you can optimize your algorithm for that particular type of file.

The area is "data compression". See our data-compression tag, and read textbooks on data compression.

Answer 3

Anything using a BWT (Burrows–Wheeler transform) ought to be able to compress that fairly well.

My quick Python test:

>>> import gzip
>>> import lzma
>>> import zlib
>>> import bz2
>>> import time
>>> dLen = 16
>>> inputData = '\n'.join('{:0{}b}'.format(x, dLen) for x in range(2**dLen))
>>> inputData[:100]
'0000000000000000\n0000000000000001\n0000000000000010\n0000000000000011\n0000000000000100\n000000000000010'
>>> inputData[-100:]
'111111111111010\n1111111111111011\n1111111111111100\n1111111111111101\n1111111111111110\n1111111111111111'
>>> def bwt(text):
    N = len(text)
    text2 = text * 2
    class K:
        def __init__(self, i):
            self.i = i
        def __lt__(a, b):
            i, j = a.i, b.i
            for k in range(N): # use `range()` in Python 3
                if text2[i+k] < text2[j+k]:
                    return True
                elif text2[i+k] > text2[j+k]:
                    return False
            return False # they're equal

    inorder = sorted(range(N), key=K)
    return "".join(text2[i+N-1] for i in inorder)

>>> class nothing:
    def compress(x):
        return x

>>> class bwt_c:
    def compress(x):
        return bwt(x.decode('latin_1')).encode('latin_1')

>>> for first in ('bwt_c', 'nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
    fTime = -time.process_time()
    fOut = eval(first).compress(inputData)
    fTime += time.process_time()
    print(first, fTime)
    for second in ('nothing', 'lzma', 'zlib', 'gzip', 'bz2'):
        print(first, second, end=' ')
        sTime = -time.process_time()
        sOut = eval(second).compress(fOut)
        sTime += time.process_time()
        print(fTime + sTime, len(sOut))

bwt_c 53.76768319200005
bwt_c nothing 53.767727423000224 1114111
bwt_c lzma 53.83853460699993 2344
bwt_c zlib 53.7767307470001 5930
bwt_c gzip 53.782549449000044 4024
bwt_c bz2 54.15730512699997 237
nothing 6.357100005516259e-05
nothing nothing 0.0001084830000763759 1114111
nothing lzma 0.6671195740000258 27264
nothing zlib 0.05987233699988792 118206
nothing gzip 2.307255977000068 147743
nothing bz2 0.07741139000017938 187906
lzma 0.6767229399999906
lzma nothing 0.6767684639999061 27264
lzma lzma 0.6843232409999018 27324
lzma zlib 0.6774435929999072 27280
lzma gzip 0.6774431810001715 27292
lzma bz2 0.6821310499999527 27741
zlib 0.05984937799985346
zlib nothing 0.05989508399989063 118206
zlib lzma 0.09543156799986718 22800
zlib zlib 0.06264000899977873 24854
zlib gzip 0.0639041649999399 24611
zlib bz2 0.07275534999985211 21283
gzip 2.303239570000187
gzip nothing 2.303286251000145 147743
gzip lzma 2.309592880000082 1312
gzip zlib 2.3042639900002087 2088
gzip gzip 2.304663197000309 1996
gzip bz2 2.344431411000187 1670
bz2 0.07537686600016968
bz2 nothing 0.07542737000017041 187906
bz2 lzma 0.11371452700018381 22940
bz2 zlib 0.0785322910001014 24719
bz2 gzip 0.07945505000020603 24605
bz2 bz2 0.09332576600013454 27138

(Numbers here are 'first_compressor second_compressor time_taken bytes_out')

(BWT taken from here)

This is still 'not just a few bytes', but is nonetheless much better than just gzip alone. BWT + bz2 gets down to 237 bytes from 1114111 for a 16-bit input, for instance.

Alas, BWTs are far too slow and memory-hungry for many applications. Especially given this is a naive implementation in Python - on my machine I run out of RAM before 2**20.

With Pypy I was able to run the full 2**20 input, and it compresses it to 2611 bytes with a BWT followed by bz2. But taking over 3 minutes and peaking at over 4GB of RAM used...

Also unfortunately, this approach is still O(2^n) output space, it would appear - at least from curve-fitting 1..20.

Answer 4

PNG encoding does exactly what you want. It works on real life data also, not just extremely organized data.

In PNG, each row is encoded with a filter, of which 4 are specified. One of these is "encode this pixel as the difference between its value and the value of the pixel one above it." After filtering, the data is then zip'd using DEFLATE.

This filtering is a specific example of the Delta Encoding mentioned by leftaroundabout in his answer, except instead of following it up with Run Length Encoding you follow it up with the more powerful DEFLATE algorithm. It accomplishes the same goal, only DEFLATE will handle a larger variety of inputs while still providing the desirable compression ratios.

Another tool which is often used in scientific data where simple filter+DEFLATE isn't quite as effective is RICE encoding. In RICE, you take a block of values and output all of the most-significant-bits first, then all of the 2nd-most-significant-bits, all the way down to the least significant bits. You then compress the result. For your data that won't be quite as effective as the PNG style filtering (because your data is perfect for PNG filtering), but for a lot of scientific data it tends to lead to good results. In a lot of scientific data, we see the most significant bit tends to change slowly, while the least significant is almost random. This teases apart the highly predictable data from the highly entropic data.

0000000000       00000  most significant bits
0000000001       00000
0000000010  =>   00000
0000000011       00000
0000000100       00000
                 00000
                 00000
                 00001
                 00110
                 01010 least significant bits

Answer 5

Any practical algorithm searching for specific structures would be limited just to the structures hard-coded into it. You could patch 7z to recognize this specific sequence, but how often is this specific structure going to occur in real life? Not often enough to warrant the time it takes to check inputs for this input.

Practicalities aside, one can conceive of the perfect compressor as an algorithm which tries to construct the shortest program that produces a given output. Needless to say, there are no practical ways of doing this. Even if you tried a brute-force enumeration of all possible programs and checked whether they produced the desired output (not an entirely insane idea), you will run into the Halting problem, meaning that you will have to abort trial runs after a certain number of execution steps, before you know whether this program definitely cannot produce the desired output.

The search tree for such a brute-force approach grows exponentially with program length and is not practical for all but the simplest programs (something like 5-7 instructions long).

Answer 6

Compression ratios depend entirely on the targeted decompressor. If the decompressor can't decode sequential 4 byte numbers more compactly than 4 bytes per number then you are SOL.

There are various things that would allow encoding of sequential numbers. For example a differential encoding. You take n bytes at a time and then take the difference or the xor of the bits and then compress the result. This adds 4 options here to try for every byte count: identity a'[i] = a[i]; difference a'[i] = a[i-1]-a[i]; reverse difference a'[i] = a[i]-a[i-1]; and the xor a'[i] = a[i]^a[i-1]. That means adding 2 bits to select the methods and a byte count for 3 out of 4 options.

However not all data is a sequence of the fixed-length records. The differential encoding doesn't make sense for that (unless the compressor can empirically prove that it works for a bit of data).