Due Thursday, 13 October, 2016 at 11:30 PM
Report problems to ablumer via email
In this assignment you will experiment with arithmetic coding using various models. I have written a small utility that generates files of random bits (represented by the bytes '0' and '1' for convenience). A simple model that assumes independent characters gives a reasonable amount of compression, since the file only contains zeroes and ones, but more compression is possible with a more sophisticated model.
Source code, a makefile, and the data generator are in ~ablumer/150mdchw4
Generate data files using the command ./genbits size seed filename, where
the defaults are ./genbits 1000 1234 randbits. The makefile makes "encode"
and "decode", which are run using ./encode < infile > outfile.
Modify "adaptive_model.c" so that it gives better compression on the files produced by "genbits". Try various fixed and adaptive models, including at least second-order Markov models (where the probability of the next bit depends on the values of the two previous bits), and record how much compression each gives.
Submit the code for your best adaptive model. Put a brief summary of the
performance you observed with other models in comments at the top of the code you submit.
Document your code so that it's easily understandable by the grader.
Please put your first name, last name, and CS login name on the first line of your comments.
Also include a brief summary of the amounts of compression obtained by
various models in the comment at the top of the file.
Submit your adaptive model file using this command (substitute a different name if your file
isn't called "model.cpp":
provide comp150mdc a4 model.cpp