Coduri de compresie

Atunci când dorim să reprezentăm informații, spre exemplu o imagine, în format digital, trebuie să o împărțim în bucățele mici. Acest lucru ne permite să trimitem imaginea sub forma unui șir de simboluri ale culorilor, iar aceste culori pot fi reprezentate sub forma unor coduri unice. Iată următoarea provocare. Alice și Bob pot trimite și primi mesaje în format binar. (Codul Morse) Taxează clienții cu un cent pentru fiecare bit pentru a folosi sistemul lor. Un client dorește să transmită un mesaj cu lungimea de 1000 de caractere. Semnificația mesajului nu este cunoscută. În mod normal, acesta este transmis cu ajutorul unui cod binar, rezultând 2000 de biți. Însă Alice și Bob au analizat mesajul și au observat că probabilitatea fiecărui caracter din mesaj e diferită. Pot folosi aceste probabilități cunoscute pentru a comprima transmisia și pentru a crește profitul? Care este strategia optimă de codificare? David Huffman a inventat strategia optimă și a publicat-o în 1952. Aceasta se bazează pe construirea unui arbore binar de jos în sus. Pentru început, afișăm o singură dată caracterele care apar în mesaj, pe care le vom numi noduri. Apoi identificăm două noduri cu cea mai mică probabilitate de apariție, în acest caz B și C, și le unim, adunând probabilitățile. Repetăm acest pas cu următoarele noduri cu probabilități minime și continuăm să le unim până când obținem un singur nod în vârf. La final, numerotăm muchiile drepte ale arborelui cu 0 și pe cele stângi cu 1 (sau invers). Codificarea fiecărei litere e obținută prin parcurgerea drumului de la rădăcină la litera respectivă. Așadar, codificarea lui A este 1. Algoritmul este cunoscut drept codificare Huffman, și este cel mai eficient în situații de acest tip. Poți încerca să demonstrezi contrariul. De exemplu, dacă scurtezi codificarea lui D la 0, atunci mesajul 011 ar putea însemna atât DAA, cât și B. Așadar, pentru a face această situație să funcționeze, ar trebui să introduci spații între litere, care ar anula orice economisiri din timpul transmiterii. Cât de mult a fost comprimat mesajul, comparativ cu cei 2000 de biți pe care îi avea inițial? Trebuie să calculăm în medie numărul de biți per caracter. Înmulțim lungimea fiecărei codificări cu probabilitatea de apariție a literei, facem suma și obținem lungimea medie de 1.75 biți per caracter. Așadar, codificarea Huffman comprimă mesajul de la 2000 de biți la 1750. Claude Shannon a fost primul care a observat că limita comprimării va fi întotdeauna entropia mesajului inițial. Pe măsură ce entropia, sau incertitudinea mesajului inițial scade, capacitatea de comprimare crește. (Codul Morse) Pe de altă parte, dacă entropia crește datorită imprevizibilității, capacitatea noastră de comprimare scade. (Codul Morse) Dacă vrem să comprimăm mai mult decât ne permite entropia, trebuie să renunțăm informații pe care vrem să le trimitem.