On the Reduction of Entropy Coding Complexity via Symbol Grouping:

Said, Amir

HP Development Company

关键词: data compression;    symbol grouping;    dynamic programming;    Monge matrices;   

RP-ID  :  HPL-2004-145

学科分类：计算机科学（综合）

美国|英语

来源: HP Labs

【 摘 要 】

We analyze the technique for reducing the complexity of entropy coding that consists in the a priori grouping of the source alphabet symbols, and in the decomposition of the coding process in two stages: first coding the number of the symbol's group with a more complex method, followed by coding the symbol's rank inside its group using a less complex method, or simply using its binary representation. This technique proved to be quite effective, yielding great reductions in complexity with reasonably small losses in compression, even when the groups are designed with empiric methods. It is widely used in practice and it is an important part in standards like MPEG and JPEG. However, the theory to explain its effectiveness and optimization had not been sufficiently developed. In this work, we provide a theoretical analysis of the properties of these methods in general circumstances. Next, we study the problem of finding optimal source alphabet partitions. We demonstrate a necessary optimality condition that eliminates most of the possible solutions, and guarantees that a more constrained version of the problem, which can be solved via dynamic programming, provides the optimal solutions. In addition, we show that the data used by the dynamic programming optimization has properties similar to the Monge matrices, allowing the use of much more efficient solution methods. 42 Pages