Compressie in Big Data: Types en Technieken

\

Inleiding

Dit artikel bespreekt compressie in de context van Big Data, waarbij de types en methoden van compressie worden behandeld. Ik zal ook belichten waarom en wanneer elk type en elke methode moet worden gebruikt.

\

Wat is compressie?

Volgens de algemene Engelse definitie van compressie verwijst het naar het verkleinen van iets zodat het minder ruimte inneemt. In de computerwetenschappen is compressie het proces van het verkleinen van gegevens tot een kleinere omvang. Gegevens kunnen in dit geval worden weergegeven in tekst, audio, videobestanden, etc. Zie het als alles wat je opslaat op de harde schijf van je computer, als gegevens weergegeven in verschillende formaten. Om een meer technische definitie te geven: compressie is het proces van het coderen van gegevens om minder bits te gebruiken.

\ Er zijn meerdere redenen om gegevens te comprimeren. De meest voorkomende en intuïtieve reden is om opslagruimte te besparen. Andere redenen zijn een gevolg van het feit dat de gegevens kleiner zijn. De voordelen van het werken met kleinere gegevens zijn onder meer:

1. Snellere gegevensoverdrachtijd: Gecomprimeerde gegevens zijn kleiner in omvang en nemen minder tijd in beslag om van bron naar bestemming te worden verzonden.
2. Verminderd bandbreedteverbruik: Deze reden is sterk verbonden met het voordeel van snellere gegevensoverdracht. Gecomprimeerde gegevens gebruiken minder netwerkbandbreedte, waardoor de doorvoer toeneemt en de latentie afneemt.
3. Verbeterde prestaties voor digitale systemen die sterk afhankelijk zijn van gegevens: Dit is duidelijk zichtbaar in systemen die afhankelijk zijn van het verwerken van gegevens. Deze systemen maken gebruik van compressie om de prestaties van de systemen te verbeteren door het volume aan te verwerken gegevens te verminderen. Let op dat dit systeemspecifiek kan zijn en afhankelijk is van het gebruik van de juiste compressietechniek. Compressietechnieken worden later in dit artikel besproken.
4. Kostenefficiëntie: Cloudservices brengen kosten in rekening voor de opslag van gegevens. Door minder opslag te gebruiken, worden kostenbesparingen geïntroduceerd, vooral in Big Data-systemen.

\ Andere redenen voor compressie zijn afhankelijk van verschillende compressietechnieken en -formaten. Sommige versleutelingsalgoritmen kunnen worden gebruikt als een methode van compressie. Hierdoor wordt een beveiligingslaag toegevoegd voor de eerder besproken redenen om gegevens te comprimeren. Bovendien brengt het gebruik van veelvoorkomende compressieformaten compatibiliteit en ruimte voor uitbreidbaarheid naar externe systemen voor integratiedoeleinden.

\ Het is vermeldenswaard dat de redenen voor compressie ook klinken als voordelen. Compressie is echter niet zonder afwegingen. Een veelvoorkomende afweging bij compressie is de behoefte aan decompressie, wat zorgwekkend kan zijn voor systemen met beperkte middelen. Andere afwegingen hangen af van de compressietechniek en het type gegevens dat wordt gebruikt.

\

Compressietypen

Om de verschillende technieken te bespreken die worden gebruikt om gegevens te comprimeren, zal ik compressie eerst indelen in 2 hoofdcategorieën. Dit artikel zal vervolgens de technieken bespreken die relevant zijn voor elke categorie. Compressie kan grofweg worden onderverdeeld in Lossy en Lossless compressie.

\ Zoals de namen al weggeven wat ze betekenen, Lossy compressie technieken zijn technieken die de volledige getrouwheid van de gegevens niet behouden. Simpel gezegd, sommige gegevens worden weggegooid, maar niet genoeg om wat de gegevens vertegenwoordigen onherkenbaar te maken. Daarom kan lossy compressie een zeer hoog compressieniveau bieden in vergelijking met lossless compressie, die binnenkort zal worden geïntroduceerd.

\ Een kenmerk van lossy compressie is dat het onomkeerbaar is, d.w.z. wanneer het gecomprimeerde bestand wordt gepresenteerd, kan men de ruwe gegevens niet herstellen met de oorspronkelijke getrouwheid. Bepaalde bestanden en bestandsformaten zijn geschikt voor lossy compressie. Het wordt meestal gebruikt voor afbeeldingen, audio en video's. JPEG-geformatteerde afbeeldingen lenen zich bijvoorbeeld goed voor compressie, en door een JPEG-afbeelding te comprimeren, kan de maker of editor kiezen hoeveel verlies er moet worden geïntroduceerd.

\ Aan de andere kant is lossless compressie omkeerbaar, wat betekent dat bij compressie alle gegevens worden bewaard en volledig worden hersteld tijdens decompressie. Dit houdt in dat lossless compressie geschikt is voor tekstachtige bestanden, en in de wereld van datawarehouses en lakehouses zou het het enige relevante type zijn om te gebruiken. Sommige audio- (FLAC en ALAC) en afbeeldingsbestandsformaten (GIF, PNG, enz.) werken goed met dit compressietype.

Een methode kiezen

Er is geen algemeen beste compressiemethode. Verschillende factoren spelen een rol bij het kiezen van welke methode geschikt zou zijn op case-by-case basis. Om dit te onderstrepen met voorbeelden: een data engineer in de financiële sector die werkt aan opgeslagen tabulaire gegevens, zou de voorkeur geven aan lossless compressie vanwege de impact van ontbrekende gegevens bij het creëren van nauwkeurige rapportages. Als alternatief zou lossy compressie de juiste keuze kunnen zijn bij het optimaliseren van de webpagina met veel afbeeldingen door de afbeeldingen te comprimeren en de laadtijd te verminderen door de website lichter te maken. Daarom is het cruciaal om een beoordeling uit te voeren om de meest geschikte compressiemethode te bepalen die aansluit bij de bedrijfsvereisten.

Compressietechnieken

Deze sectie behandelt alleen de veelvoorkomende compressietechnieken voor zowel lossy als lossless compressie. Houd er rekening mee dat dit op geen enkele manier uitputtend is. Bovendien kunnen de besproken technieken kleine variaties hebben om hun prestaties te verbeteren, zoals ondersteund door verschillende onderzoeken.

Lossless compressietechnieken

Drie veelvoorkomende lossless technieken zijn de Run-Length Encoding (RLE), Huffman Coding en de Lempel-Ziv-Welch technieken.

\ Run-Length Encoding: RLE is gebaseerd op het coderen van gegevens, zodanig dat het reeksen van herhalende gegevens vervangt door een enkel stuk gegevens en de telling van dat stuk gegevens. Het is effectief voor lange reeksen van herhaalde gegevens. Ook datasets die dimensies (velden) hebben die zijn gesorteerd van een laag niveau naar een hoog niveau van kardinaliteit, profiteren van RLE.

\ Neem bijvoorbeeld een eenvoudige string zoals AAAAABBCDDD. RLE comprimeert de gegevens tot A(5)B(2)C(1)D(3). Om praktischer te zijn, neem een tabel in de onderstaande afbeelding.

\ Figuur 1 - voor RLE. Het is belangrijk om op te merken dat het kardinaliteitsniveau toeneemt op de velden van links naar rechts

Figuur 2 - Na RLE

Omdat RLE afhankelijk is van reeksen van herhaalde velden, en in het tweede voorbeeld de kardinaliteit en de sorteervolgorde van de gegevens, kan het Mouse record in de itemkolom niet worden gecomprimeerd tot alleen Mouse (3) omdat de voorgaande kolom alle waarden splitst in IT, Mouse en HR, Mouse. Bepaalde bestandsformaten zijn compatibel met RLE, zoals bitmap-bestandsformaten zoals TIFF, BMP, enz. Parquet-bestanden ondersteunen ook RLE, waardoor het erg nuttig is in moderne data lakehouses die objectopslag gebruiken zoals S3 of GCS.

\ Huffman Coding: Het is gebaseerd op statistische modellering die codes van variabele lengte toewijst aan waarden in de ruwe gegevens op basis van de frequentie waarmee ze voorkomen in de ruwe gegevens. De weergave van deze modellering kan worden aangeduid als een Huffman-boom, die vergelijkbaar is met een binaire boom. Deze boom wordt vervolgens gebruikt om een Huffman-code te creëren voor elke waarde in de ruwe gegevens. Het algoritme geeft prioriteit aan het coderen van de meest voorkomende waarden in zo min mogelijk bits.

\ Laten we dezelfde gegevens nemen die zijn gebruikt in het RLE-voorbeeld AAAAABBCDDD. De bijbehorende Huffman-boom ziet er als volgt uit.

\ Huffman-boom

Uit de boom kunnen we zien dat de letter A wordt weergegeven door 0 en evenzo wordt D gepresenteerd door 10. Vergeleken met letters B: 111 en C:110, zien we dat A en D worden weergegeven door minder bits. Dit komt omdat ze een hogere frequentie hebben; daarom vertegenwoordigt het Huffman-algoritme ze met minder bits door ontwerp. De resulterende gecomprimeerde gegevens worden 00000111111110101010.

\ Huffman Coding gebruikt de prefixregel, die stelt dat de code die een teken vertegenwoordigt, niet aanwezig mag zijn in de prefix van een andere code. Een geldige Huffman-code kan bijvoorbeeld geen letters c en d hebben die worden weergegeven met C: 00 en D: 000 omdat de weergave van C een prefix is van D.

\ Om dit in actie te zien, heeft de Computer Science Field Guide een Huffman Tree Generator waarmee je kunt spelen.

\ Lempel–Ziv–Welch Coding: Het werd gecreëerd door Abraham Lempel, Jacob Ziv en Terry Welch in 1984 en is vernoemd naar de makers, uiteraard 😅. Net als RLE en Huffman Coding werkt LZW goed met gegevens die veel herhaalde gegevens bevatten. Het LZW-algoritme is op woordenboek gebaseerd en creëert een woordenboek met sleutel-waardeparen van veelvoorkomende patronen in de ruwe gegevens. Een dergelijk woordenboek kan ook worden aangeduid als de codetabel. Met behulp van een illustratie om uit te leggen hoe deze techniek werkt, laten we onze ruwe gegevens weergeven door ABBABABABA. Wanneer het wordt doorgegeven aan het algoritme met een configuratie van A-Z als mogelijke waarden, ziet de resulterende codetabel er als volgt uit:

\ LZW Codetabel

Uit de bovenstaande codetabel is er een sleutel-waardepaar voor alle letters A-Z en sleutel-waardeparen voor patronen zoals AB, BB, BA en ABA. Door een kortere weergave van deze patronen te hebben, kan het LZW-algoritme de ruwe gegevens comprimeren door deze in minder bits te coderen. Daarom is de gecomprimeerde versie, met behulp van de codetabel die uit die invoer is gegenereerd, 0 1 1 26 29 28. Het is belangrijk om de spaties in de gecomprimeerde gegevens op te merken. Men zou ze kunnen zien als het einde van een teken, zodat de decoder een 1,0 niet zal interpreteren als een 10 omdat ze verschillende dingen betekenen.

\ LZW is meestal voor algemene doeleinden en wordt vandaag de dag veel gebruikt. Het is geïntegreerd in veel Unix/Linux-gebaseerde besturingssystemen achter het compress shell-commando. Ook zijn veelvoorkomende bestandsformaten die compatibel zijn met LZW GIF, TIFF en PDF. Andere toepassingen van LZW-compressie kunnen worden gezien op het gebied van Natural Language Processing, zoals besproken in dit artikel over tokenisatie in NLP.

\ RLE, Huffman Coding en LZW Coding zijn slechts veelvoorkomende voorbeelden. Lossless compressietechnieken gaan verder dan deze drie (3) hierboven beschreven. Andere technieken omvatten DEFLATE, dat een combinatie van Huffman en LZW gebruikt - specifiek LZ77 - Coding.

Lossy compressietechnieken

In deze sectie zullen we kijken naar twee soorten lossy compressie. Bedenk dat lossy compressie een verlies introduceert in de oorspronkelijke gegevens, wat betekent dat niet alle gegevens worden bewaard.

\ Discrete Cosine Transform (DCT): Deze compressiemethode wordt voornamelijk gebruikt in audio-, afbeeldings- en videobestanden en wordt ook wel blokcompressie genoemd. Het gebruikt een wiskundige functie - de cosinusfunctie, zoals de naam al aangeeft - om blokken van de oorspronkelijke gegevens om te zetten in frequenties. De blokken gegevens zijn meestal een matrix van 8x8, 4x4, enzovoort, in die orde van grootte.

\ De compressie komt binnen bij het omgaan met de hoge frequenties die in de gegevens voorkomen, zodra de ruwe gegevens zijn vertaald naar het frequentiedomein met behulp van de wiskundige functie. Het algemene proces van het gebruik van DCT voor compressie is:

• Verdeel ruwe gegevens in stukken. Bij beeldcompressie zou dit bijvoorbeeld 8x8 pixels kunnen zijn.
• Pas de wiskundige functie toe om de stukken gegevens om te zetten in frequenties. Dit zal resulteren in enkele hoge frequenties en lage frequenties.
• De hoge frequenties worden vervolgens verminderd of verwijderd, afhankelijk van de acceptabele mate van verlies die men wil introduceren. Dit is waar het echt lossy compressie wordt.
• Om terug te converteren naar representeerbare gegevens, worden alle resterende frequenties doorgegeven aan een Inverse Discrete Cosine Transform - IDCT - om de gegevens uit de frequenties te herstellen.

\ DCT wordt vandaag de dag op verschillende gebieden veel gebruikt, niet alleen bij compressie maar ook bij signaalverwerking. Veelvoorkomende bestandsformaten die compatibel zijn met DCT zijn JPEG (afbeeldingen), MP3 (audio) en MPEG (video). Bovendien kan DCT hoge compressieverhoudingen bereiken, waardoor het geschikt is voor digitale systemen met veel afbeeldingen, zoals webpagina's op het internet.

\ Fractal Compressie: Een fractal is een zichzelf herhalend oneindig patroon dat zich op verschillende schalen herhaalt. Wanneer bekeken vanuit elk punt op de schaal, lijkt het patroon vergelijkbaar. Omdat de patronen op elke schaal vergelijkbaar zijn, vermindert fractal compressie de schaal van 'grote' fractals om de grootte van de gegevens te verminderen.

\ Voorbeelden van Fractals

Fractal Compressie werd geïntroduceerd door Michael Barnsley in de jaren tachtig. Het algemene idee met behulp van een afbeelding is dat als een afbeelding verschillende delen bevat die op elkaar lijken, waarom deze dan twee keer opslaan? Om dit te doen, doet fractal compressie het volgende:

• Verdeelt de afbeelding in niet-overlappende blokken die bekend staan als bereikblokken. Dit kunnen bereikblokken zijn van 8x8, 16x16 pixels, enz.
• Het scant de afbeelding op zichzelf herhalende patronen (fractal patronen). Met behulp van de bereikblokken vindt het algoritme grotere secties van de afbeelding die vergelijkbaar zijn met deze bereikblokken. Deze grotere secties worden aangeduid als de domeinblokken.
• Een transformatiefunctie wordt vervolgens toegepast op het domeinblok om de bereikblokken te benaderen. Deze transformatiefuncties zijn wiskundige functies zoals schalen, translatie, rotatie, enz. Ze kunnen ook worden aangeduid als transformaties. Deze transformaties worden fractal codes genoemd met betrekking tot Fractal Compressie.
• De gegevens worden vervolgens gecodeerd naar die transformatiefuncties. In plaats van de pixel-pixel gegevens op te slaan, worden de transformaties opgeslagen. Deze transformaties zijn de regels die beschrijven hoe de afbeelding uit domeinblokken moet worden gereconstrueerd.

\ Met de fractal codes wordt de afbeelding gereconstrueerd met behulp van een iteratief proces. Dit proces kan rekenkundig duur zijn, maar fractal compressie zou een hoge compressieverhouding kunnen bereiken in vergelijking met andere compressietechnieken. Vanwege de afhankelijkheid van zichzelf herhalende patronen, zou het beter presteren op gegevens die voldoen aan het hebben van dergelijke zichzelf herhalende patronen. Voorbeelden zijn landschapsfoto's (afbeeldingen van de natuur) en DNA-afbeeldingen.

\ Er zijn andere lossy compressietechnieken, zoals de Discrete Wavelet Transform, Quantization. Deze technieken worden meestal gebruikt in afbeeldingen, audio en videobestanden en zijn geschikt voor bepaalde typen of bestandsformaten - JPEG, MP3 - voor elk bestandstype.

\ Lossy compressie heeft over het algemeen hogere compressieverhoudingen dan lossless compressie en verwacht soms dat de gebruiker de hoeveelheid verlies die moet worden geïntroduceerd van tevoren kent. Het is van belang te benadrukken dat de keuze van compressiemethode en -techniek afhangt van verschillende factoren. De kern van deze factoren zijn het gegevensformaat en het gewenste resultaat.

TL;DR

Over het geheel genomen bespreekt dit bericht compressie in de wereld van data. Het steunt sterk op de bestaande kennisbasis in de computerwetenschappen en informatietheorie. Comprimeren betekent het volume dat een entiteit inneemt verminderen, en op het gebied van data verwijst volume naar opslagruimte. Compressie in digitale systemen heeft veel voordelen wanneer het goed wordt gedaan. Het voor de hand liggende is dat het de ruimte vermindert en ruimte geeft om meer gegevens op te slaan. Andere voordelen zijn onder meer snellere overdracht, minder bandbreedtegebruik en algemene verbetering van de efficiëntie van het genoemde systeem. Vergeet niet, dit is wanneer het goed wordt gedaan.

\ Om te profiteren van de voordelen van compressie, is het essentieel om te weten welk type te gebruiken. Compressie is ofwel lossy of lossless. Lossy compressie introduceert een verlies in de oorspronkelijke gegevens dat meestal onomkeerbaar is, terwijl lossless compressie de gegevens comprimeert en alle informatie behoudt die in de oorspronkelijke gegevens is opgenomen. Verder is er discussie over hybride compressietypes, maar ik denk dat een combinatie van lossy en lossless gewoon lossy is. Laat me weten wat je ervan vindt in de reacties.

\ Ten slotte werden verschillende technieken geïntroduceerd voor zowel lossy als lossless compressie. De lijst met technieken en uitleg van deze technieken is niet uitputtend noch volledig. Ik beschouw ze alleen als een goed begin om je een idee te geven van hoe elke techniek werkt. Om af te sluiten heb ik aanvullende bronnen toegevoegd om je te helpen verder te onderzoeken en dieper te lezen over compressie in big data.

Aanvullende bronnen

Video: Data Lake fundamentals - RLE encoding with Parquet in practice

Paper: A review of data compression techniques

Paper: lossless compression techniques

A concise introduction to Data Compression by David Salomon

Paper: A Study of Various Data Compression Techniques

Blog Post: Compression in open file formats

Article: Open file formats

Article: Compression in databases

Lossy Compression for Genomic data (RNA)

\