Lempel-Ziv-Welch-Algorithmus
Der LZW oder auch Lempel-Ziv-Welch-Algorithmus, ist ein häufig bei Grafikformaten zur Datenkompression, also zur Reduzierung der Datenmenge, eingesetzter Algorithmus. Ein Großteil der Funktionweise dieses Algorithmus wurde 1978 von Lempel und Ziv entwickelt und veröffentlicht (LZ78). Einige Detailverbesserungen wurden 1984 von Welch gemacht.
Funktionsweise
LZW ist ein verlustfreies Komprimierungsverfahren. Es wird z.B. in den Bildformaten GIF, TIFF und JPEG eingesetzt.
Patente
Für LZW und ähnliche Algorithmen wurden verschiedene Patente in den USA und anderen Ländern ausgestellt. LZ78 wurde durch das am 10. August 1981 eingereichte US-Patent 4.464.650 der Sperry Corporation (später zu Unisys fusioniert) abgedeckt, in dem Lempel, Ziv, Cohn und Eastman als Erfinder eingetragen sind. Dieses Patent ist inzwischen wahrscheinlich ausgelaufen.
Zwei US-Patente wurden für den LZW-Algorithmus ausgestellt: Nr. 4.814.746 von Victor S. Miller and Mark N. Wegman für IBM, eingereicht am 1. Juni 1983, sowie Nr. 4.558.302 von Welch für die Sperry Corporation, später Unisys Corporation, eingereicht am 20. Juni 1983.
Das US-Patent 4.558.302 verursachte die größte Kontroverse. Unisys erlaubte ursprünglich Entwicklern von freier Software und Freeware die tantiemenfreie Nutzung des LZW-Algorithmus, beendete diese Lizenzpolitik jedoch im August 1999. Viele Rechtsexperten kamen zum Schluss, dass das Patent solche Geräte nicht abdeckt, die LZW-Daten zwar dekomprimieren, aber nicht komprimieren können. Aus diesem Grund kann das weit verbreitete Programm Gzip Dateiarchive im Z-Format zwar lesen, aber nicht schreiben.
In den Debian Weekly News wurde in Bezug auf einen Newsgroup-Beitrag berichtet, dass das Unisys-Patent in den USA am 20. Dezember 2002 auslaufen werde - 17 Jahre und 10 Tage, nachdem es ausgestellt wurde. Die meisten anderen Quellen nennen den 20. Juni 2003 (20 Jahre nach Einreichung) als Ablaufzeitpunkt.