Entropia

Nume de lungimi diferite

Prima noastră lecție s-a încheiat cu o bănuială plină de bun-simț: dacă literele dintr-o limbă nu apar la fel de des, oare de ce le-am pedepsi pe toate să poarte etichete de aceeași lungime? Pentru a transforma această bănuială într-o metodă practică, avem nevoie de o singură idee nouă, iar ea este la fel de firească precum ordonarea lucrurilor dintr-o casă.

Un sistem în care fiecare literă sau simbol primește un cod cu exact același număr de cifre binare se numește cod de lungime fixă. Dacă avem în vedere treizeci și două de semne posibile, fiecare dintre ele va costa neclintit 5 biți, indiferent dacă este folosit de mii de ori pe pagină sau o singură dată într-un întreg volum. Acest mod de lucru este extrem de comod pentru ingineri — motiv pentru care primele calculatoare l-au adoptat peste tot —, însă el ignoră cu desăvârșire realitatea lumii: tratează o literă omniprezentă precum „e” exact la fel ca pe o literă rară precum „q”.

Putem însă alege o altă cale: să permitem etichetelor să aibă lungimi diferite. În acest caz, ceea ce contează cu adevărat nu mai este dimensiunea unei litere luate izolat, ci lungimea medie a întregului text. În această medie, fiecare simbol își cântărește lungimea în funcție de cât de des este chemat la apel. Dacă atribuim un cod lung unei litere rare, aproape că nu-i vom simți povara, fiindcă o plătim doar rareori. Dar dacă am pune același cod lung pe o literă frecventă, am plăti acea taxă la fiecare câteva cuvinte! Este exact logica unui bagaj bine făcut: obiectele de care avem nevoie la fiecare pas stau chiar la îndemână, deasupra, în timp ce lucrurile pentru cazuri rare pot fi așezate oricât de adânc pe fundul valizei.

Întrebarea centrală a acestei lecții devine astfel una esențială pentru comunicații: cât de mult putem coborî această lungime medie a mesajelor? Răspunsul constituie una dintre cele mai frumoase surprize ale științei: această limită nu depinde de cât de iscusiți suntem noi în născocirea de coduri, ci este dictată strict de probabilitățile simbolurilor din natură.

Cât informează un rezultat

Pentru a descoperi această limită, este util să privim mai întâi un singur eveniment, nu un întreg text. Imaginați-vă o veste care are doar o șansă din opt să se adeverească. Când ea se produce, situația seamănă perfect cu găsirea unei cutii dintr-un grup de opt: pentru a o lămuri aveam nevoie de trei întrebări binare succesive, deci vestea ne aduce exact trei biți de noutate. Un eveniment care avea o șansă din două (50%) cere o singură întrebare: ne aduce un singur bit. Iar un eveniment absolut sigur, pe care îl știam dinainte cu certitudine, nu cere nicio întrebare: ne aduce zero biți.

Regula generală se desprinde cu o claritate desăvârșită: un rezultat care are o probabilitate p de apariție ne oferă o cantitate de informație egală cu numărul de înjumătățiri necesare pentru a-l deosebi de restul posibilităților. Cu cât un eveniment este mai rar și mai neașteptat, cu atât mai multă informație aduce atunci când chiar are loc. Această cantitate se numește conținutul de informație al rezultatului sau, într-o exprimare mult mai vie și mai intuitivă, gradul de surpriză pe care îl produce. Această surpriză nu este obligată să fie un număr întreg: de pildă, un eveniment cu o probabilitate de 1 din 3 aduce aproximativ 1,58 biți de surpriză, situându-se firesc între certitudinea relativă a unei șanse de 1 din 2 și raritatea uneia de 1 din 4.

Să ne oprim o clipă și să respirăm adânc această idee: informația nu este o substanță închisă în obiectul în sine, ci o punte între ceea ce s-a petrecut și ceea ce ne așteptam noi să se întâmple. Vestea că la munte ninge în toiul iernii, în luna ianuarie, abia dacă stârnește o tresărire: surpriza e aproape nulă, deci informația e minimă. Dar aceeași știre, „la munte a nins”, dacă sosește într-o amiază toridă din iulie, ne lasă uimiți și devine pe loc o știre de senzație. Teoria informației preia această experiență umană cotidiană și îi conferă o unitate de măsură impecabilă.

Entropia

Acum putem privi din nou imaginea de ansamblu. O sursă de mesaje — fie că este vorba despre o tastatură, un zar aruncat pe covor sau o stație meteo — generează simboluri unul după altul, fiecare cu propria sa probabilitate și propriul său grad de surpriză. Entropia acelei surse este pur și simplu surpriza medie pe care o produce fiecare simbol emis: luăm surpriza fiecărui rezultat posibil, o cântărim cu probabilitatea cu care acesta se ivește și le adunăm pe toate. Entropia se măsoară în biți pe simbol și se notează în mod tradițional cu litera H.

Entropia se întinde întotdeauna între două extreme foarte clare. La o extremă, dacă toate cele N simboluri posibile au șanse strict egale de apariție, imprevizibilitatea este maximă, iar entropia atinge valoarea maximă posibilă (exact cazul cutiilor din lecția precedentă). La cealaltă extremă, dacă unul dintre simboluri este garantat 100%, iar celelalte nu apar niciodată, entropia se prăbușește la zero: rezultatul este știut dinainte, iar sursa, oricât ar „vorbi”, nu ne învață absolut nimic nou. Între aceste două țărmuri se scaldă toate limbile pământului și toate semnalele din viața reală, iar figura interactivă de mai jos vă permite să explorați această trecere.

De ce este entropia o descoperire monumentală? Pentru că ea răspunde definitiv la marea întrebare a eficienței. În celebra sa lucrare din 1948, Claude Shannon a demonstrat două adevăruri fundamentale dintr-o singură lovitură: în primul rând, nicio schemă de codificare, oricât de strălucită ar fi, nu poate coborî lungimea medie a unui text sub valoarea entropiei sursei; iar în al doilea rând, există întotdeauna metode practice care ne permit să ne apropiem oricât de mult dorim de această barieră! Entropia este, prin urmare, greutatea pură, netă a informației dintr-un mesaj, eliberată de orice convenție arbitrară de scriere. Un text de o mie de litere nu „cântărește” automat cinci mii de biți doar pentru că tastatura folosește 5 biți pe caracter; el conține doar atâția biți câtă surpriză autentică aduce, restul fiind simplu ambalaj sau spațiu irosit.

Termenul a fost împrumutat din fizică. Când Shannon a descoperit formula matematică a surprizei medii, a observat că ea coincidea până la ultima virgulă cu ecuația prin care Ludwig Boltzmann descrisese, cu jumătate de secol mai devreme, dezordinea microscopică dintr-un gaz. Legenda spune că marele matematician John von Neumann l-ar fi sfătuit zâmbind: „Boteaz-o entropie! În primul rând pentru că este aceeași formulă ca în termodinamică, iar în al doilea rând pentru că nimeni nu știe cu adevărat ce este entropia, așa că într-o dispută vei avea întotdeauna dreptate!”. Dincolo de anecdotă, legătura este autentică și profundă: lipsa de informație a unui observator și dezordinea particulelor din natură sunt două fețe ale aceleiași monede.

Codul Huffman

A sosit momentul să vedem cum putem construi practic un astfel de cod optim. În anul 1952, un tânăr student la MIT pe nume David Huffman s-a găsit în fața unei alegeri: profesorul său de renume, Robert Fano, le oferise studenților opțiunea fie de a susține un examen final greu, fie de a găsi o metodă optimă de codificare a simbolurilor — o problemă rămasă nerezolvată. Huffman a muncit luni de zile fără succes și era pe punctul de a renunța pentru a învăța pentru examen. Când a adunat ciornele mototolite să le arunce la coș, i-a venit brusc o idee sclipitoare: secretul nu era să construiești codul de sus în jos, împărțind simbolurile frecvente, ci să pornești de jos în sus, unind cele mai rare două simboluri!

Metoda lui Huffman este pe cât de simplă, pe atât de elegantă. Căutăm cele două simboluri care apar cel mai rar și le unim într-o pereche; ele vor avea coduri identice, diferențiate doar prin ultima cifră (una primește 0, cealaltă 1). Această pereche este tratată acum ca o singură entitate combinată, a cărei probabilitate este suma celor două. Repetăm pasul cu ceea ce a rămas: căutăm din nou cele mai mici două probabilități și le unim, treaptă cu treaptă, până când toate ramurile se adună într-o singură rădăcină. La final, citind drumul de la rădăcină înapoi spre fiecare literă, obținem codul optim garantat.

Acest cod are o proprietate de aur, fără de care calculatoarele s-ar poticni la fiecare pas: niciun cod nu reprezintă începutul (prefixul) unui alt cod mai lung. Datorită acestei caracteristici, numită cod prefix, toate literele pot fi alipite direct una după alta într-un singur șir neîntrerupt de biți, fără a avea nevoie de spații sau virgule despărțitoare! La recepție, citim cifră cu cifră: în clipa exactă în care recunoaștem un cod valid, știm sigur că litera s-a terminat, o afișăm pe ecran și reîncepem descifrarea pentru următorul caracter.

În analiza textelor reale, spațiul dintre cuvinte este numărat ca un caracter de sine stătător și este aproape întotdeauna cel mai frecvent simbol din text. Pentru claritate, literele mari sunt transformate în litere mici, iar semnele de punctuație sunt simplificate.

Codul Huffman oferă fiecărui caracter individual un număr întreg de biți — cel puțin un bit —, iar aici se ascunde singura sa limitare practică. Dacă avem un mesaj compus aproape exclusiv din litera „a”, surpriza adusă de fiecare „a” scade mult sub un bit (de pildă, la 0,1 biți), însă codul Huffman nu-i poate da mai puțin de o cifră binară întreagă (1 bit). În astfel de cazuri extreme, codul Huffman rămâne blocat puțin deasupra entropiei ideale.

Cum putem atinge atunci promisiunea teoretică a lui Shannon? Soluția este să nu mai codificăm literele izolate una câte una, ci să le grupăm în blocuri: perechi de câte două sau grupuri de câte trei litere deodată! O secvență extrem de previzibilă primește un singur cod scurt de un bit, iar acel cost se împarte acum la două sau trei caractere deodată. Pe măsură ce privim grupuri mai mari de simboluri, lungimea medie coboară lin și atinge practic pragul absolut al entropiei.

Redundanța

Diferența dintre lungimea unui cod de lungime fixă și entropia reală a mesajului ne arată cât de mult „balast” conține modul obișnuit în care transmitem datele. Acest surplus de reprezentare, raportat la spațiul total, poartă numele de redundanță.

Limbajul uman pe care îl vorbim zi de zi este extraordinar de redundant, și asta din mai multe motive împletite: unele litere sunt mult mai frecvente decât altele, anumite combinații de sunete sunt practic imposibile, iar cuvintele dintr-o propoziție se anunță reciproc prin reguli gramaticale și de sens. Datorită redundanței putem înțelege fără efort un mesaj precum „b_nă d_m_neața, c_ m_i f_ci?”, chiar dacă o treime din litere lipsesc, sau putem desluși glasul unui prieten într-o cafenea zgomotoasă. Redundanța este o sabie cu două tăișuri minunate: pe de o parte, este ceea ce ne permite să comprimăm masiv fișierele pe calculator; pe de altă parte, este plasa de siguranță care protejează vorbirea și scrierea de erori și neînțelegeri.

Algoritmul Huffman pe care l-am explorat mai sus exploatează doar prima parte a acestei redundanțe: frecvența individuală a fiecărei litere. Dar o compresie cu adevărat puternică merge mai adânc: ține cont de contextul literelor precedente. De pildă, dacă tocmai am întâlnit litera „q”, știm aproape cu certitudine că va urma litera „u”; apariția lui „u” nu mai constituie o surpriză pentru nimeni, deci nu merită să cheltuim biți prețioși pentru a o anunța.

Aici ajungem la o concluzie de o frumusețe copleșitoare: a comprima un text înseamnă, în esență, a-l putea prezice! Cu cât un sistem înțelege mai bine regulile și contextul unei limbi, cu atât anticipează mai precis ce va urma, iar ceea ce este perfect anticipat nu mai are nevoie să fie transmis. Această capacitate de predicție — extinsă de la litere la cuvinte, fraze și idei întregi — constituie chiar motorul secret din care se vor naște, în a doua parte a cursului nostru, marile modele de limbaj și inteligența artificială de astăzi.