Dube and Beaudoin have proposed a technique of lossless data compression called compression via substring enumeration (CSE) for a binary source alphabet. Dube and Yokoo proved that CSE has a linear complexity both in time and in space worst-case performance for the length of string to be encoded. Dubé and Yokoo have specified appropriate predictors of the uniform and combinatorial prediction models for CSE, and proved that CSE has the asymptotic optimality for stationary binary ergodic sources. Our previous study evaluated the worst-case maximum redundancy of the modified CSE for an arbitrary binary string from the class of k-th order Markov sources. We propose a generalization of CSE for k-th order Markov sources with a finite alphabet X based on Ota and Morita in this study.

We consider a situation where n-tuples generated from a general source are encoded by a fixed-length code and discuss coding theorems on the worst-case redundancy, where the worst-case redundancy is defined as the maximum of the difference between the rate and the ideal codeword length per symbol with respect to all the correctly decodable n-tuples. We treat the four cases where the decoding error probability εnis required to satisfy (a) limn→∞εn= 0, (b) lim infn→∞εn= 0, (c) lim supn→∞εn≤ ε, and (d) lim infn→∞εn≤ ε, respectively, where ε ∈ [0; 1) is an arbitrary constant. We give general formulas of the optimum worst-case redundancy that are closely related to the width of the entropy-spectrum of a source.

This paper is concerned with the redundancy rate of fixed length source code for a general source with a countably infinite alphabet. We evaluate the minimum achievable redundancy rate R of fixed-to-fixed length (FF) and variable-to-fixed length (VF) codes with two definitions of redundancy rates, which are (i) the difference between the coding rate and the spectral sup-entropy rate and (ii) the difference between the coding rate and the self information rate. First we show that, when we restrict the fixed-length code class within the class of FF codes, R with definition (i) is zero, but R with definition (ii) can be positive. Next we show that, by taking the VF codes into account, R with definition (ii) can be decreased to zero.

This paper investigates the minimum achievable redundancy rate of fixed-to-fixed length lossless source codes (FF codes) for general sources. This paper defines the redundancy rate of the FF code by the difference between the coding rate and the self information rate. We prove that the minimum achievable redundancy rate is equal to the limit superior in probability of the width of the information spectrum, which is defined in this paper. This paper also considers the ε-source coding. We show two criteria for bounding the error probability. The first one bounds the sum of the decoding error probability and the redundancy-overflow probability, and the other one bounds these two probabilities separately. We also give the minimum achievable redundancy rate of these two types of ε-source coding.

In the previous work in Proc. ISIT2003 and Proc. ISITA2004, we have investigated some relationships between sufficient statistic and weakly universal lossless source coding, and proposed asymptotically sufficient statistic method to evaluate the pointwise redundancy of source codes. This method is an attempt to understand the universality of general lossless source codes from a simple and unified viewpoint. In this paper, we present a new theorem which enables our method to show the pointwise strong universality of lossless source codes. As an example of the theorem, we prove the pointwise strong universality of the original Lynch-Davisson code and conditional Lynch-Davisson code for the class of stationary memoryless and Markov sources, respectively. Moreover, it is shown that this method can be applied to the class of finite state sources. We prove that a blockwise Lynch-Davisson code is pointwise strongly universal for this class. From the viewpoint of our method, all of these algorithms can be seen as examples of a two-step source code using a kind of asymptotically sufficient statistic. The result of this paper gives a unified viewpoint for the universality of context-based algorithms and block-based algorithms, which are typical two types of universal lossless source coding algorithms

The Move-to-front (MTF) scheme is a data-compression method which converts each symbol of a source sequence to a positive integer sequentially, and encodes it to a binary codeword. The compression performance of this algorithm has been analyzed usually under the assumption of the so-called symbol extension. But, in this paper, upper and lower bounds are derived for the redundancy of the MTF scheme without the symbol extension for stationary ergodic sources and Markov sources. It is also proved that for the stationary ergodic first-order Markov sources, the MTF scheme can attain the entropy rate if and only if the transition matrix of the source is a kind of doubly stochastic matrix. Moreover, if the source is a Kth-order Markov source (K/spl ges/2), the MTF scheme cannot attain the entropy rate of the source generally.