Bio

Tomáš Komárek is an undergraduate student at Palacky University in Olomouc, Czech Republic, studying applied physics to earn his bachelor’s and, subsequently, master’s degree. He is looking forward to beginning work on his bachelor’s thesis in the area of accelerator physics after the summer school ends. In addition to physics and mathematics, he is interested in programming and tries to keep track of modern technologies. But he also does not refuse any philosophically aimed debate and likes thinking about answer to the Ultimate Question of Life, the Universe, and Everything.

Project: PNGcrush Compression and Randomness in Patterns

I use the open-source software “PNGcrush” for compression of patterns, mostly produced by cellular automata. PNGcrush contains over 100 strategies for compression.

PNG compression consists of two main parts, the first of which is DEFLATE compression (lossless) after applying various reversible filters. DEFLATE consists of a LZ77 algorithm (which can use a number of ways of finding repetitions). What follows is further compression by the Huffman algorithm. The search for the best compression ratio in PNGcrush is based on brute force, trying over 100 combinations of filters and ways of compression when commanded so. By compression strategy, I mean one of these combinations.

I managed to set up a user interface for pattern generation and code to call PNGcrush to store and parse its output. Using information about IDAT size (pure image data without any headers), I was able to compute the compression ratio for every single used compression strategy.

Compression ratio can be one of the ways to determine how good randomness is present in the compressed data. Data with few randomness in it or purely repetitive data are easily compressible, while random data are hard to compress or incompressible at all. In my project, I used this principle with a combination of many compression strategies used in PNGcrush to determine quality of randomness in 2D patterns.

Favorite Four-Color, Four State Turing Machine

Rule 430668276334908560862918