Huffman coduri: cerere exemple

În acest moment, puțini oameni cred despre faptul, cum se compresie de fișiere. Comparativ cu utilizarea anterioară a calculatorului personal a devenit mult mai ușor. Și aproape fiecare persoană care lucrează cu sistemul de fișiere utilizează fișiere. 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.

algoritmul Istoric

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. De asemenea, algoritmul Huffman este utilizat pentru a comprima JPEG-imagini și alte obiecte grafice. Ei bine, toate faxurile sunt, de asemenea, folosind codificare modernă, inventat în 1952. În ciuda faptului că de la crearea codului a durat atât de mult timp pentru această zi este utilizat într-o varietate de noi membrane și echipamente de tipurile vechi și moderne.

Principiul de codificare eficiente

Baza algoritmului Huffman include un sistem care vă permite să înlocuiască cel mai credibil, cel mai adesea simboluri care apar codate binar sistem. Iar cei care sunt mai puțin frecvente, înlocuite cu coduri mai lungi. Mergând coduri Huffman lungi are loc numai după ce sistemul utilizează toate valorile minime. Această tehnică permite minimizarea lungimii codului pentru fiecare simbol al mesajului original, ca un întreg. Punctul important este faptul că, la începutul probabilității de codificare de apariție a literelor trebuie să fie deja cunoscute. Este de la ei vor fi pregătite și mesajul final. Pe baza acestor date, a efectuat construcția codului copac Huffman, pe baza cărora se va desfășura procesul de codificare litere în arhivă.

cod Huffman, exemplu

Pentru a ilustra algoritmul, ia în considerare o variantă grafică de construcție a arborelui de cod. Pentru a utiliza această metodă pentru a fi eficiente, este necesar să se clarifice definiția anumitor valori necesare pentru conceptul de proces. Setul din multitudinea de noduri și arce, care sunt direcționate de la un nod la altul, numit grafic. Arborele in sine este un grafic cu un set de proprietăți specifice:

• în fiecare nod poate include nu mai mult de una dintre arcele;
• unul dintre nodurile trebuie să fie rădăcina copacului, adică, nu ar trebui să fie o parte a arcului la toate;
• în cazul în care tija se deplasează de-a lungul a începe arcele, procesul ar trebui să permită să se complet în oricare dintre nodurile.

Există, de asemenea, un astfel de lucru, o parte din codurile Huffman ca o frunză de copac. Este un nod care nu ar trebui să meargă nici un arc de cerc. 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. Doar ca este arborele 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.

Un algoritm pentru construirea arborelui Huffman

Construcția codului Huffman este de intrare de la literele alfabetului. A generat o listă de site-uri care sunt libere, în viitor, arborele de cod. Greutatea fiecărui nod din listă trebuie să fie aceeași ca și probabilitatea de apariție a posturilor de litere corespunzătoare acestui nod. În acest caz, cel care cântărește cel mai puțin este ales dintre mai multe site-uri gratuite ale arborelui viitorului. În acest caz, în cazul în care sunt respectate ratele minime în mai multe site-uri, puteți selecta în mod liber oricare dintre perechi. Apoi vine crearea nodului părinte, care trebuie să cântărească la fel de mult ca suma ponderilor perechii de noduri. După aceea, părinții trimit lista cu toaletele libere, iar copiii sunt eliminate. În acest arc sunt indicatori adecvați, și cele zerouri. Acest proces este repetat la fel de mult cum este necesar pentru a păstra doar un singur nod. Apoi scrie cifre binare de sus în jos.

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

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 comprimare

Pentru a accelera algoritmul, definiția literelor ar trebui să se facă, nu în ceea ce privește probabilitatea de apariție a unei anumite litere, precum și frecvența apariției acesteia. Cu acest algoritm devine mai ușor, și de a lucra cu ei mult mai repede. se evită, de asemenea, operațiunile asociate cu diviziunea în virgulă mobilă. Î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 Huffman - algoritm simplu și lung stabilit, care este încă folosit de multe programe bine cunoscute și companii. simplitatea și claritatea sa pot obține rezultate eficiente comprima fișiere de orice volum și reduce semnificativ spațiul de pe disc de stocare. Cu alte cuvinte, algoritmul Huffman - a fost mult timp investigat și diagrama de lucru care urgența nu este redusă cu această zi. Și cu capacitatea de a reduce dimensiunea fișierelor, a le transfera într-o rețea sau prin alte mijloace, este mult mai simplu, rapid și convenabil. Lucrul cu algoritmul, puteți comprima orice informație complet fără a afecta structura și calitatea acesteia, dar cu efect maxim pentru a reduce fișierul de greutate. Cu alte cuvinte, codificarea codului Huffman a fost și rămâne cel mai popular și relevante metoda de comprimare dimensiunea fișierului.