Komprimierung in Big Data: Typen und Techniken

\

Einführung

Dieser Artikel behandelt Komprimierung im Big-Data-Kontext und deckt die Arten und Methoden der Komprimierung ab. Ich werde auch hervorheben, warum und wann jede Art und Methode verwendet werden sollte.

\

Was ist Komprimierung?

Gemäß der allgemeinen englischen Definition von Komprimierung bezieht sich diese auf die Reduzierung von etwas, um weniger Platz einzunehmen. In der Informatik ist Komprimierung der Prozess der Reduzierung von Daten auf eine kleinere Größe. Daten können in diesem Fall in Text-, Audio-, Videodateien usw. dargestellt werden. Denken Sie daran als alles, was Sie auf der Festplatte Ihres Computers speichern, als Daten, die in verschiedenen Formaten dargestellt werden. Um eine technischere Definition zu geben, ist Komprimierung der Prozess der Codierung von Daten, um weniger Bits zu verwenden.

\ Es gibt mehrere Gründe, Daten zu komprimieren. Der häufigste und intuitivste Grund ist das Einsparen von Speicherplatz. Andere Gründe ergeben sich daraus, dass die Daten kleiner sind. Die Vorteile der Arbeit mit kleineren Daten umfassen:

1. Schnellere Datenübertragungszeit: Komprimierte Daten sind kleiner und benötigen weniger Zeit für die Übertragung von der Quelle zum Ziel.
2. Reduzierter Bandbreitenverbrauch: Dieser Grund ist stark mit dem Vorteil der schnelleren Datenübertragung verbunden. Komprimierte Daten nutzen weniger Netzwerkbandbreite, wodurch der Durchsatz erhöht und die Latenz reduziert wird.
3. Verbesserte Leistung für digitale Systeme, die stark auf Daten angewiesen sind: Dies ist bei Systemen ersichtlich, die auf die Verarbeitung von Daten angewiesen sind. Diese Systeme nutzen Komprimierung, um die Leistung der Systeme zu verbessern, indem sie das Volumen der zu verarbeitenden Daten reduzieren. Bitte beachten Sie, dass dies systemspezifisch sein kann und von der Verwendung der geeigneten Kompressionstechnik abhängt. Kompressionstechniken werden später in diesem Artikel besprochen.
4. Kosteneffizienz: Cloud-Dienste berechnen die Speicherung von Daten. Durch die Nutzung von weniger Speicher werden Kosteneinsparungen eingeführt, insbesondere in Big-Data-Systemen.

\ Andere Gründe für die Komprimierung hängen von verschiedenen Kompressionstechniken und -formaten ab. Einige Verschlüsselungsalgorithmen können als Kompressionsmethode verwendet werden. Dabei wird eine Sicherheitsebene für die zuvor besprochenen Gründe zur Datenkomprimierung einbezogen. Darüber hinaus bringt die Verwendung gängiger Kompressionsformate Kompatibilität und Raum für Erweiterbarkeit zu externen Systemen für Integrationszwecke.

\ Es ist erwähnenswert, dass die Gründe für die Komprimierung auch wie Vorteile klingen. Die Komprimierung ist jedoch nicht ohne Kompromisse. Ein häufiger Kompromiss bei der Komprimierung ist der Bedarf an Dekomprimierung, was für ressourcenbeschränkte Systeme besorgniserregend sein kann. Andere Kompromisse hängen von der Kompressionstechnik und der Art der verwendeten Daten ab.

\

Komprimierungsarten

Um die verschiedenen Techniken zur Komprimierung von Daten zu diskutieren, werde ich zunächst die Komprimierung in 2 Hauptkategorien einteilen. Dieser Artikel wird dann die für jede Kategorie relevanten Techniken diskutieren. Die Komprimierung kann grob in verlustbehaftete und verlustfreie Komprimierung eingeteilt werden.

\ Wie die Namen bereits verraten, was sie bedeuten, sind verlustbehaftete Kompressionstechniken Techniken, die die vollständige Wiedergabetreue der Daten nicht bewahren. Einfach ausgedrückt, werden einige Daten verworfen, aber nicht genug, um das, was die Daten darstellen, unkenntlich zu machen. Daher kann die verlustbehaftete Komprimierung im Vergleich zur verlustfreien Komprimierung, die in Kürze eingeführt wird, ein sehr hohes Kompressionsniveau bieten.

\ Ein Merkmal der verlustbehafteten Komprimierung ist, dass sie irreversibel ist, d.h., wenn die komprimierte Datei vorgelegt wird, kann man die Rohdaten nicht mit ihrer ursprünglichen Wiedergabetreue wiederherstellen. Bestimmte Dateien und Dateiformate sind für verlustbehaftete Komprimierung geeignet. Sie wird typischerweise für Bilder, Audio und Videos verwendet. Zum Beispiel eignen sich JPEG-formatierte Bilder gut für die Komprimierung, und durch die Komprimierung eines JPEG-Bildes kann der Ersteller oder Editor wählen, wie viel Verlust eingeführt werden soll.

\ Andererseits ist die verlustfreie Komprimierung reversibel, was bedeutet, dass bei der Komprimierung alle Daten erhalten bleiben und während der Dekomprimierung vollständig wiederhergestellt werden. Dies impliziert, dass die verlustfreie Komprimierung für textähnliche Dateien geeignet ist, und in der Data-Warehouse- und Lakehouse-Welt wäre sie die einzige relevante Art zu verwenden. Einige Audio- (FLAC und ALAC) und Bilddatei- (GIF, PNG usw.) Formate funktionieren gut mit dieser Komprimierungsart.

Auswahl einer Methode

Es gibt keine allgemein beste Kompressionsmethode. Verschiedene Faktoren fließen in die Auswahl ein, welche Methode von Fall zu Fall geeignet wäre. Um dies mit Beispielen zu untermauern: Ein Dateningenieur in der Finanzbranche, der an gespeicherten tabellarischen Daten arbeitet, würde aufgrund der Auswirkungen fehlender Daten bei der Erstellung genauer Berichte tendenziell verlustfreie Komprimierung verwenden. Alternativ könnte verlustbehaftete Komprimierung der richtige Weg sein, um die Webseite mit vielen Bildern zu optimieren, indem die Bilder komprimiert und die Ladeelemente durch die Verschlankung der Website reduziert werden. Daher ist es entscheidend, eine Bewertung durchzuführen, um die am besten geeignete Kompressionsmethode zu bestimmen, die mit den Geschäftsanforderungen übereinstimmt.

Kompressionstechniken

Dieser Abschnitt behandelt nur die gängigen Kompressionstechniken für sowohl verlustbehaftete als auch verlustfreie Komprimierung. Bitte beachten Sie, dass dies in keiner Weise erschöpfend ist. Darüber hinaus können die besprochenen Techniken leichte Variationen aufweisen, um ihre Leistung zu verbessern, wie durch verschiedene Forschungen unterstützt.

Verlustfreie Kompressionstechniken

Drei gängige verlustfreie Techniken sind die Lauflängenkodierung (RLE), Huffman-Kodierung und die Lempel-Ziv-Welch-Techniken.

\ Lauflängenkodierung: RLE basiert auf der Kodierung von Daten, sodass sie Sequenzen sich wiederholender Daten durch ein einzelnes Datenstück und die Anzahl dieses Datenstücks ersetzt. Sie ist effektiv für lange Läufe sich wiederholender Daten. Auch Datensätze mit Dimensionen (Feldern), die von einem niedrigen bis zu einem hohen Kardinalitätsniveau sortiert sind, profitieren von RLE.

\ Nehmen Sie zum Beispiel eine einfache Zeichenkette wie AAAAABBCDDD. RLE komprimiert die Daten zu A(5)B(2)C(1)D(3). Um praktischer zu sein, nehmen Sie eine Tabelle im Bild unten.

\ Abbildung 1 - vor RLE. Es ist wichtig zu beobachten, dass das Kardinalitätsniveau in den Feldern von links nach rechts zunimmt

Abbildung 2 - Nach RLE

Da RLE von Läufen wiederholter Felder abhängt, und im zweiten Beispiel die Kardinalität und die Sortierreihenfolge der Daten, kann der Mouse -Datensatz in der Elementspalte nicht einfach zu Mouse (3) komprimiert werden, weil die vorhergehende Spalte alle Werte in IT, Mouse und HR, Mouse aufteilt. Bestimmte Dateiformate sind mit RLE kompatibel, wie Bitmap-Dateiformate wie TIFF, BMP usw. Parquet-Dateien unterstützen auch RLE, was sie in modernen Data Lakehouses mit Object-Storage wie S3 oder GCS sehr nützlich macht.

\ Huffman-Kodierung: Sie basiert auf statistischer Modellierung, die den Werten in den Rohdaten variable Codewortlängen zuweist, basierend auf der Häufigkeit, mit der sie in den Rohdaten auftreten. Die Darstellung dieser Modellierung kann als Huffman-Baum bezeichnet werden, der einem binären Baum ähnelt. Dieser Baum wird dann verwendet, um für jeden Wert in den Rohdaten einen Huffman-Code zu erstellen. Der Algorithmus priorisiert die Kodierung der häufigsten Werte in den wenigsten möglichen Bits.

\ Nehmen wir die gleichen Daten, die im RLE-Beispiel verwendet wurden AAAAABBCDDD. Der entsprechende Huffman-Baum sieht so aus.

\ Huffman-Baum

Aus dem Baum können wir sehen, dass der Buchstabe A durch 0 dargestellt wird, ebenso wird D durch 10 dargestellt. Im Vergleich zu den Buchstaben B: 111 und C:110 beobachten wir, dass A und D durch weniger Bits dargestellt werden. Dies liegt daran, dass sie eine höhere Frequenz haben; daher repräsentiert der Huffman-Algorithmus sie durch weniger Bits. Die resultierenden komprimierten Daten werden zu 00000111111110101010.

\ Huffman-Kodierung verwendet die Präfixregel, die besagt, dass der Code, der ein Zeichen darstellt, nicht im Präfix eines anderen Codes vorhanden sein sollte. Zum Beispiel kann ein gültiger Huffman-Code nicht die Buchstaben c und d mit C: 00 und D: 000 darstellen, da die Darstellung von C ein Präfix von D ist.

\ Um dies in Aktion zu sehen, hat der Computer Science Field Guide einen Huffman Tree Generator mit dem Sie spielen können.

\ Lempel–Ziv–Welch-Kodierung: Sie wurde 1984 von Abraham Lempel, Jacob Ziv und Terry Welch erstellt und ist nach den Erstellern benannt, offensichtlich 😅. Ähnlich wie RLE und Huffman-Kodierung funktioniert LZW gut mit Daten, die viele wiederholte Daten enthalten. Der LZW-Algorithmus ist wörterbuchbasiert und erstellt ein Wörterbuch mit Schlüssel-Wert-Paaren häufig gesehener Muster in den Rohdaten. Ein solches Wörterbuch kann auch als Code-Tabelle bezeichnet werden. Zur Veranschaulichung, wie diese Technik funktioniert, nehmen wir an, unsere Rohdaten werden durch ABBABABABA dargestellt. Wenn sie durch den Algorithmus mit einer Konfiguration von A-Z als möglichen Werten geleitet werden, sieht die resultierende Code-Tabelle so aus:

\ LZW Code-Tabelle

Aus der obigen Code-Tabelle gibt es ein Schlüssel-Wert-Paar für alle Buchstaben A-Z und Schlüssel-Wert-Paare für Muster wie AB, BB, BA und ABA. Durch eine kürzere Darstellung dieser Muster kann der LZW-Algorithmus die Rohdaten komprimieren, indem er sie in weniger Bits kodiert. Daher ist die komprimierte Version unter Verwendung der aus dieser Eingabe generierten Code-Tabelle 0 1 1 26 29 28. Es ist wichtig, die Leerzeichen in den komprimierten Daten zu bemerken. Man könnte sie als das Ende eines Zeichens betrachten, sodass der Decoder eine 1,0 nicht als 10 interpretiert, da sie unterschiedliche Bedeutungen haben.

\ LZW ist normalerweise universell einsetzbar und wird heute weit verbreitet. Es ist in viele Unix/Linux-basierte Betriebssysteme hinter dem compress Shell-Befehl integriert. Auch gängige Dateiformate, die mit LZW kompatibel sind, sind GIF, TIFF und PDF. Weitere Anwendungen der LZW-Komprimierung können im Bereich der natürlichen Sprachverarbeitung gesehen werden, wie in diesem Papier über Tokenisierung in NLP diskutiert.

\ RLE, Huffman-Kodierung und LZW-Kodierung sind nur gängige Beispiele. Verlustfreie Kompressionstechniken gehen über diese drei (3) oben beschriebenen hinaus. Andere Techniken umfassen DEFLATE, das eine Kombination aus Huffman- und LZW-Kodierung - speziell LZ77 - verwendet.

Verlustbehaftete Kompressionstechniken

In diesem Abschnitt werden wir uns zwei Arten der verlustbehafteten Komprimierung ansehen. Denken Sie daran, dass verlustbehaftete Komprimierung einen Verlust der Originaldaten einführt, was bedeutet, dass nicht alle Daten erhalten bleiben.

\ Diskrete Cosinustransformation (DCT): Diese Kompressionsmethode wird hauptsächlich in Audio-, Bild- und Videodateien verwendet und wird auch häufig als Blockkomprimierung bezeichnet. Sie verwendet eine mathematische Funktion - die Cosinusfunktion, wie der Name schon sagt - um Blöcke der Originaldaten in Frequenzen umzuwandeln. Die Datenblöcke sind normalerweise eine Matrix von 8x8, 4x4 und so weiter, in dieser Größenordnung.

\ Die Komprimierung erfolgt beim Umgang mit den hohen Frequenzen, die in den Daten auftreten, sobald die Rohdaten mithilfe der mathematischen Funktion in den Frequenzbereich übersetzt werden. Der Gesamtprozess der Verwendung von DCT zur Komprimierung ist:

• Rohdaten in Blöcke aufteilen. Zum Beispiel könnte dies bei der Bildkomprimierung 8x8 Pixel sein.
• Die mathematische Funktion anwenden, um die Datenblöcke in Frequenzen umzuwandeln. Dies führt zu einigen hohen Frequenzen und niedrigen Frequenzen.
• Die hohen Frequenzen werden dann reduziert oder entfernt, abhängig vom akzeptablen Grad des Verlustes, den man einführen möchte. Hier wird es wirklich zur verlustbehafteten Komprimierung.
• Um zurück zu darstellbaren Daten zu konvertieren, werden alle verbleibenden Frequenzen durch eine Inverse Diskrete Cosinustransformation - IDCT - geleitet, um die Daten aus den Frequenzen wiederherzustellen.

\ DCT wird heute in verschiedenen Bereichen weit verbreitet, nicht nur bei der Komprimierung, sondern auch bei der Signalverarbeitung. Gängige Dateiformate, die mit DCT kompatibel sind, sind JPEG (Bilder), MP3 (Audio) und MPEG (Video). Darüber hinaus kann DCT hohe Komprimierungsverhältnisse erreichen, was es für digitale Systeme mit vielen Bildern geeignet macht, wie Webseiten im Internet.

\ Fraktale Komprimierung: Ein Fraktal ist ein sich selbst wiederholendes unendliches Muster, das sich in verschiedenen Maßstäben wiederholt. Von jedem Punkt auf der Skala aus betrachtet, sieht das Muster ähnlich aus. Da die Muster in jedem Maßstab ähnlich sind, reduziert die fraktale Komprimierung den Maßstab von „großen" Fraktalen, um die Größe der Daten zu reduzieren.

\ Beispiele für Fraktale

Fraktale Komprimierung wurde in den 1980er Jahren von Michael Barnsley eingeführt. Die allgemeine Idee bei Verwendung eines Bildes ist, dass, wenn ein Bild mehrere Teile enthält, die gleich aussehen, warum sollte man sie zweimal speichern? Um dies zu tun, macht die fraktale Komprimierung Folgendes:

• Teilt das Bild in nicht überlappende Blöcke auf, die als Bereichsblöcke bekannt sind. Dies könnten Bereichsblöcke von 8x8, 16x16 Pixeln usw. sein.
• Es scannt das Bild nach sich selbst wiederholenden Mustern (fraktalen Mustern). Unter Verwendung der Bereichsblöcke findet der Algorithmus größere Abschnitte des Bildes, die diesen Bereichsblöcken ähnlich sind. Diese größeren Abschnitte werden als Domänenblöcke bezeichnet.
• Eine Transformationsfunktion wird dann auf den Domänenblock angewendet, um die Bereichsblöcke zu approximieren. Diese Transformationsfunktionen sind mathematische Funktionen wie Skalierung, Verschiebung, Rotation usw. Sie können auch als Transformationen bezeichnet werden. Diese Transformationen werden in Bezug auf fraktale Komprimierung als fraktale Codes bezeichnet.
• Die Daten werden dann in diese Transformationsfunktionen kodiert. Anstatt die Pixel-für-Pixel-Daten zu speichern, werden die Transformationen gespeichert. Diese Transformationen sind die Regeln, die beschreiben, wie das Bild aus Domänenblöcken rekonstruiert werden kann.

\ Mit den fraktalen Codes wird das Bild mithilfe eines iterativen Prozesses rekonstruiert. Dieser Prozess kann rechenintensiv sein, aber die fraktale Komprimierung könnte ein hohes Kompressionsverhältnis im Vergleich zu anderen Kompressionstechniken erreichen. Aufgrund ihrer Abhängigkeit von sich selbst wiederholenden Mustern würde sie bei Daten besser abschneiden, die solche sich selbst wiederholenden Muster aufweisen. Beispiele wären Landschaftsfotografien (Bilder der Natur) und DNA-Bilder.

\ Es gibt andere verlustbehaftete Kompressionstechniken, wie die Diskrete Wavelet-Transformation, Quantisierung. Diese Techniken werden normalerweise in Bildern, Audio- und Videodateien verwendet und sind für bestimmte Typen oder Dateiformate - JPEG, MP3 - für jeden Dateityp geeignet.

\ Verlustbehaftete Komprimierung hat im Allgemeinen höhere Komprimierungsverhältnisse als verlustfreie Komprimierung und erwartet manchmal, dass der Benutzer die Menge des im Voraus einzuführenden Verlustes kennt. Es ist wichtig zu betonen, dass die Wahl der Kompressionsmethode und -technik von mehreren Faktoren abhängt. Im Kern dieser Faktoren stehen das Datenformat und das gewünschte Ergebnis.

TL;DR

Insgesamt behandelt dieser Beitrag die Komprimierung in der Welt der Daten. Er stützt sich stark auf den bestehenden Wissensstand in Informatik und Informationstheorie. Komprimieren bedeutet, das Volumen zu reduzieren, das eine Entität einnimmt, und im Bereich der Daten bezieht sich Volumen auf Speicherplatz. Komprimierung in digitalen Systemen hat viele Vorteile, wenn sie richtig durchgeführt wird. Das Offensichtliche ist, dass sie den Platz reduziert und Raum gibt, mehr Daten zu speichern. Andere Vorteile umfassen schnellere Übertragung, geringere Bandbreitennutzung und allgemeine Verbesserung der Effizienz des Systems. Denken Sie daran, dies gilt, wenn es richtig gemacht wird.

\ Um die Vorteile der Komprimierung zu nutzen, ist es wichtig zu wissen, welche Art zu verwenden ist. Komprimierung ist entweder verlustbehaftet oder verlustfrei. Verlustbehaftete Komprimierung führt einen Verlust in den Originaldaten ein, der normalerweise irreversibel ist, während verlustfreie Komprimierung die Daten komprimiert und alle in den Originaldaten enthaltenen Informationen beibehält. Darüber hinaus gibt es Diskussionen über hybride Komprimierungstypen, aber ich denke, eine Kombination aus verlustbehaftet und verlustfrei ist einfach verlustbehaftet. Lassen Sie mich in den Kommentaren wissen, was Sie denken.

\ Schließlich wurden verschiedene Techniken sowohl für verlustbehaftete als auch für verlustfreie Komprimierung eingeführt. Die Liste der Techniken und Erklärungen dieser Techniken ist weder erschöpfend noch umfassend. Ich betrachte sie nur als einen guten Start, um Ihnen eine Vorstellung davon zu geben, wie jede Technik funktioniert. Abschließend habe ich zusätzliche Ressourcen hinzugefügt, um Ihnen zu helfen, weiter zu recherchieren und tiefer über Komprimierung in Big Data zu lesen.

Zusätzliche Ressourcen

Video: Data Lake Grundlagen - RLE-Kodierung mit Parquet in der Praxis

Papier: Eine Überprüfung von Datenkomprimierungstechniken

Papier: Verlustfreie Kompressionstechniken

Eine prägnante Einführung in die Datenkomprimierung von David Salomon

Papier: Eine Studie über verschiedene Datenkomprimierungstechniken

Blog-Beitrag: Komprimierung in offenen Dateiformaten

Artikel: Offene Dateiformate

Artikel: Komprimierung in Datenbanken

Verlustbehaftete Komprimierung für genomische Daten (RNA)

\