Example Animation: LZW Compression

In this example posting, we examining one concrete output of the generation process. Because this is the first such step, we will provide a few more details than we will do in later postings.

First, start the generation process as outlined in the blog posting How to create a new animation using a generator by selecting File ➜ Generate…. Then navigate to English (en), Java, Compression, and choose the algorithm LZW (Lempel, Ziv, Welch). You will see a window as blow that gives some basic details on the generator, includings its author and the name of the class (in case something was broken, you can use this to report a precise error). You can also see the underlying implementation code in Java at the bottom.

Choosing the LZW Compression algorithm

Next, click on Confirm to see the options. The algorithm has one parameter, as also indicated on the screenshot above, called stringArray in this case. You can adjust the value by modifying the length of the array ("Number of elements" - please make sure to press RETURN when you change the size to notify the Java program of the change!). Here, we leave the array in its default state, which was chosen to give some helpful output. 

We could also modify the display options of six different entries, but we will leave them alone here. Click Confirm to confirm the values, and then either choose a filename to save the file (and load it in later), or click Confirm again to directly see the animation.

The user can modify the algorithm parameter(s) and/or layout settings

The animation starts with a very brief overview of the algorithm and how it works "in plain English". There is no screenshot for this here; put simply, the algorithm maintains a dictionary of entries, where each "word" is associated with a number. The dictionary initially contains the entries 0-255 for the 256 entries in the ASCII character set. Whenever a new word combination is encountered, for example "LZ", the algorithm checks if this "word" is already in its dictionary. If this is the case, we add the next input character and repeat the process. If not, the new "word" is added to the dictionary at the next free position and the encoding for the "last known word" (shorter by the last character) is added to the encoded output.

In the next image, you see the main animation. The red code line is the one currently being executed, in the context of the "else" statement. We have just added the text LZ77 to our dictionary with the numerical value 262. The last output was 259, representing the LZ7 part of the "word" that was already contained in the dictionary. The next word to be encoded would be 7L, using the last 7 of the previously unknown word LZ77 and the next character (right next to the arrow) L; this will again be added to the dictionary as a new element and the code for 7 (55) will be added to the output.

LZW compression at work: adding a new word to the dictionary

One of the great advantages of the LZW compression algorithm is that the dictionary can be rebuilt from the compressed contents and thus does not have to be transferred, saving network bandwidth and/or disk space.

Why don't you try out the generator on your own?

© Dr. Guido Rößling 1998-today