15 Beliebteste Datenkompressionsalgorithmen

Datenkompressionsalgorithmen können als Prozess der Größenreduzierung von Dateien bei gleichzeitiger Beibehaltung der gleichen oder in gewissem Umfang ähnlichen Daten definiert werden. Dies geschieht durch die Eliminierung unnötiger Daten oder durch die Wiederherstellung der Daten für eine höhere Effizienz.

Bei der Komprimierung haben Sie die Möglichkeit, zwischen verlustbehafteten und verlustfreien Methoden zu wählen. Bei der verlustbehafteten Methode werden die Daten dauerhaft gelöscht. Bei der verlustfreien Methode hingegen bleiben Ihre Originaldaten erhalten. Welchen Typ Sie wählen, hängt davon ab, welche Qualität Ihre Dateien haben sollen.
In diesem Artikel finden Sie eine Mischung aus verlustfreien Datenkompressionsalgorithmen und Bild- und Videokompressionsalgorithmen, die auf Deep Learning basieren.

Verlustfreie Datenkompressionsalgorithmen sind normalerweise Wesen, die für die Durchführung der Funktion des Archivs oder anderer hochwertiger Funktionen verwendet werden. Diese Datenkompressionsalgorithmen ermöglichen es, eine Reduzierung der Dateigröße durchzuführen. Es stellt auch sicher, dass Dateien vollständig wiederhergestellt werden können, wenn sie wiederhergestellt werden müssen.

LZ77

LZ77 wurde 1977 angekündigt und als Basis für viele andere verlustfreie Kompressionsalgorithmen bezeichnet. Er verwendet normalerweise die Methode des „Sliding Window“. In dieser Methodik, es kümmert sich um ein Wörterbuch, das die Verwendung von Dreiergruppen für die Darstellung macht:

• Offset- Es kann als der tatsächliche Beginn der Phrase und dem Beginn der Datei bezeichnet werden.
• Run-Länge-es ist definiert als die Menge der Zeichen, die Sie bei der Herstellung einer Phrase helfen.
• Abweichende Zeichen-Dies sind die Vermarkter, die eine neue Phrase anzuzeigen.

Es enthält einen Hinweis darauf, dass die verwendete Phrase vollständig gleich der ursprünglichen Phrase ist und definiert auch, ob es ein anderes Zeichen gibt.

Wenn Sie eine Datei parsen, wird das Wörterbuch dynamisch für die Reflexion des komprimierten Dateninhalts und der Größe auch aktualisiert.

LZR

LZR wurde im Jahr 1981 entwickelt und angekündigt. Michael Rodeh kündigte es an, und er modifizierte es später. Er kann als primäre Alternative für den LZ77-Datenkomprimierungsalgorithmus verwendet werden, aber Sie haben auch die Möglichkeit, ihn für jeden beliebigen Offset innerhalb der Datei zu verwenden. Wenn Sie ihn nicht linear verwenden, benötigt er eine erhebliche Menge an Speicherplatz. Unter dieser Bedingung ist LZ77 die bessere Option für die Verwendung. Dieser Datenkomprimierungsalgorithmus ist einfach zu implementieren und hat das Potenzial für eine sehr hohe Leistung, wenn er in Hardware implementiert wird.

Es ist der Algorithmus, der weit verbreitet ist Unix Datenkomprimierungsalgorithmus Dienstprogramm komprimieren und ist in der GIF-Bildformat verwendet. Er war der erste Datenkomprimierungsalgorithmus, der auf Computern weit verbreitet war. Eine große englische Textdatei kann in der Regel von LZW auf etwa die Hälfte ihrer ursprünglichen Größe komprimiert werden.

LZSS

LZSS steht für Lempel Ziv Storer Szymanski und wurde im Jahr 1982 entwickelt und angekündigt. Es handelt sich um einen Datenkomprimierungsalgorithmus, der LZ77 verbessert. Bei der Komprimierung wird eine Methode eingesetzt, die überwacht, ob eine Ersetzung die Dateigröße verringert. Wenn dies nicht der Fall ist, wird die Eingabe in ihrer ursprünglichen Form belassen. Er bevorzugt auch keine abweichenden Zeichen, sondern nur Offset-Längen-Paare.

Dieser Algorithmus wird hauptsächlich für die Archivierung von Dateien in verschiedenen Formaten wie RAR oder ZIP oder für die Komprimierung von Netzwerkdaten verwendet.

Er kann als eine Wörterbuch-Codierungstechnik bezeichnet werden. LZSS versucht, eine Zeichenfolge durch einen Verweis auf eine Wörterbuchposition derselben Zeichenfolge zu ersetzen. Der Hauptunterschied zwischen LZ77 und LZSS besteht darin, dass bei LZ77 der Wörterbuchverweis länger sein kann als die zu ersetzende Zeichenfolge. In LZSS werden solche Verweise weggelassen, wenn die Länge unter dem „Break-even“-Punkt liegt.

Deflate

Deflate ist ein verlustfreies Dateiformat für Datenkomprimierungsalgorithmen, das eine Kombination aus LZSS und Huffman-Kodierung verwendet. Es wurde von Phil Katz im Jahr 1993 entwickelt. Die Huffman-Kodierung ist ebenfalls ein Algorithmus, der im Jahr 1952 entwickelt wurde. Er kann als ein Entropie-Kodierungsalgorithmus definiert werden, der Ihnen hilft, Ihren Code auf der Grundlage der Häufigkeit des Zeichens zuzuordnen.

Katz entwarf auch den ursprünglichen Algorithmus, der zum Aufbau von Deflate-Streams verwendet wird. Wie es im RFC-Dokument heißt, war man der Meinung, dass ein Algorithmus, der Deflate-Dateien erzeugt, auf eine Weise implementiert werden kann, die nicht durch Patente geschützt ist. Dies führte zur weit verbreiteten Verwendung des Algorithmus, zusätzlich zum ZIP-Dateiformat, das der Hauptzweck von Katz war, es zu entwickeln. Das Patent ist nicht mehr verfügbar.

LZMA

LZMA steht für den Lempel-Ziv-Markov-Ketten-Algorithmus und wurde im Jahr 1998 entwickelt und veröffentlicht. Er kann auch als eine Modifikation des LZ77 bezeichnet werden. Diese Modifikation wurde für das -Zip-Archivierungsprogramm mit dem .7z-Format entwickelt. Es wird die Methode der Kettenkompression verwendet, die das modifizierte LZ77 auf Bit- statt auf Byte-Ebene implementiert. Die Ausgabe wird durch arithmetische Kodierung weiterverarbeitet, um eine stärkere Komprimierung zu erreichen.

Die Leistung der anderen Komprimierungsschritte ist von der genauen Implementierung abhängig. Dieser Datenkompressionsalgorithmus verwendet ein Wörterbuchkompressionsschema, das dem LZ77-Algorithmus, der von Abraham Lempel und Jacob Ziv im Jahr 1977 veröffentlicht wurde, sehr ähnlich ist. Er zeichnet sich ebenfalls durch ein hohes Kompressionsverhältnis und eine variable Größe des Kompressionswörterbuchs aus. Die Geschwindigkeit der Dekompression ist jedoch ähnlich wie bei anderen gängigen Kompressionsalgorithmen.

LZMA2

LZMA2 wurde im Jahr 2009 entwickelt und veröffentlicht. Es kann auch als Modifikation von LZMA definiert werden. Es macht LZMA besser, indem es seine Leistung mit größeren Multithreading-Fähigkeiten verbessert. LZMA2 bietet auch eine verbesserte Handhabung von inkompressiblen Daten. Es handelt sich um ein einfaches Containerformat, das sowohl unkomprimierte Daten als auch LZMA-Daten enthalten kann, und zwar mit mehreren verschiedenen LZMA-Kodierungsparametern.

LZMA2 unterstützt eine beliebig skalierbare Multithread-Komprimierung und -Dekomprimierung sowie eine effiziente Komprimierung von Daten, die teilweise inkomprimierbar sind. Es kann jedoch einige Sicherheitsprobleme haben und kann unsicher und weniger effizient als LZMA sein. Mit einfachen Worten: Es kann für Sie nützlich sein, aber es ist im Vergleich zu LZMA nicht so sicher.

Multi-Layer Perceptron (MLP)-basierte Kompression

MLP kann als eine Technologie definiert werden, die mehrere Neuronenschichten für die Eingabe, Verarbeitung und Ausgabe von Daten verwendet. Sie kann für Aufgaben der Dimensionsreduzierung und der Datenkompression eingesetzt werden. Der MLP-basierte Algorithmus wurde erstmals im Jahr 1988 entwickelt und reiht sich in die bereits bestehenden Prozesse ein:

• Binärkodierung – Standard-Zweisymbolkodierung.
• Quantisierung – Probleme der Eingabe von einer kontinuierlichen Menge in eine diskrete Menge.
• Transformation des räumlichen Bereichs – pixelweise Änderung der Daten.

Zur Bestimmung des optimalen Binärcodes verwendet der MLP-Algorithmus die Ergebnisse der oben genannten Prozesse in einem neuronalen Netz zur Dekomposition.

Weiterhin wurde dieser Algorithmus mit intuitiven Techniken modifiziert, die eine genaue Annäherung der Daten vollständig auf der Grundlage benachbarter Daten durch Backpropagation ermöglichen. Er kann bei der Kompression von Bild- und Videodaten sehr nützlich sein.

Dee Coder- Deep Neural Network Based Video Compression

Deep Coder ist definiert als ein auf Convolutional Neural Network (CNN) basierendes Framework. Dies macht die Darstellung einer Alternative zu den Videokompressionstechniken, die wir so lange verwendet haben. Für prädiktive und residuale Signale werden bei diesem Modell verschiedene Convolutional Neural Networks (CNNs) eingesetzt.

Es führt die Kodierung von Merkmalskarten in den Binärstrom mit Hilfe von Skalarquantisierung und einem sehr alten und traditionellen Dateikompressionsalgorithmus namens Huffman-Kodierung durch. Es wird behauptet, dass dieses Modell in der Lage ist, im Vergleich zum bekannten H.264/AVC-Videokodierungsstandard eine überlegene Leistung zu erbringen.

Convolutional Neural Network (CNN) – Basierende Kompression

CNNs sind als neuronale Netze mit verschiedenen Schichten definiert. Sie werden hauptsächlich für die Erkennung von Bildern und die Erkennung von Merkmalen verwendet. In dem Moment, in dem man es auf die Komprimierung anwendet, nutzen diese Netze die Faltung, um die Verbindung zwischen benachbarten Pixeln zu berechnen. Im Vergleich zu MLP-basierten Algorithmen zeigen CNNs bessere Komprimierungsergebnisse als diese.

Sie bieten auch eine verbesserte Superauflösungsleistung und Artefaktreduzierung. Darüber hinaus verbessern CNN-basierte Datenkompressionsalgorithmen die Qualität von JPEG-Bildern. Dies geschieht durch die Verringerung des Spitzen-Signal-Rausch-Verhältnisses und der strukturellen Ähnlichkeit.

CNN-basierte Komprimierung kann auch mit der Leistung des High-Efficiency Video Coding-Standards mithalten. Dies geschieht durch den Einsatz von Entropie-Schätzung. Es kann auch sehr nützlich für Sie bei der Durchführung der Kompression von Dateien sein.

Generative Adversarial Network (GAN)- Based Compression

GANs können als eine Alternative von neuronalen Netzen definiert werden, die zwei konkurrierende Netze verwenden. Dies geschieht, um genauere Analysen und Vorhersagen zu erstellen. Im Jahr 2017 wurden erstmals GAN-basierte Algorithmen entwickelt. Diese Algorithmen zur Datenkomprimierung können die Dateien im Vergleich zu herkömmlichen, häufig verwendeten Methoden wie JPEG oder WebP um mehr als das Zweieinhalbfache komprimieren.

GAN-basierte Algorithmen können für die Komprimierung in Echtzeit verwendet werden, wobei die parallele Verarbeitung gemeinsam genutzt wird. Dieser Algorithmus komprimiert die Bilder vollständig auf der Grundlage der am besten passenden Merkmale.

Bei der Dekodierung werden die Bilder auf der Grundlage der Vorhersagen rekonstruiert, die durch diese Merkmale gemacht wurden. Im Vergleich zur CNN-basierten Komprimierung liefert die GAN-basierte Komprimierung durch die Eliminierung von Verlusten sehr hochwertige Bilder.

Prediction by partial matching (PPM)

PPM ist eine adaptive statistische Datenkomprimierungstechnik, die auf Kontextmodellierung und Vorhersage basiert. Diese Modelle verwenden eine Reihe von früheren Symbolen im unkomprimierten Symbolstrom, um das nächste Symbol im Strom vorherzusagen. PPM-Algorithmen können auch zum Clustern von Daten in vorhergesagte Gruppen in der Clusteranalyse verwendet werden.
Die Anzahl der vorherigen Symbole, n, bestimmt die Reihenfolge des PPM-Modells, das als PPM(n) bezeichnet wird.

Es gibt auch unbegrenzte Varianten, bei denen der Kontext keine Längenbeschränkungen hat und als PPM bezeichnet werden. Wenn auf der Grundlage aller n Kontextsymbole keine Vorhersage gemacht werden kann, wird eine Vorhersage mit n – 1 Symbol versucht. Dieser Vorgang wird so lange wiederholt, bis eine Übereinstimmung gefunden wird oder keine weiteren Symbole im Kontext verbleiben. An diesem Punkt wird eine feste Vorhersage getroffen.
PPM-Komprimierungsimplementierungen unterscheiden sich stark in anderen Details. Die eigentliche Symbolauswahl wird in der Regel mit arithmetischer Kodierung aufgezeichnet, obwohl auch eine Huffman-Kodierung oder sogar eine Art von Wörterbuchkodierungstechnik möglich ist.

Run-length encoding (RLE)

RLW ist eine Form der verlustfreien Datenkompression, bei der Datenläufe (Sequenzen, in denen derselbe Datenwert in vielen aufeinanderfolgenden Datenelementen vorkommt) als ein einziger Datenwert und eine Zählung gespeichert werden, und nicht als der ursprüngliche Lauf. Dies ist besonders nützlich bei Daten, die viele solcher Läufe enthalten.

Zum Beispiel einfache Grafiken wie Icons, Strichzeichnungen, Conway’s Game of Life und Animationen. Es ist nicht nützlich für Dateien, die nicht viele Durchläufe haben, da es die Dateigröße stark erhöhen könnte.

RLE kann auch verwendet werden, um sich auf ein frühes Grafikdateiformat zu beziehen, das von CompuServe für die Komprimierung von Schwarz-Weiß-Bildern unterstützt wurde, aber weitgehend durch das spätere Graphics Interchange Format (GIF) verdrängt wurde. RLE bezieht sich auch auf ein wenig verwendetes Bildformat in Windows 3.x, mit der Erweiterung rule, die eine Run Length Encoded Bitmap ist, die zur Komprimierung des Windows 3.x Startbildschirms verwendet wird.

bzip2

bzip2 ist ein freies und quelloffenes Datenkompressionsprogramm, das den Burrows-Wheeler-Algorithmus verwendet. Es komprimiert nur einzelne Dateien und ist kein Dateiarchivierungsprogramm. Es wird von Julian Seward entwickelt und von Federico Mena gepflegt. Seward veröffentlichte die erste öffentliche Version von bzip2, Version 0.15, im Juli 1996. Die Stabilität und Popularität des Kompressors wuchs in den nächsten Jahren, und Seward veröffentlichte Ende 2000 die Version 1.0.

Nach einer neunjährigen Unterbrechung der Aktualisierungen für das Projekt seit 2010. Am 4. Juni 2019 übernahm Federico Mena die Maintainerschaft des bzip2-Projekts. bzip2 komprimiert Daten in Blöcken mit einer Größe zwischen 100 und 900 kB.

Es verwendet die Burrows-Wheeler-Transformation, um häufig wiederkehrende Zeichensequenzen in Strings aus identischen Buchstaben umzuwandeln. Anschließend wendet es die Move-to-Front-Transformation und die Huffman-Kodierung an. Der Vorgänger von bzip2, bzip, verwendete arithmetische Kodierung anstelle von Huffman. Die Änderung wurde aufgrund einer Softwarepatent-Beschränkung vorgenommen.

Huffman-Kodierung

Der Huffman-Code ist eine besondere Art von optimalem Präfix-Code, der häufig für die verlustfreie Datenkompression verwendet wird. Um einen solchen Code zu finden oder zu verwenden, wird die Huffman-Kodierung verwendet, ein Algorithmus, der von David A. Huffman als Doktorand am MIT entwickelt und 1952 in der Abhandlung „A Method for the Construction of Minimum-Redundancy Codes“ veröffentlicht wurde.

Die Ausgabe von Huffmans Algorithmus kann als eine Codetabelle variabler Länge für die Kodierung eines Quellensymbols (z. B. eines Zeichens in einer Datei) betrachtet werden. Der Algorithmus leitet diese Tabelle aus der geschätzten Wahrscheinlichkeit oder Häufigkeit des Auftretens (Gewicht) für jeden möglichen Wert des Quellensymbols ab.

Wie bei anderen Entropie-Kodierungsmethoden werden häufigere Symbole im Allgemeinen mit weniger Bits dargestellt als weniger häufige Symbole. Die Huffman-Methode kann effizient implementiert werden. Sie findet einen Code in einer Zeit, die linear zur Anzahl der Eingangsgewichte ist, wenn diese Gewichte sortiert sind.

ZStandard

Zstandard (oder zstd) ist ein verlustfreier Datenkomprimierungsalgorithmus, der von Yann Collet bei Facebook entwickelt wurde. Zstd ist die Referenzimplementierung in C. Version 1 dieser Implementierung wurde am 31. August 2016 als freie Software veröffentlicht.
Zstandard wurde entwickelt, um eine Kompressionsrate zu erreichen, die mit der des DEFLATE-Algorithmus (1991 entwickelt und in den ursprünglichen ZIP- und gzip-Programmen verwendet) vergleichbar ist, aber schneller, insbesondere bei der Dekompression. Der Algorithmus ist einstellbar, wobei die Komprimierungsstufen von minus 5 (am schnellsten) bis 22 (langsamste Komprimierungsgeschwindigkeit, aber bestes Komprimierungsverhältnis) reichen.

Zstd erreicht bei maximaler Komprimierung ein Kompressionsverhältnis, das dem von LZMA, LZAHM und PPM nahe kommt. Es schneidet besser ab als LZA oder bzip2. Zstandard erreicht die aktuelle Pareto-Grenze, da es schneller dekomprimiert als jeder andere derzeit verfügbare Algorithmus mit einer ähnlichen oder besseren Kompressionsrate

Wörterbücher können einen großen Einfluss auf die Kompressionsrate von kleinen Dateien haben, daher kann Zstandard ein vom Benutzer bereitgestelltes Kompressionswörterbuch verwenden. Zstandard bietet auch einen Trainingsmodus, mit dem ein Wörterbuch aus einer Reihe von Beispielen erstellt werden kann.

Fazit

Diese Datenkomprimierungsalgorithmen helfen Ihnen, die Dateigröße zu optimieren. Verschiedene Arten von Datenkomprimierungsalgorithmen liefern unterschiedliche Ergebnisse. Wenn Sie hier jedoch nicht den richtigen Algorithmus finden, können Sie einen Blick auf diesen Leitfaden werfen und Ihre Suche verfeinern. An Algorithmen herrscht kein Mangel, aber Sie müssen bei der Suche nach dem richtigen Algorithmus für Ihr Projekt sehr genau sein.

Ich hoffe, dieser Artikel war hilfreich für Sie bei der Auswahl des besten Datenkomprimierungsalgorithmus für Ihre Bedürfnisse. Vielen Dank, dass Sie diesen Artikel gelesen haben. Sie können auch die besten Verschlüsselungs- und Hashing-Algorithmen lesen.

Stay Tuned