See on masintõlge ja ingliskeelne tekst on originaal. Loe originaali
Ükski tihendusprogramm ei suuda tihendada iga faili ja tõestus võtab ühe lõigu
Iga mõne aasta tagant teatab keegi algoritmist, mis pakib mis tahes faili 50% võrra kokku. Kaks korda rakendatuna tihendaks see iga faili veerandini ja piisavalt palju kordi rakendatuna üheainsa bitini.
Vaatleme kõiki võimalikke täpselt 1,000-bitiseid faile. Neid on 2¹⁰⁰⁰. Nüüd vaatleme kõiki võimalikke sellest lühemaid faile — 999 bitti, 998 ja nii edasi kuni tühjuseni. Liitke need kokku ja saate 2¹⁰⁰⁰ − 1 faili, mis on ühe võrra vähem kui alustades.
Kadudeta tihendusprogramm peab kujutama erinevad sisendid erinevateks väljunditeks, sest muidu ei saaks see oma tegevust tagasi pöörata. Kuid 2¹⁰⁰⁰ eset ei saa mahutada 2¹⁰⁰⁰ − 1 kasti ilma, et kahte eset ühte kasti ei pandaks. Seega ei tihenda ükski kadudeta tihendusprogramm iga sisendit. Kui see tihendab mõnda, peab see teisi suurendama.
Algoritmi kohta ei olnud vaja teha ühtegi eeldust, seega ei saa ükski nutikas lahendus sellest mööda hiilida. See on Dirichlet' printsiip ja just seepärast on igal tegelikul tihendusprogrammil halvim juhtum, kus väljund on sisendist veidi suurem: originaal pluss mõned baidid päist.
Mida siis tegelikult ära kasutatakse
Struktuuri. Pakkimine ei eemalda mingis hägusas mõttes „redundantsust”; see määras lühikesed koodid ümber asjadele, mis esinevad sageli.
Ingliskeelne tekst on ülimalt ettearvatav. Pärast tähti „th” on järgmine täht valdaval hulgal juhtudest „e”. Tühikud on kõige sagedasem märk. Pilt seinast koosneb pikalt peaaegu identsete pikslite jadadest. Igal juhul on failil, kui seda vaadelda juhusliku suurusena, madal entropia — keskmine üllatus sümboli kohta on väike — ning Shannon näitas 1948. aastal, et see suurus on täpne alampiir. Allikat ei saa kodeerida vähema arvu bittidega sümboli kohta kui selle entropia, ning sellele piirile on alati võimalik jõuda suvaliselt lähedale.
Mis muudab pakkimise võistluseks ennustamise nimel. Tihendusprogramm, mis mudeldab allikat hästi, määrab lühikesed koodid täpselt ja jõuab entropia lähedale. Tihendusprogramm, mis mudeldab seda halvasti, raiskab bitte. Seetõttu meenutab tekstitihenduse tipptase üha enam keelemudelit: järgmise sümboli hea ennustamine ja hea tihendamine on üks ja sama probleem erinevas kuues.
Alampiirile lähenemist saab jälgida tööriistas Entropy Coding ning koodide määramist ennast tööriistas Huffman Encoding.
Miks ZIP-faili uuesti pakkimine ei anna midagi
Hästi tihendatud failist on selle struktuur eemaldatud. See, mis järele jääb, meenutab statistiliselt müra: iga sümbol on peaaegu võrdselt tõenäoline ja naabrite vahel puuduvad kasulikud korrelatsioonid. Selle entropia biti kohta on lähedal arvule 1, seega ei ole enam midagi ära kasutada, ning teine läbivaatus muudab selle tavaliselt veidi suuremaks — põhjuseks päis ning pakkija suutmatus leida ühtegi kodeerimist väärivat mustrit.
Sama selgitab, miks JPEG ZIP-arhiivi sees vaevalt tiheneb, miks krüpteeritud andmed ei ole tihendatavad (hea krüpteering on loodud näima just mürana) ja miks enne krüpteerimist tihendamine on õige järjekord — pärast seda pole enam midagi tihendada.
Aus versioon väitest „50% väiksem”
Iga tõene tihendamisväide on väide teatava sisendite klassi kohta. „Vähendab ingliskeelse proosa mahtu poole võrra” on reaalne ja kasulik väide. „Vähendab mis tahes faili mahtu poole võrra” on tõestatavalt väär ning selle tõestuseks on artikli alguses olev lõik.
Kus kadudega pakkimine on täiesti teine teema
Ükski neist piirangutest ei kehti kadudega pakkimise kohta, sest see ei pea olema pööratav. JPEG, MP3 ja iga videokoodek eemaldavad infot tahtlikult, valides kõrvaleheidetava info mudelite alusel, mis määravad, mida inimsilm ja -kõrv ei märka.
See muudab küsimuse „kui palju on siin struktuuri” küsimuseks „kui palju saab ära visata, enne kui keegi kaebab”, mis on küsimus taju, mitte matemaatika kohta. Seetõttu on kadudega tihendamise kompromissil reguleerimisnupp ja kadudeta tihendamisel ei ole: entropia on fakt andmete kohta, kuid lubatav moonutus on hinnang sihtrühma taju kohta.
Ainus asi, mis on mõlemale ühine, on see, et aus spetsifikatsioon on alati tingimuslik. Kadudeta tihendusprogramm on hea teatud sisendite klassi jaoks. Kadudega tihendusprogramm on hea teatud moonutuse korral.