A PARALLEL IMPLEMENTATION OF THE CTW COMPRESSION ALGORITHM
M.L.A. Stassen, T.J. Tjalkens, G.H.L.M. Heideman · TU/e Research Portal · 2001
The Context-Tree Weighting achieves a very good compression ratio but has a much slower execution speed than e.g. Lempel-Ziv type of algorithms. We consider the possibilities for parallel processing at the encoder side with the restriction that the encoder output is identical to the sequential single processor implementation. The approach we follow here is to split the tree over a given number of independent processors such that every processor processes symbols whose context reaches into a particular subtree. A final processor combines the results into the final estimated symbol probabilities. We discuss the optimal assignment of subtree processors for the two-layer ap-proach and the efficient distribution of symbols over these processors. THE NEED FOR SPEED From several studies [1, 2] we may conclude that the compression ratio achieved by the Context-Tree Weighting algorithm is among the best possible and it certainly outperforms the Lempel-Ziv type of methods. Other modern compression algorithms based on PPM [3] or the Burrows-Wheeler Transform [4] achieve a compression ratio closer to the CTW and the RK implementation [5] performs comparable to the CTW but also shares its undesirable features such as a huge memory requirements and low compression and decompression speed (as compared to the LZ algorithms). The CTW algorithm actually performs a sophisticated model and parameter esti-mation and thus it can be used in other (data-mining) applications [6]. In applications like these we only need the modeler (encoder) and therefor it will be useful to consider methods that will speed up the encoding process. We consider a design strategy for the Context-Tree Weighting (CTW) compression algorithm that allows a speed-up of the encoder by using more processors in parallel. We require of the parallel implementation that the encoder output is identical to the more standard single processor sequential implementation.