Codurile Huffman: exemple, aplicații

În prezent, puțini oameni se gândesc la modul în care 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 cred despre modul în care acestea funcționează și pe ce bază este de compresie a fișierelor. prima versiune a acestui proces au fost codurile Huffman, iar acestea sunt utilizate în prezent într-o varietate de archivers populare. Mulți utilizatori nici măcar nu cred cât de ușor are loc compresie de fișiere și este de lucru pe o schemă. În acest articol ne uităm la modul în care compresia este ceea ce nuanțează viteza de ajutor și a simplifica procesul de codificare, precum și a vedea ce principiul codificării arborelui.

Istoria algoritmului

Chiar primul algoritm de codificare eficientă a informațiilor electronice a devenit un cod Huffman a propus încă de la mijlocul secolului al XX-lea, și anume în 1952. El a fost cel care în acest moment este elementul de bază al majorității programelor create pentru a comprima informațiile. În acest moment, una dintre cele mai populare surse utilizând acest cod sunt arhive ZIP, ARJ, RAR și multe altele. Acest algoritm Huffman este, de asemenea, folosit pentru compresia imaginilor JPEG și alte 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 este folosit în cele mai noi cochilii și pe echipamentele vechi și moderne.

Principiul codificării eficiente

Algoritmul Huffman se bazează pe o schemă care permite înlocuirea simbolurilor cele mai probabile, cele mai frecvent întâlnite codurile binare sistem. Iar cele care sunt 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. Un punct important este că, la începutul codificării, probabilitatea apariției literelor ar trebui deja cunoscută. Din acestea, mesajul final va fi compilat. 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ă.

Codul lui Huffman, exemplu

Pentru a ilustra algoritmul, să luăm o variantă grafică de construire a unui arbore de cod. Pentru a utiliza această metodă a fost eficientă, merită clarificată definirea unor valori necesare pentru conceptul acestei metode. Setul de arce și noduri direcționate de la nod la nod este denumit de obicei un grafic. Arborele în sine este un grafic cu un set de anumite proprietăți:

• în fiecare nod nu poate intra mai mult decât unul din arce;
• unul dintre noduri trebuie să fie rădăcina copacului, adică nici un arc nu ar trebui să intre în el;
• dacă din rădăcină începe să se deplaseze de-a lungul arcurilor, acest proces ar trebui să permită obținerea completă a oricăror noduri.

Există, de asemenea, un astfel de lucru, o parte din codurile Huffman ca o frunză de copac. Este un nod din care nu ar trebui să scape nici un arc. Dacă două noduri sunt conectate printr-un arc, unul dintre ei este părintele celuilalt copil, în funcție de care nod arcul se stinge, și ceea ce este inclus. Dacă două noduri au același nod părinte, ele sunt numite site-uri surori. În cazul în care, în frunze, frunze din nodurile de mai multe arce, atunci este numit un arbore binar. Acesta este exact copacul lui Huffman. Particularitatea construcției de unități este faptul că greutatea fiecărui părinte este egală cu suma greutăților tuturor nodurilor sale pentru copii.

Algoritm pentru construirea unui copac în funcție de Huffman

Construcția codului Huffman se face din literele alfabetului de intrare. Se creează o listă a acelor noduri care sunt libere în arborele de cod viitor. 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, printre puținele noduri libere ale copacului viitor, se alege cel care cântărește cel mai puțin. În același timp, dacă indicatorii minime sunt observate în mai multe noduri, atunci este posibil să alegeți libere oricare dintre perechi. După aceasta, se creează nodul părinte, care ar trebui să cântărească atât cât cântărește suma acestei perechi de noduri. După aceasta, părintele este trimis la lista cu noduri gratuite, iar copiii sunt șterși. În același timp, arcele primesc indicii corespunzători, unul și zerouri. Acest proces este repetat exact atâta timp cât este necesar pentru a lăsa un singur nod. După aceasta, numerele binare sunt scrise de sus în jos.

Îmbunătățirea eficienței compresiei

Pentru a spori eficiența de compresie, este necesar ca în timpul codului de construcții copac pentru a utiliza toate datele cu privire la probabilitatea de apariție a literelor într-un anumit fișier, atașat la un copac, și să nu permită faptul că acestea sunt împrăștiate peste un număr mare de documente de tip text. În cazul în care pre-plimbare prin acest fișier, puteți calcula imediat statisticile cât de des există scrisori de unități aflate sub rezerva de compresie.

Accelerarea procesului de compresie

Pentru a accelera munca algoritm, definiție literele ar trebui să fie efectuate nu în funcție de indicii de probabilitate de apariție a unei anumite litere, ci de frecvența apariției acesteia. Datorită acestui lucru, algoritmul devine mai simplu, iar lucrul cu acesta este foarte accelerat. Acest lucru evită, de asemenea, operațiunile asociate cu virgule și diviziuni plutitoare. În plus, în acest mod de lucru, codul dinamic 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ța. Este demn de atenție faptului că greutatea finală a fișierului, sau nodul așa-numita rădăcină este egală cu suma numărului de caractere din obiectul care urmează să fie tratat.

concluzie

Codurile lui Huffman sunt un algoritm simplu și de lungă durată, care este încă folosit de multe programe și companii renumite. Simplitatea și claritatea acesteia permit obținerea unor rezultate eficiente de compresie pentru fișiere de orice dimensiune și reduc semnificativ spațiul pe care îl ocupă pe discul de stocare. Cu alte cuvinte, algoritmul Huffman este o schemă studiată și bine concepută, a cărei relevanță nu scade până în prezent. Și datorită capacității de a reduce dimensiunea fișierelor, de a le transfera în rețea sau în alte moduri, devine mai ușoară, mai rapidă și mai convenabilă. Lucrul cu algoritmul, puteți comprima absolut orice informație fără a afecta structura și calitatea sa, dar cu efectul maxim de reducere a greutății fișierului. Cu alte cuvinte, codificarea codului Huffman a fost și rămâne metoda cea mai populară și actuală de comprimare a dimensiunii fișierului.