May 15, 2005 6:28 PM
Arithmetic coding takes a stream of symbols and replaces it with a
floating point number. It can be combined with statistical modeling
to provide reasonable data compression.
For more details regarding Arithmetic Coding, visit Mark Nelson's website where his original article published in Dr. Dobbs Journal is still preserved intact.
I've written an arithmetic coding library in C++ that uses a
statistical model. It's compression ratio (42% for a C source file) is
currently way lower than that provided by gzip (a whopping 73%) but
the version using a higher order (3) provides better performance
(75.4%). gzip running with the best compression option (gzip -9
)
gives a ratio of 73.5% on the same file though it takes far lesser
time to run. Here's the output of a sample session:
%./anicmpr sample.c Compressing sample.c to test.out. SimpleCompress Running Building Model (SimpleModel in compression mode)... Building Totals... Done. Writing Model to File... Done. Initializing Arithmetic Coder... Done. Coding........................... Done. Input Bytes: 166909 Output Bytes: 96973 Compression Ratio: 41.9007 Uncompressing test.out to test1.out. SimpleUncompress Running Building Model (SimpleModel in decompression mode)... Finished creating scaledcounts... Building Totals... Done. Initializing Arithmetic Decoder.... Done. Decoding.................................................. Done. Input Bytes: 96973 Output Bytes: 166909 Compression Ratio: 41.9007
The problem with programming in C++ is that there is always this temptation to revert to good old C. But then, the advantages of C++ are obvious. I can plug in any model into the compressor during the creation of the object at runtime. Namespaces make it easy to group objects together and exceptions aid in improved error handling though I suspect it makes it harder to track program flow. Though a compression library might not be the best scenario for Object Oriented Programming, I got to learn C++ which was one of the objectives in doing this project besides writing a compression library that does not use Huffman Coding1. I had made rough sketches of class diagrams and sequence diagrams beforehand and they have proved invaluable during the project.
This post marks the anniversary of this website. Exactly one year ago, I posted the first entry, Assembly in Linux.
CategoryProgramming Comment(s)
[1] Since almost everyone has done that at some point of time.