Veszteségmentes tömörítés

A veszteségmentes adattömörítési algoritmusok nem garantálják a tömörítést minden bemeneti adathalmaz esetében. Más szóval, bármely veszteségmentes adattömörítési algoritmus esetében lesz olyan bemeneti adathalmaz, amely nem lesz kisebb, amikor az algoritmus feldolgozza, és bármely veszteségmentes adattömörítési algoritmus esetében, amely legalább egy fájlt kisebbé tesz, lesz legalább egy olyan fájl, amelyet nagyobbá tesz. Ez könnyen bizonyítható elemi matematikával, egy számolási érv segítségével, a következőképpen:

• Tegyük fel, hogy minden fájl egy tetszőleges hosszúságú bitekből álló karakterláncként van ábrázolva.
• Tegyük fel, hogy létezik egy tömörítési algoritmus, amely minden fájlt olyan kimeneti fájlba alakít át, amely nem hosszabb, mint az eredeti fájl, és hogy legalább egy fájlt olyan kimeneti fájlba tömörít, amely rövidebb, mint az eredeti fájl.
• Legyen M a legkisebb olyan szám, amelynél létezik egy M bit hosszúságú F fájl, amely rövidebbé tömörül. Legyen N az F tömörített változatának hossza (bitben).
• Mert N<M, minden N hosszúságú fájl megtartja méretét a tömörítés során. Lehetséges, hogy 2N ilyen fájl van. Ez F-fel együtt 2N+1 fájlt eredményez, amelyek mindegyike a 2N N hosszúságú fájl egyikébe tömörül.
• De a 2N kisebb, mint a 2N+1, tehát a galambdugó elv alapján kell lennie olyan N hosszúságú fájlnak, amely egyszerre két különböző bemeneten a tömörítési függvény kimenete. Ezt a fájlt nem lehet megbízhatóan dekomprimálni (a két eredeti közül melyiknek kellene adnia?), ami ellentmond annak a feltételezésnek, hogy az algoritmus veszteségmentes.
• Ezért arra kell következtetnünk, hogy az eredeti hipotézisünk (miszerint a tömörítési függvény egyetlen fájlt sem tesz hosszabbá) szükségszerűen nem igaz.

Minden olyan veszteségmentes tömörítési algoritmus, amely néhány fájlt rövidebbé tesz, szükségszerűen hosszabbá tesz néhány fájlt, de nem szükséges, hogy ezek a fájlok nagyon sokkal hosszabbak legyenek. A legtöbb gyakorlati tömörítési algoritmus biztosít egy “menekülési” lehetőséget, amely kikapcsolja a normál kódolást azon fájlok esetében, amelyek a kódolással hosszabbak lennének. Elméletileg csak egyetlen további bitre van szükség ahhoz, hogy a dekódoló tudassa a dekódolóval, hogy a normál kódolást a teljes bemenetre vonatkozóan kikapcsolták; a legtöbb kódoló algoritmus azonban legalább egy teljes bájtot (és általában több mint egyet) használ erre a célra. Például a deflate tömörített fájloknak soha nem kell 5 bájtnál többel nőniük 65 535 bájt bemenetenként.

Tény, hogy ha N hosszúságú fájlokat tekintünk, és ha minden fájl egyformán valószínű lenne, akkor bármilyen veszteségmentes tömörítés esetén, amely csökkenti valamely fájl méretét, a tömörített fájl várható hossza (az összes lehetséges N hosszúságú fájl átlagában) szükségszerűen nagyobb kell legyen, mint N. Ha tehát semmit sem tudunk a tömörítendő adatok tulajdonságairól, akkor akár nem is tömöríthetjük azokat. Egy veszteségmentes tömörítési algoritmus csak akkor hasznos, ha bizonyos típusú fájlokat nagyobb valószínűséggel tömörítünk, mint másokat; ekkor az algoritmust úgy lehet megtervezni, hogy ezeket az adattípusokat jobban tömörítse.

Az érvelés fő tanulsága tehát nem az, hogy nagy veszteségeket kockáztatunk, hanem csupán az, hogy nem mindig nyerhetünk. Egy algoritmus kiválasztása mindig azt jelenti, hogy implicit módon kiválasztjuk az összes fájl egy részhalmazát, amely hasznosan rövidebb lesz. Ez az elméleti oka annak, hogy miért van szükség különböző tömörítési algoritmusokra a különböző típusú fájlokhoz: nem létezhet olyan algoritmus, amely minden típusú adathoz jó.

A “trükk”, amely lehetővé teszi, hogy a veszteségmentes tömörítési algoritmusok, ha olyan típusú adatokra használják őket, amelyekre tervezték őket, következetesen rövidebbé tömörítsék az ilyen fájlokat, az, hogy az algoritmusok által tervezett fájlok mindegyike rendelkezik valamilyen könnyen modellezhető redundanciával, amelyet az algoritmusnak el kell távolítania, és így a fájlok azon részhalmazába tartoznak, amelyet az algoritmus rövidebbé tud tenni, míg más fájlok nem tömörülnek, vagy még nagyobbak lesznek. Az algoritmusok általában eléggé specifikusan egy adott fájltípusra vannak hangolva: például a veszteségmentes audiotömörítő programok nem működnek jól a szöveges fájlokon, és fordítva.

Különösen a véletlenszerű adatokból álló fájlokat nem lehet következetesen tömöríteni semmilyen elképzelhető veszteségmentes adattömörítő algoritmussal: valójában ezt az eredményt használják a véletlenszerűség fogalmának meghatározására az algoritmikus bonyolultságelméletben.

Bizonyíthatóan lehetetlen olyan algoritmust létrehozni, amely veszteségmentesen képes tömöríteni bármilyen adatot. Bár az évek során számos olyan vállalat állította, hogy “tökéletes tömörítést” értek el, ahol egy tetszőleges számú N véletlen bit mindig N – 1 bitre tömöríthető, az ilyen állításokat nyugodtan el lehet vetni anélkül, hogy az állítólagos tömörítési séma további részleteit megnéznénk. Egy ilyen algoritmus ellentmond a matematika alapvető törvényeinek, mert ha létezne, akkor ismételten alkalmazható lenne bármely fájl veszteségmentes 0 hosszúságúvá csökkentésére. Az állítólag “tökéletes” tömörítési algoritmusokat emiatt gyakran nevezik gúnyosan “mágikus” tömörítési algoritmusoknak.

Másrészt az is bizonyított, hogy nincs algoritmus annak megállapítására, hogy egy fájl a Kolmogorov-féle komplexitás értelmében tömöríthetetlennek tekinthető-e. Ezért lehetséges, hogy egy adott fájl, még ha véletlenszerűnek is tűnik, jelentősen tömöríthető, még a dekompresszor méretét is figyelembe véve. Erre példa a pi matematikai állandó számjegyei, amelyek véletlenszerűnek tűnnek, de egy nagyon kis programmal generálhatók. Azonban még ha nem is lehet megállapítani, hogy egy adott fájl tömöríthetetlen-e, egy egyszerű tétel a tömöríthetetlen karakterláncokról azt mutatja, hogy az adott hosszúságú fájlok több mint 99%-a nem tömöríthető egy bájtnál nagyobb mértékben (beleértve a dekompresszor méretét is).

Matematikai háttérEdit

A tömörítési algoritmus elvileg úgy tekinthető, mint egy függvény (általában oktetteket tartalmazó) sorozatokon. A tömörítés akkor sikeres, ha a kapott szekvencia rövidebb, mint az eredeti szekvencia (és a dekompressziós térkép utasításai). Ahhoz, hogy egy tömörítési algoritmus veszteségmentes legyen, a tömörítési térképnek egy injekciót kell alkotnia a “sima” és a “tömörített” bitsorozatok között.

A pigeonhole-elv tiltja a bijekciót az N hosszúságú sorozatok gyűjteménye és az N-1 hosszúságú sorozatok gyűjteményének bármely részhalmaza között. Ezért nem lehet olyan veszteségmentes algoritmust előállítani, amely minden lehetséges bemeneti szekvencia méretét csökkenti.

Alkalmazási pontok a valós tömörítéselméletbenSzerkesztés

A valós tömörítési algoritmusok tervezői elfogadják, hogy a nagy információs entrópiájú folyamokat nem lehet tömöríteni, és ennek megfelelően tartalmaznak olyan lehetőségeket, amelyek ezt az állapotot felismerik és kezelik. A felismerés nyilvánvaló módja egy nyers tömörítési algoritmus alkalmazása és annak vizsgálata, hogy a kimenete kisebb-e, mint a bemenete. Néha a felismerés heurisztikával történik; például egy tömörítő alkalmazás minden kifinomultabb felismerés nélkül tömöríthetetlennek tekinti azokat a fájlokat, amelyek neve “.zip”-re, “.arj”-re vagy “.lha”-ra végződik. Az ilyen helyzet kezelésének gyakori módja a bemenet vagy a bemenet tömöríthetetlen részeinek idézése a kimeneten, minimalizálva a tömörítési többletköltséget. A zip adatformátum például a “Stored” tömörítési módot adja meg az archívumba szó szerint bemásolt bemeneti fájlokra.

The Million Random Digit ChallengeEdit

Mark Nelson, válaszul a comp.compression című lapokban megjelentek, egy 415 241 bájtos, rendkívül entrópikus tartalmú bináris fájlt készített, és nyilvános, 100 dolláros kihívást intézett bárkihez, aki olyan programot ír, amely a bemenetével együtt kisebb, mint az általa megadott bináris adat, mégis képes hibátlanul visszaállítani azt.

A comp.compression hírcsoport GYIK-je tartalmazza Mike Goldman kihívását, amelyben 5000 dollárt ajánl egy olyan programért, amely képes véletlenszerű adatokat tömöríteni.

A comp.compression hírcsoport GYIK-je tartalmazza Mike Goldman kihívását, amelyben 5000 dollárt ajánl egy olyan programért, amely képes véletlenszerű adatokat tömöríteni. Patrick Craig vállalta a kihívást, de ahelyett, hogy tömörítette volna az adatokat, felosztotta azokat különálló fájlokra, amelyek mindegyike az 5-ös számmal végződött, ami nem volt a fájl részeként tárolva. E karakter elhagyása lehetővé tette, hogy az így kapott fájlok (plusz a szabályoknak megfelelően az azokat újra összerakó program mérete) kisebbek legyenek, mint az eredeti fájl. Tényleges tömörítés azonban nem történt, és a fájlok nevében tárolt információ szükséges volt ahhoz, hogy a fájlokat az eredeti fájlban a megfelelő sorrendben rakják össze, és ezt az információt nem vették figyelembe a fájlméret összehasonlításánál. A fájlok önmagukban tehát nem elegendőek az eredeti fájl rekonstruálásához; a fájlnevekre is szükség van. Patrick Craig egyetértett azzal, hogy nem történt érdemi tömörítés, de azzal érvelt, hogy a kihívás megfogalmazása valójában nem követeli meg ezt. Az esemény teljes története, beleértve annak megvitatását, hogy a kihívás technikailag teljesült-e vagy sem, Patrick Craig weboldalán található.