An adaptive multi-alphabet arithmetic coding based on generalized virtual sliding window
Adaptive multi-alphabet arithmetic coding is a key component of many data compression algorithms. The well-known integer implementation of the arithmetic coding, proposed by Witten and Cleary, requires multiplications and divisions. This makes it difficult to use the coder, especially in hardware. Therefore, the vast majority of existing implementations represent non-binary data as a set of binary symbols (called binarization) and compress them using context modeling and a multiplication-free adaptive binary arithmetic coding (BAC). However, this approach can provide less compression performance comparing to multi-alphabet arithmetic coding. In this project we developed novel adaptive multi-alphabet arithmetic coding based on generalized virtual sliding window, which has the following advantages:
For more detailed information please see .
2. Performance comparison
For comparisons, we used classic Witten and Cleary multi-alphabet adaptive arithmetic coding implementation and four multi-alphabet adaptive arithmetic coding based on adaptive BAC. As an adaptive BAC we used MQ-coder from JPEG2000 image coding standard and M-coder from H.264/AVC and H.265/HEVC video coding standards. For representing non-binary data into binary format we applied unary binarization and tree binarization. The proposed coder was realized in two versions. The first version, denoted as Proposed 1, is the case, when the best window length was selected for each file, while Proposed 2 utilizes single window for all files using different precision of approximation of the multiplication (higher K means better precision).
The following table shows the compression performance for Large Calgary Corpus. Here we use Witten and Cleary's implementation as reference coder and compare it with the multiplication-free implementations, so that an average gain with sign '-' means that a considered coder provides better results than the reference one.
The following table shows the compression performance for Large Corpus.
The presented results show that:
GVSW arithmetic coder, Version 1.0 [download]
If you plan to use GVSW software, please also refer to the following paper: