Preface
With nothing much to do during summer vacation, I spent a few days writing a fairly complete implementation of the LZW compression algorithm, so here are some brief notes.
I will not reiterate what the algorithm itself is about; there are already countless tutorials online. I will only share two that I think are excellent. The first describes the entire algorithm in great detail, including Examples, special cases, and nearly every detail you need to pay attention to during implementation. You can tell the author is truly passionate about compression and encryption algorithms; it would be worth reading his other articles when you have time. But oddly, despite being so thorough, he did not implement the CLEAR reset code in the gif standard. This is a very basic and necessary feature; without it, the resulting program simply cannot compress large files. Still, the C code he provides is rigorous and readable, although it uses many strange optimization tricks, and the comments seem to far outnumber the lines of code... The second one includes two somewhat unclear flowcharts, but fortunately the author provides a very concise implementation. It is rough, but quite suitable for understanding the core idea of the algorithm.
Core Idea
For essentially all compression algorithms, the task is nothing more than reducing information redundancy—in other words, converting information that takes a lot of space into information that takes less space, while defining an inverse transform so that the former can be losslessly restored from the latter. For the LZW compression algorithm, this is essentially accomplished using a String->Int dictionary for the transform, and an Int->String dictionary for the inverse transform during decompression. What is clever about LZW, however, is that through an agreed-upon sequence of operations, we do not need to store the dictionary produced during compression: during decompression, the dictionary can be recreated, and we only need to store the compressed file itself.
The compression operation of LZW is defined as follows: first, we have a String to store the substring not yet output in compressed form, and a Char to store the currently read character. Suppose at some moment we have a non-empty String and have read a new Char. If the new string String + Char exists in the dictionary, then set String += Char and read again; otherwise, first output the compressed code corresponding to String, then add String + Char to the dictionary, and finally set String = Char. We know that at the initial state String is empty. If we push forward from that state for a few steps, we will find that the operation defined above is continuously trying to construct new dictionary entries, ensuring that every String in the dictionary has been directly output as ASCII values, and only when it appears again will it be replaced by a compressed code—this is precisely the process of reducing information redundancy. The algorithm uses a compressed code to replace an entire segment of characters.
With the above in place, we can introduce the clever decompression procedure. During decompression we define two strings, NewString and OldString. The former represents the string currently decompressed, while the latter represents the string decompressed last time. In decompression, assume we know in advance that we can basically guarantee that each compressed code read exists in the dictionary (there is a special case, not discussed in detail here). Then each NewString equals the string in the dictionary corresponding to the compressed code. The question is: how do we ensure this guarantee? From the compression process we can see that the only thing added to the dictionary each time is String + Char, and each time we output only the compressed code corresponding to String—so during decompression it clearly corresponds to OldString. As for that Char, when it is output, by order it must be the first character of NewString; that is, in decompression, for each string that should be added to the dictionary, the first part is the OldString decompressed last time, and the second part is precisely NewString[0]! Therefore, as long as during decompression we add OldString + NewString[0] to the dictionary each time, we can “basically” guarantee that each compressed code read will exist in the dictionary. What remains is just handling some boundary conditions; RTFSC is enough to fully understand it, and I will not elaborate further here.
Implementation Details
First, in the process of outputting data, it is obviously not feasible to output using a fixed-width type such as int; otherwise, after compression it might even take more space. From the compression procedure we can see that the codes for dictionary entries will gradually increase, meaning the output code length can also be regarded as continuously growing. To output variable-length integer codes, we need to implement an IO library that supports outputting integers by bit-length. My approach was to derive from the fstream class, then add a buffer, a buffered byte, and several functions to achieve the above. But I did something rather silly: I added an extra buffer to fstream, a class that already has buffering. It is truly redundant and meaningless. However, given that the implementation was indeed quite troublesome, I did not optimize this part away; consider it an exercise in coding.
Because variable-length coding is required, the output needs to indicate when the code length should be increased. The implementation of this marker is shown in the code; it is a very clever method. On the other hand, we can see that the dictionary in the algorithm is almost a natural red-black tree, so using STL's map makes it easy to implement. But the problem is that the number of entries recorded in the map obviously cannot grow without bound, or performance will be severely affected. Therefore, it is necessary to clear and rebuild the dictionary when it grows to a certain size. The gif standard defines a CLEAR code, meaning that if this marker is read, the current dictionary is cleared and rebuilt. The implementation of this marker is also quite tricky, which is clearly reflected in the code. My LZW implementation is here, along with a crude GUI written in Python.
Finally, a brief reflection: doing development on Windows with VS is truly a powerful tool. Not only does it natively integrate git and connect seamlessly with Github, but the interface is also very straightforward and easy to use, supporting arbitrary inclusion/exclusion of files, and so on. I have to say, an IDE that tightly integrates an editor, compiler, debugger, code optimization, version control, and more, while providing an extremely stable and reliable GUI, is highly competitive.
References
- http://michael.dipperstein.com/lzw/
- http://blog.csdn.net/abcjennifer/article/details/7995426