CS180 Proposal
CFG Based File Compression
James Keesey (jlkeesey at mindspring.com)
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.
|