Entropia explicată

În 1948, un inginer de la Bell Labs, Claude Shannon, a pus o întrebare pe care nimeni nu o formulase precis: câtă informație conține un mesaj? Răspunsul lui a fost un număr, măsurat în biți, care nu depinde de ce înseamnă un mesaj, ci de cât de surprinzător este. Acest număr, entropia, stabilește limitele oricărui program de compresie, ale oricărei legături de rețea și ale oricărui dispozitiv de stocare și explică de ce unele texte se micșorează la o fracțiune din mărimea lor, în timp ce altele nu pot fi comprimate deloc.

Bare cu probabilitățile literelor care se estompează de la cele frecvente la cele rare, cu curba entropiei coborând pe măsură ce se cunoaște mai mult context
Bare cu probabilitățile literelor care se estompează de la cele frecvente la cele rare, cu curba entropiei coborând pe măsură ce se cunoaște mai mult context

Informația este surpriză

Ideea lui Shannon a fost să măsoare informația după cât de neașteptat este un mesaj, nu după ce înseamnă. Dacă știți deja răspunsul, a-l auzi nu vă spune nimic; dacă ar fi putut fi oricare dintre o mie de lucruri, vă spune mult. Un mesaj care alege una dintre două posibilități la fel de probabile poartă un bit. Una dintre patru cere doi biți, una dintre opt trei biți și, în general, una dintre N posibilități la fel de probabile cere log₂ N biți. Prin urmare, un simbol care apare cu probabilitatea p poartă −log₂ p biți: cu cât este mai rar, cu atât spune mai mult.

Formula lui Shannon

Entropia este informația medie pe simbol: H = −Σ p log₂ p, însumată peste toate simbolurile, fiecare cu probabilitatea lui p. Pentru o monedă corectă, H este 1 bit. Pentru o monedă care cade cap în 90% din aruncări, este doar 0,47 biți, pentru că rezultatul de obicei nu surprinde. Entropia este maximă când toate simbolurile sunt la fel de probabile, log₂ n biți pentru n simboluri, și zero când un simbol este sigur. Shannon a ales numele la sfatul lui John von Neumann, pentru că aceeași formulă apare în fizică, unde entropia măsoară dezordinea.

Claude Shannon, care în 1948, la Bell Labs, a precizat câtă informație conține un mesaj și a măsurat-o în biți.
Claude Shannon, care în 1948, la Bell Labs, a precizat câtă informație conține un mesaj și a măsurat-o în biți.

Limita compresiei

Teorema codării sursei a lui Shannon spune că niciun cod fără pierderi nu poate folosi, în medie, mai puțini biți pe simbol decât entropia sursei și că un cod se poate apropia de ea oricât de mult. Codarea Huffman, inventată de David Huffman în 1952, pe când era student, dă simbolurilor frecvente coduri scurte și celor rare coduri lungi și ajunge la mai puțin de un bit pe simbol de entropie; codarea aritmetică se apropie și mai mult. Entropia nu este așadar doar o descriere, ci o limită strictă: un fișier de octeți aleatorii, cu 8 biți de entropie pe octet, nu poate fi comprimat deloc.

David Huffman, fotografiat ca profesor la Universitatea California din Santa Cruz. Ca doctorand la MIT, în 1951 și-a găsit codul optim într-o lucrare pentru cursul lui Robert Fano.
David Huffman, fotografiat ca profesor la Universitatea California din Santa Cruz. Ca doctorand la MIT, în 1951 și-a găsit codul optim într-o lucrare pentru cursul lui Robert Fano.

Context și redundanță

Literele unui text nu sunt independente. În engleză, după Q vine U, după un punct urmează o majusculă, iar un cuvânt care începe cu INFORMA continuă aproape sigur cu TION. Dacă se ține seama de simbolurile anterioare, se obține entropia condiționată, care este mai mică decât entropia simbolurilor numărate unul câte unul. Diferența este redundanța: partea mesajului care ar fi putut fi prezisă. Programele de compresie precum ZIP, care folosește metoda deflate, găsesc șiruri repetate și le înlocuiesc cu referințe scurte, iar compresoarele moderne prezic fiecare simbol din contextul lui.

Câtă informație conține limba engleză?

Numărată literă cu literă, cu frecvențele limbii engleze, o literă poartă circa 4,1 biți, față de 4,7 pentru litere alese la întâmplare. În 1951, Shannon a mers mai departe: le-a arătat unor oameni începutul unui text și le-a cerut să ghicească litera următoare, numărând câte încercări le trebuiau. Din răspunsurile lor a estimat că engleza poartă doar între 0,6 și 1,3 biți pe literă. Cu alte cuvinte, aproximativ trei sferturi din engleza scrisă sunt redundanță, motiv pentru care un text din care lipsesc litere poate fi de obicei citit totuși.

Aleatorism și parole

Entropia măsoară și imprevizibilitatea, de care depinde securitatea. O cheie sau o parolă aleasă uniform dintre N posibilități are log₂ N biți de entropie, iar un atacator trebuie să încerce în medie cam jumătate dintre ele. O parolă aleatorie de 12 litere din cele 26 de litere mici are circa 56 de biți; un cuvânt obișnuit are mult mai puțini, oricât de lung ar fi. Generatoarele de numere aleatorii sunt testate verificând că ieșirea lor are entropia completă a unei surse aleatorii, iar sistemele de operare colectează entropie din zgomotul de temporizare pentru a le inițializa.

Unde apare entropia

Entropia decide de câți biți are nevoie un apel telefonic, o fotografie sau un flux video și cât de aproape poate ajunge un modem sau o legătură Wi-Fi de capacitatea canalului său. Biologii o folosesc pentru a măsura informația din ADN, unde patru baze pot purta cel mult 2 biți fiecare, precum și diversitatea unui ecosistem. În învățarea automată, arborii de decizie aleg întrebarea care reduce cel mai mult entropia, iar funcția de pierdere bazată pe entropia încrucișată antrenează majoritatea rețelelor neuronale. Lingviștii compară limbile după entropia lor pe caracter și pe cuvânt.

Explorați

Deschideți calculatorul de entropie pentru a măsura orice text pe caractere, cuvinte sau octeți. Comparați un paragraf cu litere, biți, cifre și ADN aleatorii, vedeți surpriza fiecărui simbol, câtă informație conține textul față de mărimea lui stocată și cum scad biții pe simbol pe măsură ce se cunoaște mai mult context, alături de ce obține de fapt ZIP.

Întrebări frecvente

De ce se măsoară entropia în biți?

Pentru că Shannon a folosit logaritmi în baza 2, astfel încât o alegere cu da sau nu între variante egale să conteze ca o unitate. Cu logaritmul natural, unitatea este natul, circa 1,44 biți, iar cu baza 10, hartley-ul, circa 3,32 biți; acestea sunt folosite de fizicieni și de unii statisticieni.

Poate un text să aibă mai multă entropie decât log₂ din mărimea alfabetului său?

Nu. Cu n simboluri diferite, entropia este de cel mult log₂ n biți pe simbol, valoare atinsă doar când toate sunt la fel de frecvente. Orice dezechilibru și orice predictibilitate dată de context o reduc.

Entropia din teoria informației este aceeași cu cea din fizică?

Formulele au aceeași formă: Boltzmann și Gibbs au scris entropia fizică drept o sumă peste probabilitățile stărilor microscopice ale unui sistem. Sensul este înrudit, căci ambele măsoară cât de mult nu știți, iar fizicienii au arătat de atunci că ștergerea unui bit de informație trebuie să elibereze o mică cantitate de căldură.

De ce nu ajută comprimarea unui fișier deja comprimat?

Un compresor bun elimină cea mai mare parte a redundanței, așa că ieșirea lui este aproape aleatorie, cu aproape 8 biți de entropie pe octet. Nu mai rămâne nimic de eliminat, iar o nouă comprimare îl face de obicei puțin mai mare, din cauza surplusului de date adăugat de compresorul însuși.

Ești gata să încerci?

Deschide PictorX în browser – fără instalare și fără card de credit.

Deschideți calculatorul de entropie