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