LZW (named after the inventors Lempel, Zif and Welch) is a compression algorithm used among other things in [GIF], [TIFF] (when used with the corresponding options) and Unix' [compress].

The algorithm is patented by the company UNISYS.  In the mid-nineties, when the Internet took off and GIF became popular with web browser support, UNISYS began enforcing their patent, see http://www.unisys.com/about__unisys/lzw/.

According to the interpretation of the LPF at http://lpf.ai.mit.edu/Patents/Gif/Gif.html the UNISYS patent will expire in June 2003 (IANAL, and sources on the 'net are not really reliable for legal advice either, so don't depend on this opinion).

----
[LV] According to [http://yro.slashdot.org/article.pl?sid=04/07/06/1717243&mode=thread&tid=136&tid=152&tid=155&tid=185&tid=187&tid=99], the Unisys patent expired July 7, 2004. 

''''HOWEVER''', LZW was a modification of a patented algorithm by Lempel and Zif, which according to this just referenced slashdot discussion, is still patented (???) by IBM.  So the state of LZW is still unknown.

----
According to Unisys' own page at http://www.unisys.com/about__unisys/lzw: Unisys U.S. LZW Patent No. 4,558,302 expired on June 20, 2003, the counterpart patents in the United Kingdom, France, Germany and Italy expired on June 18, 2004, the Japanese counterpart patents expired on June 20, 2004 and the counterpart Canadian patent expired on July 7, 2004. 

----
Here's a simple lwz compressor and decompressor.

    proc comp {data} {
      set cpre {}
      # set dict {a b c d e f g h i j k l m n o p q r s t u v w x y z { }}
      # set dict {}
      # for {set x 0} {$x < 256} {incr x} {lappend dict [binary format c $x]}
      for {set x 0} {$x < 256} {incr x} {set dict([binary format c $x]) $x}
      set pos 0
      set rval {}
      while {$pos < [string length $data]} {
        set ch [string index $data $pos]
        incr pos
        # set ci [lsearch -exact $dict $cpre$ch]
        set ci [info exists dict($cpre$ch)]
        if {$ci != 0} {
          # string in dictionary
          append cpre $ch
        } else {
          # lappend dict $cpre$ch
          set dict($cpre$ch) [array size dict]
          # lappend rval [lsearch -exact $dict $cpre]
          lappend rval $dict($cpre)
          set cpre $ch
        }
      }
      # lappend rval [lsearch -exact $dict $cpre]
      lappend rval $dict($cpre)
      puts "compressed from [string length $data] to [llength $rval]"
      return $rval
    }

    proc decomp {cdata} {
      set cpre {}
      set dict {}
      for {set x 0} {$x < 256} {incr x} {lappend dict [binary format c $x]}
      set pos 0
      set rval {}
      while {$pos < [llength $cdata]} {
        set co [lindex $cdata $pos]
        incr pos
        if {$co >= [llength $dict]} {
          lappend dict $cpre[string index $cpre 0]
          set cpre [lindex $dict $co]
        } else {
          append cpre [string index [lindex $dict $co] 0]
          # this only won't apply for the very first character
          if {[string length $cpre] > 1} {
            lappend dict $cpre
          }
          set cpre [lindex $dict $co]
        }
        append rval [lindex $dict $co]
      }
      puts "uncompressed from [llength $cdata] to [string length $rval]"
      return $rval
    }

JR

----
[PT] 13-Jun-2003: Is this code compatible with anything? compress(1), gzip(1) etc? Any references relevant to this code?

----
13-Jun-2003:  As it stands, this code is not terribly useful other than as an exercise because 
   * its not really compatable with anything other than itself
   * it returns a list of integers (the indices into the dictionary) rather than a binary compressed string
   * the dictionary grows without bound, rather than being adaptive
My original goal was to write some code that could translate a [GIF] into r/g/b values in pure tcl; that will still require parsing of the gif file format and binary variable word length reading.

This is a straightforward implementation of LZW following the pseudocode in http://www.cis.udel.edu/~amer/CISC651/lzw.and.gif.explained.html

JR
----
[Category Acronym] |
[Category Graphics]