Adaptive coding techniques have been increasingly used in lossless data compression. They are suitable for a wide range of applications, in which on-line compression is required, including communications, internet, e-...
详细信息
Adaptive coding techniques have been increasingly used in lossless data compression. They are suitable for a wide range of applications, in which on-line compression is required, including communications, internet, e-mail, and e-commerce. In this paper, we present an adaptive fano coding method applicable to binary and multi-symbol code alphabets. We introduce the corresponding partitioning procedure that deals with consecutive partitionings, and that possesses, what we have called, the nearly-equal-probability property, i.e. that satisfy the principles of fano coding. To determine the optimal partitioning, we propose a brute-force algorithm that searches the entire space of all possible partitionings. We show that this algorithm operates in polynomial-time complexity on the size of the input alphabet, where the degree of the polynomial is given by the size of the output alphabet. As opposed to this, we also propose a greedy algorithm that quickly finds a sub-optimal, but accurate, consecutive partitioning. The empirical results on real-life benchmark data files demonstrate that our scheme compresses and decompresses faster than adaptive Huffman coding, while consuming less memory resources. (c) 2005 Elsevier Inc. All rights reserved.
A rigorous performance analysis of fano coding is presented, providing an upper bound on the average codeword length of binary and ternary fano codes for an arbitrary discrete memoryless source. The performance bound ...
详细信息
ISBN:
(纸本)9781467377041
A rigorous performance analysis of fano coding is presented, providing an upper bound on the average codeword length of binary and ternary fano codes for an arbitrary discrete memoryless source. The performance bound is slightly better than Shannon's well-known bound for Shannon coding. As a by-product a novel general lower bound on Shannon entropy is derived that might be of interest also in a different context. This bound is expressed with the help of variational distance and provides a special case of a reverse Pinsker inequality.
Statistical coding techniques have been used for a long time in lossless data compression, using methods such as Huffman's algorithm, arithmetic coding, Shannon's method, fano's method, etc. Most of these ...
详细信息
Statistical coding techniques have been used for a long time in lossless data compression, using methods such as Huffman's algorithm, arithmetic coding, Shannon's method, fano's method, etc. Most of these methods can be implemented either statically or adaptively. In this paper, we show that although fano coding is sub-optimal, it is possible to generate static fano-based encoding schemes which are arbitrarily close to the optimal, i.e. those generated by Huffman's algorithm. By taking advantage of the properties of the encoding schemes generated by this method, and the concept of "code word arrangement", we present an enhanced version of the static fano's method, namely fano(+). We formally analyze fano(+) by presenting some properties of the fano tree, and the theory of list rearrangements. Our enhanced algorithm achieves compression ratios arbitrarily close to those of Huffman's algorithm on files of the Calgary corpus and the Canterbury corpus. (C) 2003 Elsevier Ltd. All rights reserved.
This correspondence shows that learning automata techniques, which have been useful in developing weak estimators, can be applied to data compression applications in which the data distributions are nonstationary. The...
详细信息
This correspondence shows that learning automata techniques, which have been useful in developing weak estimators, can be applied to data compression applications in which the data distributions are nonstationary. The adaptive coding scheme utilizes stochastic learning-based weak estimation techniques to adaptively update the probabilities of the source symbols, and this is done without resorting to either maximum likelihood, Bayesian, or sliding-window methods. The authors have incorporated the estimator in the adaptive fano coding scheme and in an adaptive entropy-based scheme that "resembles" the well-known arithmetic coding. The empirical results obtained for both of these adaptive methods are obtained on real-life files that possess a fair degree of non-stationarity. From these results, it can be seen that the proposed schemes compress nearly 10% more than their respective adaptive methods that use maximum-likelihood estimator-based estimates.
暂无评论