Wie funktioniert Komprimierung?

Es grenzt an Zauberei, was Komprimierungsprogramme tun: Packt man beliebige Computerdaten in eine Art «Containerdatei» und zieht den Reissverschluss zu (dies bedeutet das englische Wort «to zip», das die WinZIP-Macher als Name für ihr Produkt ausgeliehen haben), dann verkleinert sich der Platzbedarf auf wundersame Weise: Ein Worddokument, vorher mehrere Megabyte gross, benötigt noch ein paar Tausend Bytes.

Komprimierungsprogramme arbeiten nicht mit Zauberei, sondern mit einem Verfahren, das auf die Forscher Jakob Ziv und Abraham Lempel zurückgeht: Sie wiesen 1977 und 1978 nach, dass sich Computerdaten verdichten lassen, wenn eine sich im Datenstrom wiederholende Zeichenkette durch ein Symbol ersetzt wird, das auf ein früheres Auftreten verweist: Der Ziv-Lempel-Algorithmus entfernt Wiederholungen. Beim umgekehrten Vorgang kann jede Datei originalgetreu rekonstruiert werden.

Textdateien bieten ein grosses Potenzial für Reduktion von Redundanz (Wiederholungen). Einerseits ist geschriebene Sprache sehr redundant, andererseits speichern Programme wie Winword Daten nicht Platz sparend, sondern mit «viel Luft dazwischen». Schlecht lassen sich Dateiformate komprimieren, die auf effiziente Informationsspeicherung ausgelegt sind: So kann WinZIP ein JPEG-Bild kaum verkleinern. (schü.)