Codurile Huffman: exemple, aplicații

În prezent, puțini oameni se gândesc la acest fapt,cum funcționează compresia. Comparativ cu trecutul, utilizarea unui computer personal a devenit mult mai ușoară. Practic, fiecare persoană care lucrează cu sistemul de fișiere folosește arhive. Dar puțini oameni se gândesc la modul în care funcționează și la ce principiu este compresia fișierelor. Prima versiune a acestui proces a fost codurile Huffman și acestea sunt încă folosite în diverse arhive populare. Mulți utilizatori nu se gândesc nici măcar cât de ușor este să comprimați fișierul și în funcție de ce schemă funcționează. În acest articol, vom examina modul în care compresia funcționează, ce nuanțe ajută la accelerarea și simplificarea procesului de codificare și vom înțelege, de asemenea, care este principiul construirii unui copac de codificare.

Istoria algoritmului

Primul algoritm pentru un algoritm eficientcodificarea informațiilor electronice a fost codul propus de Huffman la mijlocul secolului al XX-lea, și anume în 1952. Acesta este în prezent principalul element de bază al majorității programelor create pentru a comprima informații. În prezent, una dintre cele mai populare surse care folosesc acest cod sunt arhivele ZIP, ARJ, RAR și multe altele.

Acest algoritm Huffman este, de asemenea, folosit pentrucompresia imaginilor JPEG și a altor obiecte grafice. Ei bine, toate faxurile moderne folosesc și codificarea, inventată în 1952. În ciuda faptului că de la crearea codului a trecut atât de mult timp, până în ziua de azi se folosește în cele mai noi cochilii și pe echipamentele vechi și moderne.

Principiul codificării eficiente

Algoritmul Huffman se bazează pe o schemăpermițând înlocuirea caracterelor cele mai probabile, cel mai adesea găsite cu codurile sistemului binar. Iar cele mai puțin frecvente sunt înlocuite cu coduri mai lungi. Trecerea la codurile Huffman lungi are loc numai după ce sistemul folosește toate valorile minime. Această tehnică vă permite să minimizați lungimea codului pentru fiecare caracter al mesajului original ca un întreg.

Punctul important este că la începutProbabilitățile de codificare a apariției literelor ar trebui deja cunoscute. Din acestea, mesajul final va fi compus. Pe baza acestor date, se construiește arborele de cod Huffman, pe baza căruia se va efectua procesul de codificare a literelor din arhivă.

Exemplul codului Huffman

Pentru a ilustra algoritmul, luațiversiunea grafică a construcției arborelui de cod. Pentru a utiliza în mod eficient această metodă, merită clarificată definirea unor valori necesare pentru conceptul acestei metode. Setul de arce și noduri direcționate de la nod la nod se numește grafic. Arborele în sine este un grafic cu un set de proprietăți specifice:

• fiecare nod poate conține nu mai mult de unul din arce;
• unul dintre noduri trebuie să fie rădăcina copacului, adică nu ar trebui să intre nici un arc;
• dacă începeți să vă deplasați de la rădăcină de-a lungul arcurilor, acest proces ar trebui să vă permită să cădeți complet în oricare dintre noduri.

Există, de asemenea, un astfel de lucru inclus în coduriHuffman ca o frunză de copac. Este un nod din care nu ar trebui să se extindă un arc. Dacă două noduri sunt conectate printr-un arc, atunci unul dintre ele este părinte, celălalt copil, în funcție de care nod arcul trece și în care intră. Dacă două noduri au același nod părinte, ele sunt numite noduri fraternale. Dacă, în afară de frunze, nodurile ies în mai multe arcuri, atunci acest copac este numit binar. Doar așa este copacul Huffman. O caracteristică a nodurilor acestei construcții este că greutatea fiecărui părinte este egală cu suma greutății tuturor copiilor cheie.

Huffman algoritm de construcție copac

Construirea unui cod Huffman este făcută din literealfabetul de intrare. Se formează o listă a acelor noduri care sunt libere în viitorul arbore de cod. Greutatea fiecărui nod din această listă ar trebui să fie aceeași cu probabilitatea de apariție a literei mesajului corespunzător acestui nod. În acest caz, între mai multe noduri libere ale copacului viitor este selectat cel care cântărește cel mai mic. Mai mult, dacă indicatorii minime sunt observate în mai multe noduri, atunci puteți alege oricare dintre perechi.

După aceea, crearea părinteluiun nod care ar trebui să cântărească la fel de mult ca suma acestei perechi de noduri. După aceea, părintele este trimis la lista cu noduri libere, iar copiii sunt eliminați. În acest caz, arcele primesc indicatorii corespunzători, unul și zerouri. Acest proces este repetat exact atâta timp cât este nevoie să lăsați un singur nod. Apoi numerele binare sunt scrise în direcția de sus în jos.

Îmbunătățirea eficienței de compresie

Pentru a îmbunătăți eficiența compresiei, trebuie să faceți astatimp pentru a construi un arbore de cod pentru a utiliza toate datele referitoare la probabilitatea de a scrie într-un anumit fișier atașat unui copac și pentru a împiedica împrăștierea acestora într-un număr mare de documente text. Dacă treceți mai întâi prin acest fișier, puteți calcula imediat statisticile despre cât de des se găsesc literele din obiectul care urmează a fi comprimat.

Accelerarea procesului de compresie

Pentru a accelera algoritmul, definiția literelorar trebui să fie efectuată nu în funcție de probabilitatea apariției unei litere, ci de frecvența apariției acesteia. Din acest motiv, algoritmul devine mai ușor, iar lucrul cu acesta este foarte accelerat. De asemenea, se evită operațiunile cu puncte plutitoare și diviziuni.

În plus, lucrează în acest mod, dinamicCodul Huffman, sau mai degrabă algoritmul în sine, nu este supus nici unei modificări. Acest lucru se datorează în principal faptului că probabilitățile sunt direct proporționale cu frecvențele. Merită acordată o atenție deosebită faptului că greutatea finală a fișierului sau așa-numitul nod rădăcină va fi egală cu suma numărului de litere din obiectul care urmează să fie procesat.

concluzie

Codurile Huffman - un simplu și lung stabilitun algoritm care este încă utilizat de multe programe și companii bine-cunoscute. Simplitatea și claritatea acesteia fac posibilă obținerea unor rezultate efective de comprimare a fișierelor de orice dimensiune și reducerea semnificativă a spațiului pe care îl ocupă. Cu alte cuvinte, algoritmul Huffman este o schemă studiată și dezvoltată de mult timp, a cărei relevanță nu scade până în prezent.

Și datorită capacității de a reduce dimensiunea fișierelor,transmisia lor prin rețea sau în alte moduri devine mai simplă, mai rapidă și mai convenabilă. Lucrul cu algoritmul, puteți comprima complet orice informație fără a afecta structura și calitatea acesteia, dar cu efectul maxim de reducere a greutății fișierului. Cu alte cuvinte, codarea Huffman a fost și rămâne cea mai populară și actuală metodă de comprimare a dimensiunii fișierului.