Analysis of Lempel-Ziv'78 for Markov Sources

9 Lempel-Ziv’78 is one of the most popular data compression algorithms. Over the last few decades 10 fascinating properties of LZ’78 were uncovered. Among others, in 1995 we settled the Ziv conjecture 11 by proving that for a memoryless source the number of LZ’78 phrases satisfies the Central Limit 12 Theorem (CLT). Since then the quest commenced to extend it to Markov sources. However, despite 13 several attempts this problem is still open. The 1995 proof of the Ziv conjecture was based on two 14 models: In the DST-model, the associated digital search tree (DST) is built over m independent 15 strings. In the LZ-model a single string of length n is partitioned into variable length phrases such 16 that the next phrase is not seen in the past as a phrase. The Ziv conjecture for memoryless source 17 was settled by proving that both DST-model and the LZ-model are asymptotically equivalent. The 18 main result of this paper shows that this is not the case for the LZ78 algorithm over Markov sources. 19 In addition, we develop here a large deviation for the number of phrases in the LZ78 and give a 20 precise asymptotic expression for the redundancy which is the excess of LZ78 code over the entropy 21 of the source. We establish these findings using a combination of combinatorial and analytic tools. 22 In particular, to handle the strong dependency between Markov phrases, we introduce and precisely 23 analyze the so called tail symbol which is the first symbol of the next phrase in the LZ’78 parsing. 24

• Publication year

  2020

• Venue

  International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms

• Publication date

  Unknown publication date

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.4230/LIPIcs.AofA.2020.15
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Analytic Pattern Matching - From DNA to Twitter

  2015influential reference
• On the Limiting Distribution of Lempel-Ziv’78 Redundancy for Memoryless Sources

  2014influential reference
• Towards More Realistic Probabilistic Models for Data Structures: The External Path Length in Tries under the Markov Model

  2012cited by this paper
• Average redundancy of the Shannon code for Markov sources

  2012cited by this paper
• Analysis of the average depth in a suffix tree under a Markov model

  2005cited by this paper
• A general limit theorem for recursive algorithms and combinatorial structures

  2004cited by this paper
• Average Case Analysis of Algorithms on Sequences

  2001cited by this paper
• Average Profile of the Lempel-Ziv Parsing Scheme for a Markovian Source

  2001influential reference
• Analytical Depoissonization and its Applications

  1998cited by this paper
• Redundancy of the Lempel-Ziv incremental parsing rule

  1997cited by this paper
• On the amount of statistical side information required for lossy data compression

  1997cited by this paper
• On the average redundancy rate of the Lempel-Ziv code

  1997cited by this paper
• Asymptotic Behavior of the Lempel-Ziv Parsing Scheme and Digital Search Trees

  1995influential reference
• Average profile and limiting distribution for a phrase size in the Lempel-Ziv parsing algorithm

  1995cited by this paper
• Universal coding with minimum probability of codeword length overflow

  1991cited by this paper
• A diffusion limit for a class of randomly-growing binary trees

  1988cited by this paper
• Compression of individual sequences via variable-rate coding

  1978cited by this paper
• The art of computer programming: sorting and searching (volume 3)

  1973cited by this paper
• The Art of Computer Programming

  1968cited by this paper

• No citing papers are available for this paper.