LZ77 und LZ78 sind die zwei lossless Datenkompressionsalgorithmen, die in Vorträgen von Abraham Lempel und Jacob Ziv 1977 und 1978 veröffentlicht sind. Sie sind auch bekannt als LZ1 und LZ2 beziehungsweise. Diese zwei Algorithmen bilden die Basis für viele Schwankungen einschließlich LZW, LZSS, LZMA und anderer. Außer ihrem akademischen Einfluss haben diese Algorithmen die Basis von mehreren allgegenwärtigen Kompressionsschemas, einschließlich GIF und des DEFLATIONIEREN in PNG verwendeten Algorithmus gebildet.

Sie sind beide theoretisch Wörterbuch-Codierer. LZ77 erhält ein gleitendes Fenster während der Kompression aufrecht. Wie man später zeigte, war das zum ausführlichen Wörterbuch gleichwertig, das durch LZ78-jedoch gebaut ist, sie sind nur gleichwertig, wenn die kompletten Daten beabsichtigt sind, um dekomprimiert zu werden. LZ78 Dekompression erlaubt zufälligen Zugang zum Eingang, so lange das komplette Wörterbuch verfügbar ist, während LZ77 Dekompression immer am Anfang des Eingangs anfangen muss.

Die Algorithmen wurden einen IEEE Meilenstein 2004 genannt.

Verschlüsselung und Entzifferung

Während es viele Varianten von LZ Algorithmen gibt, arbeiten sie alle, indem sie die Eingangsfolge in verschiedene Ausdrücke grammatisch analysieren. Jeder Ausdruck wird bezüglich eines vorherigen Ausdrucks und vielleicht etwas Zusatzinformation verschlüsselt. Das nutzt Überfülle in der Eingangsfolge aus. Eine besonders einfache Variante, die unten beschrieben ist, tut seine Syntaxanalyse auf eine gierige Weise. An jedem Punkt in seiner Ausführung ist es an einem Punkt entlang der Eingangsfolge. Von hier sucht es vorn nach dem kürzesten Ausdruck, der vorher nicht gesehen worden ist. Kompression wird erreicht, weil dieser neue Ausdruck bezüglich eines vorher gesehenen Ausdrucks plus ein Charakter verschlüsselt werden kann. In diesen neuen Ausdruck wird jetzt im Wörterbuch und den Prozess-Wiederholungen eingegangen.

EINGANG: Die Folge, die S über ein begrenztes Alphabet von Charakteren zusammenzupressen

ist

PRODUKTION: Eine Folge von Paaren (Verweisung, Charakter)

A1 Suchen nach dem kürzesten Block W, der nicht im Wörterbuch ist

A2, wenn W ein einzelner Charakter c ist

A3 verschlüsseln W als (0, c)

A4 sonst W ist ein Ausdruck X, der im Wörterbuch plus ein Charakter c ist

A5 verschlüsseln W als (Verweisung auf X in D, c)

A6 Fügen W zum Wörterbuch Hinzu

A7 Gehen zum Schritt A1

Beispiel

Nehmen Sie an, dass der Eingangstext ist

AABABBBABAABABBBABBABB

Der erste gefundene Block ist einfach A, verschlüsselt als (0, A). Das folgende ist AB, verschlüsselt als (1, B), wo 1 eine Verweisung auf A ist:

A|AB|ABBBABAABABBBABBAB

Der folgende Block ist ABB, der als verschlüsselt wird (2, B), wo 2 eine Verweisung auf AB ist, der im Wörterbuch vor einer Wiederholung eingegangen ist. Diesen Weg gehend, analysiert die Schnur in grammatisch

A|AB|ABB|B|ABA|ABAB|BB|ABBA|BB

und der letzte BB wird einfach als eine Verweisung auf die vorherige verschlüsselt. Im Allgemeinen wird ein schleifendes Wort, das im Wörterbuch ist, durch eine Verweisung und einen speziellen Charakter verschlüsselt, der anzeigt, dass es das Ende der Folge ist. Am Ende des Algorithmus ist das Wörterbuch:

Die Folge von encodings unten die letzte Säule gibt die Produktion des Algorithmus. Die Entzifferung der Arbeitsparallele zur Verschlüsselung und baut ein Wörterbuch ebenso auf.

EINGANG: Eine Folge von Paaren (Verweisung, Charakter)

PRODUKTION: Die unkomprimierte Folge S

A1 für jedes Paar (r, c) im Eingang:

A2, wenn r 0 ist

A3 W  c

A4 lassen sonst X der Ausdruck an der Position r im Wörterbuch sein

A5 W  c angehangen am Ende von X

A6 Hängen W am Ende des Wörterbuches An; Produktion W

A7 Gehen zum Schritt A1

Theoretische Leistungsfähigkeit

In der zweiten von den zwei Zeitungen, die diese Algorithmen eingeführt haben, werden sie als encoders definiert durch Zustandsmaschinen analysiert. Ein dem Informationswärmegewicht analoges Maß wird für individuelle Folgen (im Vergleich mit probabilistic Ensembles) entwickelt. Dieses Maß gibt einem gebundenen das Kompressionsverhältnis, das erreicht werden kann. Es wird dann gezeigt, dass dort begrenzter lossless encoders für jede Folge bestehen, die erreichen, hat das gebunden, als die Länge der Folge zur Unendlichkeit wächst. In diesem Sinn erzeugt ein auf diesem Schema gestützter Algorithmus asymptomatically optimalen encodings. Dieses Ergebnis kann mehr direkt bezüglich des Beispiels in Zeichen von Peter Shor bewiesen werden.

LZ77

LZ77 Algorithmen erreichen Kompression durch das Ersetzen von wiederholten Ereignissen von Daten mit Verweisungen auf eine einzelne Kopie davon Daten vorhanden früher im Eingang (unkomprimierter) Datenstrom. Ein Match wird von einem Paar von Zahlen genannt ein Paar der Länge-Entfernung verschlüsselt, das zur Behauptung "jeder der folgenden Länge-Charaktere gleichwertig ist, ist den Charakteren genau Entfernungscharaktere dahinter im unkomprimierten Strom gleich". (Die "Entfernung" wird manchmal den "Ausgleich" stattdessen genannt.)

Um Matchs zu entdecken, muss der encoder einen Betrag der neusten Daten, wie die letzten 2 Kilobytes, 4 Kilobytes oder 32 Kilobytes nachgehen. Die Struktur, in der das Daten gehalten wird, wird ein gleitendes Fenster genannt, das ist, warum LZ77 manchmal genannt wird, Fensterkompression gleiten lassend. Der encoder muss das Daten halten, um nach Matchs zu suchen, und der Decoder muss das Daten halten, um die Matchs zu interpretieren, auf die sich der encoder bezieht. Je größer das gleitende Fenster ist, desto längerer Rücken der encoder nach dem Schaffen von Verweisungen suchen kann.

Es ist nicht nur annehmbar, aber oft nützlich, Paaren der Länge-Entfernung zu erlauben, eine Länge anzugeben, die wirklich die Entfernung überschreitet. Als ein Kopie-Befehl ist das rätselhaft: "Gehen Sie vier Charaktere zurück und kopieren Sie zehn Charaktere von dieser Position in die aktuelle Position". Wie zehn Charaktere kann, kopiert werden, wenn nur vier von ihnen wirklich im Puffer sind? Wenn es ein Byte auf einmal anpackt, gibt es kein Problem, das dieser Bitte dient, weil weil ein Byte kopiert wird, kann es, wieder wie eingegeben, zum Kopie-Befehl gefüttert werden. Wenn die Kopie - von der Position es zur anfänglichen Bestimmungsort-Position macht, sind es folglich gefütterte Daten, der vom Anfang der Kopie - von der Position aufgeklebt wurde. Die Operation ist so zur Behauptung gleichwertig "kopieren die Daten Ihnen wurde gegeben und klebt es wiederholend auf, bis es passt". Da dieser Typ des Paares eine einzelne Kopie von Daten mehrmals wiederholt, kann er verwendet werden, um eine flexible und leichte Form der Verschlüsselung der Lauf-Länge zu vereinigen.

Durchführungen

Wenn auch alle LZ77 Algorithmen definitionsgemäß an demselben Kernprinzip arbeiten, können sie sich weit darin ändern, wie sie ihre komprimierten Daten verschlüsseln, um die numerischen Reihen eines Paares der Länge-Entfernung zu ändern, die Zahl von Bit zu verändern, die für ein Paar der Länge-Entfernung verbraucht sind, und ihre Paare der Länge-Entfernung von Druckfehlern (rohe Daten zu unterscheiden, verschlüsselt als selbst, aber nicht als ein Teil eines Paares der Länge-Entfernung). Einige Beispiele:

• Der Algorithmus hat in Lempels ursprünglichen 1977-Papierproduktionen und Zivs alle seine Daten drei Werte auf einmal illustriert: Die Länge und Entfernung des längsten Matchs haben im Puffer und dem Druckfehler gefunden, der diesem Match gefolgt ist. Wenn zwei aufeinander folgende Charaktere im Eingangsstrom nur als Druckfehler verschlüsselt werden konnten, würde die Länge des Paares der Länge-Entfernung 0 sein.
• Im Format von PalmDoc wird ein Paar der Länge-Entfernung immer durch eine Zwei-Byte-Folge verschlüsselt. Der 16 Bit, die diese zwei Bytes zusammensetzen, gehen 11 Bit zur Verschlüsselung der Entfernung, 3 gehen zur Verschlüsselung der Länge, und die restlichen zwei werden verwendet, um sicherzustellen, dass der Decoder das erste Byte als der Anfang solch einer Zwei-Byte-Folge identifizieren kann.
• In der Durchführung, die für viele Spiele durch Elektronische Künste verwendet ist, kann die Größe in Bytes eines Paares der Länge-Entfernung innerhalb des ersten Bytes des Paares der Länge-Entfernung selbst angegeben werden; je nachdem, wenn das erste Byte mit 0, 10, 110, oder 111 (wenn gelesen, in der großen-endian Bit-Orientierung) beginnt, kann die Länge des kompletten Paares der Länge-Entfernung 1 bis 4 Bytes groß sein.

• gestützte Kompressionsmethode des populärsten LZ77 ist DEFLATIONIEREN; es verbindet LZ77 mit Huffman, der codiert. Druckfehler, Längen und ein Symbol, um das Ende des aktuellen Datenblocks anzuzeigen, werden alle zusammen in ein Alphabet gelegt. Entfernungen können in ein getrenntes Alphabet sicher gelegt werden; da eine Entfernung nur gerade vorkommt, nach einer Länge kann es nicht für eine andere Art des Symbols oder umgekehrt falsch sein.

LZ78

LZ78 Algorithmen erreichen Kompression durch das Ersetzen von wiederholten Ereignissen von Daten mit Verweisungen auf ein Wörterbuch, das gestützt auf dem Eingangsdatenstrom gebaut wird. Jeder Lexikoneintrag ist des Form-Wörterbuches [...] = {Index, Charakter}, wo Index der Index zu einem vorherigen Lexikoneintrag ist, und wird Charakter an der Schnur angehangen, die durch das Wörterbuch [Index] vertreten ist. Zum Beispiel würde "Alphabet" (in umgekehrter Reihenfolge) wie folgt versorgt: Wörterbuch [k] = {j, 'c'}, Wörterbuch [j] = {ich, 'b'}, Wörterbuch [ich] = {0,}, wo ein Index 0 das Ende einer Schnur einbezieht. Der Algorithmus initialisiert letzten zusammenpassenden Index = 0 und als nächstes verfügbaren Index = 1. Für jeden Charakter des Eingangsstroms wird das Wörterbuch nach einem Match gesucht: {Letzter zusammenpassender Index, Charakter}. Wenn ein Match dann gefunden wird, wird letzter zusammenpassender Index auf den Index des zusammenpassenden Zugangs gesetzt, und nichts ist Produktion. Wenn ein Match nicht gefunden wird, dann wird ein neuer Lexikoneintrag geschaffen: Wörterbuch [als nächstes verfügbarer Index] = {letzter zusammenpassender Index, Charakter}, und die Algorithmus-Produktionen letzter zusammenpassender Index, der vom Charakter gefolgt ist, fasst dann letzten zusammenpassenden Index = 0 neu und erhöht als nächstes verfügbaren Index. Sobald das Wörterbuch voll ist, werden keine Einträge mehr hinzugefügt. Wenn das Ende des Eingangsstroms, die Algorithmus-Produktionen letzter zusammenpassender Index erreicht wird. Bemerken Sie, dass Schnuren im Wörterbuch in umgekehrter Reihenfolge versorgt werden, der ein LZ78 Decoder gestützt hat, wird sich befassen müssen.

LZW ist ein LZ78-basierter Algorithmus, der ein Wörterbuch verwendet, das mit allen möglichen Charakteren (Symbole), (oder Wetteifer eines vorinitialisierten Wörterbuches) vorinitialisiert ist. Die Hauptverbesserung von LZW ist, dass, wenn ein Match nicht gefunden wird, der aktuelle Eingangsstrom-Charakter angenommen wird, dass es der erste Charakter einer vorhandenen Schnur im Wörterbuch sein wird (da das Wörterbuch mit allen möglichen Charakteren initialisiert wird), so ist nur der letzte zusammenpassende Index Produktion (der der vorinitialisierte Wörterbuch-Index entsprechend dem vorherigen (oder die Initiale) Eingangscharakter) sein kann. Beziehen Sie sich auf den Artikel LZW für Durchführungsdetails.

• Jacob Ziv und Abraham Lempel; ein Universaler Algorithmus für die Folgende Datenkompression, IEEE Transaktionen auf der Informationstheorie, 23 (3), Seiten 337-343, Mai 1977.
• Jacob Ziv und Abraham Lempel; Kompression von Individuellen Folgen über das Codieren der Variablen Rate, die IEEE Transaktionen auf der Informationstheorie, 24 (5), Seiten 530-536, September 1978.