Radek Mos, September 2011--April 2011, "Context-based Compression", Computer Science Department, University of Western Ontario, Canada.

B.Sc. Thesis Abstract

This report looks at the implementation of the compression and decompression algorithm based on Lempel-Ziv-Welch design (Dipperstein). The author outlines a process of extending the LZW algorithm with concepts from the successful PPM compression to further utilize data correlation by using the concept of a context and produce a two-dimensional context based LZW compression. This concept is implemented with the aid of LZW implementation published by Michael Dipperstein (Dipperstein). Included in this report are required data structures necessary for proposed extension which include: implementation details, architectural requirements, control flow requirements and major pitfalls of implementing this design. Additionally, a series of test on a standard Kodak image set is provided to describe relative performance and scaling performance of resulting compression algorithm. The project demonstrates a significant improvement to the LZW compression which may be extended to other implementations of LZ based coders. The author concludes with suggestions including the augmentation with a more sophisticated context prediction algorithm for future versions.