Datenkompression/Verlustfrei
Verlustfrei
- Verlustfreie Kompression
Bei der verlustfreien Kompression können die Originaldaten exakt aus den komprimierten Daten wiederhergestellt werden
- Dabei geht keinerlei Information verloren
- Im Wesentlichen nutzen verlustfreie Kompressionsverfahren die Redundanz von Daten aus, man spricht auch von Redundanzreduktion
Die theoretische Grundlage bildet die Informationstheorie (verwandt mit der algorithmischen Informationstheorie)
- Sie gibt durch den Informationsgehalt eine minimale Anzahl an Bits vor, die zur Kodierung eines Symbols benötigt werden
- Verlustlose Kompressionsverfahren versuchen nun Nachrichten so zu kodieren, dass sie sich ihrer Entropie möglichst gut annähern
Text
Texte, sofern sie aus Buchstaben bestehen oder als Zeichenketten abgespeichert sind, und somit nicht als Bild (Rastergrafik, typischerweise eine Bilddatei nach dem Einscannen eines Buches), belegen vergleichsweise wenig Speicherplatz
- Dieser lässt sich durch ein Verfahren zur verlustfreien Kompression auf 20 % bis 10 % des ursprünglich von ihr benötigten Platzes reduzieren
Beispiele:
Ausgangstext: AUCH EIN KLEINER BEITRAG IST EIN BEITRAG Kodiertext: AUCH EIN KLEINER BEITRAG IST /2 /4
Hier wurde erkannt, dass die Wörter EIN und BEITRAG zweimal auftauchen, und dadurch angegeben, dass diese mit den gerade zurückliegenden übereinstimmen
- Bei genauerer Betrachtung könnte dann auch das in KLEINER enthaltene EIN entsprechend kodiert werden
Wörterbuchmethode
Verwandt ist die tokenbasierte Kompression
- Häufig wiederkehrende Schlüsselwörter werden durch Abkürzungen, Tokens, ersetzt
Ausgangstext: Print "Hallo"; Print "Hier" Kodiertext: 3F "Hallo"; 3F "Hier"
Für die Zuordnung der Tokens zu den eigentlichen Wörtern muss entweder ein externes Wörterbuch vorhanden sein, oder in der komprimierten Datei ersichtlich/mit enthalten sein
Run length encoding (RLE)
Bei der RLE, deutsch Lauflängenkodierung, werden identische Textbestandteile, die hintereinander stehen, nur einmal abgespeichert – mit der Anzahl ihrer Wiederholungen
- Hier wird " 10 Grad," drei Mal wiederholt:
Ausgangstext: In den letzten Tagen betrug die Temperatur 10 Grad, 10 Grad, 10 Grad, und dann 14 Grad Kodiertext: In den letzten Tagen betrug die Temperatur/3/ 10 Grad,/ und dann 14 Grad
Die Burrows-Wheeler-Transformation ist eine umkehrbare Operation, welche einen gegebenen Text so umformt, dass dieselben Buchstaben möglichst oft gleich hintereinander stehen
- So können die Daten dann mit RLE komprimiert werden
Entropiekodierung
Verfahren der so genannten Entropiekodierung:
- Huffman-Code (in modifizierter Form zum Beispiel für die Fax-Übertragung)
- Arithmetische Kodierung
Der bekannte Morse-Code funktioniert nach einem ähnlichen Prinzip und dient als gutes Beispiel: Häufige Buchstaben der englischen Sprache (z. B. E = .) werden als kurze Codes abgespeichert, seltene als lange Codes (z. B. Q = _ _ . _)
Als Beispiel ein Ausgangstext von 66 Zeichen Länge (Datenmenge 462 Bit bei 7 Bit pro Zeichen, siehe ASCII):
WENN HINTER FLIEGEN FLIEGEN FLIEGEN, FLIEGEN FLIEGEN FLIEGEN NACH
Eine sehr einfache, aber nicht sehr effiziente Entropiekodierung besteht darin, alle Teile einer Nachricht (siehe Tabelle; "_" steht für das Leerzeichen) nach ihrer Häufigkeit zu sortieren, und mittels binären Zahlen zu nummerieren:
| Textteil… | …wird ersetzt durch… |
|---|---|
| _FLIEGEN | 1 |
| WENN_ | 10 |
| _NACH. | 11 |
| HINTER | 100 |
| , | 101 |
Der mit diesem Wörterbuch komprimierte Text lautet
10 100 1 1 1 101 1 1 1 11
und benötigt in binärer Kodierung 50 Bit, denn das Ergebnis enthält drei verschiedene Zeichen (0, 1 und das Trennzeichen " "), also 2 Bit pro Zeichen
- Die Trennzeichen sind hier notwendig, da dieser Code nicht präfixfrei ist
- Der präfixfreie Huffman-Code, also folgendes Wörterbuch,
| Textteil… | …wird ersetzt durch… |
|---|---|
| _FLIEGEN | 1 |
| WENN_ | 011 |
| _NACH. | 010 |
| HINTER | 001 |
| , | 000 |
ist effizienter, denn es führt direkt zu einem binären Ergebnis von 18 Bit Länge:
011001111000111010
In beiden Fällen muss aber auch das Wörterbuch in der komprimierten Datei abgespeichert werden – sonst lässt sich der Ausgangstext nicht rekonstruieren
Programmdateien
Bei Programmdateien ist es kritisch, dass sie nach erfolgter Dekomprimierung wieder im ursprünglichen Zustand sind
- Andernfalls wäre eine fehlerfreie bzw. korrekte Ausführung unwahrscheinlich
- Komprimierte Programmdateien sind meist selbst wieder ausführbare Dateien
- Sie bestehen aus einer Routine, die den Programmcode wieder dekomprimiert und anschließend ausführt
- Dadurch ist die Kompression des Programms für den Benutzer vollkommen ‚transparent‘ (er bemerkt sie nicht)