Tapsfri datakomprimering (eller tapsfri datakomprimering ), i informatikk og telekommunikasjon , er en klasse av datakomprimeringsalgoritmer som ikke fører til tap av noen del av den opprinnelige informasjonen under datakomprimerings- /dekompresjonsfasen .
Et eksempel på denne typen komprimering er gitt av formatene Zip , Gzip , Bzip2 , Rar , 7z . Filer der tap av informasjon ikke er akseptabelt, for eksempel tekster eller programmer, bruker denne metoden. For fotografiske bilder brukes generelt ikke tapsfrie algoritmer da de ville være veldig ineffektive, men for bilder som inneholder store områder med rene farger er ofte "tapfri" komprimering ikke bare aktuelt, men også praktisk ( GIF , PNG , MNG , TIFF med LZW, ZIP- eller RLE-komprimering).
Tapsfrie komprimeringsalgoritmer kan ikke alltid garantere at hvert sett med inndata reduseres i størrelse. Med andre ord, for hver tapsfri algoritme vil det være spesielle inngangsdata som ikke vil reduseres i størrelse når de behandles av algoritmen. Dette kan enkelt verifiseres med elementær matematikk:
Det kan sees at forskjellen i størrelse er så stor at det ikke gjør noen forskjell om vi anser filer av nøyaktig N størrelse som et sett med filer som skal komprimeres: dette settet er fortsatt større ( 2 N ) enn settet med komprimerte filer.
Et enda enklere (men tilsvarende) bevis er følgende:
og derfor:
L ( C (F)) <= N-1 L ( C2 (F)) <= N- 2 L ( C k (F)) <= NkEtter maksimalt N iterasjoner må vi ha L ( C N-1 (F)) = 1, fordi hver iterasjon må redusere lengden med minst én bit: denne prosedyren er ikke avhengig av verdien av N. Fra våre hypoteser er det følger at de bare vil eksistere to distinkte filer (den som inneholder bit 0 og den som inneholder bit 1). Dette er åpenbart usant, så hypotesen er feil.
Derfor må enhver komprimeringsalgoritme som gjør noen filer mindre, nødvendigvis gjøre andre filer større eller la dem være uendret i lengde.
I praktisk bruk regnes komprimeringsalgoritmer som faktisk komprimerer de fleste av de vanligste formatene som gode : dette tilsvarer ikke nødvendigvis et mål på godhet i teoretisk forstand (som måler gjennomsnittlig avstand, målt på alle mulige filer, mellom lengden oppnådd og antall entropibiter i filen, som ved en Claude Shannon-teorem er den teoretiske komprimerbarhetsgrensen). Motsatt kan det hende at en teoretisk god algoritme ikke har praktisk anvendelighet (for eksempel fordi den ikke reduserer ofte brukte formater).
Faktisk forventer mange applikasjoner som bruker tapsfri komprimering å forlate uendrede datasett hvis størrelse har økt etter komprimering. Flagget som indikerer at denne datagruppen ikke skal behandles av algoritmen øker åpenbart den effektive størrelsen som er nødvendig for å lagre datagruppen, men det gjør det mulig å unngå ytterligere sløsing med plass og tid som er nødvendig for komprimering/dekompresjon.
Generelt er det ingen indirekte proporsjonalitet mellom kvaliteten på komprimeringen som kan oppnås av en algoritme og dens utførelseshastighet.
La oss ta følgende datastreng for eksempel:
00555555005555550055555500555555500555555500555555Strengen krever 48 tegn, men er umiddelbart tilgjengelig for bruk. En tapsfri komprimeringsalgoritme kan være "sifferantall repetisjoner". Strengen, ved hjelp av denne algoritmen, blir da:
025602560256025602560256Det er klart at dataene ikke lenger er direkte tilgjengelige, men et mellomtrinn (dekompresjon) må utføres.
Siden, gitt det samme dataarkivet, dekompresjon vanligvis er mye hyppigere enn komprimering, er mange algoritmer svært asymmetriske: tiden som kreves for komprimering er vesentlig større enn den som kreves for dekompresjon. Dette skjer også med hensyn til forespørsler om minne og datakapasitet.
Det finnes flere komprimeringsalgoritmer. Blant de mest kjente:
Blant de mange komprimeringsprogrammene bruker mange en algoritme blant de som er oppført ovenfor, mens noen har sine egne:
De støtter alle AES-128 eller AES-256 algoritmekryptering.
Uansett er det mulig å kryptere og komprimere filen med to forskjellige programmer, men dette bremser åpning og lukking, sammenlignet med et enkelt program som gjør begge deler.