Data Compression

with Cellular Automata.

Wiktor K. Macura

Department of Computer Science,
The University of Maryland, Baltimore County,
1000 Hilltop Circle,
Baltimore, MD — 21228

The State of the Art.

Current loss-less compression methods rely on encoding sequences of tokens into a shorthand. The general tradeoff is size of the data vs. computational time require to convert to normal form.

Run-Length Encoding

Sequences of repeating tokens are translated to a multiplier and a single token sample.

"aaaaaaaaaaeeeeeeeeeeeasasasasasas" -> "10a 11e\
  12as"

IFF/IFF-ILBM; LZ77;

Entropy Encoding

Algorithms which encode "token streams" based on the probability of the tokens appearing. Tokens with higher probabilities are expected to occur more often and thus recieve shorter encoded forms.

Huffman Encoding; Arithmetic Encoding; Range Encoding;

Others

Other filtering methods tend to combine RLE or Entropy Encoding, or specialize for a particular usage.

Delta Encoding—Save space by only compressing differences between files.

Burrows-Wheeler Transform—Convert token data into a more compressable form using a reversable transform.

The Idea.

Cellular Automata provide a method for generating continous sequences of bits based on initial conditions.

What if we can translate a sequence of binary data into a cellular automaton rule and initial condition?

Hence, a potentially very long sequence of bits can be translated simply into a rule number and a short initial condition.

Benefits:

Massive potential savings in memory usage.

Cellular Automata may be simulated with great efficiency.

Perhaps the approach will be conducive to multiple passes.

The Obstacles; Part 1

How to translate a 2 dimensional cellular automata history into a one dimensional binary sequence? Should we partition into a rectangle?

[({{■, ■, ■, ■, ■, ■, ■, ■, ■}, {1, 2, 3, 4, 5, 6, 7, 8, 9}}) ]  ⟶   ({{–, –, 1, 2, 3, –, –}, {–, –, 4, 5, 6, –, –}, {–, –, 7, 8, 9, –, –}})

Or into a pyramid?

[({{■, ■, ■, ■, ■, ■, ■, ■, ■}, {1, 2, 3, 4, 5, 6, 7, 8, 9}}) ]  ({{ }, {⟶}, { }})   ({{–, –, –, 1, –, –, –}, {–, –, 2, 3, 4, –, –}, {–, 5, 6, 7, 8, 9, –}})

The Obstacles; Part 2

Obviously, not all binary sequences may be represented as the output of a cellular automata. Assuming we are using a 5×8 rectangular scheme to encode 40 bits:

({{–, –, –, ■, ■, ■, ■, ■, –, –, –}, {–, –, –, 1, 2, 3, 4, 5, –, –, –}, {–, –, –, 6, 7, 8, 9, 10, –, –, –}, {–, –, –, 11, 12, 13, 14, 15, –, –, –}, {–, –, –, 16, 17, 18, 19, 20, –, –, –}, {–, –, –, 21, 22, 23, 24, 25, –, –, –}, {–, –, –, 26, 27, 28, 29, 30, –, –, –}, {–, –, –, 31, 32, 33, 34, 35, –, –, –}, {–, –, –, 36, 37, 38, 39, 40, –, –, –}})

With 5 bit initial conditions, there are (2^5) possible initial conditions, and (2^8) elementary cellular automata rules. Thus yielding a total of (2^5)×(2^8) = (2^13) = 8192 outputs, of these 4606 are unique.

Therefore, we must somehow generate the other outputs.

We suggest to combine the outputs using a logical operator, like AND, OR, XOR, etc. However, when decompressing the data, the logical operator must be reversible. XOR and NOT-XOR are the only reversible logical operators.

The Method.

Assume we have already found a representation of the sequence.

Let us assume we have i initial condition cells. Then the cost of encoding a particular step is: 7 bits for the rule and i bits for the initial condition. Hence, the total cost is i + 7 bits per block.

In "real life" this is slightly more complicated. But our simplified model assumes we're compressing a single block.

Results so far.

This line of research is very far from complete. But preliminary results are very promising.

For 26 bits.

Using a 5×6 rectangle, with the last 4 bits ignored.

Total Sequences: 67 108 864

Level 1 Compressible: 4490, 14 bits saved per 26-bit block.

Level 2 Compressible: 45  492 080, 2 bits saved per 26-bit block.

Savings

On average, the compression ratio is 0.947799.

For 60 bits.

Using a 9x7 rectangle, with the last 7 bits ignored.

Total Sequences: \(TraditionalForm\`2\^60 = 
        1 152 921 504 606 846 976\).

Known

Level 1 Compressible: 78538, 47 bits saved per 60-bit block.

Level 2 Compressible: 6 156 497 831, 34 bits saved per 60-bit block.

Estimated by Extrapolation

Level 3 Compressible: 11 000 000 000 000 (4 billion known), 21 bits saved per 60-bit block.

Level 4 Compressible: 1 060 000 000 000 000 000. 8 bits saved per 60-bit block.

Estimated Savings

On average, the compression ratio is 0.877413.

The Future.

Considerable amounts of research still need to be preformed.

Perhaps the histological approach is non-optimal.

Perhaps a pyramidal approach would work better.

The 60-bit experiment will not end in a reasonable

An Interesting Note.

Within a 5-cell wide and 6-cell deep history, any output from a cellular automaton with any initial condition may be modeled by some cellular automaton with rule number less than or equal to 31.

Ask.

Questions?