LZ77 und LZ78

LZ77 und LZ78 sind die beiden verlustfreien Datenkomprimierungsalgorithmen, die 1977 und 1978 in den Abhandlungen von Abraham Lempel und Jacob Ziv veröffentlicht wurden. Sie sind auch als LZ1 bzw. LZ2 bekannt. Diese beiden Algorithmen bilden die Grundlage für viele Variationen einschließlich LZW, LZSS, LZMA und anderen. Neben ihrem akademischen Einfluss bildeten diese Algorithmen die Grundlage für verschiedene ubiquitäre Kompressionsverfahren, darunter GIF und den in PNG verwendeten DEFLATE-Algorithmus. Sie sind beide theoretisch Wörterbuchcodierer. LZ77 behält während der Komprimierung ein Schiebefenster bei. Dies erwies sich später als äquivalent zu dem von LZ78 erstellten expliziten Wörterbuch. Sie sind jedoch nur dann äquivalent, wenn die gesamten Daten dekomprimiert werden sollen. Die LZ78-Dekomprimierung ermöglicht den wahlfreien Zugriff auf die Eingabe, solange das gesamte Wörterbuch verfügbar ist, während die LZ77-Dekomprimierung immer am Anfang der Eingabe beginnen muss. Die Algorithmen wurden 2004 als IEEE-Meilenstein bezeichnet. Theoretische Effizienz. In der zweiten der beiden Veröffentlichungen, die diese Algorithmen vorstellten, werden sie als von Finite-State-Maschinen definierte Encoder analysiert. Ein für die Informationsentropie analoges Maß wird für einzelne Sequenzen entwickelt (im Gegensatz zu probabilistischen Ensembles). Diese Maßnahme gibt eine Einschränkung des erzielbaren Kompressionsverhältnisses vor. Es wird dann gezeigt, dass es endliche verlustfreie Kodierer für jede Sequenz gibt, die diese Grenze erreichen, wenn die Länge der Sequenz unendlich wird. In diesem Sinne erzeugt ein auf diesem Schema basierender Algorithmus asymptotisch optimale Kodierungen. Dieses Ergebnis kann direkter nachgewiesen werden, wie beispielsweise in Anmerkungen von Peter Shor. LZ77. LZ77-Algorithmen erzielen eine Komprimierung, indem sie wiederholtes Vorkommen von Daten durch Verweise auf eine einzelne Kopie dieser Daten ersetzen, die zuvor im (unkomprimierten) Datenstrom vorhanden waren. Eine Übereinstimmung wird durch ein Zahlenpaar codiert, das als “Längen-Distanz-Paar” bezeichnet wird. Dies entspricht der Anweisung “Jedes der nächsten” Längenzeichen ist gleich den Zeichen “Entfernungszeichen”, die im unkomprimierten Stream genau dahinter stehen. . (Die “Entfernung” wird manchmal auch als “Versatz” bezeichnet.) Um Übereinstimmungen zu erkennen, muss der Codierer die letzte Datenmenge wie die letzten 2 kB, 4 kB oder 32 kB nachverfolgen. Die Struktur, in der diese Daten gespeichert werden, wird als “Schiebefenster” bezeichnet, weshalb LZ77 manchmal auch als Schiebefensterkompression bezeichnet wird. Der Codierer muss diese Daten beibehalten, um nach Übereinstimmungen zu suchen, und der Decodierer muss diese Daten aufbewahren, um die Übereinstimmungen zu interpretieren, auf die sich der Codierer bezieht. Je größer das Schiebefenster ist, desto länger dauert es, bis der Encoder nach Referenzen sucht. Es ist nicht nur akzeptabel, sondern häufig auch sinnvoll, wenn Länge-Distanz-Paare eine Länge angeben, die die Distanz tatsächlich überschreitet. Als Kopierbefehl ist dies rätselhaft: “Gehen Sie vier” Zeichen zurück und kopieren Sie “zehn” Zeichen von dieser Position in die aktuelle Position “. Wie können zehn Zeichen kopiert werden, wenn sich tatsächlich nur vier im Puffer befinden? Bei der Bearbeitung eines Bytes zu einem Zeitpunkt besteht kein Problem bei der Bereitstellung dieser Anforderung, da ein Byte, das kopiert wird, erneut als Eingabe in den Kopierbefehl eingegeben werden kann. Wenn die Kopie-von-Position die ursprüngliche Zielposition erreicht, werden folglich Daten zugeführt, die vom “Anfang” der Kopie-von-Position eingefügt wurden. Die Operation entspricht somit der Anweisung “kopiere die Daten, die du erhalten hast, und füge sie wiederholt ein, bis sie passt”. Da dieser Paartyp eine einzelne Datenkopie mehrmals wiederholt, kann eine flexible und einfache Form der Lauflängencodierung verwendet werden.Ein anderer Weg, die Dinge zu sehen, ist wie folgt: Während der Codierung, damit der Suchzeiger nach dem Ende des Suchfensters weiter passende Paare findet, müssen alle Zeichen der ersten Übereinstimmung am Offset D und vorwärts bis zum Ende des Suchfensters übereinstimmen Eingabe, und dies sind die (zuvor gesehenen) Zeichen, die eine einzelne Laufeinheit der Länge LR umfassen, die gleich D sein muss. Dann, wenn der Suchzeiger an dem Suchfenster vorbeigeht und vorwärts geht, solange sich das Laufmuster in der Eingabe wiederholt Die Such- und Eingabezeiger sind synchron und stimmen mit den Zeichen überein, bis das Laufmuster unterbrochen wird. Dann wurden insgesamt L Zeichen gefunden, L> D, und der Code lautet [D, L, c].Bei der Decodierung von [D, L, c] wiederum ist D = LR. Wenn die ersten LR-Zeichen in die Ausgabe eingelesen werden, entspricht dies einer einzelnen Laufeinheit, die an den Ausgabepuffer angehängt ist. An diesem Punkt könnte man sich vorstellen, dass der Lesezeiger nur einmal int (L / LR) + (1, wenn L mod LR nicht gleich 0 ist) bis zum Start dieser einzelnen gepufferten Laufeinheit zurückgeben muss, LR-Zeichen lesen (oder (möglicherweise weniger bei der letzten Rückkehr) und wiederholen, bis insgesamt L Zeichen gelesen sind. Da der Codierungsprozess jedoch gespiegelt wird, muss der Lesezeiger nur synchron mit dem Schreibzeiger um einen festen Abstand laufen, der der Lauflänge LR entspricht, da das Muster wiederholt wird, bis L-Zeichen insgesamt zur Ausgabe kopiert wurden. In Anbetracht des Vorstehenden, insbesondere wenn erwartet wird, dass die Komprimierung von Datenläufen vorherrscht, sollte die Fenstersuche am Ende des Fensters beginnen und rückwärts ablaufen, da Laufmuster, sofern vorhanden, zuerst gefunden werden und die Suche beenden lassen. absolut, wenn die aktuelle maximale Übereinstimmungssequenzlänge oder vernünftigerweise eingehalten wird, wenn eine ausreichende Länge eingehalten wird, und schließlich für die einfache Möglichkeit, dass die Daten aktueller sind und möglicherweise besser mit der nächsten Eingabe korrelieren. Implementierungen. Obwohl alle LZ77-Algorithmen per Definition nach dem gleichen Grundprinzip arbeiten, können sie stark davon abweichen, wie sie ihre komprimierten Daten kodieren, um die numerischen Bereiche eines Längen-Distanz-Paares zu variieren. Ändern Sie die Anzahl der für ein Längen-Distanz-Paar verbrauchten Bits. und ihre Längen-Distanz-Paare von “Literalen” unterscheiden (Rohdaten, die als sie selbst codiert sind, und nicht als Teil eines Längen-Distanz-Paares). Einige Beispiele: LZ78. LZ78-Algorithmen erzielen eine Komprimierung, indem wiederholte Vorkommen von Daten durch Verweise auf ein Wörterbuch ersetzt werden, das auf dem Eingangsdatenstrom basiert. Jeder Wörterbucheintrag hat das Formwörterbuch […] = {index, character}, wobei “index” der Index eines vorherigen Wörterbucheintrags ist und ein Zeichen an die durch “dictionary” dargestellte Zeichenfolge angehängt wird. Beispiel: “abc” wäre (in umgekehrter Reihenfolge) wie folgt gespeichert: Wörterbuch [k = {j, ‘c’}, wörterbuch = {i, ‘b’}, wörterbuch [i = {0, ‘a’}, wobei ein Index von 0 die Zahl angibt erstes Zeichen einer Zeichenfolge. Der Algorithmus initialisiert “letzter übereinstimmender Index” = 0 und “nächster verfügbarer Index” = 1. Für jedes Zeichen des Eingabestroms wird das Wörterbuch nach einer Übereinstimmung durchsucht: {letzter übereinstimmender Index, Zeichen}. Wenn eine Übereinstimmung gefunden wird, wird “letzter übereinstimmender Index” auf den Index des übereinstimmenden Eintrags gesetzt, und es wird nichts ausgegeben. Wenn keine Übereinstimmung gefunden wird, wird ein neuer Wörterbucheintrag erstellt: dictionaryavailable index = {letzter übereinstimmender Index, Zeichen}, und der Algorithmus gibt “letzten übereinstimmenden Index” gefolgt von “Zeichen” aus und setzt dann “letzten übereinstimmenden Index” = zurück 0 und erhöht den “nächsten verfügbaren Index”. Sobald das Wörterbuch voll ist, werden keine weiteren Einträge hinzugefügt. Wenn das Ende des Eingabestroms erreicht ist, gibt der Algorithmus den “letzten übereinstimmenden Index” aus. Beachten Sie, dass Zeichenfolgen in umgekehrter Reihenfolge im Wörterbuch gespeichert werden, mit denen ein LZ78-Decoder umgehen muss. LZW ist ein LZ78-basierter Algorithmus, der ein Wörterbuch verwendet, das mit allen möglichen Zeichen (Symbolen) (oder der Emulation eines vorinitialisierten Wörterbuchs) vorinitialisiert ist. Die Hauptverbesserung von LZW besteht darin, dass, wenn keine Übereinstimmung gefunden wird, angenommen wird, dass das aktuelle Eingabestromzeichen das erste Zeichen einer vorhandenen Zeichenfolge im Wörterbuch ist (da das Wörterbuch mit allen möglichen Zeichen initialisiert wird), also nur das letzte Zeichen Übereinstimmungsindex “wird ausgegeben (was der vorinitialisierte Wörterbuchindex sein kann, der dem vorherigen (oder dem anfänglichen) Eingabezeichen entspricht). Informationen zur Implementierung finden Sie im LZW-Artikel.1}

Leave a Comment