Letzte Stunde haben wir uns über verschiedene Grafikformate (BMP, TIFF, PCX, GIF, JPEG, PNG, PSD) erkundigt. Wir haben für jeder Format 5 Stichwörter aufgeschrieben, damit wir es uns besser merken konnten. Im Zuge dieser Stunden werde ich nun kurz die RLE- und LZW-Komprimierung näher erläutern.
RLE-Komprimierung
Run-length encoding oder Lauflängenkodierung.
RLE ist eine verlustfreie Komprimierung.
Anwendungen:
Dateiformate: Windows Bitmap, GEM Image, Targa oder PCX.
bei Microsoft Windows:
- Endung .RLE für komprimierte BMP-Bilder
- .BMP für unkomprimierte
Eignet sich bei langen Folgen des selben Wertes (bei Icons oder Clip-Art Bildern: weil mit wenigen Farben gezeichnet) wie z.B.:
B… Blauer Punkt
R… Roter Punkt
RRRRRRRRRRRRRRBBRRRRRRBBB
mit RLE komprimiert:
14R2B6R3B
Die Zahlen stehen für die Anzahl der Punkte/Pixel einer Farbe.
—
Liegt eine Wiederholung vor, wird die Anzahl der Wiederholungen sowie der wiederholte Wert gespeichert.
Marker-Bytes: Bytes, die nicht im Datenstrom vorkommen.
Offset: Mindestwiederholrate.
Beispiel:
Gibt es jetzt einen Offset von 3, dann wird ab einer Wiederholung von 3 mit RLE komprimiert.
Wert der Komprimierung = Anzahl der Wiederholungen – Offset
00 00 00 00 = AA 1 00
AA … Marker-Byte
–
Komprimierung nicht empfehlenswert bei z.B.:
789789
171819171819
weil Vergrößerung der Datenmenge!
Es gibt einige Möglichkeiten, ein Vergrößern der Daten zu verringern, ganz vermeiden lässt sich dieser Effekt jedoch nicht.
LZW-Komprimierung
Lempel-Ziv Welch-Algorithmus.
verlustfreies Komprimierungsverfahren, dass bei fast allen Grafikformaten (GIF, TIFF, JPEG) verwendet werden kann.
Algorithmus 1978 von Abraham Lempel und Jacob Ziv entwickelt und veröffentlicht.
LZW ist der bekannteste Vertreter der LZ-Familie
Funktionsweise:
Mit Hilfe von Wörterbüchern werden die häufigsten Zeichenketten gespeichert und nun nur mehr mit Abkürzungen angegeben. Der Decoder kann das Wörterbuch (das in die Datei eingeschrieben ist) ohne Probleme rekonstruieren. Die in das Wörterbuch eingetragenen Zeichen werden über einen 12 Bit langen Index angeben. => maximal 2 hoch 12 (=4096) Einträge sind möglich.
Weitere Einträge werden generiert, indem der gefundene Eintrag plus dem nächsten Zeichen gespeichert wird.
Aus der folgenden Tabelle kann man eine Zahlenfolge erkennen. Sie kann beim Entschlüsseln den gegebenen Text komplett wiederherstellen. Somit ist dieser Vorgang reversibel und der Klartext wird verlustfrei wiedergegeben.
eigenes Beispiel zur LZW-Komprimierung (angelehnt an das aus dem wiki):
| Zeichenkette | gefundener Eintrag | Ausgabe | neuer Eintrag |
|---|---|---|---|
| LZWKOKOPKOP5 | L | L | LZ <256> |
| ZWKOKOPKOP5 | Z | Z | ZW <257> |
| WKOKOPKOP5 | W | W | WK <258> |
| KOKOPKOP5 | K | K | KO <259> |
| OKOPKOP5 | O | O | OK <260> |
| KOPKOP5 | KO <259> | <259> | KOP <261> |
| PKOP5 | P | P | P <262> |
| KOP5 | KOP <261> | <261> | KOP5 <263> |
| 5 | 5 | 5 | - |
Natürlich gibt es dazu auch eine Dekomprission, aber das ist ein anderes Thema. Auf jeden Fall gilt dafür, dass die „Ausgabe“ von oben nach unten gelesen wieder die vorher codierte Zeichenkette “LZWKOKOPKOP5″ ergibt.
ENDE!
Gut gemacht!