Advisor: Dr. Chris Pollett

Description:

The purpose of this independent study project is to examine the compression methods described in Approximating the Smallest Grammar: Kolmogorov Complexity in Natural Models by Moses Charikar et al. and to create a complete application that implements the context-free grammar compression algorithm defined in the paper. The application will be able to process any file to create a context-free grammar compression for it and to take a context-free grammar compression and regenerate the original input file. The application will also collect statistics for use in analyzing the effectiveness of the method and to allow for comparison of the method with other common compression algorithms. The application will be implanted in Java and will be fully commented and will be delivered with its Javadoc and the user documentation as well as any sample data, data runs, and analysis.