SAKDC

SAKDC is a variable order Markov text compression algorithm. The algorithm is an abstract predictor that can be connected to an arithmetic coder.

SAKDC stands for Swiss Army Knife Data Compression. The algorithm was named this because it has so many parameters that one can twiddle! SAKDC was created as a research algorithm and the algorithm and its parameter space are thoroughly explored in Chapter 4 of my Ph.D. Thesis which was published as a book (which you can purchase online).

The algorithm's parameters allow the control of maximum nodes, maximum tree depth, tree growth rate and regime, node recycling regime, the blending of predictions from various model orders, the estimation formula, and a variety of other aspects.

Chapter 4 of my Ph.D. Thesis describes SAKDC in detail and explores the parameter space, arriving at a set of "best" parameters called "Opt1" which yield a proportion remaining of 0.317 for the Calgary Corpus. To my knowledge, this was the best compression of the corpus at the time the thesis was published.

The implementation of SAKDC is not available. SAKDC was implemented as about 4000 lines of Ada on the VAX/VMS operating system. The code resides on a tape somewhere.