Datakomprimering

Datakomprimering är en  algoritmisk (vanligtvis reversibel) datatransformation som utförs för att minska volymen de upptar. Den används för mer rationell användning av lagrings- och dataöverföringsenheter . Synonymer  - datapaketering , komprimering , komprimeringskodning , källkodning . _ Det omvända förfarandet kallas dataåterställning (dekompression, dekompression).

Kompression baseras på eliminering av redundans som finns i originaldata. Det enklaste exemplet på redundans är upprepningen av fragment i texten (till exempel ord av naturligt språk eller maskinspråk). Sådan redundans elimineras vanligtvis genom att ersätta den upprepande sekvensen med en referens till ett redan kodat fragment med en indikation på dess längd. En annan typ av redundans beror på det faktum att vissa värden i data som komprimeras förekommer oftare än andra. Att minska mängden data uppnås genom att ersätta ofta förekommande data med korta kodord och sällsynta med långa ( entropikodning ). Att komprimera data som inte har egenskapen redundans (till exempel en slumpmässig signal eller vitt brus , krypterade meddelanden) är i grunden omöjligt utan förlust.

Förlustfri komprimering gör att du kan återställa det ursprungliga meddelandet helt, eftersom det inte minskar mängden information i det, trots minskningen i längd. En sådan möjlighet uppstår endast om fördelningen av sannolikheter på uppsättningen av meddelanden inte är enhetlig, till exempel förekommer inte några av de meddelanden som är teoretiskt möjliga i den tidigare kodningen i praktiken.

Principer för datakomprimering

Kärnan i varje komprimeringsmetod är en datakällsmodell, eller mer exakt, en redundansmodell . Med andra ord, datakomprimering använder viss a priori kunskap om vilken typ av data som komprimeras. Utan sådan information om källan är det omöjligt att göra några antaganden om transformationen som skulle minska storleken på meddelandet. Redundansmodellen kan vara statisk, oförändrad för hela det komprimerade meddelandet, eller byggd eller parametriserad vid komprimerings- (och återställnings)stadiet. Metoder som tillåter att ändra informationsredundansmodellen baserat på indata kallas adaptiva. Icke-adaptiva är vanligtvis högt specialiserade algoritmer som används för att arbeta med data som har väldefinierade och oföränderliga egenskaper. De allra flesta tillräckligt universella algoritmer är adaptiva till viss del.

Alla datakomprimeringsmetoder är indelade i två huvudklasser:

När du använder förlustfri komprimering är det möjligt att helt återställa originaldata, medan förlustkomprimering gör att du kan återställa data med förvrängningar som vanligtvis är obetydliga med tanke på vidare användning av återställd data. Förlustfri komprimering används vanligtvis för att överföra och lagra textdata, datorprogram, mer sällan - för att minska volymen av ljud- och videodata , digitala fotografier , etc., i fall där distorsion är oacceptabel eller oönskad. Förlustkomprimering, som är mycket effektivare än förlustfri komprimering, används vanligtvis för att minska mängden ljud, video och digitala fotografier i fall där sådan minskning är en prioritet och en fullständig matchning av original och återställd data inte krävs.

Egenskaper för komprimeringsalgoritmer och deras tillämpbarhet

Kompressionsförhållande

Kompressionsförhållandet är den huvudsakliga egenskapen hos kompressionsalgoritmen. Det definieras som förhållandet mellan volymen av den ursprungliga okomprimerade datan och volymen av den komprimerade datan, det vill säga: , där k är komprimeringsförhållandet, So är volymen av originaldata  och Sc  är volymen  av den komprimerade datan. Således, ju högre kompressionsförhållande, desto effektivare är algoritmen. Det bör noteras:

Situationen med k  < 1 är fullt möjlig under kompression. Det är i grunden omöjligt att erhålla en förlustfri komprimeringsalgoritm som, givet vilken data som helst, skulle producera data av mindre eller lika lång längd vid utgången. Skälet för detta faktum är att eftersom antalet olika meddelanden med längden n bitar är exakt 2 n , kommer antalet olika meddelanden med längden mindre än eller lika med n (om det finns minst ett meddelande av mindre längd) att vara på mest 2 n . Detta innebär att det är omöjligt att entydigt mappa alla originalmeddelanden till ett komprimerat: antingen kommer vissa originalmeddelanden inte att ha en komprimerad representation, eller så kommer flera originalmeddelanden att ha samma komprimerade representation, vilket innebär att de inte kan särskiljas. Men även när komprimeringsalgoritmen ökar storleken på originaldata är det lätt att säkerställa att deras storlek garanteras inte ökar med mer än 1 bit. Då kommer, även i värsta fall, ojämlikhet att ske: Detta görs på följande sätt: om mängden komprimerad data är mindre än mängden original returnerar vi den komprimerade datan genom att lägga till "1" till dem, annars återgår vi originaldata genom att lägga till "0" till dem).

Kompressionsförhållandet kan antingen vara konstant (vissa algoritmer för att komprimera ljud, bilder etc., såsom A-law , μ-law , ADPCM , trunkerad blockkodning ) och variabel. I det andra fallet kan det fastställas antingen för varje specifikt meddelande eller utvärderas enligt några kriterier:

eller någon annan. I det här fallet beror det förlustgivande komprimeringsförhållandet starkt på det tillåtna komprimeringsfelet eller kvaliteten , som vanligtvis fungerar som en algoritmparameter. I det allmänna fallet kan endast datakomprimeringsmetoder med förlust ge ett konstant komprimeringsförhållande.

Tillåtlighet för förluster

Huvudkriteriet för att skilja mellan komprimeringsalgoritmer är närvaron eller frånvaron av förluster som beskrivs ovan. I det allmänna fallet är förlustfria komprimeringsalgoritmer universella i den meningen att deras användning säkerligen är möjlig för data av vilken typ som helst, medan möjligheten att använda förlustfri komprimering måste motiveras. För vissa datatyper är förvrängningar i princip inte tillåtna. Bland dem

Systemkrav för algoritmer

Olika algoritmer kan kräva olika mängd resurser i det datorsystem där de är implementerade:

Generellt sett beror dessa krav på algoritmens komplexitet och "intelligens". Den allmänna trenden är följande: ju effektivare och mångsidigare algoritmen är, desto större krav på datorresurser ställer den. Men i specifika fall kan enkla och kompakta algoritmer fungera lika bra som komplexa och universella. Systemkraven avgör deras konsumentkvaliteter: ju mindre krävande algoritmen är, desto enklare och därför mer kompakt, tillförlitligt och billigt system kan det implementeras.

Eftersom komprimerings- och återställningsalgoritmer fungerar i par, spelar förhållandet mellan systemkrav och dem roll. Det är ofta möjligt, genom att komplicera en algoritm, att avsevärt förenkla en annan. Således är tre alternativ möjliga:

Komprimeringsalgoritmen kräver mer beräkningsresurser än återställningsalgoritmen. Detta är det vanligaste förhållandet, typiskt för fall där en gång komprimerad data kommer att användas upprepade gånger. Ett exempel är digitala ljud- och videospelare. Komprimerings- och återställningsalgoritmerna kräver ungefär lika stora beräkningsresurser. Det mest acceptabla alternativet för kommunikationslinjer, när komprimering och återställning sker en gång i dess två ändar (till exempel i digital telefoni). Kompressionsalgoritmen är betydligt mindre krävande än återställningsalgoritmen. Denna situation är typisk för fall där komprimeringsproceduren implementeras av en enkel, ofta bärbar, enhet för vilken mängden tillgängliga resurser är mycket kritisk, till exempel en rymdfarkost eller ett stort distribuerat nätverk av sensorer. Det kan också vara data som behöver dekomprimeras i en mycket liten andel av fallen, till exempel CCTV-bilder.

Okända datakomprimeringsalgoritmer

Det finns två huvudsakliga metoder för att komprimera data av ett okänt format:

Se även

Litteratur

Länkar

 Kompressionsmetoder _
Teori
Information
Enheter
Förlust mindre
Entropikompression
Ordboksmetoder
Övrig
Audio
Teori
Metoder
Övrig
Bilder
Villkor
Metoder
Övrig
Video
Villkor
Metoder
Övrig