Paper Info
Title
Optimal encoding of non-stationary sources
Abstract
The usual assumption for proofs of the optimality of lossless encoding is a stationary ergodic source. Dynamic sources with non-stationary probability distributions occur in many practical situations where the data source is formed from a composition of distinct sources, for example, a document with multiple authors, a multimedia document, or the composition of distinct packets sent over a communication channel. There is a vast literature of adaptive methods used to tailor the compression to dynamic sources. However, little is known about optimal or near optimal methods for lossless compression of strings generated by sources that are not stationary ergodic. Here, we do not assume the source is stationary. Instead, we assume that the source produces an infinite sequence of concatenated finite strings s1…sn, where:(i) Each finite string si is generated by a sampling of a (possibly distinct) stationary ergodic source Si, and(ii) the length of each of the si is lower bounded by a function L(n) such that L(n)/log(n) grows unboundedly with the length n of all the text within s1…si. Thus each input string is a sequence of substrings generated by possibly distinct and unknown stationary ergodic sources. The optimal expected length of a compressed coding of a finite prefix s1…sk is∑i=1kniHi,where ni is the length of si and Hi is the entropy of Si. We give a window-based LZ77-type method for compression that we prove gives an encoding with asymptotically optimal expected length. We give another LZ77-type method for compression where the expected time for encoding and decoding is nearly linear (approaching arbitrarily close to linear O(n) for large n). We also prove that this later method gives an encoding with asymptotically optimal expected length. In addition, give a dictionary-based LZ78-type method for compression, which takes linear time with small constant factors. This final algorithm also gives an encoding with asymptotically optimal expected length, assuming the Si are stationary ergodic sources that satisfy certain mixing conditions and L(n)⩾nε for some ε>0.
Year
DOI
Venue
2001
10.1016/S0020-0255(01)00103-7
Inf. Sci.
Keywords
Field
DocType
non-stationary source,optimal encoding,probability distribution,lossless compression,linear time,satisfiability,lower bound,communication channels
Discrete mathematics,Combinatorics,Sequence,Ergodic theory,Probability distribution,Concatenation,Time complexity,Asymptotically optimal algorithm,Mathematics,Bounded function,Lossless compression
Journal
Volume
Issue
ISSN
135
1-2
0020-0255
Citations 
PageRank 
References 
5
0.55
26
Authors
2
Name
Order
Citations
PageRank
John H. Reif14180810.75
James A. Storer2931156.06