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.