Nachdem ich das HBO-Drama "Silicon Valley" gesehen habe, habe ich mich schon immer für Kompressionsalgorithmen interessiert. Richard Hendricks und sein Middle-Out-Kompressionsalgorithmus darin sind natürlich gefälscht, aber nachdem ich gründlich gegoogelt habe, habe ich herausgefunden, dass es im echten Leben ein solches Kompressionsalgorithmus-Genie gibt.
Yann Collet erfand 2011 den Kompressionsalgorithmus LZ4. Natürlich ist der LZ4-Algorithmus nicht so großartig wie Middle Out, aber er ist bekannt für seine unbesiegbare Kompressionsgeschwindigkeit und schnellere Dekompressionsgeschwindigkeit, wenn eine bestimmte Kompressionsrate garantiert werden kann.
Ich werde hier nicht ins Detail über die Bewertung der Kompressionsgeschwindigkeit gehen; falls Sie interessiert sind, können Sie diesen Vergleichsartikel lesen:Der Hyperlink-Login ist sichtbar.
Ebenfalls angehängt ist die GitHub-Adresse von LZ4:Der Hyperlink-Login ist sichtbar.
Dieser Artikel konzentriert sich darauf, das Prinzip des LZ4-Kompressionsalgorithmus zu erklären. Ein großer Gott hat zuvor eine Erklärung des LZ4-Algorithmus geschrieben:Der Hyperlink-Login ist sichtbar.Aber als ich vorher studiert habe, hatte ich das Gefühl, dass dieser Artikel für Anfänger nicht sehr freundlich ist, also habe ich einen weiteren Artikel für Anfänger wie mich begonnen.
Wenn man es in einem Satz zusammenfasst, ist LZ4 ein LZ77, das ein Wörterbuch mit einer 16k-Hashtabelle speichert und den Abruf vereinfacht.
LZ4 ist ein verlustfreier Kompressionsalgorithmus, der eine Kompressionsgeschwindigkeit von > 500 MB/s pro Kern bietet und mit Mehrkern-CPUs skaliert werden kann. Er verfügt über extrem schnelle Decoder mit Geschwindigkeiten von mehreren GB/s pro Kern, die oft RAM-Geschwindigkeitsgrenzen bei Mehrkernsystemen erreichen.
Die Geschwindigkeit kann dynamisch angepasst werden, wobei ein "Beschleunigungsfaktor" gewählt wird, der das Verdichtungsverhältnis gegen eine höhere Geschwindigkeit eintauscht. Andererseits wird auch eine hochkompressive Ableitung LZ4_HC bereitgestellt, um die Kompression auf Kosten der CPU-Zeit zu erhöhen. Alle Versionen haben die gleiche Dekompressionsgeschwindigkeit.
Was ist also LZ77?
LZ77-Kompression und Prinzip
LZ77 ist ein Algorithmus, der ein Wörterbuch zur Kompression anwendet. Laienausgedrückt bedeutet es, das Programm beobachten zu lassen (im Wörterbuch zu schauen), ob die aktuell angezeigten Daten mit dem vorherigen dupliziert sind, und falls ja, speichern wir den Abstand (Offset) und die Länge der doppelten Felder, um die doppelten Felder zu ersetzen und die Daten zu komprimieren.
ReferenzDer Hyperlink-Login ist sichtbar.
Für eine Buchstabenfolge A A B C B B A B C speichert das Programm beim Lesen des zweiten A (1,1) (1 Ziffer des vorherigen, Länge 1), und ebenso speichert das Programm beim Lesen des zweiten B (2,1) (Entfernung 2, Länge 1).
Aber wenn die Zeichenkette länger ist und das Programm die Daten ständig ins Wörterbuch einweist, wird die Suche nach doppelten Feldern extrem zeitaufwendig, weil das Programm im schlimmsten Fall mit jedem neuen Buchstaben das gesamte Wörterbuch durchgeht. LZ77 verwendet eine Schiebefenster-Methode, um dieses Problem zu lösen.
Ähnlich wie bei TCP mit einem Sliding Window kann ein Sliding Window den Cache-Bereich verkleinern, um zu vermeiden, dass zu viele zwischengespeicherte Daten gleichzeitig verarbeitet werden. In LZ77 wächst das Wörterbuch nicht ständig, sondern verwirft die ersten hinzugefügten Zeichen, wenn sie die vom Wörterbuch angegebene maximale Größe überschreiten, um sicherzustellen, dass die Größe des Wörterbuchs immer auf der angegebenen maximalen Größe gehalten wird.
Angenommen, die Wörterbuchlänge beträgt 3
| Wörterbuch |
| A | A B C B B A B C
Ausgabe (0,0,A)
| A A | B C B B A B C
Ausgabe(1,1)
| A A B | C B B A B C
Ausgabe (0,0,B)
A | A B C | B B A B C
Ausgabe (0,0,C)
A A | B C B | B A B C
Output(2,1)
Der andere Teil des Schiebefensters ist der zu durchsuchte Cache (der Look Ahead Buffer hat keine offizielle Übersetzung). Der zu durchsuchte Cache ist der unkomprimierte Teil der Länge, der dem Wörterbuch am nächsten liegt. Der LZ77-Algorithmus passt zur längsten Zeichenkette in diesem Teil des Zeichens, die mit dem Wörterbuch übereinstimmt. Das vorherige Beispiel kann als Look-Ahead-Puffer von 1 betrachtet werden.
Angenommen, die Wörterbuchlänge beträgt 5 und die zu durchsuchende Cache-Größe beträgt 3
| Wörterbuch | Vorausschauen Puffer |
A | A B C B B | A B C |
Ausgabe(5,3)
Die längste Reihe, die dazu passt, ist ABC
Vollständiger Kompressionsprozess:
Angenommen, die Wörterbuchlänge beträgt 5 und die zu durchsuchende Cache-Größe beträgt 3
| Wörterbuch | Vorausschauen Puffer |
| A A B | C B B A B C
Ausgabe (0,0,A)
| A | A B C | B B A B C
Ausgabe(1,1)
| A A | B C B | B A B C
Ausgabe (0,0,B)
| A A B | C B B | A B C
Ausgabe (0,0,C)
| A A B C | B B A | B C
Output(2,1)
| A A B C B | B A B | C
Ausgabe(1,1)
A | A B C B B | A B C |
Ausgabe(5,3)
A A B C | B B A B C | 。。。 |
Es ist nicht notwendig, das Wörterbuch in der Ausgabedatei des Kompressors zu speichern, da das Dekompressionsprogramm das Wörterbuch wiederherstellt, indem es die Ausgabeeinheiten abgleicht.
Dekompressionsprozess
Einer der großen Vorteile des LZ77-Algorithmus ist, dass er sich sehr schnell dekomprimieren lässt.
Wenn die erste passende Einheit (0,0,A) ist, dann wird A ausgegeben.
Die zweite Matching-Einheit ist (1,1), die das vorherige Bit in der Ausgabefolge kopiert und A ausgibt, wenn die Kopierlänge 1 beträgt.
。。。
Wenn die letzte passende Einheit (5,3) ist, schauen Sie 5 Bit im Kopier-Ausgabestring zurück, und wenn die Kopierlänge 3 beträgt, geben Sie A, B, C aus.
Der zeitaufwändigste Teil der Kompression des LZ77-Algorithmus ist es, das am längsten passende Zeichen im Cache zu finden, das im Wörterbuch gesucht werden soll. Wenn das Wörterbuch und der zu durchsuchte Cache zu kurz sind, sind die Chancen, einen Treffer zu finden, gering. Daher hat LZ4 den Matching-Algorithmus für LZ77 geändert.
Erstens ist das Wörterbuch des LZ4-Algorithmus eine Hashtabelle. Der Schlüssel im Wörterbuch ist ein 4-Byte-String, jeder Schlüssel entspricht nur einem Slot, und der Wert im Slot ist die Position dieses Strings.
Anstatt den Cache zu durchsuchen, liest LZ4 jeweils vier Bytes aus der Eingabedatei und sucht dann nach dem Slot, der dem String in der Hashtabelle entspricht, der im Folgenden als der aktuelle String bezeichnet wird.
Wenn du die letzten 12 Zeichen erreicht hast, füge sie direkt in die Ausgabedatei ein.
Wenn im Slot kein Wert zugewiesen ist, bedeutet das, dass die vier Bytes zum ersten Mal erscheinen, diese vier Bytes und Positionen zur Hashtabelle hinzufügen und die Suche fortsetzen.
Wenn es eine Zuweisung im Slot gibt, bedeutet das, dass wir einen passenden Wert gefunden haben.
Wenn der Wert im Slot plus die Größe des Schieberfensters die Position des aktuellen Zeichens <, übersteigt die Übereinstimmung die Größe des Blocks, und das Programm aktualisiert den Wert im Hash-Slot auf die Position der aktuellen Zeichenkette.
LZ4 prüft, ob es einen Hash-Konflikt gab. Wenn die 4 Bytes im Slot nicht mit dem aktuellen String übereinstimmen, muss es einen Hash-Konflikt geben. Der eigene xxhash des Autors ist ebenfalls für seine Effizienz bekannt, aber Konflikte sind unvermeidlich. Im Falle eines Konflikts aktualisiert das Programm auch den Wert im Hash-Slot auf die aktuelle Position der Zeichenkette
Schließlich können wir bestätigen, dass das Match gültig ist, und das Programm prüft weiterhin, ob die nachfolgenden Zeichen in der passenden Zeichenkette gleich sind. Schließlich kopieren Sie alle Zeichen vom Ende des vorherigen gültigen Matches zum Anfang dieses gültigen Matches in die komprimierte Datei und fügen die entsprechende Sequenz dieses gültigen Matches hinzu.
Collet ruft die von LZ4-Sequenzen ausgegebenen Matching-Einheiten auf, und sie bilden die komprimierte LZ4-Datei. Die Details sind wie folgt:
Das Token ist 1 Byte lang, wobei die ersten 4 Wörter die wörtliche Länge und die letzten 4 Wörter die Match-Länge sind. Wie bereits erwähnt, werden alle Zeichen vom Ende des vorherigen gültigen Matches bis zum Beginn dieses gültigen Matches in eine komprimierte Datei kopiert, diese unkomprimierten Dateien sind literal und ihre Länge ist literal length.
Wörtlich gefolgt von einer Abweichung. Wie bei LZ77 beziehen sich Abweichung und Match-Länge auf die Länge der aktuellen Zeichenkette aus ihrem Match, und die Match-Länge bezieht sich auf die Länge der Match-Länge der aktuellen Strings auf dieselbe Zeichenkette im Wörterbuch. Bei der Dekompression geht man hindurch, um die zu kopierende Zeichenkette und die zu kopierende Länge zu finden. Die Größe der Abweichung ist festgelegt.
In der Abbildung nehmen die wörtliche Länge+ und die Match-Länge+, wenn die wörtlichen oder passenden Wörter 4 im Token nicht ausreichen, sie an den entsprechenden Positionen weiter zunehmen. 4 Wörter können 0-15 repräsentieren, und falls es noch mehr gibt, ein Byte hinzufügen, also 255 Byte zur Größe hinzufügen, bis das Byte weniger als 255 ist. In der passenden Länge steht 0 für 4 Bytes.
Die letzten 12 Bytes enden buchstäblich, weil sie direkt kopiert wurden.
Schauen wir uns den Code an (Python ist abstrakter)
Zusammenfassung: Nachdem ich das alles gesagt habe, habe ich immer noch nicht zusammengefasst, warum die LZ4 so schnell ist. Vergleichen wir zunächst die Wörterbuchsuche zwischen LZ77 und LZ4. Das native LZ77 sucht nach Wörterbüchern, indem es nach dem größten Treffer im zu suchenden Cache und im Wörterbuch sucht. Dies ist ein Problem, die größte identische Zeichenkette in zwei Zeichenketten zu finden. Wenn wir keine dynamische Programmierung verwenden, müssen wir im schlimmsten Fall alle Teilstrings eines Strings betrachten und sie dann in einem anderen String abgleichen. Wenn ×wir dynamische Programmierung verwenden, verwenden wir eine Tabelle, um das längste Match in der Dynamik zu halten, was uns nur erlaubt, das Match im Fall von O(m*n) zu vervollständigen. Und das gilt nur für ein Paar Suchcaches und Wörterbücher. Im schlimmsten Fall, falls keine Übereinstimmungen vorliegen, muss LZ77 (die Länge der gesamten Datei – die Länge des zu durchsuchenden Caches) als viele solcher Matching-Probleme zählen. LZ4 verwendet tatsächlich eine größere Ebene dynamischer Programmierung: Es speichert 4 Bytes und deren Positionen in einer Hashtabelle und ordnet dann jedes Mal neue 4 Bytes Daten ab, nur um zu prüfen, ob die Werte in der Hashtabelle gültig sind. Nachdem Sie einen gültigen Matching-Wert gefunden haben, können Sie, wenn Sie sich die Nachverfolgungsdaten der beiden Sätze von Matching-Werten ansehen, auch die längste Übereinstimmung finden. Da jeder Schlüssel der LZ4-Hashtabelle nur einem Slot entspricht, erfordert das Finden, Hinzufügen und Ändern der Hashtabelle nur O(1). Wenn nach dem Matching mehr Übereinstimmungen gefunden werden, sind mehr Gruppenvergleiche nötig, aber in der Gesamtzeit ersetzt diese Vergleiche mehr Zeit, um die Hashtabelle nachzuschlagen, sodass die Gesamtzeit des LZ4-Algorithmus nur O(n) beträgt. Ich muss die Schönheit von Collets Algorithmus bewundern! Um den Algorithmus noch schneller zu machen, setzt Collet die Standardgröße der Hashtabelle auf 16k, was empfohlen wird, nicht mehr als 32k zu überschreiten, sodass sie in den L1-Cache fast aller CPUs (Intel) gelegt werden kann. Jeder weiß, dass das Verhältnis von Geschwindigkeit und Speicher im CPU-L1-Cache sehr unterschiedlich ist, daher ist es nicht überraschend, dass LZ4 schnell läuft, ganz zu schweigen davon, dass die Hash-Gleichung in der Hashtabelle von LZ4 immer noch die schnellste xxhash ist. Natürlich hat ein solches Design auch seine Nachteile. Je kleiner die Hashtabelle, desto weniger Schlüssel hat sie. Das bedeutet, dass mehr Hash-Konflikte auftreten werden, was unvermeidlich ist. Und mehr Hash-Kollisionen bedeuten weniger Matches. Und eine kleinere Hashtabelle bedeutet auch ein kleineres gleitendes Fenster, was bedeutet, dass mehr Matches verworfen werden, weil sie zu weit entfernt sind. Weniger Übereinstimmungen bedeuten ein geringeres Verdichtungsverhältnis, weshalb der LZ4 ein weniger ausgeprägtes Verdichtungsverhältnis hat. Looking Ahead LZ4 bietet eine breite Palette von Anwendungsszenarien. So wie Middle Out in VR im Silicon Valley verwendet wurde, kann LZ4 die Bandbreitenauslastung erhöhen, indem es weniger IOs bringt, allerdings auf Kosten sehr geringer Latenz aufgrund seiner sehr hohen Kompressionsgeschwindigkeit. Es gibt auch eine kleine Vermutung: Wenn es eine CPU mit einem größeren Cache auf Level 1 gibt, kann der LZ4 das Kompressionsverhältnis erhöhen, ohne die Geschwindigkeit zu beeinträchtigen?
Original:Der Hyperlink-Login ist sichtbar. |
Veröffentlicht am 03.01.2022 13:54:23
|
|
|
|
