Compresie în Big Data: Tipuri și Tehnici

\

Introducere

Acest articol va discuta despre compresie în contextul Big Data, acoperind tipurile și metodele de compresie. Voi evidenția, de asemenea, de ce și când ar trebui utilizat fiecare tip și metodă.

\

Ce este compresia?

Conform definiției generale în limba engleză a compresiei, aceasta se referă la reducerea a ceva pentru a ocupa un spațiu mai mic. În Informatică, compresia este procesul de reducere a datelor la o dimensiune mai mică. Datele, în acest caz, pot fi reprezentate în text, fișiere audio, video etc. Gândește-te la ele ca orice stochezi pe hard disk-ul computerului tău, ca date reprezentate în diferite formate. Pentru a oferi o definiție mai tehnică, compresia este procesul de codificare a datelor pentru a utiliza mai puțini biți.

\ Există multiple motive pentru a comprima datele. Motivul cel mai comun și intuitiv este economisirea spațiului de stocare. Alte motive sunt rezultatul faptului că datele sunt mai mici. Beneficiile lucrului cu date mai mici includ:

1. Timp mai rapid de transmisie a datelor: Datele comprimate sunt mai mici ca dimensiune și necesită mai puțin timp pentru a fi transmise de la sursă la destinație.
2. Consum redus de lățime de bandă: Acest motiv este strâns legat de avantajul transmisiei mai rapide a datelor. Datele comprimate utilizează mai puțină lățime de bandă de rețea, crescând astfel debitul și reducând latența.
3. Performanță îmbunătățită pentru sistemele digitale care se bazează în mare măsură pe date: Acest lucru este evident în sistemele care se bazează pe procesarea datelor. Acele sisteme valorifică compresia pentru a îmbunătăți performanța sistemelor prin reducerea volumului de date care trebuie procesat. Vă rugăm să rețineți că acest lucru poate fi specific sistemului și va depinde de utilizarea tehnicii de compresie adecvate. Tehnicile de compresie vor fi discutate mai târziu în acest articol.
4. Eficiență a costurilor: Serviciile cloud taxează pentru stocarea datelor. Prin utilizarea mai puțin spațiu de stocare, se introduc economii de costuri, în special în sistemele Big Data.

\ Alte motive pentru compresie depind de diferite tehnici și formate de compresie. Unii algoritmi de criptare pot fi folosiți ca metodă de compresie. Făcând acest lucru, se include un nivel de securitate pentru motivele discutate anterior pentru a comprima datele. În plus, utilizarea formatelor comune de compresie aduce compatibilitate și spațiu pentru extensibilitate către sistemele externe în scopuri de integrare.

\ Merită remarcat faptul că motivele pentru compresie sună și ca beneficii. Cu toate acestea, compresia nu este fără compromisuri. Un compromis comun pentru compresie este nevoia de decompresie, care ar putea fi îngrijorătoare pentru sistemele cu resurse limitate. Alte compromisuri depind de tehnica de compresie și tipul de date utilizat.

\

Tipuri de compresie

Pentru a discuta diferitele tehnici utilizate pentru a comprima datele, voi categoriza mai întâi compresia în 2 categorii principale. Acest articol va discuta apoi tehnicile relevante pentru fiecare categorie. Compresia poate fi grupată pe scară largă în compresie cu pierderi și fără pierderi.

\ Așa cum numele sugerează deja ce înseamnă, tehnicile de compresie cu pierderi sunt tehnici care nu păstrează fidelitatea completă a datelor. Spus simplu, unele date sunt eliminate, dar nu suficient pentru a face ceea ce reprezintă datele de nerecunoscut. Prin urmare, compresia cu pierderi poate oferi un nivel foarte ridicat de compresie în comparație cu compresia fără pierderi, care va fi introdusă în curând.

\ O caracteristică a compresiei cu pierderi este că este ireversibilă, adică atunci când se prezintă fișierul comprimat, nu se poate restaura datele brute cu fidelitatea sa originală. Anumite fișiere și formate de fișiere sunt potrivite pentru compresia cu pierderi. Este utilizată de obicei pentru imagini, audio și video. De exemplu, imaginile în format JPEG se pretează bine la compresie și prin comprimarea unei imagini JPEG, creatorul sau editorul poate alege câtă pierdere să introducă.

\ Pe de altă parte, compresia fără pierderi este reversibilă, ceea ce înseamnă că atunci când este comprimată, toate datele sunt păstrate și restaurate complet în timpul decompresiei. Acest lucru implică faptul că compresia fără pierderi este potrivită pentru fișiere de tip text și, în lumea depozitelor de date și lakehouse-urilor, ar fi singurul tip relevant de utilizat. Unele formate de fișiere audio (FLAC și ALAC) și imagini (GIF, PNG etc.) funcționează bine cu acest tip de compresie.

Alegerea unei metode

Nu există o metodă generală cea mai bună de compresie. Diferiți factori intră în joc atunci când alegeți ce metodă ar fi potrivită de la caz la caz. Pentru a sublinia acest lucru cu exemple, un inginer de date din industria financiară care lucrează cu date tabulare stocate ar tinde să utilizeze compresia fără pierderi datorită impactului datelor lipsă în crearea de rapoarte precise. Alternativ, compresia cu pierderi ar putea fi calea de urmat în optimizarea paginii web cu multe imagini prin comprimarea imaginilor și reducerea elementelor de încărcare prin realizarea unui site web mai ușor. Prin urmare, este esențial să efectuați o evaluare pentru a determina cea mai adecvată metodă de compresie care se aliniază cu cerințele de afaceri.

Tehnici de compresie

Această secțiune va acoperi doar tehnicile comune de compresie pentru compresia cu pierderi și fără pierderi. Vă rugăm să rețineți că aceasta nu este în niciun caz exhaustivă. În plus, tehnicile discutate pot avea variații ușoare pentru a-și îmbunătăți performanța, susținute de diferite cercetări.

Tehnici de compresie fără pierderi

Trei tehnici comune fără pierderi sunt Run-Length Encoding (RLE), Huffman Coding și tehnicile Lempel-Ziv-Welch.

\ Run-Length Encoding: RLE se bazează pe codificarea datelor, astfel încât înlocuiește secvențele de date repetate cu o singură bucată de date și numărul acelei bucăți de date. Este eficientă pentru secvențe lungi de date repetate. De asemenea, seturile de date care au dimensiuni (câmpuri) sortate de la un nivel scăzut la un nivel ridicat de cardinalitate beneficiază de RLE.

\ De exemplu, luați un șir simplu ca AAAAABBCDDD. RLE comprimă datele pentru a deveni A(5)B(2)C(1)D(3). Pentru a fi mai practic, luați un tabel în imaginea de mai jos.

\ Figura 1 - înainte de RLE. Este important să observăm că nivelul de cardinalitate crește pe câmpuri de la stânga la dreapta

Figura 2 - După RLE

Deoarece RLE depinde de secvențe de câmpuri repetate și, în al doilea exemplu, de cardinalitate și ordinea de sortare a datelor, înregistrarea Mouse din coloana articol nu poate fi comprimată la doar Mouse (3) deoarece coloana anterioară împarte toate valorile în IT, Mouse și HR, Mouse. Anumite formate de fișiere sunt compatibile cu RLE, cum ar fi formatele de fișiere bitmap precum TIFF, BMP etc. Fișierele Parquet suportă, de asemenea, RLE, făcându-l foarte util în lakehouse-urile de date moderne care utilizează stocarea de obiecte precum S3 sau GCS.

\ Huffman Coding: Se bazează pe modelare statistică care atribuie coduri de lungime variabilă valorilor din datele brute pe baza frecvenței cu care apar în datele brute. Reprezentarea acestei modelări poate fi denumită arbore Huffman, care este similară cu un arbore binar. Acest arbore este apoi utilizat pentru a crea un cod Huffman pentru fiecare valoare din datele brute. Algoritmul prioritizează codificarea valorilor cele mai frecvente în cât mai puțini biți posibil.

\ Să luăm aceleași date folosite în exemplul RLE AAAAABBCDDD. Arborele Huffman corespunzător arată astfel.

\ Arbore Huffman

Din arbore, putem vedea că litera A este reprezentată de 0 la fel D este prezentat de 10. Comparativ cu literele B: 111 și C:110, observăm că A și D sunt reprezentate de mai puțini biți. Acest lucru se datorează faptului că au o frecvență mai mare; prin urmare, algoritmul Huffman le reprezintă cu mai puțini biți prin design. Datele comprimate rezultate devin 00000111111110101010.

\ Huffman Coding utilizează regula prefixului, care afirmă că codul care reprezintă un caracter nu ar trebui să fie prezent în prefixul oricărui alt cod. De exemplu, un cod Huffman valid nu poate avea literele c și d reprezentate folosind C: 00 și D: 000 deoarece reprezentarea lui C este un prefix al lui D.

\ Pentru a vedea acest lucru în acțiune, Computer Science Field Guide are un Generator de Arbore Huffman cu care puteți experimenta.

\ Lempel–Ziv–Welch Coding: A fost creat de Abraham Lempel, Jacob Ziv și Terry Welch în 1984 și este denumit după creatori, evident 😅. Similar cu RLE și Huffman Coding, LZW funcționează bine cu date care conțin multe date repetate. Algoritmul LZW se bazează pe dicționar și creează un dicționar care conține perechi cheie-valoare ale modelelor văzute frecvent în datele brute. Un astfel de dicționar poate fi, de asemenea, denumit tabel de cod. Folosind o ilustrație pentru a explica cum funcționează această tehnică, să considerăm datele noastre brute reprezentate de ABBABABABA. Când este trecut prin algoritm folosind o configurație de A-Z ca valori posibile, tabelul de cod rezultat arată astfel:

\ Tabel de cod LZW

Din tabelul de cod de mai sus, există o pereche cheie-valoare pentru toate literele A-Z și perechi cheie-valoare pentru modele precum AB, BB, BA și ABA. Având o reprezentare mai scurtă a acestor modele, algoritmul LZW poate comprima datele brute prin codificarea lor în mai puțini biți. Prin urmare, folosind tabelul de cod generat din acea intrare, versiunea comprimată este 0 1 1 26 29 28. Este esențial să observați spațiile din datele comprimate. S-ar putea gândi la ele ca la sfârșitul unui caracter, astfel încât decodorul să nu interpreteze un 1,0 ca un 10 deoarece înseamnă lucruri diferite.

\ LZW este de obicei de uz general și utilizat pe scară largă astăzi. Este integrat în multe sisteme de operare bazate pe Unix/Linux în spatele comenzii shell compress. De asemenea, formatele comune de fișiere compatibile cu LZW sunt GIF, TIFF și PDF. Alte aplicații ale compresiei LZW pot fi văzute în domeniul procesării limbajului natural, așa cum se discută în această lucrare despre tokenizarea în NLP.

\ RLE, Huffman Coding și LZW Coding sunt doar exemple comune. Tehnicile de compresie fără pierderi depășesc aceste trei (3) descrise mai sus. Alte tehnici includ DEFLATE, care utilizează o combinație de codificare Huffman și LZW - în mod specific LZ77.

Tehnici de compresie cu pierderi

În această secțiune, vom examina două tipuri de compresie cu pierderi. Amintim că compresia cu pierderi introduce o pierdere în datele originale, ceea ce înseamnă că nu toate datele sunt păstrate.

\ Discrete Cosine Transform (DCT): Această metodă de compresie este utilizată în principal în fișiere audio, imagine și video și este, de asemenea, denumită în mod obișnuit compresie pe blocuri. Utilizează o funcție matematică - funcția cosinus, așa cum sugerează și numele - pentru a converti blocurile de date originale în frecvențe. Blocurile de date sunt de obicei o matrice de 8x8, 4x4 și așa mai departe, în acea ordine de mărime.

\ Compresia apare atunci când se ocupă de frecvențele ridicate care apar în date, odată ce datele brute sunt traduse în domeniul frecvenței folosind funcția matematică. Procesul general de utilizare a DCT pentru compresie este:

• Împărțiți datele brute în bucăți. De exemplu, în compresia imaginii, aceasta ar putea fi 8x8 pixeli.
• Aplicați funcția matematică pentru a converti bucățile de date în frecvențe. Acest lucru va duce la unele frecvențe ridicate și frecvențe scăzute.
• Frecvențele ridicate sunt apoi reduse sau eliminate în funcție de gradul acceptabil de pierdere pe care cineva este dispus să îl introducă. Aici devine cu adevărat compresie cu pierderi.
• Pentru a converti înapoi în date reprezentabile, toate frecvențele rămase sunt trecute printr-o transformată cosinusoidală discretă inversă - IDCT - pentru a restaura datele din frecvențe.

\ DCT este utilizat pe scară largă în diferite domenii astăzi, nu numai în compresie, ci și în procesarea semnalelor. Formatele comune de fișiere compatibile cu DCT sunt JPEG (imagini), MP3 (audio) și MPEG (video). În plus, DCT poate obține rate ridicate de compresie, făcându-l potrivit pentru sistemele digitale cu multe imagini, precum paginile web de pe Internet.

\ Fractal Compression: Un fractal este un model infinit auto-repetat care se repetă la diferite scări. Când este vizualizat din orice punct de pe scară, modelul arată similar. Deoarece modelele sunt similare la orice scară, compresia fractală reduce scala fractalelor „mari" pentru a reduce dimensiunea datelor.

\ Exemple de fractali

Compresia fractală a fost introdusă de Michael Barnsley în anii 1980. Ideea generală folosind o imagine este că dacă o imagine conține mai multe părți care arată la fel, de ce să le stocați de două ori? Pentru a face acest lucru, compresia fractală face următoarele:

• Împarte imaginea în blocuri fără suprapunere cunoscute sub numele de blocuri de interval. Acestea ar putea fi blocuri de interval de 8x8, 16x16 pixeli etc.
• Scanează imaginea pentru modele auto-repetate (modele fractale). Folosind blocurile de interval, algoritmul găsește secțiuni mai mari ale imaginii care sunt similare cu aceste blocuri de interval. Aceste secțiuni mai mari sunt denumite blocuri de domeniu.
• O funcție de transformare este apoi aplicată blocului de domeniu pentru a aproxima blocurile de interval. Aceste funcții de transformare sunt funcții matematice precum scalarea, translația, rotația etc. Ele pot fi, de asemenea, denumite transformări. Aceste transformări sunt denumite coduri fractale în ceea ce privește compresia fractală.
• Datele sunt apoi codificate la acele funcții de transformare. În loc să stocheze datele pixel-pixel, sunt stocate transformările. Aceste transformări sunt regulile care descriu cum să reconstruim imaginea din blocurile de domeniu.

\ Cu codurile fractale, imaginea este reconstruită folosind un proces iterativ. Acest proces poate fi costisitor din punct de vedere computațional, dar compresia fractală ar putea obține o rată ridicată de compresie în comparație cu alte tehnici de compresie. Datorită dependenței sale de modele auto-repetate, ar funcționa mai bine pe date care se conformează la astfel de modele auto-repetate. Exemple ar fi fotografiile de peisaj (imagini ale naturii) și imaginile ADN.

\ Există alte tehnici de compresie cu pierderi, cum ar fi transformata wavelet discretă, cuantizarea. Aceste tehnici sunt utilizate de obicei în fișiere de imagini, audio și video și sunt potrivite pentru anumite tipuri sau formate de fișiere - JPEG, MP3 - pentru fiecare tip de fișier.

\ Compresia cu pierderi are în general rate de compresie mai mari decât compresia fără pierderi și uneori se așteaptă ca utilizatorul să știe cantitatea de pierdere de introdus în prealabil. Este pertinent să se sublinieze că alegerea metodei și tehnicii de compresie depinde de mai mulți factori. În centrul acestor factori se află formatul datelor și rezultatul dorit.

TL;DR

Per ansamblu, această postare discută despre compresie în lumea datelor. Se bazează puternic pe corpul existent de cunoștințe în informatică și teoria informației. A comprima înseamnă a reduce volumul pe care îl ocupă o entitate și în domeniul datelor, volumul se referă la spațiul de stocare. Compresia în sistemele digitale are multe avantaje atunci când este făcută corect. Evidentul este că reduce spațiul și oferă loc pentru a stoca mai multe date. Alte avantaje includ transmisia mai rapidă, utilizarea mai puțină a lățimii de bandă și îmbunătățirea generală a eficienței sistemului menționat. Rețineți, acest lucru este atunci când este făcut corect.

\ Pentru a valorifica avantajele compresiei, este esențial să știți ce tip să utilizați. Compresia este fie cu pierderi, fie fără pierderi. Compresia cu pierderi introduce o pierdere în datele originale care este de obicei ireversibilă, în timp ce compresia fără pierderi comprimă datele și păstrează toate informațiile conținute în datele originale. În plus, există discuții despre tipurile de compresie hibride, dar cred că o combinație de cu pierderi și fără pierderi este doar cu pierderi. Spune-mi ce crezi în comentarii.

\ În cele din urmă, au fost introduse diferite tehnici atât pentru compresia cu pierderi, cât și pentru cea fără pierderi. Lista tehnicilor și explicațiile acestor tehnici nu sunt nici exhaustive, nici cuprinzătoare. Le consider doar un început bun în a vă oferi o idee despre cum funcționează fiecare tehnică. Pentru a încheia, am adăugat resurse suplimentare pentru a vă ajuta să investigați mai departe și să citiți mai profund despre compresia în big data.

Resurse suplimentare

Video: Fundamentele Data Lake - codificare RLE cu Parquet în practică

Lucrare: O revizuire a tehnicilor de compresie a datelor

Lucrare: tehnici de compresie fără pierderi

O introducere concisă în compresia datelor de David Salomon

Lucrare: Un studiu al diverselor tehnici de compresie a datelor

Postare pe blog: Compresia în formatele de fișiere deschise

Articol: Formate de fișiere deschise

Articol: Compresia în baze de date

Compresie cu pierderi pentru date genomice (ARN)

\