1. Introduction

 

The CTW encoder (and also the decoder) actually consists of two parts (figure 1.1):

• A source modeller (the actual CTW algorithm), which accepts the uncompressed data and estimates the probability on the next symbol.
• An arithmetic encoder, which uses the estimated probabilities to compress the data generated by the actual source. Any arithmetic encoder could be used for this purpose and therefore this part of the encoder will not be discussed in this article.

 

 

 

Figure 1.1: CTW encoder

 

A very important property of the CTW (Context Tree Weighting) algorithm is the context tree, which is built dynamically during the encoding/decoding process:

• The context is defined as all preceding symbols of the symbol that is being encoded. Every context that occurs is stored as a path in the context trees.
• The context trees are 256-ary trees with a certain maximum depth (to limit the amount of memory required). The reason that 256-ary tree structures are used, is that weighting only takes place at byte boundaries (chapter 4), which is especially suitable for byte-oriented files (e.g. files containing text).

• Each node of a context tree contains two types of data (figure 5.4):
1. Four bytes of data required for managing the tree-structure.
2. Four bytes of data required for estimating and weighting the probabilities, which will eventually be used in the arithmetic encoder and decoder.
• The trees require a lot of memory and therefore need to be stored in an efficient way. In this implementation of CTW, hashing (chapter 6) is used for this purpose. To limit the number of nodes in a tree, the paths in the tree are not always extended to the maximal depth. This is called unique path pruning (chapter 5) and results in a great reduction of the required number of nodes (and thus the required amount of memory). Unique path pruning does not affect the compression rate, but it does lead to a small increase in complexity.

 

When encoding a certain bit, the following steps are performed:

• The path in the context tree that coincides with the current context is searched and, if needed, extended (to make sure all paths are unique, see chapter 5). This means the symbols from the context are used to decide in which direction the path continues from every node.
• In every node on this context path, the estimated probability on the next symbol P_e is calculated, using the data that is stored inside the node. This estimated probability is calculated with the Krichevski-Trofimov or Zero-Redundancy estimator (chapter 2).
• Then, a weighted probability P_w is calculated using a weighting function on all of the P_e values (chapter 3). The idea behind this is that if good coding distributions for two different sources are weighted, then the weighted distribution is a good coding distribution for both sources (see [IEEE par. 9]).
• Finally the weighted probability is sent to the arithmetic encoder, which encodes the symbol, and then the tree is updated with the new data.

 

A "mini-course" on the basic properties of the CTW algorithm can be found in [IEEE], which is considered to be understood before reading this article. The main program file is ctw.c and the actual steps required for encoding and decoding can be found in ctwencdec.c.