Codarea Huffman explicată
De obicei, calculatoarele stochează fiecare literă pe același număr de biți, opt în ASCII simplu. Este simplu, dar risipitor, pentru că unele litere sunt mult mai frecvente decât altele. În 1951, un student a găsit cel mai bun mod de a da fiecărui simbol un cod de lungime proprie, scurt pentru simbolurile frecvente și lung pentru cele rare, printr-o construcție atât de simplă încât încape în câteva rânduri. Codarea Huffman se află astăzi în aproape fiecare fișier comprimat, imagine și sunet pe care îl deschideți.
Coduri scurte pentru simbolurile frecvente
Codul Morse folosea deja ideea în anii 1830: E, cea mai frecventă literă în engleză, este un singur punct, în timp ce Q este linie linie punct linie. Un asemenea cod economisește timp și spațiu ori de câte ori unele simboluri apar mai des decât altele. Dar lungimile variabile ridică o problemă pe care Morse a rezolvat-o cu pauze: de unde știți unde se termină un cod și unde începe următorul? Și ce lungimi trebuie să primească fiecare simbol pentru ca totalul să fie cât mai mic?
Coduri prefix
Prima problemă dispare dacă niciun cod nu este începutul altuia. Cu codurile A = 0, B = 10, C = 110 și D = 111, biții 0101100 pot fi citiți doar ca A B C A: de îndată ce biții citiți până acum formează un cod, acel cod este complet. Astfel de coduri prefix corespund exact arborilor binari cu simbolurile în frunze, în care fiecare ramură spre stânga înseamnă 0 și fiecare ramură spre dreapta 1. A alege un cod înseamnă a alege un arbore.
Construcția lui Huffman
Începeți cu câte o frunză pentru fiecare simbol, cu ponderea egală cu numărul său de apariții. Luați cei doi arbori cei mai ușori și uniți-i sub un nod nou a cărui pondere este suma lor, apoi repetați până când rămâne un singur arbore. Acesta este tot algoritmul. Simbolurile rare sunt unite primele și ajung adânc în arbore, cu coduri lungi; cele frecvente sunt unite ultimele și rămân aproape de vârf, cu coduri scurte. Cu o coadă cu priorități, durează un timp proporțional cu n log n pentru n simboluri.
De ce este optim
Într-un arbore optim, cele două simboluri cele mai rare pot fi întotdeauna așezate ca frați pe nivelul cel mai adânc: schimbarea lor cu ce se află acolo nu poate decât să scurteze totalul. Uniți-le într-un singur simbol cu ponderea lor combinată, iar restul este aceeași problemă cu un simbol mai puțin, așa că pasul greedy nu închide niciodată drumul spre cel mai bun răspuns. Numărul total de biți folosiți este egal cu suma ponderilor tuturor nodurilor interne, pe care unirile o păstrează cât mai mică.
O lucrare în locul unui examen
În 1951, David Huffman, student la studii postuniversitare la MIT, urma cursul de teoria informației al lui Robert Fano. Fano le-a dat studenților de ales: să dea examenul final sau să scrie o lucrare despre găsirea celui mai eficient cod binar. Huffman aproape că renunțase la lucrare, apoi a văzut că a construi arborele de jos în sus, în loc de a-l împărți de sus în jos ca în metoda Shannon–Fano, dă întotdeauna cel mai bun rezultat. A publicat-o în 1952; metoda studentului a întrecut-o pe cea pe care profesorul său o elaborase împreună cu Claude Shannon.
Aproape de entropie
Claude Shannon a arătat că niciun cod nu poate folosi, în medie, mai puțini biți pe simbol decât entropia sursei. Un cod Huffman atinge exact entropia când fiecare probabilitate este o putere a lui o doime și nu o depășește niciodată cu un bit întreg pe simbol. Diferența contează când un simbol este foarte frecvent: un simbol cu o pondere de 99% are totuși nevoie de cel puțin un bit întreg, deși poartă doar aproximativ 0,015 biți de informație. Codarea aritmetică și sistemele numerice asimetrice ale compresoarelor mai noi evită această limită.
Coduri Huffman peste tot
Codarea Huffman este rareori folosită singură, dar formează ultima etapă a multor formate. Deflate, folosit în ZIP, gzip și PNG, înlocuiește mai întâi repetițiile cu referințe și apoi scrie rezultatul cu coduri Huffman. JPEG le folosește pentru numerele rămase după transformarea imaginii, MP3 pentru datele audio, iar aparatele de fax pentru lungimile secvențelor de alb și negru. De obicei, formatele transmit un cod Huffman canonic, la care trebuie stocate doar lungimile codurilor, pentru că înseși codurile pot fi reconstruite din ele.
Explorați
Deschideți constructorul de coduri Huffman pentru a construi, pas cu pas, arborele pentru ABRACADABRA, MISSISSIPPI RIVER, o propoziție proprie sau orice alt text. Urmăriți cum se unesc la fiecare pas cei doi arbori cei mai ușori, faceți clic pe o frunză pentru a-i vedea codul, urmăriți un simbol prin biții codificați și comparați totalul cu un cod de lungime fixă, cu UTF-8 și cu entropia.
Întrebări frecvente
Care este diferența dintre codarea Huffman și codarea Shannon–Fano?
Codarea Shannon–Fano construiește arborele de sus, împărțind simbolurile iar și iar în două grupuri cu ponderi aproape egale. Deseori este bună, dar nu întotdeauna optimă. Huffman construiește arborele de jos, unind cei doi arbori cei mai ușori, și dă întotdeauna cel mai scurt cod prefix posibil.
Are decodorul nevoie de arbore?
Da, are nevoie de același cod. De aceea fișierele comprimate îl stochează, de obicei ca listă de lungimi de cod pentru un cod canonic, ceea ce ocupă doar câteva zeci de octeți. La textele scurte, acest cost suplimentar poate depăși economia; constructorul numără doar biții codificați.
Poate codarea Huffman să mărească un fișier?
Simbolurile codificate nu ocupă niciodată mai mulți biți decât un cod de lungime fixă pentru aceleași simboluri. Dar și tabelul de coduri trebuie stocat, așa că pentru date foarte scurte sau aproape aleatorii rezultatul poate fi puțin mai mare decât originalul.
Ce spune inegalitatea lui Kraft?
Că un cod prefix cu lungimile de cod l₁, l₂, … există exact atunci când suma lui 2 la puterea −l pentru toate simbolurile este cel mult 1. Pentru un arbore complet, cum este orice arbore Huffman cu cel puțin două simboluri, suma este exact 1.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Deschideți constructorul de coduri Huffman