Unterschied: LZ77 vs. LZ4 vs. LZ4HC (Kompressionsalgorithmen)?

Question

Ich verstehe die LZ77 und LZ78 Algorithmen. Ich lese über LZ4 here und here und gefunden code for it.

Diese Links beschrieben das LZ4-Blockformat. Aber es wäre großartig, wenn jemand erklären könnte (oder mich zu einer Ressource erklären könnte):

Wie unterscheidet sich LZ4 von LZ77?

Wie unterscheidet sich LZ4HC von LZ4?

Welche Idee macht den LZ4HC-Algorithmus so schnell?

Answer 1

LZ4 ist gebaut, um schnell zu komprimieren, wie über 400 MB/s pro Kern. Es eignet sich für Anwendungen, bei denen eine sehr günstige Komprimierung gewünscht wird: Sie versuchen beispielsweise, ein Netzwerk- oder Festplattenformat kompakter zu gestalten, können aber keine CPU-Zeit für die Komprimierung aufwenden. Es ist in einer Familie mit zum Beispiel snappy und LZO. Diese Algorithmen unterscheiden sich von dem beliebten DEFLATE weil:

1. Sie Wiederholungserkennungscode verwenden, der ist schneller (oft ein einfaches hashtable ohne Kollisionserkennung), aber sucht nicht durch alle möglichen Spiele für die beste (das nehmen würde Zeit, führt jedoch zu einer höheren Komprimierung) und kann keine kurzen Übereinstimmungen finden.
2. Sie versuchen nur, Wiederholungen in der Eingabe zu komprimieren - sie versuchen nicht, einige Bytes auszunutzen, die häufiger sind als andere.
3. Eng verwandt mit 2, erzeugen sie Bytes der Ausgabe zu einer Zeit, nicht Bits; das Erlauben von Bruchteil-von-Byte-Codes würde manchmal mehr Kompression erlauben, würde aber mehr CPU-Operationen (möglicherweise Bitverschiebung und Maskierung und Verzweigung) zum Codieren und Decodieren erfordern.
4. Es wurde viel praktische Arbeit geleistet, um ihre Implementierungen auf modernen CPUs schnell zu machen.

Im Vergleich dazu wird DEFLATE bessere Kompression aber komprimiert und dekomprimiert langsamer und hohe Kompressionsalgorithmen wie LZMA, bzip2, LZHAM oder brotli neigen noch mehr Zeit in Anspruch nehmen (obwohl Brotli at its faster settings can compete with zlib). Es gibt viele Unterschiede zwischen den hochkomprimierten Algorithmen, aber im Großen und Ganzen neigen sie dazu, Redundanzen über längere Distanzen zu erfassen, nutzen mehr Kontext, um festzustellen, welche Bytes wahrscheinlich sind, und verwenden kompaktere, aber langsamere Wege, ihre Ergebnisse in Bits auszudrücken.

LZ4HC ist eine "high-compression" Variante von LZ4, die, glaube ich, den obigen Punkt 1 ändert - der Kompressor versucht alle Wiederholungen zu finden und wählt die "beste", um sicherzustellen, dass die Ausgabe klein ist. Dies verbessert die Kompression Verhältnis aber senkt die Komprimierung Geschwindigkeit im Vergleich zu LZ4. Die Dekompressionsgeschwindigkeit ist jedoch nicht verletzt. Wenn Sie also mehrmals komprimieren und dekomprimieren und meistens eine extrem billige Dekompression wünschen, wäre LZ4HC sinnvoll.

Beachten Sie, dass selbst ein schneller Kompressor es einem Core nicht erlaubt, eine große Bandbreite zu sättigen, wie sie von SSDs oder schnellen Verbindungen im Datencenter bereitgestellt wird. Es gibt sogar schnellere Kompressoren mit niedrigeren Verhältnissen, manchmal verwendet zu temporarily pack data in RAM. WKdm und Density sind zwei solcher Kompressoren, und manchmal kann spezialisierte Hardware sehr schnelle Kompression erreichen, wie in Samsung's Exynos chips oder Intel's QuickAssist technology.

Wenn Sie mehr als LZ4 komprimieren möchten, aber mit weniger CPU-Zeit als deflate, schrieb der Autor von LZ4 (Yann Collet) eine Bibliothek namens Zstd; bei seiner stabilen Freisetzung, Facebook posted about how they use it. Es verwendet finite state machines, nicht Huffman-Codes, für die Entropiecodierung; Ich wünschte, ich könnte mehr über die Details sagen, aber zuerst müsste ich etwas darüber nachlesen. Apple schrieb lzfse nach den gleichen Prinzipien. Vor ein paar Jahren veröffentlichte Google eine Bibliothek mit der Bezeichnung gipfeli, die allerdings nicht so gut zu greifen schien. Es gibt auch Projekte, die eine schnellere Komprimierung im Zlib-Format anstreben, wie SLZ und patches to zlib by CloudFlare and Intel.

Im Vergleich zu den schnellsten Kompressoren, fügen Sie diese „mittel“ Packer eine Form von Entropiecodierung, die sie nutzen, wie sind häufiger als andere einige Bytes nehmen zu sagen ist und (in der Tat) setzen in der weniger Bits Ausgabe für die gebräuchlicheren Bytewerte.

Wenn Sie die Latenzzeit und nicht die gesamte CPU-Zeit im Hinterkopf haben und einen langen Datenstrom komprimieren, gibt es Tools für die parallele Komprimierung, wie pigz und pzstd. (Es gibt various experimentelle packers da draußen auch, aber sie existieren mehr Grenzen auf Geschwindigkeit oder Dichte zu drücken, anstatt für den Einsatz heute.)

Also, im Allgemeinen haben Sie ein ziemlich gutes Spektrum an alternativen Kompressoren für verschiedene Anwendungen : LZ4 (oder noch schwächere Speicherkompressoren) für die Echtzeitkomprimierung, DEFLATE als den alten Standard für die ausgeglichene Komprimierung und Zstd und lzfse als neuere Alternativen, und Brotli und andere für die hohe Komprimierung. Wenn Sie von LZ4 über DEFLATE nach Brotli ziehen, müssen Sie mehr Aufwand betreiben, um Daten vorherzusagen und zu codieren und mehr Kompression auf Kosten einer gewissen Geschwindigkeit zu erzielen.