Redundancy of the Lempel-Ziv-Welch code Conference Paper uri icon


  • The Lempel-Ziv codes are universal variable-to-fixed length codes that have become virtually standard in practical lossless data compression. For any given source output string from a Markov or unifilar source, we upper bound the difference between the number of binary digits needed by the Lempel-Ziv-Welch code (LZW) to encode the string and the self-information of the string. We use this result to demonstrate that for unifilar, Markov sources, the redundancy of encoding the first n letters of the source output with LZW is O((ln n)-1), and we upper bound the exact form of convergence.

name of conference

  • Proceedings DCC '97. Data Compression Conference

published proceedings


author list (cited authors)

  • Savari, S. A.

citation count

  • 4

complete list of authors

  • Savari, SA

editor list (cited editors)

  • Storer, J. A., & Cohn, M.

publication date

  • January 1997