Data-Compression.org

data compression link collection

LZ78/LZW and derivatives

This topic encompasses the LZ78 algorithm and its descendant, LZW. LZ78 is one of two seminal compression algorithms developed in the late 1970s. LZW is best know as the core compennt of the GIF compression format.


About LZW Compression

A tutorial by Martin Zolnieryk on LZW, along with some pseudo code and links.

http://www.starsdev.com/developer/lzw.php

         

Posted in July 16th, 2004

LZW Compression

An article that describes itself as showing how to implement LZW compression in MFC.

http://codeproject.com/cpp/LZWCompression.asp

* * * * *

Posted in June 2nd, 2004

Compression of Individual Sequences via Variable-Rate Coding

by Ziv and Lempel. The seminal LZ78 paper which spawned LZW, GIF, and an entire academic industry.

Update 2004: Document is now packed in RAR format.

http://www.compression.ru/download/articles/lz/ziv_lempel_1978_variable-rate_pdf.rar

         

Posted in May 16th, 2004

Replacing a Dictionary with a Square Root

Tom Cagill creates GIF files without using LZW.

http://www.ddj.com/documents/s=1486/ddj0110o/

         

Posted in March 14th, 2004

GAO Research Modem Software

GAO Research sells modem software for quite a few different platforms, including a big batch of DSP parts. Naturally, this includes modules to perform both V.42bis and V.44 data compression.

http://www.gaoresearch.com/products/modemsoftware/modemsoftware.php

         

Posted in December 21st, 2003

Lempel-Ziv-Welch (LZW) Compression

A good description of LZW, along with some specific information about TIFF’s implemenation of this compression algorithm.

http://netghost.narod.ru/gff/graphics/book/ch09_04.htm

         

Posted in November 9th, 2003

Redundanz - Lempel-Ziv-Kodierung

A lecture in German on LZ coding.

http://www.stud.uni-karlsruhe.de/~un55/lz_ToC.html

* * *    

Posted in September 28th, 2003

License Information on GIF and Other LZW-based Technologies

A Unisys press release explaining their beliefs regarding licensing required to use GIF technology in your products. As of this posting (8/2003) the US patents appear to have expired, but there are European and Japanese patents will not expire until some time in 2004.

http://www.unisys.com/about__unisys/lzw/

* * * *  

Posted in August 24th, 2003

LZW Patent Expiration

Drew Scott Daniels was attempting to find out when
all the LZW patents all over the world were
going to expire. This is not as easy as you might think!
Drew was kind enough to forward links to the message
boards where the question was posted. To follow the thread,
go to the bottom of the page and click on the Next
by thread
link.

http://lists.debian.org/debian-legal/2003/debian-legal-200303/msg00526.html

         

Posted in April 26th, 2003

Contributions à la compression de données

Steven Pigeon’s Ph. D Thesis from the University of Montreal. Proposes a new set of universal codes, which he dubs taboo codes, as well as new optimization algorithms for (Start, Step, Stop) codes. Plus lossy variations on LZW.

http://www.iro.umontreal.ca/~pigeon/science/publications/phd.ps.zip

         

Posted in March 17th, 2003

Lempel-Ziv Welch - NIST Reference Page

The National Insitute of Standards and Techology reference page on LZW compression. Pointers to an explanation, implementation, and more information.

http://www.nist.gov/dads/HTML/lempelZivWelch.html

         

Posted in March 17th, 2003

David Scott’s Bijective LZW Compression Methods

David describes his work creating a bijective LZW compressor. (See this and other pages of David for details on what he means by bijective.) The page includes C++ source.

http://bijective.dogma.net/compreslzw1.htm

* * *    

Posted in December 27th, 2002

TCompress Component Set

File and database compression components for Delphi. Compress to/from file, memory, and blob. Uses RLE, LZH, and LZW. Shareware.

Version 7.0 was released in September of 2002.

http://www.spis.co.nz/compress.htm

* * * *  

Posted in September 15th, 2002

LZW Patent Expiration

This thread reveals the actual dates for the LZW patent expiration, including US, European, and Japanese patents.

http://groups.google.com/groups?&threadm=a5aa8dd0.0208271613.3cd18da6%40posting.google.com

* * * * *

Posted in September 15th, 2002

Xpdf

This is an open source PDF renderer, which includes code that decompresses LZW data embedded in the PDF file. It doesn’t actually do the LZW decompression itself - it converts the data to a format that can be handled by UNIX compress.

http://www.foolabs.com/xpdf/

* * *    

Posted in August 8th, 2002

The Multivalent Browser

This Java browswer knows how to render PDF files, which means it understands the elusive LZW compressed data format used by Adobe.

http://www.cs.berkeley.edu/~phelps/Multivalent/

* * *    

Posted in August 8th, 2002

Java PDF Libraries

A variety of libraries that can be used to read and write PDF format.

http://www.geocities.com/marcoschmidt.geo/java-document-libraries.html#pdf

* * * * *

Posted in August 8th, 2002

Lossless Compression Algorithms (Entropy Encoding)

An overview of the basics, including Shannon-Fano, Huffman, Arithmetic coding, and a section on LZW for good measure.

http://www.cs.cf.ac.uk/Dave/Multimedia/node207.html

* * *    

Posted in July 20th, 2002

LZW Examples

Notes from an Information Theory course at MIT.

http://www-mtl.mit.edu/Courses/6.095/notes/LZW-examples.html

         

Posted in June 4th, 2002

LZW and GIF explained

A guy named Steve Blackstock takes a shot at making this all clear to you. Gives some details on the LZW variation used in GIF files.

http://www.cis.udel.edu/%7Eamer/CISC651/lzw.and.gif.explained.html

         

Posted in June 4th, 2002

Dictionary Selection using Partial Matching

D. T. Hoang, P. M. Long and J. S. Vitter. “Dictionary Selection using Partial Matching,” Information Sciences, 119(1-2), 57-72, 1999. This paper describes an attempt to squeeze improved compression out of existing dictionary-based schemes by using multiple context-based dictionaries for encoding.

http://www.cs.duke.edu/~jsv/Papers/catalog/node73.html

         

Posted in April 8th, 2002

Video and Audio Compression

Class notes on lossless compression algorithms. Quick info on Huffman, Adaptive Huffman, and LZW.

http://www.cs.sfu.ca/CourseCentral/365/li/material/notes/Chap4/Chap4.1/Chap4.1.html

* * * *  

Posted in February 26th, 2002

Introduction On Text Compression Using Lempel, Ziv, Welch (LZW) method

Cheok Yan Cheng decided to write up a short tutorial on LZW compression. It is presented here, along with some source code.

http://www.geocities.com/yccheok/lzw/lzw.html

* * * *  

Posted in February 25th, 2002

Wikipedia Entry: LZW

The Wikipedia entry for LZW compression. Good overview with plenty of links.

http://en.wikipedia.org/wiki/LZW

         

Posted in January 27th, 2002

Bill Luoma’s Compression Links

Bill has some Java LZ78 code here, along with a few other links to compression info.

http://www2.hawaii.edu/~luoma/code.html

         

Posted in January 8th, 2002

Standard ECMA-151 Data Compression for Information Interchange - Adaptive Coding with Embedded Dictionary - DLCZ Algorithm

An LZW variant that has been adopted as a standard by the ECMA.

http://www.ecma.ch/ecma1/STAND/ECMA-151.HTM

         

Posted in December 5th, 2001

LZW Definition

A short (and incorrect) definiton of the acronym LZW from Computer Knowledge.

http://www.cknow.com/ckinfo/acronyms/lzw.htm

         

Posted in October 23rd, 2000

LZW compression

A page with a brief description of LZW compression by Dominik Szopa. This page includes a Java applet that helps show how LZW looks in action.

http://www.cs.sfu.ca/CC/365/li/squeeze/LZW.html

         

Posted in November 22nd, 1999

LZ78 compression

The definition of LZ78 from the Free On-line Dictionary of Computing.

http://burks.bton.ac.uk/burks/foldoc/0/68.htm

* * * ½  

Posted in November 19th, 1999

Lempel-Ziv Welch compression

The definition of LZW from the Free On-line Dictionary of Computing.

http://burks.bton.ac.uk/burks/foldoc/59/64.htm

* * *    

Posted in November 19th, 1999