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).

[Benny Riefenstahl]
----
There are some comments, that the GIF patent expires in June 2003 in the US, but there may be issues left in the EU and other places until June 2004 due to some obscure patent stuff.

----
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]