PNG: Universelle Bilder fürs Web

Auf den Spuren von LZ77

Als wettbewerbsfähiger Konkurrent gegenüber dem GIF-Format sollte PNG über einen verlust- und vor allem lizenzfreien Kompressionsalgorithmus verfügen. Diesen fand man mit dem 1977 von Lempel und Ziv vorgestellten LZ77-Algorithmus, der auf Basis der Erkennung von periodischen Sequenzen arbeitet.

Für die Kompression beim GIF-Format sorgt eine vereinfachte Variante von LZ77: der von der Firma Unisys als Patent angemeldete LZW-Algorithmus. Dieser erkennt horizontale Folgen gleichfarbiger Pixel und ersetzt sie durch einen Tabelleneintrag, der Farbe und Sequenzlänge angibt. So reicht für die Wiedergabe der Zeilen vier bis sechs des folgenden Bildes der Verweis "wie Zeile drei".

Kompression bei GIF funktioniert umso effektiver, je häufiger in einer Grafik gleiche Zeilen oder Zeilenabschnitte vorkommen. Umgekehrt gilt: Je unterschiedlicher die Zeilenmuster sind, um so größer fällt die Datei aus. So vergrößert eine zusätzliche Farbe pro Zeile eine Datei nicht so stark wie schräge Linien. Denn im letzteren Fall werden die Farbblöcke durch Zwischenfarben unterbrochen, die eine effektive Kompression verhindern.