International Telemetering Conference Proceedings / October 26-29, 1992 / Town and Country Hotel and Convention Center, San Diego, California / Lempel-Ziv-Welch (LZW) algorithm is a popular data compaction technique that has been
adopted by CCITT in its V.42bis recommendation and is often implemented in association
with the V.32 standard for 9600 bps modems. It has also been implemented as Microcom
Networking Protocol (MNP) Level 7, where it goes by the name of Enhanced Data
Compression. LZW compacts data by encoding frequently occurring input strings with a
single output symbol. The algorithm automatically generates a string dictionary for each
symbol at each end of the transmission path. The amount of compaction that can be
derived with the LZW algorithm varies with the type of data being transmitted and the
efficiency by which table entries can be indexed. Table indexing is usually implemented by
use of a hashing table. Although some manufacturers advertise a 4-to-1 gain in throughput,
this seems to be an extreme case. This paper documents a implementation of the exact
ZLW algorithm. The results presented in this paper are significantly less, typically on the
order of 1-to-2 for ASCII text, with substantially less compaction for pre-compacted files
or files containing random bit patterns.
The efficiency of the LZW algorith on ASCII text is shown to be a function of dictionary
size and block size. Although fewer transmitted symbols are required for larger dictionary
tables, the additional bits required for the symbol index is marginally greater than the
efficiency that is gained. The net effect is that dictionary sizes beyond 2K in size are
increasingly less efficient for input data block sizes of 10K or more. The author concludes
that the algorithm could be implemented as a direct table look-up rather than through a
hashing algorithm. This would allow the LZW to be implemented with very simple
firmware and with a maximum of hardware efficiency.
| Identifer | oai:union.ndltd.org:arizona.edu/oai:arizona.openrepository.com:10150/608924 |
| Date | 10 1900 |
| Creators | Jacobsen, H. D. |
| Publisher | International Foundation for Telemetering |
| Source Sets | University of Arizona |
| Language | en_US |
| Detected Language | English |
| Type | text, Proceedings |
| Rights | Copyright © International Foundation for Telemetering |
| Relation | http://www.telemetry.org/ |
Page generated in 0.002 seconds