Context Tree Weighting

Documentation

Package ctw provides an implementation of the Context Tree Weighting algorithm. Also contained is an implementation of the Rissanen-Langdon Arithmetic Coding algorithm, which is combined with Context Tree Weighting to create a lossless compression/decompression utility.

Below is an example of using this package to compress Lincoln's Gettysburg address:

go run compress/main.go gettysburg.txt > gettys.ctw
cat gettys.ctw | go run decompress/main.go > gettys.dctw
diff gettysburg.txt gettys.dctw

The results are noticeably superior to that of other commercial applications on a Mac OS X:

• Original: 1463
• tar.gz: 993
• 7z: 908
• zip: 874
• xz: 828
• CTW: 772

Reference: F.M.J. Willems and Tj. J. Tjalkens, Complexity Reduction of the Context-Tree Weighting Algorithm: A Study for KPN Research, Technical University of Eindhoven, EIDMA Report RS.97.01.

Full documentation at https://godoc.org/github.com/fumin/ctw.

Applications

A demonstration of using this compression tool to study mammalian evolution and construct the phylogeny of the SARS virus can be found here.

Testing

go test

Questions

• Why does increasing the depth above 48 not improve the compression of gettysburg.txt? Depth 48 gives 772 bytes, while depth 60 also gives 772 bytes.
• The exposition in https://cs.anu.edu.au/courses/comp4620/2015/slides-ctw.pdf gives a CTW based way of predicting the next bit. However, it is not clear how should we predict the next say 10 bits, without iterating through the 1024 different possibilities.