Redundancy of the Lempel-Ziv-Welch code Conference Paper

abstract

• 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

authors

• Savari, Serap

published proceedings

• DCC '97 : DATA COMPRESSION CONFERENCE, 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

publisher

• Institute of Electrical and Electronics Engineers (IEEE)  Publisher

published in

• Data Compression Conference Proceedings  Journal

keywords

• 40 Engineering
• 4006 Communications Engineering
• 46 Information And Computing Sciences

Digital Object Identifier (DOI)

• 10.1109/DCC.1997.582011

International Standard Book Number (ISBN) 10

• 0-8186-7761-9

start page

• 191

end page

• 200

URL

• http://dx.doi.org/10.1109/dcc.1997.582011