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 that Unisys page the patents have by now expired: "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."
LV According to [L1 ] (Slashdot), 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.
FPX IIRC, the slashdot article said that the IBM patent covers the same algorithm. Thus, while the LZW algorithm remains "patented," the IBM patent could be invalidated if challenged. As long as IBM does not try to enforce the patent, that is unlikely to happen, given the time and effort involved. The possibility for IBM to bully users of the LZW algorithm exists, but is largely theoretical. Until then, the IBM patent remains as a symbol of an inefficient system that only loosely checks for prior art. (While most patent offices claim that they do, it seems that the Australians are at least being honest about having given up: patents are rubber-stamped, and prior art search is delegated to challengers in court, so that patents remain until invalidated, see [L2 ].)
Here's a simple lzw 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)]#SEH Which would be faster, the above or: set ci string equal [array names -exact dict $cpre$ch $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
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
