15 mest populära algoritmer för datakomprimering

Data Algoritmer för datakomprimering kan definieras som en process för att minska storleken på filer samtidigt som man behåller samma eller liknande data i viss utsträckning. Detta görs genom att eliminera onödiga data eller genom att göra om data för att öka effektiviteten.

I samband med komprimering har du möjlighet att välja mellan förlustfyllda eller förlustfria metoder. Om vi talar om den förlustfyllda metoden raderar den data permanent. Å andra sidan tar lossless hand om dina originaldata. Vilken typ du väljer beror på vilken kvalitet du vill att dina filer ska ha.
I den här artikeln hittar du en blandning av förlustfria datakomprimeringsalgoritmer och bild- och videokomprimeringsalgoritmer baserade på djupinlärning.

Förlustfria datakomprimeringsalgoritmer är normalt varelser som används för att utföra funktionen av arkiv eller andra högkvalitativa funktioner. Dessa datakomprimeringsalgoritmer gör det möjligt att utföra en minskning av filstorleken. Det säkerställer också att filerna kan återställas fullt ut om de behövde återställas.

LZ77

LZ77 tillkännagavs 1977 och betecknas som basen för så många andra förlustfria komprimeringsalgoritmer. Den använder normalt metoden ”Sliding Window” (glidande fönster). I denna metodik tar den hand om en ordbok som använder sig av triplar för att representera:

• Offset- Det kan betecknas som den faktiska starten av frasen och början av filen.
• Run-length-Det definieras som mängden tecken som hjälper dig att göra en fras.
• Deviating characters-Detta är de marknadsförare som anger en ny fras.

Det inkluderar en indikation på att den använda frasen är helt likadan som den ursprungliga frasen och definierar också om det finns något avvikande tecken.

När du kommer att analysera en fil uppdateras ordlistan dynamiskt för att återspegla det komprimerade datainnehållet och storleken också.

LZR

LZR utvecklades och tillkännagavs under år 1981. Michael Rodeh tillkännagav det, och han modifierade det senare. Den kan användas som ett primärt alternativ till datakomprimeringsalgoritmen LZ77, men du har också möjlighet att använda den för vilken offset som helst i filen. Om du inte använder den linjärt behöver den en betydande mängd minneslagring. Detta villkor gör LZ77 till ett bättre alternativ att använda. Denna datakomprimeringsalgoritm är enkel att implementera och har potential för mycket hög prestanda när den implementeras på hårdvara.

Det är den algoritm som är allmänt använd Unix datakomprimeringsalgoritm utility komprimera och används i GIF-bildformatet. Den blev den första datakomprimeringsalgoritmen som användes allmänt på datorer. En stor engelsk textfil kan vanligtvis komprimeras från LZW till ungefär hälften av sin ursprungliga storlek.

LZSS

LZSS står för Lempel Ziv Storer Szymanski och den utvecklades och tillkännagavs år 1982. Detta är en datakomprimeringsalgoritm som förbättrar LZ77. Denna komprimeringsprocess sker genom att inkludera en metod som håller ett öga på om ett byte minskar filstorleken. Om den inte minskar kommer inmatningen att lämnas i sin ursprungliga form. Den föredrar inte heller användningen av avvikande tecken och föredrar endast att använda offset-längdpar.

Denna algoritm används främst för arkivering av filer till olika format som RAR eller ZIP, eller för komprimering av nätverksdata.

Den kan betecknas som en ordbokskodningsteknik. LZSS försöker ersätta en symbolsträng med en hänvisning till en ordboksplats för samma sträng. Den viktigaste skillnaden mellan LZ77 och LZSS är att i LZ77 kan ordboksreferensen vara längre än den sträng som den ersätter. I LZSS utelämnas sådana referenser om längden är mindre än ”break-even”-punkten.

Deflate

Deflate är ett filformat med förlustfri datakomprimeringsalgoritm som använder sig av en kombination av LZSS och Huffman-kodning. Det utformades av Phil Katz år 1993. Huffman-kodning är också en algoritm som utvecklades 1952. Den kan definieras som en entropikodningsalgoritm som hjälper dig att tilldela din kod baserat på tecknets frekvens.

Katz utformade också den ursprungliga algoritmen som används för att konstruera Deflate-strömmar. Som det angavs i RFC-dokumentet ansågs det allmänt att en algoritm som producerade Deflate-filer kunde implementeras på ett sätt som inte omfattades av patent. Detta ledde till en utbredd användning av den, utöver ZIP-filformatet som var det huvudsakliga syftet för Katz att konstruera den. Patentet finns inte längre tillgängligt.

LZMA

LZMA står för Lempel Ziv Markov chain-algoritmen och den utformades och släpptes år 1998. Den kan också sägas vara en modifiering av LZ77. Denna modifiering gjordes för -Zip-arkivet med ett .7z-format. Metoden för kedjekomprimering används som implementerar den modifierade LZ77 på bit- snarare än byte-nivå. Utdata som visas kommer att bearbetas ytterligare med hjälp av aritmetisk kodning för att utföra mer komprimering.

Prestationen för andra komprimeringssteg är beroende av den exakta implementeringen. Denna datakomprimeringsalgoritm använder ett ordbokskomprimeringsschema som är mycket likt LZ77-algoritmen som publicerades av Abraham Lempel och Jacob Ziv år 1977. Den har också ett högt kompressionsförhållande och en variabel kompressionsordboksstorlek. Samtidigt behåller den fortfarande en dekomprimeringshastighet som är mycket lik andra vanligt förekommande komprimeringsalgoritmer.

LZMA2

LZMA2 utformades och släpptes år 2009. Den kan också definieras som en modifiering av LZMA. Den gör LZMA bättre genom att förbättra dess prestanda med större möjligheter till multitrådning. LZMA2 ger också en förbättrad hantering av inkompressibel data. Det är ett enkelt containerformat som kan innehålla både okomprimerade data och LZMA-data och dessutom med flera olika LZMA-kodningsparametrar.

LZMA2 stöder godtyckligt skalbar komprimering och dekomprimering med flera trådar och effektiv komprimering av data som är delvis inkomprimerbara. Den kan dock ha vissa säkerhetsproblem och kan vara osäker och mindre effektiv än LZMA. Med enkla ord kan detta vara användbart för dig, men ja, det är inte så säkert i jämförelse med LZMA.

Multi-Layer Perceptron (MLP)-baserad komprimering

MLP kan definieras som en teknik som använder sig av flera neuronlager för att mata in, bearbeta och ge utdata. Den kan användas för att reducera dimensioner och för att komprimera data. Den MLP-baserade algoritmen utvecklades för första gången 1988 och ansluter sig till de redan existerande processerna:

• Binär kodning – standardkodning med två symboler.
• Kvantisering – problem med inmatning från en kontinuerlig mängd till en diskret mängd.
• Spatial domain transformation – pixel för pixel förändringar av data.

För att bestämma den optimala binära koden använder MLP-algoritmen utdata från ovanstående processer i ett neuralt nätverk för dekomposition.

Fortsättningsvis modifierades denna algoritm med intuitiva tekniker som tillät noggrann approximation av data helt baserat på närliggande data genom backpropagation. Den kan vara mycket användbar för dig vid komprimering av bild- och videodata.

Dee Coder- Deep Neural Network Based Video Compression

Deep Coder definieras som ett Convolutional Neural Network (CNN) baserat ramverk. Detta gör representationen av ett alternativ till de videokomprimeringstekniker som vi har använt så länge. För prediktiva och resterande signaler används olika Convolutional Neural Networks (CNN) av denna modell.

Den utför kodning av funktionskartor till den binära strömmen med hjälp av skalär kvantisering och en mycket gammal och traditionell filkomprimeringsalgoritm som kallas Huffman-kodning. Det hävdas att denna modell kan ge överlägsen prestanda i jämförelse med den välkända videokodningsstandarden H.264/AVC.

Convolutional Neural Network (CNN) – Baserad komprimering

CNN:s definieras som neurala nätverk med olika lager. Det används främst för att känna igen bilder och upptäcka funktioner. I det ögonblick du tillämpar det på komprimering använder sig dessa nätverk av konvolution för att beräkna anslutningen mellan angränsande pixlar. Om vi jämför det med MLP-baserade algoritmer visar CNNs bättre komprimeringsresultat än dem.

Detta ger dig också förbättrad superupplösningsprestanda och minskning av artefakter. Utöver detta gör CNN-baserade datakomprimeringsalgoritmer förbättringar av JPEG-bildernas kvalitet. Detta görs genom att minska toppsignal-till-brusförhållandet och den strukturella likheten.

CNN-baserad komprimering kan också samsas med prestandan hos standarden High-Efficiency Video Coding. Detta görs med hjälp av entropiskattning. Det kan också vara mycket användbart för dig när du utför komprimering av filer.

Generative Adversarial Network (GAN)- Based Compression

GANs kan definieras som ett alternativ till neurala nätverk som använder sig av två nätverk som konkurrerar. Detta görs för att producera mer exakta analyser och förutsägelser. År 2017 utvecklades GAN-baserade algoritmer för första gången. Dessa datakomprimeringsalgoritmer kan komprimera filerna mer än två och en halv gånger mindre i jämförelse med traditionella allmänt använda metoder, som JPEG eller WebP.

GAN-baserade algoritmer kan användas för komprimering i realtid med parallell bearbetning som används tillsammans. Denna algoritm fungerar eftersom den komprimerar bilderna helt och hållet baserat på de mest matchande egenskaperna.

När avkodningen utförs rekonstrueras bilderna utifrån de förutsägelser som gjorts av dessa egenskaper. Om vi jämför den med CNN-baserad komprimering kommer den GAN-baserade komprimeringen att producera bilder av mycket hög kvalitet för dig genom eliminering av adversarial loss.

Prediction by partial matching (PPM)

PPM är en adaptiv statistisk datakomprimeringsteknik som bygger på kontextmodellering och prediktion. Dessa modeller använder en uppsättning tidigare symboler i den okomprimerade symbolströmmen för att förutsäga nästa symbol i strömmen. PPM-algoritmer kan också användas för att gruppera data i förutspådda grupperingar i klusteranalys.
Antalet tidigare symboler, n, bestämmer ordningen för PPM-modellen som betecknas PPM(n).

Obundna varianter där kontexten inte har några längdbegränsningar existerar också och betecknas som PPM. Om ingen förutsägelse kan göras på grundval av alla n kontextsymboler försöker man göra en förutsägelse med n – 1 symbol. Denna process upprepas tills en matchning hittas eller tills det inte finns några fler symboler kvar i sammanhanget. Vid den tidpunkten görs en fast prediktion.
PPM-komprimeringsimplementationer varierar mycket i andra detaljer. Själva symbolvalet registreras vanligen med aritmetisk kodning, även om det också är möjligt att använda Huffman-kodning eller till och med någon typ av ordbokskodningsteknik.

Run-length encoding (RLE)

RLW är en form av förlustfri datakomprimering där datakörningar (sekvenser där samma datavärde förekommer i många på varandra följande dataelement) lagras som ett enda datavärde och räknevärde, i stället för som den ursprungliga körningen. Detta är mest användbart för data som innehåller många sådana körningar.

Till exempel enkla grafiska bilder som ikoner, linjedragningar, Conway’s Game of Life och animationer. Det är inte användbart med filer som inte har många körningar eftersom det kan öka filstorleken kraftigt.

RLE kan också användas för att hänvisa till ett tidigt grafiskt filformat som stöddes av CompuServe för att komprimera svartvita bilder, men som i stor utsträckning ersattes av deras senare Graphics Interchange Format (GIF). RLE hänvisar också till ett lite använt bildformat i Windows 3.x, med tilläggsregeln, som är en Run Length Encoded Bitmap, som används för att komprimera startskärmen i Windows 3.x.

bzip2

bzip2 är ett datakomprimeringsprogram med fri och öppen källkod som använder Burrows-Wheeler-algoritmen. Det komprimerar endast enskilda filer och är inte en filarkiverare. Det har utvecklats av Julian Seward och underhålls av Federico Mena. Seward gjorde den första offentliga versionen av bzip2, version 0.15, i juli 1996. Kompressorns stabilitet och popularitet ökade under de följande åren och Seward släppte version 1.0 i slutet av 2000.

Efter ett nioårigt uppehåll av uppdateringar för projektet sedan 2010. Den 4 juni 2019 accepterade Federico Mena underhållsansvaret för bzip2-projektet. bzip2 komprimerar data i block med en storlek mellan 100 och 900 kB.

Det använder Burrows-Wheeler-transformationen för att omvandla ofta återkommande teckensekvenser till strängar av identiska bokstäver. Den tillämpar sedan move-to-front transform och Huffman-kodning. bzip2:s föregångare bzip använde aritmetisk kodning i stället för Huffman-kodning. Ändringen gjordes på grund av en begränsning i ett mjukvarupatent.

Huffman-kodning

Huffman-kodning är en särskild typ av optimal prefixkod som vanligen används för förlustfri datakomprimering. För att hitta eller använda en sådan kod används Huffman-kodning, en algoritm som utvecklades av David A. Huffman när han var doktorand vid MIT och som publicerades i artikeln ”A Method for the Construction of Minimum-Redundancy Codes” från 1952.

Utgången från Huffmans algoritm kan ses som en kodtabell med variabel längd för kodning av en källsymbol (t.ex. ett tecken i en fil). Algoritmen härleder denna tabell från den uppskattade sannolikheten eller förekomstfrekvensen (vikt) för varje möjligt värde av källsymbolen.

Som i andra entropikodningsmetoder representeras vanligare symboler i allmänhet med färre bitar än mindre vanliga symboler. Huffmans metod kan genomföras på ett effektivt sätt. Man hittar en kod på en tid som är linjär med antalet ingående vikter om dessa vikter är sorterade.

ZStandard

Zstandard (eller zstd) är en förlustfri datakomprimeringsalgoritm som utvecklats av Yann Collet på Facebook. Zstd är referensimplementationen i C. Version 1 av denna implementation släpptes som fri programvara den 31 augusti 2016.
Zstandard utformades för att ge ett kompressionsförhållande som är jämförbart med DEFLATE-algoritmen (som utvecklades 1991 och användes i de ursprungliga ZIP- och gzip-programmen), men snabbare, särskilt vid dekomprimering. Den kan ställas in med komprimeringsnivåer som sträcker sig från negativ 5 (snabbast) till 22 (långsammast i komprimeringshastighet, men bästa kompressionsförhållande).

Zstd med sin maximala komprimeringsnivå ger ett kompressionsförhållande som ligger nära LZMA, LZAHM och PPM. Den presterar bättre än LZA och bzip2. Zstandard når den nuvarande Pareto-gränsen, eftersom den dekomprimerar snabbare än någon annan för närvarande tillgänglig algoritm med ett liknande eller bättre kompressionsförhållande

Vordböcker kan ha stor inverkan på kompressionsförhållandet för små filer, så Zstandard kan använda en kompressionsordbok som tillhandahålls av användaren. Den erbjuder också ett träningsläge, som kan generera en ordbok från en uppsättning prover.

Slutsats

Dessa datakomprimeringsalgoritmer hjälper dig att optimera filstorleken. Olika typer av datakomprimeringsalgoritmer ger dig olika resultat. Men om du inte hittar rätt algoritm här kan du ta en titt på den här guiden och förfina din sökning. Det finns ingen brist på algoritmer, men du måste vara specifik när du letar efter rätt algoritm för ditt projekt.

Jag hoppas att den här artikeln var användbar för dig när du ska välja den bästa datakomprimeringsalgoritmen enligt dina behov. Tack för att du läste den här artikeln. Du kan också läsa Best Encryption and Hashing algorithms.

Stay Tuned