Bounds on expansion in LZ'77-like coding

We investigate the maximum increase in number of phrases that results from changing k consecutive symbols in a string x having length n parsed using an LZ'77-like algorithm. We consider a class of compression algorithms that partition a sequence into a collection y of nonoverlapping, variable-length phrases and encode them. Each phrase either is a singleton or matches a substring that starts to its left. We show that changing a single symbol of x in position i can yield an expansion that is of order O(n-i)/sup 2/3/ as (n-i)/spl rarr//spl infin/. Our lower bound requires an alphabet size of O(n-i)/sup 1/3/. We also show that changing k consecutive symbols starting from position i can yield an expansion having a similar but somewhat more involved form. The paper contains both analytically derived upper and lower bounds, and algorithms for numerically computing tighter bounds. While deriving the bounds, we provide a detailed analysis of how expansion can arise when changing consecutive symbols. This problem is motivated by management policies for computer systems, such as the IBM Memory eXpansion Technology (MXT) or the IBM iSeries compressed disks, that use LZ'77-like coding on small compression units, such as 1-4 kbyte, and store the compressed data in memory or on disk tracks. Here, when a change of a portion of the compression unit occurs, for example, an L2 cache line, or a 512-byte disk sector, the data is recompressed and potentially stored in a different location. Knowing the maximum expansion, rather than the average expansion, is an important factor for designing policies for allocation and management of memory or disk space.     

On Certain Pathwise Properties of the Sliding-Window Lempel–Ziv Algorithm

We derive several almost-sure results related to the sliding-window Lempel-Ziv (SWLZ) algorithm. A principal result is a path-wise lower bound to the redundancy equal to 1/2hlog₂log ₂n_w/log₂n_w in the main term, where n_w is the sliding window size. This bound is off by a factor of two from the main term in the lower bound of A. J. Wyner and the work of Yang and Kieffer, which hold in the expected sense for the fixed-database Lempel-Ziv algorithm (FDLZ). Another aspect of the present work studies the asymptotic behavior of the ratio of the number of phrases to the length of the parsed string for any finite sliding window size; in here we exploit the theory of asymptotic mean stationary processes of Gray and Kieffer and some results of Kieffer and Rahe. In all cases it is assumed that the source is stationary and that in the most restrictive case it is an irreducible and aperiodic Markov chain; some of the results hold for sources that have exponential rates for entropy and more generally for the ergodic setting     

On Successive Refinement of the Binary Symmetric Markov Source

We show that for every n>2 the standard nth-order approximation R_n(D), to the rate-distortion function of the binary-symmetric Markov source (BSMS) is not successively refineable under the Hamming distortion measure in an open interval of the form D _nmax