Cum funcționează compresia fără pierderi a datelor | Revista Quanta

Cu peste 9 miliarde de gigaocteți de informații care circulă pe internet în fiecare zi, cercetătorii caută în mod constant noi modalități de a comprima datele în pachete mai mici. Tehnicile de ultimă oră se concentrează pe abordări cu pierderi, care realizează compresia prin „pierderea” intenționată a informațiilor dintr-o transmisie. Google, de exemplu, a dezvăluit recent o strategie cu pierderi în care computerul care trimite detaliile dintr-o imagine, iar computerul care primește folosește inteligența artificială pentru a ghici părțile lipsă. Chiar și Netflix folosește o abordare cu pierderi, reducând calitatea video ori de câte ori compania detectează că un utilizator urmărește pe un dispozitiv cu rezoluție joasă.

În schimb, foarte puține cercetări sunt în curs de desfășurare asupra strategiilor fără pierderi, în care transmisiile sunt reduse, dar nu se sacrifică nicio substanță. Motivul? Abordările fără pierderi sunt deja remarcabil de eficiente. Acestea alimentează totul, de la standardul de imagine JPEG la utilitarul software omniprezent PKZip. Și totul se datorează unui student absolvent care pur și simplu căuta o cale de ieșire dintr-un examen final dificil.

În urmă cu șaptezeci de ani, un profesor al Institutului de Tehnologie din Massachusetts, pe nume Robert Fano, le-a oferit studenților din clasa sa de teoria informației o alegere: să susțină un examen final tradițional sau să îmbunătățească un algoritm de comprimare a datelor. Este posibil ca Fano să fi informat sau nu studenții săi că el a fost autorul acelui algoritm existent sau că a căutat o îmbunătățire de ani de zile. Ceea ce știm este că Fano le-a oferit studenților săi următoarea provocare.

Luați în considerare un mesaj format din litere, cifre și semne de punctuație. O modalitate simplă de a codifica un astfel de mesaj ar fi să atribuiți fiecărui caracter un număr binar unic. De exemplu, un computer ar putea reprezenta litera A ca 01000001 și un semn de exclamare ca 00100001. Acest lucru are ca rezultat coduri care sunt ușor de analizat - la fiecare opt cifre sau biți, corespund unui caracter unic - dar oribil de ineficiente, deoarece același număr de cifre binare este folosit atât pentru intrările comune, cât și pentru cele neobișnuite. O abordare mai bună ar fi ceva de genul codului Morse, în care litera frecventă E este reprezentată doar de un singur punct, în timp ce Q mai puțin obișnuit necesită liniuța-linia-punctul-linia mai lungă și mai laborioasă.

Cu toate acestea, codul Morse este de asemenea ineficient. Sigur, unele coduri sunt scurte, iar altele sunt lungi. Dar, deoarece lungimile codului variază, mesajele în codul Morse nu pot fi înțelese decât dacă includ scurte perioade de tăcere între fiecare transmisie de caractere. Într-adevăr, fără aceste pauze costisitoare, destinatarii nu ar avea nicio modalitate de a distinge mesajul Morse liniuță punct-liniuță-punct punct-punct liniuță punct („trite”) de liniuță punct-liniuță-punct punct-punct-liniuță punct („adevărat” ).

Fano rezolvase această parte a problemei. Și-a dat seama că putea folosi coduri de lungimi diferite fără a avea nevoie de spații costisitoare, atâta timp cât nu a folosit niciodată același model de cifre atât ca un cod complet, cât și ca începutul altui cod. De exemplu, dacă litera S era atât de comună într-un anumit mesaj încât Fano i-a atribuit codul extrem de scurt 01, atunci nicio altă literă din acel mesaj nu ar fi codificată cu ceva care începe 01; coduri precum 010, 011 sau 0101 ar fi toate interzise. Drept urmare, mesajul codificat putea fi citit de la stânga la dreapta, fără nicio ambiguitate. De exemplu, cu litera S atribuită 01, litera A atribuită 000, litera M atribuită 001 și litera L atribuită 1, dintr-o dată mesajul 0100100011 poate fi tradus imediat în cuvântul „mic” chiar dacă L este reprezentat de unul. cifră, S cu două cifre, iar celelalte litere cu trei fiecare.

Pentru a determina efectiv codurile, Fano a construit arbori binari, plasând fiecare literă necesară la capătul unei ramuri vizuale. Codul fiecărei litere a fost apoi definit de calea de sus în jos. Dacă drumul se ramifica spre stânga, Fano a adăugat un 0; ramurile din dreapta au primit un 1. Structura arborelui i-a făcut lui Fano mai ușor să evite acele suprapuneri nedorite: odată ce Fano a plasat o literă în copac, acea ramură se va termina, ceea ce înseamnă că niciun cod viitor nu ar putea începe în același mod.

Pentru a decide ce litere vor merge unde, Fano ar fi putut testa în mod exhaustiv fiecare tipar posibil pentru o eficiență maximă, dar asta ar fi fost impracticabil. Deci, în schimb, a dezvoltat o aproximare: pentru fiecare mesaj, el organiza literele relevante după frecvență și apoi atribuie litere ramurilor, astfel încât literele din stânga din orice pereche de ramuri date să fie folosite în mesaj aproximativ de același număr de ori ca și ramurile. literele din dreapta. În acest fel, caracterele utilizate frecvent ar ajunge pe ramuri mai scurte, mai puțin dense. Un număr mic de litere de înaltă frecvență ar echilibra întotdeauna un număr mai mare de litere de frecvență inferioară.

Rezultatul a fost o compresie remarcabil de eficientă. Dar a fost doar o aproximare; trebuia să existe o strategie de compresie mai bună. Așa că Fano și-a provocat studenții să o găsească.

Fano își construise copacii de sus în jos, menținând cât mai multă simetrie între ramurile pereche. Studentul său David Huffman a răsturnat procesul, construind aceleași tipuri de copaci, dar de jos în sus. Perspectiva lui Huffman a fost că, orice s-ar întâmpla, într-un cod eficient, cele două caractere cele mai puțin comune ar trebui să aibă cele mai lungi două coduri. Așa că Huffman a identificat cele două personaje cele mai puțin comune, le-a grupat împreună ca o pereche ramificată și apoi a repetat procesul, de data aceasta căutând cele două intrări cele mai puțin comune dintre personajele rămase și perechea pe care tocmai o construise.

Luați în considerare un mesaj în care abordarea Fano se clătește. În „școală”, O apare de patru ori și S/C/H/L/R/M apar fiecare o dată. Abordarea de echilibrare a lui Fano începe prin alocarea O și încă o literă ramurii din stânga, cele cinci utilizări totale ale acelor litere echilibrând cele cinci apariții ale literelor rămase. Mesajul rezultat necesită 27 de biți.

Huffman, dimpotrivă, începe cu două dintre literele neobișnuite - să zicem, R și M - și le grupează împreună, tratând perechea ca o singură literă.

Diagrama de frecvență actualizată îi oferă apoi patru opțiuni: O care apare de patru ori, noul nod RM combinat care este utilizat funcțional de două ori și literele simple S, C, H și L. Huffman alege din nou cele două opțiuni cele mai puțin comune, potrivindu-se. (spuneți) H cu L.

Graficul se actualizează din nou: O încă are o greutate de 4, RM și HL au fiecare o greutate de 2, iar literele S și C sunt singure. Huffman continuă de acolo, în fiecare pas grupând cele două opțiuni cel mai puțin frecvente și apoi actualizând atât arborele cât și diagrama de frecvență.

În cele din urmă, „scolile” devine 11101111110000110110000101, eliminând un pic abordarea de sus în jos a Fano.

Un pic poate să nu sune prea mult, dar chiar și economiile mici cresc enorm atunci când sunt scalate cu miliarde de gigaocteți.

Într-adevăr, abordarea lui Huffman s-a dovedit a fi atât de puternică încât, astăzi, aproape fiecare strategie de compresie fără pierderi folosește în întregime sau parțial intuiția lui Huffman. Aveți nevoie de PKZip pentru a comprima un document Word? Primul pas implică încă o strategie inteligentă pentru identificarea repetiției și, prin urmare, comprimarea dimensiunii mesajului, dar al doilea pas este să luați mesajul comprimat rezultat și să îl rulați prin procesul Huffman. Stocați o imagine ca JPEG? Computerul dvs. traduce mai întâi imaginea într-o reprezentare bazată pe text și apoi, din nou, folosește codificarea Huffman pentru a comprima acel text.

Nu e rău pentru un proiect motivat inițial de dorința unui student absolvent de a sări peste un examen final.