| Simbol | Apariții | Cod | Biți | Biți în total |
|---|
Constructor de coduri Huffman
De ce ar ocupa o literă frecventă ca e tot atâția biți cât una rară ca q? Codarea Huffman dă simbolurilor frecvente coduri scurte și celor rare coduri lungi, și o face în cel mai bun mod posibil. Scrieți un text sau alegeți un exemplu și construiți-i arborele Huffman pas cu pas: cei doi arbori cei mai ușori se unesc sub un nod nou, iar și iar, până când rămâne un singur arbore. Apoi fiecare drum de la vârf formează un cod, iar dumneavoastră puteți urmări fiecare simbol prin biții codificați. Scrieți un text sau alegeți un exemplu. Fiecare simbol pornește ca o frunză cu numărul său de apariții. Parcurgeți construcția pas cu pas: fiecare pas unește cei doi arbori cei mai ușori sub un nod nou cu suma ponderilor lor, până când rămâne un singur arbore. Apoi drumul de la vârf până la o frunză dă codul ei, 0 pentru stânga și 1 pentru dreapta. Faceți clic pe o frunză, pe un rând sau pe o porțiune din biți pentru a urmări un simbol și comparați totalul cu un cod de lungime fixă și cu entropia.
Cum funcționează
- Scrieți sau lipiți un text ori alegeți un exemplu, precum ABRACADABRA sau MISSISSIPPI RIVER.
- Parcurgeți construcția cu Pasul următor sau apăsați Redă: fiecare pas unește cei doi arbori cei mai ușori sub un nod cu suma ponderilor lor.
- Când arborele este complet, faceți clic pe o frunză, pe un rând din tabel sau pe o porțiune din biți pentru a urmări un simbol și comparați totalurile din casete.
Cum se construiește arborele
Numărați de câte ori apare fiecare simbol și faceți din fiecare un arbore cu o singură frunză, cu ponderea egală cu numărul său de apariții. Apoi repetați un pas simplu: luați cei doi arbori cu ponderile cele mai mici și atârnați-i sub un nod nou a cărui pondere este suma lor. Fiecare pas lasă cu un arbore mai puțin, așa că după n − 1 pași, pentru n simboluri, rămâne un singur arbore. Simbolurile rare au fost unite primele și stau jos, în adânc; cele frecvente au fost unite târziu și stau aproape de vârf.
Citirea codurilor
Coborâți de la vârf: un pas la stânga adaugă un 0, un pas la dreapta un 1. Drumul până la o frunză este codul simbolului respectiv. Deoarece simbolurile stau doar în frunze, niciun cod nu este începutul altuia, așa că un șir de biți poate fi decodat fără separatori: urmați biții în jos prin arbore și, de fiecare dată când ajungeți la o frunză, scrieți simbolul ei și începeți din nou de la vârf. Pentru ABRACADABRA, Huffman are nevoie de 23 de biți, față de 33 pentru un cod fix de 3 biți pe literă.
Întrebări frecvente
De ce este codul Huffman cel mai bun posibil?
Dintre toate codurile care dau fiecărui simbol propriul șir de biți întregi, niciunul nu are un total mai mic pentru frecvențele date. Demonstrația urmează construcția: într-un cod optim, cele două simboluri cele mai rare pot fi întotdeauna puse ca frați pe nivelul cel mai adânc, iar unirea lor lasă o problemă mai mică de același fel. Numărul total de biți este egal cu suma ponderilor tuturor nodurilor interne ale arborelui.
Ce este un cod prefix?
Un cod în care niciun cuvânt de cod nu este începutul altuia, de exemplu 0, 10, 110 și 111. Această proprietate îi permite unui decodor să citească un flux de biți fără separatori, pentru că știe întotdeauna unde se termină un cuvânt de cod. Orice cod Huffman este un cod prefix: simbolurile stau doar în frunzele arborelui.
Este arborele Huffman unic?
Nu chiar: când doi arbori au aceeași pondere, oricare poate fi luat primul, iar stânga și dreapta pot fi inversate. Alegeri diferite dau coduri diferite, dar întotdeauna același număr total de biți. Constructorul rezolvă egalitățile mereu în același fel, așa că un text dă întotdeauna același arbore.
Cât de aproape de entropie ajunge Huffman?
Lungimea medie a codului este cel puțin egală cu entropia și o depășește cu mai puțin de un bit. Este egală cu entropia când fiecare probabilitate este o putere a lui o doime, ca în exemplul cu frecvențe înjumătățite. Codarea aritmetică și codoarele moderne de interval evită limita biților întregi și se apropie și mai mult.
Este textul meu trimis undeva?
Nu. Arborele și codurile sunt calculate în browserul dumneavoastră, iar textul rămâne în stocarea locală a acestui browser.
Ești gata să încerci?
Deschide PictorX în browser – fără instalare și fără card de credit.
Mergi la editor