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]

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