Tabsfri kompression

Tabsfri datakomprimering er en  klasse af datakomprimeringsalgoritmer (video, lyd, grafik, dokumenter præsenteret i digital form, programmer i programmeringssprog og maskinkoder og mange andre typer data), når de bruger hvilke kodede data kan rekonstrueres utvetydigt til nærmeste bit , pixel , voxel osv. I dette tilfælde gendannes de originale data fuldstændigt fra den komprimerede tilstand. Denne type komprimering er fundamentalt forskellig fra datakomprimering med tab . For hver type digital information er der som regel optimale tabsfri komprimeringsalgoritmer.

Tabsfri datakomprimering bruges i mange applikationer. For eksempel bruges det i alle filarkivere . Det bruges også som en komponent i tabsgivende kompression.

Tabsfri komprimering bruges, når identiteten af ​​de komprimerede data til originalen er vigtig. Et almindeligt eksempel er eksekverbare filer og kildekode. Nogle grafiske filformater (såsom PNG ) bruger kun tabsfri komprimering, mens andre ( TIFF , FLIF eller GIF ) kan bruge både tabsfri og tabsfri komprimering.

Kompression og kombinatorik

Sætningen er let at bevise.

For enhver N > 0 er der ingen tabsfri komprimeringsalgoritme, der:

  1. Enhver fil, der ikke er længere end N bytes, beholder enten den samme længde eller reducerer den.
  2. Reducerer en fil med en længde på ikke mere end N med mindst én byte.

Bevis. Uden tab af generalitet kan vi antage, at filen A med længden nøjagtigt N er faldet . Lad os betegne alfabetet som . Lad os overveje et sæt . I dette sæt af kildefiler, mens der ikke er mere end . Derfor er dekompressionsfunktionen tvetydig , en selvmodsigelse. Sætningen er blevet bevist.

Denne teorem kaster dog ikke det mindste en skygge af tabsfri kompression. Faktum er, at enhver komprimeringsalgoritme kan ændres, så den øger størrelsen med højst 1 bit: hvis algoritmen har reduceret filen, skriver vi "1", så skriver den komprimerede sekvens, hvis den er steget, " 0", derefter den originale.

Så ukomprimerbare fragmenter vil ikke føre til ukontrolleret "bloat" af arkivet. "Rigtige" filer med længden N er meget mindre end (de siger, at dataene har lav informationsentropi ) - for eksempel er det usandsynligt, at bogstavkombinationen "genert" vil forekomme i en meningsfuld tekst, og i digitaliseret lyd kan niveauet ikke spring fra 0 til 100 %. Derudover er det på grund af specialiseringen af ​​algoritmer for en bestemt type data (tekst, grafik, lyd osv.) muligt at opnå en høj grad af komprimering: for eksempel komprimerer universelle algoritmer, der bruges i arkiveringssystemer , lyd med ca. tredje (1,5 gange), mens FLAC  er 2,5 gange. De fleste specialiserede algoritmer er til ringe nytte for "fremmede" filtyper: for eksempel er lyddata dårligt komprimeret af en algoritme designet til tekster.

Tabsfri komprimeringsmetode

Generelt er betydningen af ​​tabsfri komprimering som følger: Der findes et eller andet mønster i de originale data, og under hensyntagen til dette mønster genereres en anden sekvens, der fuldstændigt beskriver den originale. For eksempel, for at kode binære sekvenser med mange 0'ere og få 1'ere, kan vi bruge følgende substitution:

00 → 0 01 → 10 10 → 110 11 → 111

I dette tilfælde seksten bits

00 01 00 00 11 10 00 00

vil blive konverteret til tretten bits

0 10 0 0 111 110 0 0

En sådan substitution er en præfikskode , det vil sige, at den har følgende egenskab: hvis vi skriver en komprimeret streng uden mellemrum, kan vi stadig sætte mellemrum i den - og derfor gendanne den oprindelige sekvens. Den bedst kendte præfikskode er Huffman-koden .

De fleste tabsfri komprimeringsalgoritmer fungerer i to trin: den første genererer en statistisk model for de indgående data, den anden bitmaps de indgående data, ved at bruge modellen til at producere "sandsynlighed" (det vil sige hyppigt forekommende) data, som bruges oftere end "usandsynlige" data. .

Statistiske algoritmemodeller for tekst (eller tekstbaserede binære data såsom eksekverbare filer) inkluderer:

Kodningsalgoritmer gennem generering af bitsekvenser:

Tabsfri komprimeringsmetoder

Se hele listen i Kategori: Datakomprimering

Multipurpose

Lydkomprimering

Grafikkomprimering

Videokomprimering

Tekstkomprimering

Eksempler på algoritmer

Eksempler på formater og deres implementeringer

Se også

Noter

  1. ↑ TIFF v6-specifikation (downlink) . Dato for adgang: 18. december 2010. Arkiveret fra originalen 3. juli 2012. 

Links

 Kompressionsmetoder _
Teori
Information
Enheder
Tabsfri
Entropi kompression
Ordbogsmetoder
Andet
Lyd
Teori
Metoder
Andet
Billeder
Vilkår
Metoder
Andet
Video
Vilkår
Metoder
Andet