26
$\begingroup$

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.

$\endgroup$
  • 11
    $\begingroup$ Check out Kolmogorov complexity, which is in some sense the optimal compression (up to an additive constant). Unfortunately, Kolmogorov complexity isn't computable... $\endgroup$ – Yuval Filmus May 7 '17 at 17:31
  • 12
    $\begingroup$ Why do you need to compress that data? Can't you just regenerate it any time you need it? (Which is closely related to the Kolmogorov complexity approach mentioned by @YuvalFilmus: the Kolmogorov complexity is essentially the length of the shortest program that generates the output). $\endgroup$ – David Richerby May 7 '17 at 20:35
  • 7
    $\begingroup$ I did write such an algorithm in high school, 20 years ago. Given your input, it would have compressed to a "few bytes" (approximately 3,500,000:1 in an optimal scenario). However, data rarely ever looks like this, so it's not practical to have an algorithm like this. General compression algorithms have to deal with complex patterns, not simple ones. Anyone can write an algorithm to store linear data, but storing interesting data is the challenge. $\endgroup$ – phyrfox May 8 '17 at 3:59
  • 3
    $\begingroup$ How does n = 20 gives you 22MB? I get 4.2 MB if using 4 bytes integers $\endgroup$ – njzk2 May 8 '17 at 21:22
  • 3
    $\begingroup$ @JiK oh, ok. well that would be a first notion of compression, not using 8 bits to represent a single bit. $\endgroup$ – njzk2 May 9 '17 at 14:27
27
$\begingroup$

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

$\endgroup$
45
$\begingroup$

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 tag, and read textbooks on data compression.

$\endgroup$
  • 5
    $\begingroup$ The job of a compressor is to recognize common patterns and exploit them. It's not like this pattern is uncommon or obscure. So it's a natural question to ask why it's not exploited. Telling him there's a trade-off or giving him an algorithm that fails on everything except that pattern is a total cop-out. $\endgroup$ – Mehrdad May 8 '17 at 4:10
  • 17
    $\begingroup$ Sure looks uncommon to me. This would come up in real-life data extremely rarely, compared to the kinds of patterns good compressors do look for. $\endgroup$ – amalloy May 8 '17 at 8:10
  • 17
    $\begingroup$ @Mehrdad It's not a snarky cop-out: it's the entire point. For any pattern X that's simply generated and simply checked for, there's a compression algorithm that looks for that pattern and deals with it. So this is the answer to any question along the lines of "Is there a compression algorithm that deals with such an X?" Sure, there's always an algorithm that looks for slightly more complex patterns. And there's one that looks for slightly more complex patterns than that one, too, ad infinitum. Your objection is ill-founded. $\endgroup$ – David Richerby May 8 '17 at 19:36
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Gilles May 8 '17 at 22:02
  • $\begingroup$ An extreme application of this principle is bittorrent magnet links where any file or collections of files of any size are simply represented (compressed) to a fixed 160 bits of data. There is of course a risk that hash collision can occur. $\endgroup$ – slebetman May 11 '17 at 5:55
16
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ You could get rid of eval by doing: for first in (bwt_c, nothing, lzma, zlib, gzip, bz2):and fOut = first.compress(inputData). $\endgroup$ – kasperd May 7 '17 at 22:08
  • $\begingroup$ @kasperd - how would I print the names in that case? Personally, it's simpler (and less error-prone) to do an eval than it is to try to keep the names + references synced. $\endgroup$ – TLW May 8 '17 at 1:08
  • 5
    $\begingroup$ First bwt and then bz2 compresses this extremly well. This is extremly strange behavior and probably due to this exact pattern. Note that you're doing the bwt twice (bz2 is based on the BWT) which usally results in worse compression. Also note that bwt today usally runs at 4 times block size memory (e.g. ~4MB for this) and at speeds of >10 MB/s (I'm the author of such a bwt library/compression algorithm) which is quite usable for many applications. Note that even gzip produces very good compressible results. Thanks for sharing I'm not aware of any research on using bwt twice. $\endgroup$ – Christoph May 8 '17 at 10:31
  • 3
    $\begingroup$ @Christoph - I know bz2 is based on BWT...I had actually started to write an answer to the effect of 'just use bz2', but found that it didn't compress nearly as well as I had expected, went 'huh', and decided to see if my own BWT would do better. Only I needed a compressor for the output, and went 'may as well try different compressors to see what happens'. $\endgroup$ – TLW May 9 '17 at 1:09
  • 1
    $\begingroup$ @Christoph - I took another look. 2 bwts of this data generate something that is extremely amenable to RLE encoding. As in, if you count the number of RLE pairs required for 0, 1, 2, ... nested BWTs on a 16-bit input, you get 622591 1081343 83 ... $\endgroup$ – TLW May 9 '17 at 2:24
10
$\begingroup$

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
$\endgroup$
5
$\begingroup$

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

$\endgroup$
  • $\begingroup$ It's not just the time it takes to check for this kind of input: it's also the space taken up by whatever encoding scheme you use for "And then count to $n$ in binary" and, in particular, the knock-on effect that this has on every other part of the compression, which must be annotated with "This isn't counting to some number in binary." $\endgroup$ – David Richerby May 8 '17 at 11:52
  • 1
    $\begingroup$ Also, rather than aborting, you can use the technique of "dovetailing" to deal with non-halting programs. To do this, you run the first $n$ programs for $n$ steps each, then the first $n+1$ programs for $n1$ steps each, and so on. This means that you run every program for a number of steps that isn't a priori bounded, but without having to wait for one program to halt before trying the next one. $\endgroup$ – David Richerby May 8 '17 at 11:54
  • $\begingroup$ Well, tools like Mathematica find functions for many sequences... $\endgroup$ – Raphael May 8 '17 at 20:46
3
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.