4. Organization of tree-structure
4.1. Binary decomposition
In principle CTW is a binary algorithm, but this algorithm could simply be extended to a 256-character alphabet for (de-) compression of ASCII-files and other byte-oriented files. Another possibility is to consider the file as a sequence of bits instead of a sequence of bytes, but both methods do not give the desirable results.
It appeared to be a better choice, to split each byte into eight separate bits, with separate context trees for each phase (i.e. bit) of the symbol. The context of each binary symbol now consists of all earlier binary symbols (i.e. the earlier bits of the current byte as well as all bits of earlier bytes). Now the phase of the current bit is used to select one of eight groups of trees, and the earlier bits of the current byte select a tree within this group. This means there actually are 255 different context trees (one tree for the first (most significant) bit of a certain byte, two for the second bit, four for the third bit, etc.), with all (bits of the) earlier symbols as their context (see figure 4.1).
Figure 4.1: example of a tree for the third bit of a certain byte. One of the (256-ary) trees is selected with the previous bits of the current byte.
4.2. Weighting at byte-boundaries
One might expect the 255 trees from the previous paragraph to be binary trees. However, as was already shown in figure 4.1, these trees are 256-ary trees in this implementation of CTW. This is because weighting only takes place at byte-boundaries.
Suppose the 255 trees were binary trees. Because the amount of available memory is limited, the size of the trees is also limited, which means each tree has a certain maximum depth. Now each tree can have leaves not only at byte-boundaries, but also inside the bytes, which means only part of a certain previous symbol is used as context for the current bit. This does not seem very sensible and it is questionable too if weighting inside bytes (i.e. not only on byte-boundaries) is very useful. Therefore, weighting only takes place at byte-boundaries, which means there now actually are 255 different 256-ary trees (with a certain maximum depth). At each node, the tree now splits into 256 different paths, dependent on a whole byte from the context (see figure 4.2).
Figure 4.2: weighting takes place at byte boundaries only.
This way the number of nodes in each tree is reduced, which means also the execution time will be lower. For byte-oriented sources this also gives a reduced redundancy, because less bits are required for describing a 256-ary tree than for describing a binary tree (which has more nodes). However, for sources that are not byte-oriented, a 256-ary tree-model might not fit the source as well as a binary tree-model, which might lead to an increased redundancy. Since most sources are byte-oriented, the use of 256-ary trees usually gives a better performance.
The binary decomposition is implemented in ctwencdec.c. Weighting is implemented in ctwmath.c, so there can be seen that weighting only takes place at byte-boundaries. More information on binary decomposition and weighting at byte-boundaries can be found in [IEEE par. 11].