LZW (thing)

The original LZ Algorithm was invented by Abraham Lempel Jacob Ziv and published in 1977. In 1984, Terry Welch published his refinements and this became the LZW compression algorithm.
Although Unisys holds the patent for the algorithm, many companies mistakenly thought it was public domain and used it anyway. This included CompuServe who used it in their GIFs. When it became public knowledge what was used for the GIF, Unisys tried to get money out of all the companies using LZW, because they had failed to protect their Intellectual Property rights from the start, it was judged that they couldn't get money for it.

---

The compression algorithm (in pseudo code) goes like this:

STRING = get input character
    WHILE there are still input characters DO
        CHARACTER = get input character
        IF STRING+CHARACTER is in the string table then
            STRING = STRING+character
        ELSE
            output the code for STRING
            add STRING+CHARACTER to the string table

            STRING = CHARACTER
        END of IF
    END of WHILE
    output the code for STRING

The decompression algorithm that came from this was floored in a single case and had to be modified to deal with this.
The LZW decompression algorithm:

Read OLD_CODE
output OLD_CODE
WHILE there are still input characters DO
    Read NEW_CODE
    IF NEW_CODE is not in the translation table THEN
        STRING = get translation of OLD_CODE
        STRING = STRING+CHARACTER
    ELSE
        STRING = get translation of NEW_CODE
    END of IF
    output STRING
    CHARACTER = first character in STRING
    add OLD_CODE + CHARACTER to the translation table
    OLD_CODE = NEW_CODE
END of WHILE

---

References:
http://kb.indiana.edu/data/aghf.html - Courtesy the Indiana University Knowledge Base for some of the history behind LZW
http://www.dogma.net/markn/articles/lzw/lzw.htm - Courtesy of Dr. Dobb's Journal for the datails ie. the algoritms.