Pattern Mining in Reduce-Fold Cellular Automata
Vouw is a command-line interface for printing an analysing Reduce-Fold Cellular Automata (RFCA) and is an academic implementation of the VOUW algorithm. For the visualisation of RFCA, please see the user-friendly RFExplore: https://github.com/mickymuis/rfexplore
Vouw is coded in C99 and should run on anywhere. I may have used some Linux specific functions calls, so if you run in to any trouble please notify me. Compiling is easy, just run in your terminal:
git clone https://github.com/mickymuis/vouw.git
cd vouw
./configure
cd build
make
The vouw executable is now located in build.
Let's print our first automaton! For this we pick automaton 2.2.6 and call the print module:
./vouw print -m 2 -b 2 -r 6 -i 00110 -f 5
If everything is well, this should produce the following output:
1 1 0 1 0 0 0 1 1 0
0 1 1 1 0 0 1 0 1
1 0 0 1 0 1 1 1
1 0 1 1 1 0 0
1 1 0 0 1 0
0 1 0 1 1
1 1 1 0
0 0 1
0 1
1
The arguments are the same for every module (the first argument after ./vouw). Type ./vouw without arguments to see decriptions for each parameter.
We can use the VOUW algorithm to compress an automaton and view the compressed output, code table and compression ratio:
./vouw encode -m 2 -b 2 -r 6 -i 00110 -f 5
Which appearently compresses to the following with a ratio of 81%
C . B . . A . B . B
. . A . B . B . B
. B . B . . A C
C . . A . . A
C . . A . B
. B . . A
C C . B
C . B
. B
C
Now the real power lies in the compression of an automaton with the code table of another automaton. This can be used, for example, as measure of distance. Let's compress a bigger version of 2.2.6 with the code table of 2.2.7:
./vouw encode -m 2 -b 2 -r 6 -i 00110 -f 20 using -r 7
Notice the extra using argument. The ratio is now almost 68%, indicating that 2.2.6 and 2.2.7 are quite similar. If we now were to compress the same automaton with the code table generated from 2.2.8, we would obtain a ratio of 108%, indicating that they are less similar.
2.2.6 compressed by 2.2.7's code table:
. . . G . . E G . . F . . . . E . . E G . G . . E
. G G . E G . E G . E G . E G . E . G E G E . G
D . G D . E G . C G . C D . E D D E G . . D D
G . . . G . E . . . G . E . . . . . E G E D
. . G . E . G . G . . G . E . G . G D D G
D . . . . . . . C . . . D . . . D . . G
D . . . D . . . . . . . . . . C G . G
. . . . C . . . . . D . . . D G D D
D . . . D . . . . D . . . D G G D
B . . . . . . . . . . . B . . G
B . . . . . . . . . . B G . G
B . . . . . . . . . B G D D
B . . . . . . . . B G G D
B . . . . . . . B . . G
B . . . . . . B G . G
B . . . . . B G D D
B . . . . B G G D
A . . . A . . G
A . . A G . G
A . A G D D
A A G G D
A . . G
G . G
D D
D