par Michael1954 » Sam 26 Fév 2011, 11:39
From: HenryHill
Volgens het pigeonhole-principe is het niet mogelijk om alle permutaties van X bytes te comprimeren tot een representatie die kleiner dan X bytes is. Als je dit wel doet loopt je tijdens het decomprimeren tegen het probleem aan dat er 1 gecomprimeerd bestand zich laat terugvertalen in meer dan 1 ongecomprimeerde mogelijkheden. Effectief heb je dus informatie weggegooid waardoor je niet het originele bestand terug kan halen.
Vandaar ook dat compressie (uberhaupt, alle vormen van datareductie, of Sloot het nu wel of geen compressie noemt is irrelevant) gebaseerd is op het principe: we reduceren sommige bestanden van X bytes tot een grootte die kleiner is dan X bytes, ten koste van de minder waarschijnlijke bestanden, die meer dan X bytes zullen moeten innemen.
Deze reductie staat of valt met de hoeveelheid informatie die in zo'n bestand is opgeslagen, de zgn. Entropie (bedacht door Shannon). En de entropie hangt af van de mate van voorspelbaarheid van deze gegevens. Hoge voorspelbaarheid -> lage entropie -> grote compressie. Lage voorspelbaarheid of onwaarschijnlijke combinatie gegevens -> hoge entropie -> expansie.
Gegeven de kansverdeling op het aantal mogelijke bestanden, kan men de bijbehorende entropie uitrekenen en, voor een bepaald bestand een zekere compressie bereiken.
Het feit dat deze maat van informatie, entropie, ook echt een absolute ondergrens bepaalt volgt uit inductie: stel dat elk bestand van X bytes teruggebracht kan worden tot een bestand van X-1 bytes. Wat let je om hetzelde algoritme nog een keer toe te passen op dat bestand van X-1 bytes om het te comprimeren tot X-2 bytes? Niks. En dan kan je dat nog een keer doen tot X-3 bytes, etc.
Net zolang totdat de bestandsgrootte 0 nadert. Iets wat pertinent onmogelijk is, omdat er zeker meer dan 256 films / bestanden bestaan.
Ergo: er moet wel een harde ondergrens bestaan aan de mate waarin je bestanden kunt comprimeren.