lempel-ziv welch compression

Computing Dictionary

Lempel-Ziv Welch compression definition


(LZW) The algorithm used by the Unix compress command to reduce the size of files, e.g. for archival or transmission. LZW was designed by Terry Welch in 1984 for implementation in hardware for high-performance disk controllers. It is a variant of LZ78, one of the two Lempel-Ziv compression schemes.
The LZW algorithm relies on reoccurrence of byte sequences (strings) in its input. It maintains a table mapping input strings to their associated output codes. The table initially contains mappings for all possible strings of length one. Input is taken one byte at a time to find the longest initial string present in the table. The code for that string is output and then the string is extended with one more input byte, b. A new entry is added to the table mapping the extended string to the next unused code (obtained by incrementing a counter). The process repeats, starting from byte b. The number of bits in an output code, and hence the maximum number of entries in the table is usually fixed and once this limit is reached, no more entries are added.
LZW compression and decompression are licensed under Unisys Corporation's 1984 U.S. Patent 4,558,302 and equivalent foreign patents. This kind of patent isn't legal in most coutries of the world (including the UK) except the USA. Patents in the UK can't describe algorithms or mathematical methods.
[A Technique for High Performance Data Compression, Terry A. Welch, IEEE Computer, 17(6), June 1984, pp. 8-19]
[J. Ziv and A. Lempel, "A Universal Algorithm for Sequential Data Compression," IEEE Transactions on Information Theory, Vol. IT-23, No. 3, May 1977, pp. 337-343].
The Free On-line Dictionary of Computing, © Denis Howe 2010 http://foldoc.org
Cite This Source
Explore Dictionary.com
Previous Definition: lempel-ziv compression
Next Definition: lemper
More from Thesaurus.com
Synonyms and Antonyms for lempel-ziv welch compression
More from Reference.com
Search for articles containing lempel-ziv welch compression
Dictionary.com Word FAQs

Dictionary.com presents 366 FAQs, incorporating some of the frequently asked questions from the past with newer queries.

Copyright © 2014 Dictionary.com, LLC. All rights reserved.
  • Please Login or Sign Up to use the Recent Searches feature