Förlustfri komprimering

Algoritmer för förlustfri datakomprimering kan inte garantera komprimering för alla indata. Med andra ord kommer det för varje förlustfri datakomprimeringsalgoritm att finnas en datamängd som inte blir mindre när den behandlas av algoritmen, och för varje förlustfri datakomprimeringsalgoritm som gör minst en fil mindre kommer det att finnas minst en fil som den gör större. Detta kan lätt bevisas med elementär matematik med hjälp av ett räkneargument enligt följande:

• Antag att varje fil representeras som en sträng av bitar av godtycklig längd.
• Anta att det finns en komprimeringsalgoritm som omvandlar varje fil till en utdatafil som inte är längre än den ursprungliga filen, och att minst en fil kommer att komprimeras till en utdatafil som är kortare än den ursprungliga filen.
• Låt M vara det minsta talet som gör att det finns en fil F med längden M bitar som komprimeras till något kortare. Låt N vara längden (i bitar) på den komprimerade versionen av F.
• Eftersom N<M behåller varje fil med längden N sin storlek under komprimeringen. Det finns 2N sådana filer möjliga. Tillsammans med F ger detta 2N+1 filer som alla komprimeras till en av de 2N filerna med längd N.
• Men 2N är mindre än 2N+1, så enligt pigeonhole-principen måste det finnas någon fil med längd N som samtidigt är resultatet av komprimeringsfunktionen på två olika ingångar. Den filen kan inte dekomprimeras på ett tillförlitligt sätt (vilket av de två originalen ska det ge?), vilket motsäger antagandet att algoritmen var förlustfri.
• Vi måste därför dra slutsatsen att vår ursprungliga hypotes (att komprimeringsfunktionen inte gör någon fil längre) med nödvändighet är osann.

En förlustfri komprimeringsalgoritm som gör vissa filer kortare måste med nödvändighet göra vissa filer längre, men det är inte nödvändigt att dessa filer blir väldigt mycket längre. De flesta praktiska komprimeringsalgoritmer tillhandahåller en ”escape”-funktion som kan stänga av den normala kodningen för filer som skulle bli längre av att kodas. I teorin behövs bara en enda extra bit för att tala om för avkodaren att den normala kodningen har stängts av för hela inmatningen, men de flesta kodningsalgoritmer använder minst en hel byte (och vanligtvis mer än en) för detta ändamål. Till exempel behöver deflate-komprimerade filer aldrig växa med mer än 5 byte per 65 535 byte indata.

För varje förlustfri komprimering som minskar storleken på en viss fil måste den förväntade längden på en komprimerad fil (i genomsnitt över alla möjliga filer med längden N) nödvändigtvis vara större än N. Så om vi inte vet något om egenskaperna hos de data vi komprimerar kan vi lika gärna låta bli att komprimera dem över huvud taget. En algoritm för förlustfri komprimering är endast användbar när det är mer sannolikt att vi komprimerar vissa typer av filer än andra; då kan algoritmen utformas så att den komprimerar dessa typer av data bättre.

Den viktigaste lärdomen av argumentet är alltså inte att man riskerar stora förluster, utan bara att man inte alltid kan vinna. Att välja en algoritm innebär alltid implicit att man väljer en delmängd av alla filer som kommer att bli användbart kortare. Detta är det teoretiska skälet till att vi måste ha olika komprimeringsalgoritmer för olika typer av filer: det kan inte finnas någon algoritm som är bra för alla typer av data.

Det ”knep” som gör att algoritmer för förlustfri komprimering, som används på den typ av data som de är utformade för, konsekvent komprimerar sådana filer till en kortare form är att de filer som algoritmerna är utformade för att agera på alla har någon form av lättmodellerad redundans som algoritmen är utformad för att avlägsna, och därmed tillhör den delmängd av filer som algoritmen kan göra kortare, medan andra filer inte skulle komprimeras eller till och med bli större. Algoritmer är i allmänhet ganska specifikt inställda på en viss typ av fil: till exempel fungerar förlustfria ljudkomprimeringsprogram inte bra på textfiler och vice versa.

I synnerhet kan filer med slumpmässiga data inte komprimeras konsekvent av någon tänkbar förlustfri datakomprimeringsalgoritm: detta resultat används faktiskt för att definiera begreppet slumpmässighet i algoritmisk komplexitetsteori.

Det är bevisligen omöjligt att skapa en algoritm som kan komprimera alla data utan förlust. Även om det genom åren har förekommit många påståenden om företag som uppnått ”perfekt komprimering” där ett godtyckligt antal N slumpmässiga bitar alltid kan komprimeras till N – 1 bitar, kan dessa påståenden säkert förkastas utan att man ens har tittat på ytterligare detaljer om det påstådda komprimeringssystemet. En sådan algoritm strider mot grundläggande matematiska lagar eftersom den, om den fanns, skulle kunna tillämpas upprepade gånger för att förlustfritt reducera vilken fil som helst till längden 0. Påstådda ”perfekta” komprimeringsalgoritmer kallas ofta hånfullt för ”magiska” komprimeringsalgoritmer av den anledningen.

Å andra sidan har det också bevisats att det inte finns någon algoritm för att avgöra om en fil är inkomprimerbar i den mening som avses i Kolmogorovs komplexitet. Därför är det möjligt att en viss fil, även om den verkar slumpmässig, kan vara avsevärt komprimerad, till och med inklusive storleken på dekompressorn. Ett exempel är siffrorna i den matematiska konstanten pi, som verkar slumpmässiga men som kan genereras av ett mycket litet program. Men även om det inte går att avgöra om en viss fil är inkomprimerbar visar en enkel sats om inkomprimerbara strängar att över 99 % av filerna av en given längd inte kan komprimeras med mer än en byte (inklusive storleken på dekompressorn).

Matematisk bakgrundRedigera

Abstrakt sett kan en komprimeringsalgoritm ses som en funktion på sekvenser (normalt av oktetter). Kompressionen är framgångsrik om den resulterande sekvensen är kortare än den ursprungliga sekvensen (och instruktionerna för dekompressionskartan). För att en komprimeringsalgoritm ska vara förlustfri måste kompressionskartan bilda en injektion från ”vanliga” till ”komprimerade” bitsekvenser.

Principen om duvhål förbjuder en injektion mellan samlingen av sekvenser med längden N och varje delmängd av samlingen av sekvenser med längden N-1. Därför är det inte möjligt att producera en förlustfri algoritm som minskar storleken på varje möjlig inmatningssekvens.

Tillämpningspunkter i verklig komprimeringsteoriRedigera

Designers av verkliga komprimeringsalgoritmer accepterar att strömmar med hög informationsentropi inte kan komprimeras, och inkluderar följaktligen faciliteter för att upptäcka och hantera detta tillstånd. Ett uppenbart sätt att upptäcka detta är att tillämpa en rå komprimeringsalgoritm och testa om dess utdata är mindre än dess indata. Ibland görs upptäckten med hjälp av heuristik; till exempel kan ett komprimeringsprogram betrakta filer vars namn slutar på ”.zip”, ”.arj” eller ”.lha” som okomprimerbara utan någon mer sofistikerad upptäckt. Ett vanligt sätt att hantera denna situation är att citera inmatningen, eller icke-komprimerbara delar av inmatningen i utmatningen, för att minimera komprimeringskostnaden. I zip-dataformatet anges t.ex. komprimeringsmetoden ”Stored” för inmatningsfiler som har kopierats in i arkivet ordagrant.

The Million Random Digit ChallengeEdit

Mark Nelson, som svar på påståenden om magiska komprimeringsalgoritmer som förekommer i comp.compression, har konstruerat en binär fil på 415 241 byte med ett mycket entropiskt innehåll och utfärdat en offentlig utmaning på 100 dollar till vem som helst att skriva ett program som tillsammans med sin indata skulle vara mindre än hans tillhandahållna binära data men ändå kunna återskapa den utan fel.

FaQ för nyhetsgruppen comp.compression innehåller en utmaning från Mike Goldman som erbjuder 5 000 dollar för ett program som kan komprimera slumpmässiga data. Patrick Craig antog utmaningen, men i stället för att komprimera uppgifterna delade han upp dem i separata filer som alla slutade på siffran 5, som inte lagrades som en del av filen. Genom att utelämna detta tecken kunde de resulterande filerna (plus, i enlighet med reglerna, storleken på det program som satte ihop dem igen) vara mindre än den ursprungliga filen. Ingen egentlig komprimering ägde dock rum, och den information som lagrades i filernas namn var nödvändig för att sätta ihop dem i rätt ordning i den ursprungliga filen, och denna information togs inte i beaktande vid jämförelsen av filstorleken. Filerna i sig är alltså inte tillräckliga för att återskapa den ursprungliga filen, utan filnamnen är också nödvändiga. Patrick Craig höll med om att ingen meningsfull komprimering hade ägt rum, men hävdade att formuleringen av utmaningen egentligen inte krävde detta. En fullständig historik över händelsen, inklusive en diskussion om huruvida utmaningen var tekniskt uppfylld eller inte, finns på Patrick Craigs webbplats.