LZW
Dieser Rechner kompresst/dekompresst eine Zeichenfolge mit dem Lempel-Ziv-Welch (LZW) Algorithmus.
Diese Webseite exisiert dank der Arbeit von den folgenden Menschen:
Anton
| |
Stefan Roesner
| |
 | Timur
|
Die Rechner in diesem Artikel führen eine Kompression und Dekompression einer Zeichenfolge mit dem LZW Algorithmus. Die LZW-methode ist einfach und zuverlässig, und benötigt nicht das Speichern eines Wörterbuches. Dies wird während einer Kompression oder Dekompression dynamisch kreiert.
Um die Algorithmus-Logik zu überprüfen, kann man die „Details anzeigen“ Box auswählen. Der Rechner zeigt das Arbeits-Log und das erstellte Wörterbuch für Phrasen an.
LZW Textkompression
Der Binär-Dump oder die Binärdatei, die vom vorherigen Rechner erstellt wurde, kann man direkt in den nächsten Rechner, der die originale Zeichenreihe wiederherstellt, einfügen. Es ist aber nötig, dass man das gleiche Wörterbuchquelle auswählt, die für die Kompression verwendet wurde (die gleiche Verschlüsselung auswählen, oder das gleiche Wörterbuch explizit angeben).
LZW Dekompression
- Datei hier hinziehen
Lempel-Ziv-Welch Algorithmus
Der verlustfreie Kompressionsalgorithmus LZ78 wurde in 1978 von Abraham Lempel und Jacob Ziv veröffentlicht, und dann in 1984 von Terry Welch modifiziert. Nach Welch’s Veröffentlichung wurde der Algorithmus LZW genannt, nach den Nachnamen der Autoren (Lempel, Ziv, Welch). Der Algorithmus wurde patentiert, aber alle Patente sind inzwischen ausgelaufen. Dies gib uns die Möglichkeit, diese Ausführungen hier zu veröffentlichen.
Beschreibung des LZW Algorithmus
- Erstell das anfängliche Wörterbuch, das alle möglichen Zeichen beinhaltet.
- Das erste Zeichen für die Eingabephrase W eingeben.
- Lese den nächsten Code K.
- Falls EOF das W wiedergibt, sonst gilt:
Falls die WK Phrase bereits im Wörterbuch ist, W ⟵ WK, und geht zu 3,
Sonst den Code für W wiedergeben, und man fügt WK dem Wörterbuch zu, W ⟵ K und geht zu 3.
Um die Daten, die mit diesem Verfahren kreiert wurden, zu entschlüsseln, muss man das Wörterbuch nicht speichern. Es wird durch de Dekompression wieder hergestellt:
- Erstell das anfängliche Wörterbuch, das alle möglichen Zeichen beinhaltet.
2.Das erste Zeichen für die Eingabephrase W eingeben. - Lese den nächsten Code K.
4.Falls EOF, sende das Zeichen für den Code W zurück, sonst:
Sollte die Phrase für den WK Code nicht im Wörterbuch sein, gibt man die Phrase für den WK Code zurück und fügt die Phrase für den WK Code dem Wörterbuch hinzu.
Sonst weist man die Eingabephrase dem WK Code zu und geht zu 3.
Die originale Arbeit von Welsch hat vorgesehen, die Phrase im Wörterbuch mit einem 12-Bit Code mit fixer Größe zu verschlüsseln. Dieser Ansatz würde die Länge der Verschlüsselung einer kleinen Nachricht verlängern, sodass diese sogar länger als die Eingabenachricht ist. Daher ist es nun üblich, eine dynamische Code-Länge zu verwenden, welche sich immer ändert, wenn das Limit eines Wörterbuches erreicht ist.
Umgang mit dem Wachstum der Wörterbuchgröße
In dem oben beschriebenen Kompressions-Algorithmus ist die Wörterbuchgröße nicht limitiert. In der Praxis kann dies aber zu Resourcebeschränkungen führen, wenn man eine große Menge von Daten hat.
Es gibt Modifikationen für diesen Algorithmus, die dieses Problem lösen können:
-
LZC – die Umsetzung des Algorithmus für die Kompression limitiert die Größe des Wörterbuchs auf 16-Bitss. Wenn das Maximum erreicht wird, ändert sich das Wörterbuch nicht weiter. Der Algorithmus überwacht das Verhältnis der Kompression und setzt das Wörterbuch zurück, falls es zu stark degradiert, und bildet dann ein Neues.
- LZT – Ein Überfluss – entfernt eine Phrase vom Wörterbuch, die am längsten nicht mehr verwendet wurde.
Umsetzungs-Eigenschaften
Anfängliche Wörterbuch
Unsere Rechner implementiert ein endlos wachsendes Vokabular, welches für riesige Datenmenge zu teuer sein kann. Die Größe von Phrasen fängt mit 8-Bits für das anfängliche Wörterbuch, spezifiziert durch Standardcodierung, an. Für ein manuell eingefügtes Wörterbuch ist es kleiner. In diesem Fall ist die Größte des Phrasencodes die Mindestanzahl von Bits benötigt, um die Anzahl von Zeichen im Wörterbuch darzustellen.
Bitlänge.
Multi-Byte Verschlüsselung
Einige Verschlüsselung benötigen mehr als nur 1-Byte pro Zeichen, zum Beispiel beinhaltet UTF-8 Zeichen mit variabler Länge von 1-4 Bytes. Auf jeden Fall hat jedes anfängliche Wörterbuch 256 Elemente mit Codes von 0 bis 255 – egal welche Verschlüsselung genutzt wird.
Für die Multi-Byte Verschlüsselung sieht ein dynamisch generiertes Wörterbuch eher exotisch aus, da deren Phrasen unweigerlich von verschiedenen Teilen benachbarter Zeichen erstellt wird. In solch einem Fall wird ein “Fehlender Byte-Marker” genutzt (standardmäßig ist es das Zeichen '~'), um das Ausgabefeld deutlicher darzustellen. Für die Kompression der Phrase „9 €” in der UTF-8 Verschlüsselung zum Beispiel kann das dynamische Wörterbuch mit der Kombination der folgenden Zeichen ausgefüllt werden:
9 - Nein,
' ' - Leerzeichen,
€~~ - Erste Byte für das Euro Symbol,
~€~ - Zweite Byte für das Euro Symbol,
~~€ - Dritte Byte für das Euro Symbol,
€~ - die ersten beiden Bytes für das Euro Symbol,
~€ - die letzten beiden Bytes für das Euro Symbol,
€ - Alle drei Bytes für das Euro Symbol.
Wir haben diese Zeichenerklärung nur Annehmlichkeiten eingeführt. Da die Bestandteile von vielen Multi-Byte Zeichen nur Bytes von 8-Bits sind, können diese die Gleichen für verschiedene Zeichen sein.
Zum Beispiel:
€ ~~ - Für den ersten Byte für das Euro Symbol ist der Code in utf-8 = 226
₽ ~~ - Für den ersten Byte für das Rubel Symbol ist der Code in utf-8 = 226
Nachgestellt mit Nullen
Der Algorithmus für Kompression kann verschiedene Bit-Array in einer Größe erstellen, die nicht das Vielfache von 8 sind. In diesen Fällen füllt der Rechner das Ende mit Null-Bits. Da die Ausführung eine variable Größe von dem Phrasencode verwendet, kann dieser Ansatz Probleme bereiten, wenn das manuell eingegebene anfängliche Wörterbuch klein ist.
In diesem Beispiel hat die Endnachricht nur 18 Bits und 6 Bits müssten mit Nullen aufgefüllt werden, um die gesamte Nachricht in einer Binärdatei zu speichern.
Da die Größe des Phrasencodes mit den angegebenen Parametern nur 4 Bits ist, wird das zusätzliche Wort beim Entpacken gelesen. Wenn man das ursprüngliche Wörterbuch aber mit dem Code des ersten Zeichens =0 erstellt, würde das zusätzliche Zeichen unverpackt bleiben.
Man löst das Problem, indem man ein Null-Zeichen zum Beginn des Wörterbuchs hinzufügt. Dies wird normalerweise als das Ende einer Zeichenreihe angesehen.
Wenn man die Verschlüsselung als anfängliche Wörterbuch verwendet, wird man dieses Problem nie haben, da der Phrasencode immer mindestens 8-Bits hat.
Kommentare