Compressie zonder verlies

Algoritmen voor verliesloze gegevenscompressie kunnen geen compressie voor alle invoergegevensverzamelingen garanderen. Met andere woorden, voor elk verliesloos gegevenscompressiealgoritme zal er een gegevensreeks zijn die niet kleiner wordt wanneer het algoritme het verwerkt, en voor elk verliesloos gegevenscompressiealgoritme dat ten minste één bestand kleiner maakt, zal er ten minste één bestand zijn dat het groter maakt. Dit is eenvoudig te bewijzen met elementaire wiskunde met behulp van een telredenering, en wel als volgt:

• Aannemelijk dat elk bestand wordt voorgesteld als een string van bits van een willekeurige lengte.
• Aannemelijk dat er een compressie-algoritme is dat elk bestand omzet in een uitvoerbestand dat niet langer is dan het oorspronkelijke bestand, en dat ten minste één bestand wordt gecomprimeerd tot een uitvoerbestand dat korter is dan het oorspronkelijke bestand.
• Laat M het kleinste getal zijn zodat er een bestand F met lengte M bits is dat tot iets korter wordt gecomprimeerd. Zij N de lengte (in bits) van de gecomprimeerde versie van F.
• Omdat N<M, behoudt elk bestand van lengte N zijn grootte tijdens de compressie. Er zijn 2N zulke bestanden mogelijk. Samen met F maakt dit 2N+1 bestanden die allemaal comprimeren tot een van de 2N bestanden van lengte N.
• Maar 2N is kleiner dan 2N+1, dus volgens het hokjesprincipe moet er een bestand van lengte N zijn dat tegelijkertijd de output is van de compressiefunctie op twee verschillende inputs. Dat bestand kan niet op betrouwbare wijze worden gedecomprimeerd (welk van de twee originelen zou dat moeten opleveren?), hetgeen in tegenspraak is met de aanname dat het algoritme verliesloos was.
• We moeten dus concluderen dat onze oorspronkelijke hypothese (dat de compressiefunctie geen enkel bestand langer maakt) noodzakelijkerwijs onwaar is.

Elk verliesloos compressiealgoritme dat sommige bestanden korter maakt, moet noodzakelijkerwijs sommige bestanden langer maken, maar het is niet noodzakelijk dat die bestanden heel veel langer worden. De meeste praktische compressiealgoritmen bieden een “escape”-faciliteit waarmee de normale codering kan worden uitgeschakeld voor bestanden die langer zouden worden door te worden gecodeerd. In theorie is slechts één extra bit nodig om de decoder te vertellen dat de normale codering voor de gehele invoer is uitgeschakeld; de meeste coderingsalgoritmen gebruiken echter ten minste één volledige byte (en meestal meer dan één) voor dit doel. Zo hoeven deflate gecomprimeerde bestanden nooit met meer dan 5 bytes per 65.535 bytes invoer te groeien.

In feite, als we bestanden van lengte N beschouwen, en als alle bestanden even waarschijnlijk zouden zijn, dan moet voor elke verliesloze compressie die de grootte van een of ander bestand vermindert, de verwachte lengte van een gecomprimeerd bestand (gemiddeld over alle mogelijke bestanden van lengte N) noodzakelijkerwijs groter zijn dan N. Dus als we niets weten over de eigenschappen van de gegevens die we comprimeren, kunnen we ze net zo goed helemaal niet comprimeren. Een verliesloos compressiealgoritme is alleen nuttig als we bepaalde soorten bestanden eerder zullen comprimeren dan andere; dan kan het algoritme zo worden ontworpen dat het die soorten gegevens beter comprimeert.

Dus de belangrijkste les van het argument is niet dat men grote verliezen riskeert, maar alleen dat men niet altijd kan winnen. Een algoritme kiezen betekent altijd impliciet dat een deelverzameling van alle bestanden wordt geselecteerd die nuttig korter zal worden. Dit is de theoretische reden waarom we verschillende compressie-algoritmen nodig hebben voor verschillende soorten bestanden: er kan niet één algoritme zijn dat goed is voor alle soorten gegevens.

De “truc” die verliesloze compressiealgoritmen kunnen toepassen op het soort gegevens waarvoor ze zijn ontworpen, om dergelijke bestanden consistent te comprimeren tot een kortere vorm, is dat de bestanden waarvoor de algoritmen zijn ontworpen, allemaal een vorm van gemakkelijk te modelleren redundantie hebben die het algoritme moet verwijderen, en dus behoren tot de subset van bestanden die dat algoritme korter kan maken, terwijl andere bestanden niet zouden worden gecomprimeerd of zelfs groter zouden worden. Algoritmen zijn over het algemeen heel specifiek afgestemd op een bepaald type bestand: zo werken verliesvrije audiocompressieprogramma’s niet goed op tekstbestanden, en omgekeerd.

In het bijzonder kunnen bestanden met willekeurige gegevens niet consistent worden gecomprimeerd door enig denkbaar verliesloos algoritme voor datacompressie: dit resultaat wordt zelfs gebruikt om het begrip willekeurigheid te definiëren in de algoritmische complexiteitstheorie.

Het is aantoonbaar onmogelijk om een algoritme te maken dat alle gegevens verliesloos kan comprimeren. Hoewel er in de loop der jaren veel beweringen zijn geweest van bedrijven die “perfecte compressie” hebben bereikt, waarbij een willekeurig aantal N willekeurige bits altijd kan worden gecomprimeerd tot N – 1 bits, kunnen dit soort beweringen veilig terzijde worden geschoven zonder zelfs maar te kijken naar enige verdere details betreffende het beweerde compressieschema. Een dergelijk algoritme is in strijd met de fundamentele wetten van de wiskunde, want als het zou bestaan, zou het herhaaldelijk kunnen worden toegepast om elk bestand verliesloos te reduceren tot lengte 0. Beweerdelijk “perfecte” compressie-algoritmen worden om deze reden vaak spottend “magische” compressie-algoritmen genoemd.

Aan de andere kant is ook bewezen dat er geen algoritme bestaat om te bepalen of een bestand incompressibel is in de zin van Kolmogorov complexiteit. Het is dus mogelijk dat een bepaald bestand, ook al lijkt het willekeurig, aanzienlijk wordt gecomprimeerd, zelfs met inbegrip van de grootte van de decompressor. Een voorbeeld zijn de cijfers van de wiskundige constante pi, die willekeurig lijken maar door een zeer klein programma kunnen worden gegenereerd. Maar ook al kan niet worden bepaald of een bepaald bestand incompressible is, een eenvoudige stelling over incompressible strings laat zien dat meer dan 99% van de bestanden van een gegeven lengte niet met meer dan één byte (inclusief de grootte van de decompressor) kan worden gecomprimeerd.

Wiskundige achtergrondEdit

Afstract kan een compressie-algoritme worden gezien als een functie op sequenties (normaal gesproken van octetten). De compressie is geslaagd als de resulterende sequentie korter is dan de oorspronkelijke sequentie (en de instructies voor de decompressiemap). Wil een compressie-algoritme verliesvrij zijn, dan moet de compressiekaart een injectie vormen van “gewone” naar “gecomprimeerde” bitreeksen.

Het hokjesprincipe verbiedt een bijectie tussen de verzameling van reeksen van lengte N en elke deelverzameling van de verzameling van reeksen van lengte N-1. Daarom is het niet mogelijk een verliesvrij algoritme te produceren dat de grootte van elke mogelijke invoerreeks vermindert.

Toepassingspunten in de echte compressietheorieEdit

De ontwerpers van echte compressiealgoritmen aanvaarden dat stromen met een hoge informatie-entropie niet kunnen worden gecomprimeerd, en nemen dienovereenkomstig voorzieningen op om deze toestand te detecteren en te behandelen. Een voor de hand liggende manier van detectie is het toepassen van een ruw compressiealgoritme en te testen of de output kleiner is dan de input. Soms gebeurt de detectie door heuristiek; een compressietoepassing kan bijvoorbeeld bestanden waarvan de naam eindigt op “.zip”, “.arj” of “.lha” als niet-comprimeerbaar beschouwen zonder dat een meer verfijnde detectie nodig is. Een gebruikelijke manier om met deze situatie om te gaan is het citeren van invoer, of nietcomprimeerbare delen van de invoer in de uitvoer, om de compressie-overhead te minimaliseren. Het zip-gegevensformaat specificeert bijvoorbeeld de “compressiemethode” van “Opgeslagen” voor invoerbestanden die woordelijk in het archief zijn gekopieerd.

The Million Random Digit ChallengeEdit

Mark Nelson heeft, in reactie op beweringen over magische compressie-algoritmen die verschijnen in comp.compression, een 415.241 byte binair bestand met een zeer entropische inhoud geconstrueerd, en een publieke uitdaging van $100 aan eenieder gegeven om een programma te schrijven dat, samen met de invoer, kleiner zou zijn dan de door hem geleverde binaire data en toch in staat zou zijn deze zonder fouten te reconstrueren.

De FAQ voor de comp.compression nieuwsgroep bevat een uitdaging door Mike Goldman die $5.000 biedt voor een programma dat willekeurige data kan comprimeren. Patrick Craig nam de uitdaging aan, maar in plaats van de gegevens te comprimeren, splitste hij ze op in afzonderlijke bestanden die alle eindigden op het cijfer 5, dat niet als deel van het bestand was opgeslagen. Door dit teken weg te laten waren de resulterende bestanden (plus, in overeenstemming met de regels, de grootte van het programma dat ze opnieuw samenvoegde) kleiner dan het oorspronkelijke bestand. Er vond echter geen feitelijke compressie plaats, en de in de namen van de bestanden opgeslagen informatie was nodig om ze in het oorspronkelijke bestand in de juiste volgorde weer samen te voegen, en met deze informatie werd geen rekening gehouden bij de vergelijking van de bestandsgrootte. De bestanden zelf zijn dus niet voldoende om het oorspronkelijke bestand opnieuw samen te stellen; ook de bestandsnamen zijn noodzakelijk. Patrick Craig was het ermee eens dat er geen zinvolle compressie had plaatsgevonden, maar betoogde dat de bewoordingen van de uitdaging dit eigenlijk niet vereisten. Een volledige geschiedenis van het evenement, inclusief discussie over het al dan niet technisch voldoen aan de uitdaging, staat op de website van Patrick Craig.