Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: LZ77
5 Verlustfreie_Verfahren Datenkompression: Verlustfreie Verfahren: Wörterbuchbasierte Verfahren: TOC
LZ77 - Lempel, Ziv 1977
Abraham Lempel und Jacob Ziv stellten 1977 ein einfaches und effizientes Verfahren zur Kompression von mehr oder minder beliebigen Inhalten vor. Das Verfahren wurde in einer Arbeit vorgestellt, die unter diesen beiden Titeln bekannt ist; mal mit, mal ohne das Wort 'sequential': "A Universal Algorithm for [sequential] Data Compression". Die Neuerung des Verfahrens besteht darin, dass nicht mehr einzelne Zeichen mit ihren Auftretenswahrscheinlichkeiten Entropie-codiert, sondern gezielt die Wiederholungen von Zeichenketten ausgenutzt werden.
Der Grundgedanke des Verfahrens besteht darin, einen zuvor gesehenen Datenstrom als Wörterbuch zu verwenden. Dieses verwendete Wörterbuch ist in seiner Größe begrenzt. Damit immer ein aktuelles Wörterbuch vorhanden ist, wird dieses durch einen einfachen Verschiebemechanismus realisiert, weshalb dieses Verfahren oft als "Sliding Window" bezeichnet wird. Das gleitende Fenster besteht aus zwei Teilen, einem Such-Puffer (search buffer) und einem Vorschau-Puffer der die nächsten zu codierenden Zeichen enthält (look-ahead buffer). Üblicherweise enthält der Such-Puffer mehrere tausend Zeichen und der Vorschau-Puffer für die zu codierenden Daten in etwa 100 Zeichen oder auch weniger.
Als Demonstrationsbeispiel für die LZ77 Kompression dient der folgende Zungenbrecher: "In Ulm, um Ulm, und um Ulm herum.".
| 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| leer | I | n | U | l | m | , | u | m | |||||||||||||
| Suchpuffer | Vorschaupuffer | ||||||||||||||||||||
Vorlage:Clear Wie man später erkennen kann, besitzt diese Form der Codierung einige exzellente Eigenschaften. Das LZ77-Verfahren ist besonders gut geeignet, um Wiederholungscodes zu erkennen und zu komprimieren.
Codierung
Die Codierung nach dem LZ77-Verfahren erfolgt nach dem folgenden Algorithmus.
Datenkompression: Vorlage: Algorithmus
while( !end_of_data )
{
best.index = 0;
best.length = 0;
/*
* Den Suchpuffer nach der längsten Übereinstimmung durchforsten.
*/
for(i=1 ; i<length_of(searchpuffer) ; i++)
{
}
/*
* Ausgabe des besten Treffers
*/
if( (best.index !=0) && (best.length>=2 ) )
{
output_tripel( best.index, best.length, search_buffer[best.length] );
}
else
{
output_tripel( 0,0, search_buffer[0] );
}
}
// Quelle:ThePacker
Beispiel
| 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | Ausgabe | |
| (leer) | I | n | _ | U | l | m | , | _ | u | m | (0,0,"I") | ||||||||||||
| (leer) | I | n | _ | U | l | m | , | _ | u | m | _ | (0,0,"n") | |||||||||||
| (leer) | I | n | _ | U | l | m | , | _ | u | m | _ | U | (0,0,"_") | ||||||||||
| (leer) | I | n | _ | U | l | m | , | _ | u | m | _ | U | l | (0,0,"U") | |||||||||
| (leer) | I | n | _ | U | l | m | , | _ | u | m | _ | U | l | m | (0,0,"l") | ||||||||
| (leer) | I | n | _ | U | l | m | , | _ | u | m | _ | U | l | m | , | (0,0,"m") | |||||||
| (leer) | I | n | _ | U | l | m | , | _ | u | m | _ | U | l | m | , | _ | (0,0,",") | ||||||
| (leer) | I | n | _ | U | l | m | , | _ | u | m | _ | U | l | m | , | _ | u | (5,1,"u") | |||||
| (leer) | I | n | _ | U | l | m | , | _ | u | m | _ | U | l | m | , | _ | u | n | d | (4,1,"_") | |||
| I | n | _ | U | l | m | , | _ | u | m | _ | U | l | m | , | _ | u | n | d | _ | u | (8,6,"n") | ||
| , | _ | u | m | _ | U | l | m | , | _ | u | n | d | _ | u | m | _ | U | l | m | _ | h | (0,0,"d") | |
| _ | u | m | _ | U | l | m | , | _ | u | n | d | _ | u | m | _ | U | l | m | _ | h | e | (12,7,"_") | |
| _ | u | n | d | _ | u | m | _ | U | l | m | _ | h | e | r | u | m | . | (leer) | (0,0,"h") | ||||
| u | n | d | _ | u | m | _ | U | l | m | _ | h | e | r | u | m | . | (leer) | (0,0,"e") | |||||
| n | d | _ | u | m | _ | U | l | m | _ | h | e | r | u | m | . | (leer) | (0,0,"r") | ||||||
| d | _ | u | m | _ | U | l | m | _ | h | e | r | u | m | . | (leer) | (10,2,".") | |||||||
| fertig | |||||||||||||||||||||||
Erläuterungen zum Beispiel 1
Das Beispiel links wird zeilenweise von oben nach unten gelesen. Jede Zeile zeigt einen Codierschritt. In der Spalte Ausgabe befindet sich das Dreier-Tupel, das in diesem Schritt durch den Codierer ausgegeben wird. Das rote Feld stellt das erste zu codierende Zeichen aus dem Vorschaupuffer dar. Der Vorschaupuffer wird zu Beginn mit den ersten Buchstaben des zu codierenden Strings aufgefüllt. Da der Suchpuffer zunächst noch leer ist, ist es unmöglich, eine Übereinstimmung zu finden. Deshalb wird das Zeichen I direkt in die Ausgabe geschrieben, zusammen mit der Information, dass kein Treffer gefunden werden konnte (Offset 0 und Trefferlänge 0). Genauso verhält es sich mit den folgenden neun Zeichen "n", "_", "U", "l", "m" und ",".
- muss überarbeitet werden
Der Buchstabe "m" ist bereits im Suchpuffer auf der linken Seite enthalten, dennoch stimmen die auf das "m" im Suchpuffer folgenden Symbole nicht mit dem überein, das im Vorschaupuffer auf den Buchstaben "m" folgt. Aus diesem Grund wurden die Zeichen einzeln codiert.
Das folgende Symbol "_" (Leerzeichen) stellt jedoch einen Treffer dar (im Beispiel grün markiert), der mit dem Inhalt des Vorschaupuffers zu einer bestimmten Länge übereinstimmt. Anschließend folgt ein nicht übereinstimmendes Symbol ein "n" im Vorschaupuffer und ein "m" im Suchpuffer. Das "n" wird als Symbol ausgegeben, zusammen mit der Information, an welcher Stelle der gefundene Treffer zu finden ist (Offset 8) mit der Trefferlänge (7). Diese drei Informationen werden codiert ausgegeben. Wie diese Codierung im einzelnen erfolgt soll im Anschluss an dieses Beispiel erläutert werden.
- bis hier
- Codierung des Ausgabestroms
| Länge | Offset | Folgezeichen | |||||||||||||||||||||
| 4 | 3 | 2 | 1 | 12 | 11 | 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
| Byte 1 (8 Bit) | Byte 2 (8 Bit) | Byte 3 (8 Bit) | |||||||||||||||||||||
Für die Codierung der Trefferlänge wurde ein 4 Bit langer Wert reserviert. Damit sind alle Längenangaben zwischen 0 und 15 exakt codierbar. Längere Treffer wurden durch Aneinanderreihung mehrerer Treffer erreicht. Wie Sie sehen, werden Treffer und Nicht-Treffer gleichartig codiert. Sie sind nach der Codierung immer 24 Bits lang. Bei dieser Darstellung jedoch ergibt sich ein riesiges Sparpotential, welches in vielen später entwickelten Varianten ausgenutzt wurde. Für die Offsets wurden 12 Bits zur Verfügung gestellt, womit alle Werte zwischen 0 und 4095 darstellbar sind. Die beiden Werte für Länge und Offset können in einem Block aus 16 Bits zusammengefasst werden, das entspricht 2 Bytes. Das Folgezeichen wurde stets separat dazu ausgegeben und bildete so das dritte Byte. Pro Treffer oder Nicht-Treffer werden exakt 3 Bytes Daten ausgeben. Da der Offset 12 Bit lang ist, kann maximal ein 4 Kilobyte (minus ein Byte) langer Puffer adressiert werden.
- Effizienz des Ausgabestroms
- (0,0,"X")
Lassen Sie uns nun die möglichen Codier-Fälle des LZ77-Algorithmus näher beleuchten. Zum einen kann es passieren, dass ein Zeichen noch nicht Teil des Suchpuffers ist (0,0,"X"), dann wird ein 24 Bit langer Wert ausgegeben, um ein 8 Bit langes Zeichen zu codieren. Dieser Fall ist bezüglich der Codiereffizienz nicht optimal (= Codierverlust). Es werden 3 mal so viele Bits benötigt wie für die ursprünglich Nachricht.
- (Offset,1,"X")
Nehmen wir an, das zu codierende Zeichen befindet sich bereits im Suchpuffer, aber das nachfolgende Zeichen ist noch nicht Teil des Suchpuffers oder es folgt nicht auf das zu codierende Zeichen. Es tritt also der Fall (Offset,1,"X") auf, so können zwei Zeichen codiert werden. Das erste Zeichen wird durch die Offset und Längenangabe codiert. Das Folgezeichen steht an der Stelle des Literals. Es können also 2*8 Bit (16 Bit) mit einem 24 Bit Wert dargestellt werden. Auch dieser Fall ist bezüglich der Codiereffizienz nicht hilfreich, da für jedes zu codierende statt 8 Bit im Mittel 12 Bit benötigt werden. Dieser Fall ist bereits besser (1,5 fach) als gar nicht vorhandene Zeichen (3 fach), dennoch führen sie nicht zu einem Codiergewinn (=Codierverlust). Es werden mehr Informationen zur Darstellung benötigt, als es zu codieren gilt.
- (Offset,2,"X")
Neutral bezüglich der Codiereffizienz gegenüber sind Treffer der Länge 2. Es werden 24 Bit ausgegeben, wenn 3*8 Bit codiert werden sollen. (Offset,2,"X") Bis zu dieser Treffer-Länge sind mit der LZ77-Codierung keinerlei Codiergewinne erzielbar. Die Hoffnung bei der Codierung ist, dass die Codierverluste durch die Codiergewinne der längeren Übereinstimmungen wettgemacht werden können. Weder Codiergewinn noch Codierverlust.
- (Offset,3..15,"X")
Jede Codierung der Form (Offset,3..15,"X") stellt einen Codiergewinn dar, da hiermit Zeichenketten der Länge 4 bis 16 mit durch ein 24 Bit langen Wert dargestellt werden können. Alle diese Zeichenketten sind durch eine Zeichenkette der Länge 3 codierbar.
Wenn die Codiergewinne die Codierverluste kompensieren können, ist die Gesamtausgabe des codierten Datenstroms kürzer als die Eingabe und stellt eine Kompression des Datenstroms dar.
Beispiel
| 5 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | Ausgabe | |
| (leer) | a | a | a | a | b | (0,0,a) | ||||||
| (leer) | a | a | a | a | b | (1,3,b) | ||||||
Das zweite Beispiel zeigt einen ganz speziellen Sonderfall bei der Codierung nach dem LZ77-Verfahren. In diesem Fall ist sowohl der Vorschaupuffer als auch der Suchpuffer Teil des Treffers. Das erfordert für den Fall "Offset < Länge" lediglich eine modifizierte Entpackoperation, die in diesem Fall Symbol-weise entpacken muss. Beachtet man dies nicht, so kann es zu Fehlern im decodierten Datenstrom kommen. Wie man links sehen kann, sind mit diesem Algorithmus identische aufeinanderfolgende Zeichen codierbar. Dieses Verfahren ist auch als Lauflängen-Codierung/Kompression (RLE - Run Length Encoding) bekannt.
Beispiel
| 10 | 9 | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | Ausgabe | |
| (leer) | a | b | c | a | b | c | a | b | c | a | d | (0,0,a) | ||||||||||
| (leer) | a | b | c | a | b | c | a | b | c | a | d | (0,0,b) | ||||||||||
| (leer) | a | b | c | a | b | c | a | b | c | a | d | (0,0,c) | ||||||||||
| (leer) | a | b | c | a | b | c | a | b | c | a | d | (3,7,d) | ||||||||||
| b | c | a | b | c | a | b | c | a | d | (leer) | fertig | |||||||||||
Das Beispiel 3 zeigt eine Modifikation des Beispiels 2, bei dem nicht nur ein einfacher RLE-Code präsentiert wird, sondern zeigt einen Wiederholungscode, wobei sich dieser rein programmiertechnisch vom RLE-Modus nicht unterscheidet. Es sollte lediglich eine weitere Ausprägung gezeigt werden, mit der es möglich ist, sich wiederholende Zeichenkombinationen zu packen. Dieses Beispiel soll an der Zeichenkette "abcabcabcad" demonstriert werden. Es wurden 4 Tripel (12 Byte) für 11 Zeichen ausgegeben. Man kann in diesem Fall nicht von einer effizienten Codierung sprechen.
Der gesamte Codiervorgang besteht im Grunde genommen aus zwei Teilen, aus der Codierung und aus einer Anpassung an den zu codierenden Datenstrom. Je weniger Anpassung es gibt, desto schlechter ist die Codiereffizienz. Am Anfang des Codierprozesses ist keine Anpassung an die zu codierenden Daten vorhanden. Diese wird sukzessive vorgenommen. Mit weiterem Fortschritt der Codierung steigt die Wahrscheinlichkeit, einen Treffer zu erzielen, sofern es sich nicht um völlig zufällige Daten handelt.
- Aufgaben
Datenkompression: Vorlage: Aufgaben
- Decodierung
Die Decodierung erfolgt in ähnlicher Weise. Dazu wird das oben besprochene Tripel ausgelesen, verarbeitet und interpretiert. Anschließend wird anhand der Trefferlänge ermittelt, ob der Codierer eine Übereinstimmung erzielt hat. Wenn der Codierer keine Übereinstimmung gefunden hat, so wird das Folgezeichen an die Ausgabe weitergeleitet. Sollte es sich um eine Übereinstimmung handeln, so wird zuerst die Zeichenfolge der gefundenen Übereinstimmung ausgegeben und anschließend das Folgezeichen. Die auszugebenden Zeichen der Übereinstimmung lassen sich aus der Information über die aktuelle Position des Dateiendes und dem Offset ermitteln, welcher von dieser Position abgezogen wird. Durch diese Rechnung erhält man eine Dateiposition, an der sich das gesuchte Zeichen befindet. Gibt es eine Trefferlänge größer als 1, so wird das Auslesen des Zeichens entsprechend oft wiederholt.
Mit jedem ausgegebenen Zeichen verändert sich die aktuelle Position des Dateiendes um ein Zeichen, aus diesem Grund wird der Offset statisch von der Position subtrahiert. Dazu können Sie den folgenden Pseudo-Code betrachten.
output_pointer = 0;
while(!end of data)
{
(length, offset, followchar)=inputstream.leseTripel();
if(length>0)
{
for(i=0;i<length;i++)
{
dateiposition=outputstream.Aktuelle_Position_Dateiende - offset;
zeichen=outputstream.leseZeichen(dateiposition);
outputstream.schreibe(zeichen);
}
}
outputstream.schreibe(followchar);
}
- Aufgaben
Datenkompression: Vorlage: Aufgaben
Codierergebnisse mit dem Calgary Corpus
| Calgary Corpus - Resultate | |||
Hier finden Sie die Information, mit welchen objektiven Kompressionsleistungen dieser Algorithmus aufwarten kann, sowie die Interpretation der rechts angeführten Resultate. Vorlage:Clear
- Bewertung
Der LZ77-Algorithmus spiegelt alles in allem die Codiertechniken der späten 70er Jahre des 20. Jahrhunderts wieder. Er hat den Vorteil, dass viele Erweiterungen und Varianten nicht mit Patenten belegt sind oder diese in den nächsten Jahren ablaufen werden. Dieser Algorithmus ist jedoch sehr populär und dient heute nahezu immer als einer der Algorithmen, mit denen man beginnt, einen neuen Codierer und Decodierer zu entwerfen. Er stellt eine sehr gute erste Übung dar und lässt sehr viel Spielraum für Erweiterung. Die objektiven Ergebnisse, wie sie am Calgary Corpus erzielt werden, sind quasi die am leichtesten erzielbaren Ergebnisse. Ein Algorithmus, der schlechtere Resultate liefert als dieser Algorithmus, sollte nicht als Ausgangsmaterial dienen.
- Der Algorithmus ist einfach erlern- und programmierbar.
- Der Algorithmus ist einfach zu erweitern.
- Der Algorithmus ist einfach zu verbessern (viel Spielraum)
- Mit Variationen dieses Verfahrens lassen sich Ergebnisse erzielen, die komplexen Codierern (bspw. PPM) ebenbürtig sind.
In seiner Reinstform kann dieser Algorithmus jedoch mit keinem neueren Algorithmus konkurrieren. Wie gesagt, handelt es sich um einen Algorithmus der fast 30 Jahre alt ist. Aber er ist wiederum die Quelle aller wörterbuchbasierten Codiertechniken.
- Citeseer-Link auf den Artikel