LZ77

Das LZ77 Verfahren wurde 1977 von Abraham Lempel und Jakob Ziv entwickelt. Die Kompression erfolgt durch eine Kodierung des Textes mittels der Angabe der Distanz des aktuellen Zeichens zum Anfang des Textes und der Anzahl der von dort zu kopierenden Zeichen. Erscheint ein neues Zeichen, so wird dieses hinzugefügt. Es hat dann die Form: (2,1)B

Die (2,...) bedeutet, dass um zwei Stellen zurückgegangen wird und dieses Zeichen einmal (...,1) kopiert wird. Das darauffolgende B ist das neue Zeichen.

LZ77 Beispiel

Die zu komprimierende Zeichenfolge:

Stelle	1	2	3	4	5	6	7	8	9
Zeichen	a	a	b	c	b	b	a	b	c

Zur Kodierung:

Stelle	Hit	Zeichen	Code
1	-	a	(0,0)a
2	a	b	(1,1)b
3	-	c	(0,0)c
4	b	b	(2,1)b
5	ab	c	(5,2)c

¹
[Kow04]

Vorteil: Hohe Kompression bei wiederkehrenden, langen und gleichen Zeichenketten. Schnelle Dekompression durch einfache Adressberechnung.
Nachteil: Aufwendige Kompression durch die vielen Vergleiche, die dabei entstehen.

Bemerkung: Das ''Suchfenster'', die Anzahl der Buchstaben, um welche zurück gegangen wird, bewegt sich im Rahmen von 4000 - 68000 Zeichen.