15 mest populære datakomprimeringsalgoritmer

Datakomprimeringsalgoritmer kan defineres som processen med at reducere størrelsen af filer, samtidig med at de samme eller lignende data bevares i et vist omfang. Dette sker ved at fjerne unødvendige data eller ved at gøre dataene mere effektive igen.

På tidspunktet for komprimering har du mulighed for at vælge mellem lossy eller lossless metoder. Hvis vi taler om den tabsgivende metode, sletter den permanent dataene. På den anden side tager lossless sig af dine originale data. Hvilken type du vælger, afhænger af, hvor høj kvalitet du ønsker, at dine filer skal være.
I denne artikel finder du en blanding af lossless datakomprimeringsalgoritmer og algoritmer til billed- og videokomprimering baseret på deep learning.

Lossless datakomprimeringsalgoritmer er normalt væsener, der bruges til at udføre funktionen som arkiv eller andre funktioner af høj kvalitet. Disse datakomprimeringsalgoritmer giver dig mulighed for at udføre en reduktion af filstørrelsen. Det sikrer også, at filer kan gendannes fuldt ud, hvis de skulle gendannes.

LZ77

LZ77 blev annonceret i 1977 og betegnet som grundlaget for så mange andre tabsfri komprimeringsalgoritmer. Den anvender normalt metoden “Sliding Window”. I denne metode tager den sig af en ordbog, der gør brug af tripler til at repræsentere:

• Offset- Det kan betegnes som den faktiske start af sætningen og begyndelsen af filen.
• Run-length-Det er defineret som mængden af de tegn, der hjælper dig med at lave en sætning.
• Afvigende tegn-Det er de markedsførere, der angiver en ny sætning.

Det omfatter en angivelse af, at den anvendte sætning er helt lig den oprindelige sætning og definerer også, om der er et andet tegn.

Som du vil analysere en fil, opdateres ordbogen dynamisk til afspejling af det komprimerede dataindhold og størrelsen også.

LZR

LZR blev udviklet og annonceret i år 1981. Michael Rodeh annoncerede det, og han ændrede det senere. Den kan bruges som et primært alternativ til LZ77-datakomprimeringsalgoritmen, men du har også mulighed for at bruge den til enhver forskydning i filen. Hvis du ikke bruger den lineært, så har den brug for en betydelig mængde hukommelseslagring. Denne betingelse gør LZ77 til en bedre mulighed for at bruge. Denne datakomprimeringsalgoritme er ligetil at implementere og har potentiale for meget høj ydeevne, når den implementeres på hardware.

Det er den algoritme, der er meget udbredt Unix datakomprimeringsalgoritme utility komprimere og bruges i GIF-billedformatet. Det blev den første datakomprimeringsalgoritme, der blev bredt anvendt på computere. En stor engelsk tekstfil kan typisk komprimeres fra LZW til omkring halvdelen af dens oprindelige størrelse.

LZSS

LZSS står for Lempel Ziv Storer Szymanski, og den blev udviklet og annonceret i år 1982. Det er en datakomprimeringsalgoritme, der forbedrer LZ77. Denne komprimeringsproces sker ved at inkludere en metode, der holder øje med, om en udskiftning mindsker filstørrelsen. Hvis den ikke mindskes, vil inddataet blive efterladt i sin oprindelige form. Den foretrækker heller ikke brugen af afvigende tegn og foretrækker kun at bruge offset-længdepar.

Denne algoritme bruges hovedsageligt til arkivering af filer til forskellige formater som RAR eller ZIP eller til komprimering af netværksdata.

Den kan betegnes som en ordbogskodningsteknik. LZSS forsøger at erstatte en streng af symboler med en henvisning til en ordbogsplacering af den samme streng. Den væsentligste forskel mellem LZ77 og LZSS er, at i LZ77 kunne ordbogsreferencen være længere end den streng, den erstattede. I LZSS udelades sådanne referencer, hvis længden er mindre end “break-even”-punktet.

Deflate

Deflate er et filformat med en tabsfri datakomprimeringsalgoritme, der gør brug af en kombination af LZSS og Huffman-kodning. Det blev designet af Phil Katz i 1993. Huffman-kodning er også en algoritme, der blev udviklet i 1952. Den kan defineres som en entropi-kodningsalgoritme, der hjælper dig med at tildele din kode på baggrund af tegnets hyppighed.

Katz har også designet den oprindelige algoritme, der bruges til at konstruere Deflate-strømme. Som det blev anført i RFC-dokumentet, mente man i vid udstrækning, at en algoritme, der producerede Deflate-filer, kunne implementeres på en måde, der ikke var omfattet af patenter. Dette førte til en udbredt brug af den, ud over ZIP-filformatet, som var hovedformålet med Katz’ design af den. Patentet er ikke længere tilgængeligt.

LZMA

LZMA står for Lempel Ziv Markov-kæde-algoritmen, og den blev designet og frigivet i år 1998. Den kan også siges at være en modifikation af LZ77. Denne modifikation blev foretaget til -Zip-arkivprogrammet med et .7z-format. Der anvendes en metode til kædekomprimering, som implementerer den modificerede LZ77 på bit- i stedet for byte-niveau. Output, der vises, vil blive yderligere behandlet ved hjælp af aritmetisk kodning for at udføre mere komprimering.

Den præstation af andre komprimeringstrin er afhængig af den nøjagtige implementering. Denne datakomprimeringsalgoritme anvender en ordbogskomprimeringsordning, der minder meget om LZ77-algoritmen, som blev offentliggjort af Abraham Lempel og Jacob Ziv i 1977. Den har også et højt kompressionsforhold og en variabel kompressionsordbogsstørrelse. Mens den stadig opretholder en dekomprimeringshastighed, der svarer meget til andre almindeligt anvendte komprimeringsalgoritmer.

LZMA2

LZMA2 blev designet og frigivet i år 2009. Den kan også defineres som en modifikation af LZMA. Den gør LZMA bedre ved at forbedre dens ydeevne med større multithreading-funktioner. LZMA2 giver dig også en forbedret håndtering af inkompressible data. Det er et simpelt containerformat, der kan indeholde både ukomprimerede data og LZMA-data, og det også med flere forskellige LZMA-kodningsparametre.

LZMA2 understøtter vilkårligt skalerbar multithread-komprimering og dekomprimering med flere tråde og effektiv komprimering af data, der er delvist inkomprimerbare. Den kan dog have nogle sikkerhedsproblemer og kan være usikker og mindre effektiv end LZMA. Med enkle ord kan det være nyttigt for dig, men ja, det er ikke så sikkert i forhold til LZMA.

Multi-Layer Perceptron (MLP)-baseret komprimering

MLP kan defineres som en teknologi, der bruger flere neuronlag til input, behandling og til at give outputdata. Den kan anvendes til reduktion af dimensionsopgaver og også til komprimering af data. Den MLP-baserede algoritme blev først udviklet i 1988 og slutter sig til de allerede eksisterende processer:

• Binær kodning- standard to-symbol-kodning.
• Kvantisering- problemer med input fra et kontinuerligt sæt til et diskret sæt.
• Rumlig domænetransformation – pixel for pixel ændringer af data.

Til bestemmelse af den optimale binære kode bruger MLP-algoritmen output fra ovenstående processer i et neuralt dekomponeringsnetværk.

Dertil kommer, at denne algoritme blev modificeret med intuitive teknikker, der tillod præcis tilnærmelse af data fuldstændigt baseret på nabodata gennem backpropagation. Det kan være meget nyttigt for dig i billed- og videodatakomprimering.

Dee Coder- Deep Neural Network Based Video Compression

Deep Coder er defineret som en Convolutional Neural Network (CNN) baseret ramme. Dette gør repræsentationen af et alternativ til de videokomprimeringsteknikker, som vi har brugt så længe. Til prædiktive og restsignaler anvendes forskellige Convolutional Neural Networks (CNN’er) af denne model.

Den udfører kodning af feature maps i den binære strøm med brug af skalær kvantisering og en meget gammel og traditionel filkomprimeringsalgoritme kaldet Huffman-kodning. Det hævdes, at denne model er i stand til at yde en overlegen ydelse i forhold til den velkendte H.264/AVC-videokodningsstandard.

Convolutional Neural Network (CNN) – Baseret komprimering

CNN’s defineres som neurale netværk af forskellige lag. Dette bruges hovedsageligt til genkendelse af billeder og detektion af funktionen. I det øjeblik du anvender det til komprimering, gør disse netværk brug af konvolution til beregning af forbindelsen mellem nabopixels. Hvis vi sammenligner det med MLP-baserede algoritmer, viser CNN’er bedre resultater af kompression end dem.

Dette giver dig også forbedret superopløsningspræstation og artefaktreduktion. Derudover giver CNN-baserede datakomprimeringsalgoritmer CNN-baserede datakomprimeringsalgoritmer forbedringer i kvaliteten af JPEG-billeder. Dette sker ved at reducere det maksimale signal/støjforhold og den strukturelle lighed.

CNN-baseret komprimering kan også komme sammen med ydeevnen i standarden High-Efficiency Video Coding. Dette gøres ved hjælp af entropiesstimulering. Det kan også være meget nyttigt for dig, når du udfører komprimering af filer.

Generative Adversarial Network (GAN)-baseret komprimering

GANs kan defineres som et alternativ til neurale netværk, der gør brug af to netværk, der konkurrerer. Dette gøres for at producere mere præcise analyser og forudsigelser. I år 2017 blev der for første gang udviklet GAN-baserede algoritmer. Disse datakomprimeringsalgoritmer kan komprimere filerne mere end to og en halv gang mindre i forhold til traditionelle almindeligt anvendte metoder som JPEG eller WebP.

GAN-baserede algoritmer kan bruges til komprimering i realtid med parallel behandling, der anvendes sammen. Denne algoritme fungerer, da den komprimerer billederne fuldstændigt baseret på de mest matchende funktioner.

Når afkodningen udføres, rekonstrueres billederne på grundlag af de forudsigelser, der blev foretaget af disse funktioner. Hvis vi sammenligner den med CNN-baseret komprimering, vil den GAN-baserede komprimering give dig billeder af meget høj kvalitet ved at eliminere modstandertab.

Prediction by partial matching (PPM)

PPM er en adaptiv statistisk datakomprimeringsteknik, der er baseret på kontekstmodellering og forudsigelse. Disse modeller anvender et sæt af tidligere symboler i den ukomprimerede symbolstrøm til at forudsige det næste symbol i strømmen. PPM-algoritmer kan også bruges til at gruppere data i forudsagte grupperinger i klyngeanalyser.
Antallet af tidligere symboler, n, bestemmer rækkefølgen af PPM-modellen, der betegnes som PPM(n).

Der findes også ubegrænsede varianter, hvor konteksten ikke har nogen længdebegrænsninger, og de betegnes som PPM. Hvis der ikke kan foretages en forudsigelse på grundlag af alle n kontekstsymboler, forsøges en forudsigelse med n – 1 symbol. Denne proces gentages, indtil der findes et match, eller der ikke er flere symboler tilbage i konteksten. På det tidspunkt foretages en fast forudsigelse.
PPM-komprimeringsimplementeringer varierer meget med hensyn til andre detaljer. Det faktiske symbolvalg registreres normalt ved hjælp af aritmetisk kodning, selv om det også er muligt at anvende Huffman-kodning eller endog en form for ordbogskodningsteknik.

Run-length encoding (RLE)

RLW er en form for tabsfri datakomprimering, hvor kørsler af data (sekvenser, hvor den samme dataværdi forekommer i mange på hinanden følgende dataelementer) gemmes som en enkelt dataværdi og tæller, i stedet for som den oprindelige kørsel. Dette er mest nyttigt for data, der indeholder mange sådanne kørsler.

For eksempel simple grafiske billeder som ikoner, stregtegninger, Conway’s Game of Life og animationer. Det er ikke nyttigt med filer, der ikke har mange kørsler, da det kan øge filstørrelsen betydeligt.

RLE kan også bruges til at henvise til et tidligt grafikfilformat, der blev understøttet af CompuServe til komprimering af sort/hvide billeder, men som i vid udstrækning blev fortrængt af deres senere Graphics Interchange Format (GIF). RLE henviser også til et lidt brugt billedformat i Windows 3.x, med forlængelsesreglen, som er et Run Length Encoded Bitmap, der blev brugt til at komprimere Windows 3.x-startskærmen.

bzip2

bzip2 er et gratis og open source datakomprimeringsprogram, der bruger Burrows-Wheeler-algoritmen. Det komprimerer kun enkelte filer og er ikke en filarkiveringsenhed. Det er udviklet af Julian Seward og vedligeholdes af Federico Mena. Seward lavede den første offentlige udgivelse af bzip2, version 0.15, i juli 1996. Kompressorens stabilitet og popularitet voksede i løbet af de næste mange år, og Seward udgav version 1.0 i slutningen af 2000.

Efter en niårig pause med opdateringer af projektet siden 2010. Den 4. juni 2019 accepterede Federico Mena vedligeholdelsesansvaret for bzip2-projektet. bzip2 komprimerer data i blokke med en størrelse på mellem 100 og 900 kB.

Det bruger Burrows-Wheeler-transformationen til at konvertere hyppigt tilbagevendende tegnsekvenser til strenge af identiske bogstaver. Derefter anvender den move-to-front-transformation og Huffman-kodning. bzip2’s forfader bzip anvendte aritmetisk kodning i stedet for Huffman-kodning. Ændringen blev foretaget på grund af en begrænsning i et softwarepatent.

Huffman-kodning

Huffman-kode er en særlig type optimal præfikskode, der almindeligvis anvendes til tabsfri datakomprimering. Processen med at finde eller anvende en sådan kode foregår ved hjælp af Huffman-kodning, en algoritme, der er udviklet af David A. Huffman, mens han var ph.d.-studerende ved MIT, og som blev offentliggjort i 1952 i artiklen “A Method for the Construction of Minimum-Redundancy Codes”

Outputet fra Huffmans algoritme kan ses som en kodetabel med variabel længde til kodning af et kildesymbol (f.eks. et tegn i en fil). Algoritmen udleder denne tabel fra den anslåede sandsynlighed eller hyppighed for forekomst (vægt) for hver mulig værdi af kildesymbolet.

Som i andre entropi-kodningsmetoder repræsenteres mere almindelige symboler generelt ved hjælp af færre bits end mindre almindelige symboler. Huffmans metode kan gennemføres effektivt. Finde en kode på tid, der er lineær med antallet af inputvægte, hvis disse vægte er sorteret.

ZStandard

Zstandard (eller zstd) er en tabsfri datakomprimeringsalgoritme, der er udviklet af Yann Collet på Facebook. Zstd er referenceimplementeringen i C. Version 1 af denne implementering blev frigivet som gratis software den 31. august 2016.
Zstandard blev designet til at give et kompressionsforhold, der kan sammenlignes med DEFLATE-algoritmen (udviklet i 1991 og anvendt i de oprindelige ZIP- og gzip-programmer), men hurtigere, især ved dekomprimering. Den kan indstilles med kompressionsniveauer fra negativ 5 (hurtigst) til 22 (langsomst i kompressionshastighed, men bedste kompressionsforhold).

Zstd giver ved sit maksimale kompressionsniveau et kompressionsforhold, der ligger tæt på LZMA, LZAHM og PPM. Den klarer sig bedre end LZA eller bzip2. Zstandard når den nuværende Pareto-grænse, da den dekomprimerer hurtigere end nogen anden aktuelt tilgængelig algoritme med et lignende eller bedre kompressionsforhold

Vordiktionærer kan have stor indflydelse på kompressionsforholdet for små filer, så Zstandard kan bruge en brugerforsynet kompressionsordbog. Den tilbyder også en træningstilstand, der er i stand til at generere en ordbog fra et sæt prøver.

Konklusion

Disse datakomprimeringsalgoritmer vil hjælpe dig med at optimere filstørrelsen. Forskellige typer af datakomprimeringsalgoritmer vil give dig forskellige resultater. Hvis du imidlertid ikke kan finde den rigtige algoritme her, kan du tage et kig på denne vejledning og forfine din søgning. Der er ingen mangel på algoritmer, men du skal være specifik, når du leder efter den rigtige algoritme til dit projekt.

Jeg håber, at denne artikel var nyttig for dig, når du skal vælge den bedste datakomprimeringsalgoritme i henhold til dine behov. Tak fordi du læste denne artikel. Du kan også tjekke Best Encryption and Hashing algorithms.

Stay Tuned