- cod = următorul bit din flux, lungime = 1
- În timp ce codul< base
cod = cod<< 1
cod = cod + următorul bit din flux
lungime = lungime + 1 - simbol = simbol + cod - bază]
Cu alte cuvinte, vom împinge din stânga în variabila cod bit cu bit din fluxul de intrare, până la cod< base. При этом на каждой итерации будем увеличивать переменную length на 1 (т.е. продвигаться вниз по дереву). Цикл в (2) остановится когда мы определим длину кода (уровень в дереве, на котором находится искомый символ). Остается лишь определить какой именно символ на этом уровне нам нужен.
Să presupunem că bucla din (2), după mai multe iterații, se oprește. În acest caz, expresia (cod - bază) este numărul ordinal al nodului (caracterului) necesar la nivelul lungimii. Primul nod (simbol) la nivelul lungimii din arbore este situat în matricea de simboluri la indexul offs. Dar nu ne interesează primul caracter, ci caracterul de sub număr (cod - bază). Prin urmare, indexul simbolului dorit în matricea symb este (offs + (cod - bază)). Cu alte cuvinte, simbolul necesar este simbol = simbol + cod - bază].
Să dăm un exemplu concret. Folosind algoritmul descris, decodăm mesajul Z/.
Z / = "0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 1 0010 1 1 1 0010 1 0 1 1 0 1 0 1 0 1 0 1 1 0
- cod = 0, lungime = 1
- cod = 0< base = 1
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 1 + 1 = 2
cod = 0< base = 2
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 2 + 1 = 3
cod = 0< base = 2
cod = 0<< 1 = 0
cod = 0 + 1 = 1
lungime = 3 + 1 = 4
cod = 1 = baza = 1 - simbol = simbol = 2 + cod = 1 - bază = 1] = simbol = A
- cod = 1, lungime = 1
- cod = 1 = baza = 1
- simbol = simbol = 7 + cod = 1 - bază = 1] = simbol = H
- cod = 0, lungime = 1
- cod = 0< base = 1
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 1 + 1 = 2
cod = 0< base = 2
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 2 + 1 = 3
cod = 0< base = 2
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 3 + 1 = 4
cod = 0< base = 1
cod = 0<< 1 = 0
cod = 0 + 1 = 1
lungime = 4 + 1 = 5
cod = 1> baza = 0 - simbol = simbol = 0 + cod = 1 - bază = 0] = simbol = F
Deci, am decodat primele 3 caractere: A, H, F... Este clar că urmând acest algoritm vom primi exact mesajul S.
Calcularea lungimii codului
Pentru a codifica un mesaj, trebuie să cunoaștem codurile caracterelor și lungimile acestora. După cum sa menționat în secțiunea anterioară, codurile canonice sunt bine definite prin lungimile lor. Astfel, sarcina noastră principală este să calculăm lungimile codurilor.
Se pare că această sarcină, în majoritatea covârșitoare a cazurilor, nu necesită construirea explicită a unui arbore Huffman. Mai mult, algoritmii care folosesc reprezentarea internă (implicita) a arborelui Huffman sunt mult mai eficienți în ceea ce privește viteza și consumul de memorie.
Astăzi există mulți algoritmi eficienți pentru calcularea lungimii codurilor (,). Ne vom restrânge să luăm în considerare doar una dintre ele. Acest algoritm este destul de simplu, dar, în ciuda acestui fapt, este foarte popular. Este folosit în programe precum zip, gzip, pkzip, bzip2 și multe altele.
Să revenim la algoritmul de construcție a arborelui Huffman. La fiecare iterație, am efectuat o căutare liniară pentru cele două noduri cu cea mai mică pondere. În mod clar, o coadă cu prioritate, cum ar fi o piramidă (minim), este mai potrivită în acest scop. Nodul cu cea mai mică greutate va avea cea mai mare prioritate și se va afla în vârful piramidei. Să dăm acest algoritm.
Să includem toate caracterele codificate în piramidă.
Să extragem secvenţial 2 noduri din piramidă (acestea vor fi două noduri cu cea mai mică greutate).
Să ne formăm nod nouși atașează-i, în copilărie, două noduri luate din piramidă. În acest caz, greutatea nodului format este setată egală cu suma greutăților nodurilor copil.
Să includem nodul format în piramidă.
Dacă există mai mult de un nod în piramidă, repetați 2-5.
Vom presupune că un pointer către părintele său este stocat pentru fiecare nod. Setăm acest indicator egal cu NULL la rădăcina arborelui. Acum haideți să selectăm nodul frunză (simbol) și urmând pointerii salvati vom urca în arbore până când următorul pointer devine NULL. Ultima condiție înseamnă că am ajuns la rădăcina copacului. Este clar că numărul de tranziții de la nivel la nivel este egal cu adâncimea nodului frunză (simbol) și, prin urmare, cu lungimea codului său. Ocolind în acest fel toate nodurile (simbolurile), obținem lungimile codurilor lor.
Lungimea maximă a codului
De regulă, așa-numitul cartea de coduri, o structură de date simplă, în esență două tablouri: unul cu lungimi, celălalt cu coduri. Cu alte cuvinte, codul (ca șir de biți) este stocat într-o locație de memorie sau într-un registru de dimensiune fixă (de obicei 16, 32 sau 64). Pentru a evita debordarea, trebuie să fim siguri că codul se va încadra în registru.
Se pare că pe un alfabet cu N caractere, dimensiunea maximă a codului poate fi de până la (N-1) biți în lungime. Cu alte cuvinte, pentru N = 256 (o variantă comună) putem obține un cod de 255 de biți lungime (deși pentru aceasta fișierul trebuie să fie foarte mare: 2.292654130570773 * 10 ^ 53 ~ = 2 ^ 177.259)! Este clar că un astfel de cod nu se va încadra în registru și trebuie să faci ceva cu el.
Mai întâi, să aflăm în ce condiții are loc revărsarea. Fie frecvența simbolului i-lea să fie egală cu al-lea număr Fibonacci. De exemplu: A-1, B-1, C-2, D-3, E-5, F-8, G-13, H-21. Să construim arborele Huffman corespunzător.
ROOT / \ / \ / \ / \ H / \ / \ /\ G / \ / \ /\ F / \ / \ /\ E / \ / \ /\ D / \ / \ /\ C / \ / \ A B
Un astfel de copac se numește degenerat... Pentru a-l obține, frecvențele simbolurilor trebuie să crească cel puțin ca numere Fibonacci sau chiar mai repede. Deși în practică, pe date reale, un astfel de arbore este aproape imposibil de obținut, este foarte ușor să îl generezi artificial. În orice caz, acest pericol trebuie luat în considerare.
Această problemă poate fi rezolvată în două moduri acceptabile. Primul se bazează pe una dintre proprietățile codurilor canonice. Ideea este că în codul canonic (șir de biți) cel puțin biții semnificativi pot fi non-zero. Cu alte cuvinte, este posibil ca toți ceilalți biți să nu fie salvați deloc, deoarece sunt întotdeauna zero. În cazul lui N = 256, este suficient să salvăm doar cei 8 biți mai puțin semnificativi din fiecare cod, presupunând că toți ceilalți biți sunt egali cu zero. Acest lucru rezolvă problema, dar numai parțial. Acest lucru va complica foarte mult și va încetini atât codarea, cât și decodarea. Prin urmare, această metodă este rar folosită în practică.
A doua modalitate este de a limita artificial lungimile codurilor (fie în timpul construcției, fie după). Această metodă este în general acceptată, așa că ne vom opri mai detaliat asupra ei.
Există două tipuri de algoritmi de cod de limitare a lungimii. Euristică (aproximativă) și optimă. Algoritmii de al doilea tip sunt destul de complexi în implementare și, de regulă, necesită mai mult timp și memorie decât primii. Eficacitatea codului constrâns euristic este determinată de abaterea sa de la codul constrâns optim. Cu cât diferența este mai mică, cu atât mai bine. Este de remarcat faptul că pentru unii algoritmi euristici această diferență este foarte mică (,,), în plus, ei generează foarte des cod optim (deși nu garantează că așa va fi întotdeauna). Mai mult, din moment ce în practică, depășirea apare extrem de rar (cu excepția cazului în care este stabilită o restricție foarte strictă asupra lungimii maxime a codului); cu o dimensiune alfabetică mică, este mai oportun să se utilizeze metode euristice simple și rapide.
Vom lua în considerare un algoritm euristic destul de simplu și foarte popular. Și-a găsit drumul în programe precum zip, gzip, pkzip, bzip2 și multe altele.
Problema limitării lungimii maxime a codului este echivalentă cu problema limitării înălțimii arborelui Huffman. Rețineți că, prin construcție, orice nod fără frunză al arborelui Huffman are exact doi descendenți. La fiecare iterație a algoritmului nostru, vom scădea înălțimea arborelui cu 1. Deci, fie L lungimea maximă a codului (înălțimea arborelui) și este necesar să o limităm la L / & lt L. Fie mai departe RN i cea mai dreaptă nodul frunză la nivelul i, iar LN i - cel mai din stânga.
Să începem de la nivelul L. Mută nodul RN L la locul părintelui său. pentru că nodurile merg în perechi, trebuie să găsim un loc pentru un nod adiacent RN L. Pentru a face acest lucru, găsiți nivelul j cel mai apropiat de L, care conține noduri de frunze, astfel încât j & lt (L-1). În locul lui LN j, formăm un nod fără foaie și îi atașăm ca copii nodul LN j și nodul neîmperecheat de la nivelul L. Aplicam aceeași operație tuturor perechilor de noduri rămase la nivelul L. Este clar că redistribuind nodurile în acest fel, am redus înălțimea arborelui nostru cu 1. Acum este egal cu (L-1). Dacă acum L / & lt (L-1), atunci vom face același lucru cu nivelul (L-1), etc. până la atingerea limitei cerute.
Să revenim la exemplul nostru, unde L = 5. Să limităm lungimea maximă a codului la L / = 4.
ROOT / \ / \ / \ / \ H C E / \ / \ / \ / \ /\ A D G / \ / \ B F
Se vede ca in cazul nostru RN L = F, j = 3, LN j = C... Mai întâi, mutați nodul RN L = Fîn locul părintelui lor.
ROOT / \ / \ / \ / \ H / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ C E / \ / \ / \ / \ F A D G B(nod neîmperecheat)
Acum, în locul lui LN j = C Să formăm un nod fără frunză.
ROOT / \ / \ / \ / \ H E / \ / \ / \ / \ / \ / \ F A D G ? ? B(nod neîmperecheat) C(nod neîmperecheat)
Să atașăm două nepereche la nodul format: Bși C.
ROOT / \ / \ / \ / \ H / \ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ /\ E / \ / \ / \ / \ / \ / \ F A D G B C
Astfel, am limitat lungimea maximă a codului la 4. Este clar că prin modificarea lungimii codului am pierdut puțin în eficiență. Deci mesajul S, codificat cu un astfel de cod, va avea o dimensiune de 92 de biți, adică. Încă 3 biți peste Redundanța Minimă.
Este clar că cu cât limităm mai mult lungimea maximă a codului, cu atât codul va fi mai puțin eficient. Să aflăm cât de mult poți limita lungimea maximă a codului. Evident, nu mai scurt decât puțin.
Calculul Codurilor Canonice
După cum am observat deja de multe ori, lungimile codurilor sunt suficiente pentru a genera codurile în sine. Vă vom arăta cum se poate face acest lucru. Să presupunem că am calculat deja lungimile codurilor și am numărat câte coduri din fiecare lungime avem. Fie L lungimea maximă a codului și T i numărul de coduri de lungime i.
Calculăm S i - valoarea initiala codul lungimii i, pentru tot i de la
S L = 0 (întotdeauna)
S L-1 = (S L + T L) >> 1
S L-2 = (S L-1 + T L-1) >> 1
...
S 1 = 1 (întotdeauna)
Pentru exemplul nostru, L = 5, T 1 .. 5 = (1, 0, 2, 3, 2).
S 5 = 00000 bin = 0 dec
S 4 = (S 5 = 0 + T 5 = 2) >> 1 = (00010 bin >> 1) = 0001 bin = 1 dec
S 3 = (S 4 = 1 + T 4 = 3) >> 1 = (0100 bin >> 1) = 010 bin = 2 dec
S 2 = (S 3 = 2 + T 3 = 2) >> 1 = (100 bin >> 1) = 10 bin = 2 dec
S 1 = (S 2 = 2 + T 2 = 0) >> 1 = (10 bin >> 1) = 1 bin = 1 dec
Se poate observa că S 5, S 4, S 3, S 1 sunt exact codurile de caractere B, A, C, H... Aceste simboluri sunt unite de faptul că toate vin pe primul loc, fiecare la nivelul său. Cu alte cuvinte, am găsit valoarea inițială a codului pentru fiecare lungime (sau nivel).
Acum să atribuim coduri restului simbolurilor. Codul primului caracter la nivelul i este S i, al doilea S i + 1, al treilea S i + 2 etc.
Să scriem codurile rămase pentru exemplul nostru:
| B= S 5 = 00000 bin | A= S 4 = 0001 bin | C= S 3 = 010 bin | H= S 1 = 1 bin |
| F= S 5 + 1 = 00001 bin | D= S 4 + 1 = 0010 bin | E= S 3 + 1 = 011 bin | |
| G= S 4 + 2 = 0011 bin |
Se poate observa că am primit exact aceleași coduri ca și cum am fi construit în mod explicit arborele canonic Huffman.
Trecerea unui arbore de cod
Pentru ca mesajul codificat să fie decodat, decodorul trebuie să aibă același arbore de cod (într-o formă sau alta) care a fost folosit pentru codificare. Prin urmare, împreună cu datele codificate, suntem forțați să salvăm arborele de cod corespunzător. Este clar că cu cât este mai compact, cu atât mai bine.
Există mai multe modalități de a rezolva această problemă. Cel mai solutie evidenta- salvați arborele în mod explicit (adică ca un set ordonat de noduri și pointeri de un fel sau altul). Acesta este poate cel mai risipitor și ineficient mod. În practică, nu este folosit.
Poate fi salvată o listă de frecvențe simbol (adică dicționar de frecvență). Cu ajutorul său, decodorul poate reconstrui cu ușurință arborele de cod. Deși această metodă este mai puțin risipitoare decât cea anterioară, nu este cea mai bună.
În cele din urmă, poate fi folosită una dintre proprietățile codurilor canonice. După cum sa menționat mai devreme, codurile canonice sunt complet determinate de lungimile lor. Cu alte cuvinte, tot ce are nevoie decodorul este o listă de lungimi de cod de caractere. Având în vedere că, în medie, lungimea unui cod pentru un alfabet cu N caractere poate fi codificată în [(log 2 (log 2 N))] biți, obținem un algoritm foarte eficient. Ne vom opri asupra ei mai detaliat.
Să presupunem că dimensiunea alfabetului este N = 256 și comprimăm cea obișnuită fisier text(ASCII). Cel mai probabil nu vom găsi toate N caracterele alfabetului nostru într-un astfel de fișier. Apoi punem lungimea codului caracterelor lipsă egal cu zero... În acest caz, lista salvată de lungimi de cod va conține suficient număr mare zerouri (lungimile codurilor de caractere lipsă) grupate împreună. Fiecare astfel de grup poate fi comprimat folosind așa-numita codificare de grup - RLE (Run - Length - Encoding). Acest algoritm este extrem de simplu. În loc de o secvență de M elemente identice într-un rând, vom salva primul element din această secvență și numărul repetărilor sale, adică. (M-1). Exemplu: RLE ("AAAABBCDDDDDDD") = A3 B2 C0 D6.
Mai mult, această metodă poate fi oarecum extinsă. Putem aplica Algoritmul RLE nu numai la grupuri de lungimi zero, ci la toate celelalte. Acest mod de a trece un arbore de cod este comun și este folosit în majoritatea implementărilor moderne.
Implementare: SHCODEC
Anexă: biografia lui D. Huffman
 |
David Huffman s-a născut în 1925 în Ohio, SUA. Huffman a primit licența în Inginerie Electrică de la universitate de stat Ohio (Ohio State University) la vârsta de 18 ani. Apoi a servit în armată ca ofițer de sprijin radar pe un distrugător care a ajutat la dezamorsarea minelor în apele japoneze și chineze după al Doilea Război Mondial. Ulterior, a primit un master de la Universitatea Ohio și un doctorat de la Massachusetts Institute of Technology (MIT). Deși Huffman este cel mai bine cunoscut pentru dezvoltarea unei metode de construire a codurilor minim redundante, el a adus, de asemenea, contribuții importante în multe alte domenii (mai ales în electronică). El pentru mult timp a condus Departamentul de Informatică de la MIT. În 1974, deja profesor emerit, a demisionat. Huffman a primit o serie de premii valoroase. 1999 - Medalia Richard W. Hamming de la Institutul de Ingineri Electrici și Electronici (IEEE) pentru contribuții excepționale la teoria informației, Medalia Louis E. Levy de la Institutul Franklin pentru teza sa de doctorat privind circuitele secvențiale, Premiul W. Wallace McDowell, IEEE Computer Society Award, IEEE Gold Jubilee Technology Innovation Award în 1998. În octombrie 1999, la vârsta de 74 de ani, David Huffman a murit de cancer. R.L. Milidiu, A.A. Pessoa, E.S. Laber, „Implementarea eficientă a algoritmului de încălzire pentru construirea codurilor de prefix cu restricții de lungime”, Proc. de ALENEX (Atelier internațional de inginerie și experimentare a algoritmilor), pp. 1-17, Springer, ian. 1999. |
Astăzi, puțini dintre utilizatori sunt interesați de întrebarea legată de mecanismul de comprimare a fișierelor. Procesul de lucru cu calculator personalîn comparație cu trecutul, a devenit mult mai ușor de implementat.
Astăzi, aproape orice utilizator cu care lucrează Sistemul de fișiere folosește arhive. Cu toate acestea, puțini utilizatori s-au gândit la modul în care fișierele sunt comprimate.
Codurile Huffman au fost prima opțiune. Ele sunt încă folosite în diferite arhivare. Majoritatea utilizatorilor nici măcar nu se gândesc cât de ușor este să comprimați un fișier folosind această schemă. V această recenzie ne vom uita la modul în care se realizează compresia, ce caracteristici ajută la accelerarea și simplificarea procesului de codificare. Vom încerca, de asemenea, să înțelegem principiile de bază ale construirii unui arbore de codare.
Algoritm: istorie
Primul algoritm conceput pentru a realiza o codificare eficientă informatii electronice, a devenit codul propus de Huffman în 1952. Acest cod poate fi luat în considerare astăzi element de bază majoritatea programelor concepute pentru a comprima informații. Unele dintre cele mai populare surse care folosesc codul dat, astăzi sunt arhivele RAR, ARJ, ZIP. Acest algoritm este folosit și pentru compresie Imagini JPEGși obiecte grafice... De asemenea, toate faxurile moderne folosesc un algoritm de codare care a fost inventat încă din 1952. În ciuda faptului că a trecut mult timp de la crearea acestui cod, acesta este utilizat eficient în echipamente de tip vechi, precum și în echipamente și carcase noi.
Principiul codificării eficiente
În centrul algoritmului Huffman se află o schemă care vă permite să înlocuiți cele mai probabile și mai comune caractere cu coduri sistem binar... Acele caractere care sunt mai puțin comune sunt înlocuite cu coduri lungi. Trecerea la coduri lungi Huffman se efectuează numai după ce sistemul utilizează toate valorile minime. Această tehnică face posibilă reducerea la minimum a lungimii codului pe caracter al mesajului original. V în acest caz particularitatea constă în faptul că probabilitățile de apariție a literelor la începutul codificării trebuie deja cunoscute. Mesajul final va fi compus din ele. Pe baza acestor informații, se construiește un arbore de codificare Huffman. Pe baza acestuia, se va desfășura procesul de codificare a literelor în arhivă.
Cod Huffman: exemplu
Pentru a ilustra algoritmul Huffman, luați în considerare o versiune grafică a construirii unui arbore de cod. A folosi aceasta metoda a fost mai eficient, este necesar să se clarifice definiția unora dintre valorile care sunt necesare pentru conceptul acestei metode. Întreaga colecție a unui set de noduri și arce care sunt 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 ar trebui să includă nu mai mult de unul dintre toate arcurile. Unul dintre noduri trebuie să fie rădăcina arborelui. Aceasta înseamnă că arcuri nu ar trebui să intre deloc în el. Dacă începeți de la rădăcina deplasării de-a lungul arcurilor, atunci acest proces ar trebui să vă permită să ajungeți la orice nod.
Codurile Huffman includ, de asemenea, un astfel de concept precum o frunză de copac. Reprezintă un nod din care nu ar trebui să iasă niciun arc. Dacă două noduri sunt conectate printr-un arc, atunci unul dintre ele este părinte, iar celălalt este copil. Dacă două noduri au un nod părinte comun, atunci ele se numesc noduri frați. Dacă, pe lângă frunze, nodurile au mai multe arce, atunci un astfel de arbore se numește binar. Acesta este exact ceea ce este arborele Huffman. O caracteristică a nodurilor acestei structuri este că greutatea fiecărui părinte este egală cu suma greutății copiilor nodali.
Arborele Huffman: algoritm de construcție
Construcția codului Huffman se realizează din literele alfabetului introdus. Se formează o listă de noduri care sunt libere în viitorul arbore de cod. În această listă, ponderea fiecărui nod ar trebui să fie aceeași cu probabilitatea de apariție a literei de mesaj care corespunde cu acest nod... Dintre mai multe noduri libere, este selectat cel care cântărește cel mai puțin. Dacă, în același timp, se observă indicatorii minimi în mai multe noduri, atunci puteți alege liber orice pereche. După aceea, este creat nodul părinte. Ar trebui să cântărească atât cât cântărește suma perechii date de noduri. Părintele este apoi trimis la lista cu noduri libere. Copiii sunt îndepărtați. În acest caz, arcurile primesc indicatorii corespunzători, zerouri și unu. Acest proces se repetă de câte ori este nevoie pentru a lăsa un singur nod. După aceea, cifrele binare sunt scrise de sus în jos.
Cum să îmbunătățiți eficiența compresiei
Pentru a crește eficiența compresiei, în timpul construcției arborelui de cod, este necesar să se utilizeze toate datele referitoare la probabilitatea apariției literelor într-un anumit fișier care este atașat arborelui. Ele nu ar trebui să fie împrăștiate pe un număr mare de documente text. Dacă treci prin acest fișier, apoi puteți obține statistici despre cât de des sunt găsite litere de la obiectul care urmează să fie comprimat.
Cum să accelerezi procesul de compresie
Pentru a accelera funcționarea algoritmului, identificarea literelor ar trebui să fie efectuată nu de indicatorii apariției anumitor litere, ci de frecvența apariției lor. Datorită acestui lucru, algoritmul devine mai simplu, iar lucrul cu acesta este semnificativ accelerat. De asemenea, face posibilă evitarea operațiunilor de divizare și virgulă mobilă. De asemenea, atunci când lucrați în acest mod, algoritmul nu poate fi schimbat. Acest lucru se datorează în principal faptului că probabilitățile sunt direct proporționale cu frecvențele. De asemenea, merită să acordați atenție faptului că greutatea finală a nodului rădăcină va fi egală cu suma numărului de litere din obiectul care urmează să fie procesat.
Concluzie
Codurile Huffman sunt un algoritm simplu și de lungă durată care este folosit și astăzi în mulți programe populare... Simplitatea și claritatea acestui cod vă permit să realizați compresie eficientă fișiere de orice dimensiune.
O metodă relativ simplă de comprimare a datelor poate fi realizată prin crearea așa-numiților arbori Huffman pentru un fișier și folosit pentru a-l comprima și a decomprima datele din acesta. Majoritatea aplicațiilor folosesc arbori Huffman binari (de exemplu, fiecare nod este fie o frunză, fie are exact două subnoduri). Este posibil, totuși, să construiți copaci Huffman cu un număr arbitrar subarbori (de exemplu, ternari sau, în caz general, N-ca copacii).
Arborele Huffman pentru fișierul care conține Z personaje diferite Are Z frunze. Calea de la rădăcină la frunză care reprezintă un anumit caracter determină codificarea, iar fiecare pas de-a lungul căii către frunză determină codarea (care poate fi 0 , 1 , ..., (N-1)). Prin plasarea caracterelor comune mai aproape de rădăcină și a caracterelor mai puțin comune mai departe de rădăcină, se obține compresia dorită. Strict vorbind, un astfel de arbore va fi un arbore Huffman numai dacă, ca urmare a codificării, numărul minim N caractere -ary pentru a codifica fișierul specificat.
În această problemă, vom lua în considerare doar arbori, în care fiecare nod este fie un nod intern, fie o frunză de codificare a caracterelor și nu există frunze izolate care să nu codifice un caracter.
Figura de mai jos prezintă un exemplu de arbore ternar Huffman, simboluri " A" și " e„codificat cu un singur caracter ternar; caractere mai puțin comune” s" și " p„sunt codificate folosind două caractere ternare și cele mai rare caractere” X", "q" și " y„sunt codificați folosind trei caractere ternare fiecare.
Desigur, dacă vrem să extindem lista N-are caractere apoi înapoi, este important să știți ce arbore este folosit pentru a comprima datele. Acest lucru se poate face în mai multe moduri. În această sarcină vom folosi următoarea metodă: fluxul de date de intrare va fi precedat de un antet format din valori de caractere codificate Z situat în fișier sursăîn ordine lexicografică.
Cunoașterea numărului de caractere introduse Z, sens N indicând " N-aritatea "arborelui Huffman și a antetului în sine, este necesar să se găsească valoarea primară a caracterelor codificate.
Date de intrare
Datele de intrare încep cu un număr întreg T, situat pe o linie separată și indicând numărul cazurilor de testare ulterioare. În continuare, fiecare dintre T cazuri de testare, fiecare dintre acestea fiind situat în 3 -lele rânduri, după cum urmează:
- Numărul de caractere distincte în cazul de testare Z (2 ≤ Z ≤ 20 );
- Număr N indicând " N-aritatea arborelui Huffman ( 2 ≤ N ≤ 10 );
- Un șir reprezentând antetul mesajului primit, fiecare caracter va fi o cifră în interval ... Această linie va conține mai puțin 200 personaje.
Notă: Deși rar, este posibil ca un antet să aibă mai multe interpretări la decodificare (de exemplu, pentru un antet " 010011101100 ", și valori Z = 5și N = 2). Este garantat că în toate cazurile de testare propuse în datele de intrare, există o soluție unică.
Ieșire
Pentru fiecare dintre T ieșirea cazurilor de testare Z linii care oferă o versiune decodificată a fiecăruia dintre Z caractere în ordine crescătoare. Utilizați formatul original-> codificare, Unde original- aceasta numar decimalîn intervalul și șirul de cifre codificate corespunzător pentru acele caractere (fiecare cifră ≥ 0 și< N).
- cod = următorul bit din flux, lungime = 1
- În timp ce codul< base
cod = cod<< 1
cod = cod + următorul bit din flux
lungime = lungime + 1 - simbol = simbol + cod - bază]
Cu alte cuvinte, vom împinge din stânga în variabila cod bit cu bit din fluxul de intrare, până la cod< base. При этом на каждой итерации будем увеличивать переменную length на 1 (т.е. продвигаться вниз по дереву). Цикл в (2) остановится когда мы определим длину кода (уровень в дереве, на котором находится искомый символ). Остается лишь определить какой именно символ на этом уровне нам нужен.
Să presupunem că bucla din (2), după mai multe iterații, se oprește. În acest caz, expresia (cod - bază) este numărul ordinal al nodului (caracterului) necesar la nivelul lungimii. Primul nod (simbol) la nivelul lungimii din arbore este situat în matricea de simboluri la indexul offs. Dar nu ne interesează primul caracter, ci caracterul de sub număr (cod - bază). Prin urmare, indexul simbolului dorit în matricea symb este (offs + (cod - bază)). Cu alte cuvinte, simbolul necesar este simbol = simbol + cod - bază].
Să dăm un exemplu concret. Folosind algoritmul descris, decodăm mesajul Z/.
Z / = "0001 1 00001 00000 1 010 011 1 011 1 010 011 0001 1 0010 010 011 011 1 1 1 010 1 1 1 1 0010 1 1 1 0010 1 0 1 1 0 1 0 1 0 1 0 1 1 0
- cod = 0, lungime = 1
- cod = 0< base = 1
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 1 + 1 = 2
cod = 0< base = 2
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 2 + 1 = 3
cod = 0< base = 2
cod = 0<< 1 = 0
cod = 0 + 1 = 1
lungime = 3 + 1 = 4
cod = 1 = baza = 1 - simbol = simbol = 2 + cod = 1 - bază = 1] = simbol = A
- cod = 1, lungime = 1
- cod = 1 = baza = 1
- simbol = simbol = 7 + cod = 1 - bază = 1] = simbol = H
- cod = 0, lungime = 1
- cod = 0< base = 1
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 1 + 1 = 2
cod = 0< base = 2
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 2 + 1 = 3
cod = 0< base = 2
cod = 0<< 1 = 0
cod = 0 + 0 = 0
lungime = 3 + 1 = 4
cod = 0< base = 1
cod = 0<< 1 = 0
cod = 0 + 1 = 1
lungime = 4 + 1 = 5
cod = 1> baza = 0 - simbol = simbol = 0 + cod = 1 - bază = 0] = simbol = F
Deci, am decodat primele 3 caractere: A, H, F... Este clar că urmând acest algoritm vom primi exact mesajul S.
Calcularea lungimii codului
Pentru a codifica un mesaj, trebuie să cunoaștem codurile caracterelor și lungimile acestora. După cum sa menționat în secțiunea anterioară, codurile canonice sunt bine definite prin lungimile lor. Astfel, sarcina noastră principală este să calculăm lungimile codurilor.
Se pare că această sarcină, în majoritatea covârșitoare a cazurilor, nu necesită construirea explicită a unui arbore Huffman. Mai mult, algoritmii care folosesc reprezentarea internă (implicita) a arborelui Huffman sunt mult mai eficienți în ceea ce privește viteza și consumul de memorie.
Astăzi există mulți algoritmi eficienți pentru calcularea lungimii codurilor (,). Ne vom restrânge să luăm în considerare doar una dintre ele. Acest algoritm este destul de simplu, dar, în ciuda acestui fapt, este foarte popular. Este folosit în programe precum zip, gzip, pkzip, bzip2 și multe altele.
Să revenim la algoritmul de construcție a arborelui Huffman. La fiecare iterație, am efectuat o căutare liniară pentru cele două noduri cu cea mai mică pondere. În mod clar, o coadă cu prioritate, cum ar fi o piramidă (minim), este mai potrivită în acest scop. Nodul cu cea mai mică greutate va avea cea mai mare prioritate și se va afla în vârful piramidei. Să dăm acest algoritm.
Să includem toate caracterele codificate în piramidă.
Să extragem secvenţial 2 noduri din piramidă (acestea vor fi două noduri cu cea mai mică greutate).
Să formăm un nou nod și să-i atașăm, ca copii, două noduri luate din piramidă. În acest caz, greutatea nodului format este setată egală cu suma greutăților nodurilor copil.
Să includem nodul format în piramidă.
Dacă există mai mult de un nod în piramidă, repetați 2-5.
Vom presupune că un pointer către părintele său este stocat pentru fiecare nod. Setăm acest indicator egal cu NULL la rădăcina arborelui. Acum haideți să selectăm nodul frunză (simbol) și urmând pointerii salvati vom urca în arbore până când următorul pointer devine NULL. Ultima condiție înseamnă că am ajuns la rădăcina copacului. Este clar că numărul de tranziții de la nivel la nivel este egal cu adâncimea nodului frunză (simbol) și, prin urmare, cu lungimea codului său. Ocolind în acest fel toate nodurile (simbolurile), obținem lungimile codurilor lor.
Lungimea maximă a codului
De regulă, așa-numitul cartea de coduri, o structură de date simplă, în esență două tablouri: unul cu lungimi, celălalt cu coduri. Cu alte cuvinte, codul (ca șir de biți) este stocat într-o locație de memorie sau într-un registru de dimensiune fixă (de obicei 16, 32 sau 64). Pentru a evita debordarea, trebuie să fim siguri că codul se va încadra în registru.
Se pare că pe un alfabet cu N caractere, dimensiunea maximă a codului poate fi de până la (N-1) biți în lungime. Cu alte cuvinte, pentru N = 256 (o variantă comună) putem obține un cod de 255 de biți lungime (deși pentru aceasta fișierul trebuie să fie foarte mare: 2.292654130570773 * 10 ^ 53 ~ = 2 ^ 177.259)! Este clar că un astfel de cod nu se va încadra în registru și trebuie să faci ceva cu el.
Mai întâi, să aflăm în ce condiții are loc revărsarea. Fie frecvența simbolului i-lea să fie egală cu al-lea număr Fibonacci. De exemplu: A-1, B-1, C-2, D-3, E-5, F-8, G-13, H-21. Să construim arborele Huffman corespunzător.
ROOT / \ / \ / \ / \ H / \ / \ /\ G / \ / \ /\ F / \ / \ /\ E / \ / \ /\ D / \ / \ /\ C / \ / \ A B
Un astfel de copac se numește degenerat... Pentru a-l obține, frecvențele simbolurilor trebuie să crească cel puțin ca numere Fibonacci sau chiar mai repede. Deși în practică, pe date reale, un astfel de arbore este aproape imposibil de obținut, este foarte ușor să îl generezi artificial. În orice caz, acest pericol trebuie luat în considerare.
Această problemă poate fi rezolvată în două moduri acceptabile. Primul se bazează pe una dintre proprietățile codurilor canonice. Ideea este că în codul canonic (șir de biți) cel puțin biții semnificativi pot fi non-zero. Cu alte cuvinte, este posibil ca toți ceilalți biți să nu fie salvați deloc, deoarece sunt întotdeauna zero. În cazul lui N = 256, este suficient să salvăm doar cei 8 biți mai puțin semnificativi din fiecare cod, presupunând că toți ceilalți biți sunt egali cu zero. Acest lucru rezolvă problema, dar numai parțial. Acest lucru va complica foarte mult și va încetini atât codarea, cât și decodarea. Prin urmare, această metodă este rar folosită în practică.
A doua modalitate este de a limita artificial lungimile codurilor (fie în timpul construcției, fie după). Această metodă este în general acceptată, așa că ne vom opri mai detaliat asupra ei.
Există două tipuri de algoritmi de cod de limitare a lungimii. Euristică (aproximativă) și optimă. Algoritmii de al doilea tip sunt destul de complexi în implementare și, de regulă, necesită mai mult timp și memorie decât primii. Eficacitatea codului constrâns euristic este determinată de abaterea sa de la codul constrâns optim. Cu cât diferența este mai mică, cu atât mai bine. Este de remarcat faptul că pentru unii algoritmi euristici această diferență este foarte mică (,,), în plus, ei generează foarte des cod optim (deși nu garantează că așa va fi întotdeauna). Mai mult, din moment ce în practică, depășirea apare extrem de rar (cu excepția cazului în care este stabilită o restricție foarte strictă asupra lungimii maxime a codului); cu o dimensiune alfabetică mică, este mai oportun să se utilizeze metode euristice simple și rapide.
Vom lua în considerare un algoritm euristic destul de simplu și foarte popular. Și-a găsit drumul în programe precum zip, gzip, pkzip, bzip2 și multe altele.
Problema limitării lungimii maxime a codului este echivalentă cu problema limitării înălțimii arborelui Huffman. Rețineți că, prin construcție, orice nod fără frunză al arborelui Huffman are exact doi descendenți. La fiecare iterație a algoritmului nostru, vom scădea înălțimea arborelui cu 1. Deci, fie L lungimea maximă a codului (înălțimea arborelui) și este necesar să o limităm la L / & lt L. Fie mai departe RN i cea mai dreaptă nodul frunză la nivelul i, iar LN i - cel mai din stânga.
Să începem de la nivelul L. Mută nodul RN L la locul părintelui său. pentru că nodurile merg în perechi, trebuie să găsim un loc pentru un nod adiacent RN L. Pentru a face acest lucru, găsiți nivelul j cel mai apropiat de L, care conține noduri de frunze, astfel încât j & lt (L-1). În locul lui LN j, formăm un nod fără foaie și îi atașăm ca copii nodul LN j și nodul neîmperecheat de la nivelul L. Aplicam aceeași operație tuturor perechilor de noduri rămase la nivelul L. Este clar că redistribuind nodurile în acest fel, am redus înălțimea arborelui nostru cu 1. Acum este egal cu (L-1). Dacă acum L / & lt (L-1), atunci vom face același lucru cu nivelul (L-1), etc. până la atingerea limitei cerute.
Să revenim la exemplul nostru, unde L = 5. Să limităm lungimea maximă a codului la L / = 4.
ROOT / \ / \ / \ / \ H C E / \ / \ / \ / \ /\ A D G / \ / \ B F
Se vede ca in cazul nostru RN L = F, j = 3, LN j = C... Mai întâi, mutați nodul RN L = Fîn locul părintelui lor.
ROOT / \ / \ / \ / \ H / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ C E / \ / \ / \ / \ F A D G B(nod neîmperecheat)
Acum, în locul lui LN j = C Să formăm un nod fără frunză.
ROOT / \ / \ / \ / \ H E / \ / \ / \ / \ / \ / \ F A D G ? ? B(nod neîmperecheat) C(nod neîmperecheat)
Să atașăm două nepereche la nodul format: Bși C.
ROOT / \ / \ / \ / \ H / \ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ / \ / \ / \ / \ / \ / \ / \ / \ /\ /\ /\ E / \ / \ / \ / \ / \ / \ F A D G B C
Astfel, am limitat lungimea maximă a codului la 4. Este clar că prin modificarea lungimii codului am pierdut puțin în eficiență. Deci mesajul S, codificat cu un astfel de cod, va avea o dimensiune de 92 de biți, adică. Încă 3 biți peste Redundanța Minimă.
Este clar că cu cât limităm mai mult lungimea maximă a codului, cu atât codul va fi mai puțin eficient. Să aflăm cât de mult poți limita lungimea maximă a codului. Evident, nu mai scurt decât puțin.
Calculul Codurilor Canonice
După cum am observat deja de multe ori, lungimile codurilor sunt suficiente pentru a genera codurile în sine. Vă vom arăta cum se poate face acest lucru. Să presupunem că am calculat deja lungimile codurilor și am numărat câte coduri din fiecare lungime avem. Fie L lungimea maximă a codului și T i numărul de coduri de lungime i.
Se calculează S i - valoarea inițială a codului lungimii i, pentru tot i din
S L = 0 (întotdeauna)
S L-1 = (S L + T L) >> 1
S L-2 = (S L-1 + T L-1) >> 1
...
S 1 = 1 (întotdeauna)
Pentru exemplul nostru, L = 5, T 1 .. 5 = (1, 0, 2, 3, 2).
S 5 = 00000 bin = 0 dec
S 4 = (S 5 = 0 + T 5 = 2) >> 1 = (00010 bin >> 1) = 0001 bin = 1 dec
S 3 = (S 4 = 1 + T 4 = 3) >> 1 = (0100 bin >> 1) = 010 bin = 2 dec
S 2 = (S 3 = 2 + T 3 = 2) >> 1 = (100 bin >> 1) = 10 bin = 2 dec
S 1 = (S 2 = 2 + T 2 = 0) >> 1 = (10 bin >> 1) = 1 bin = 1 dec
Se poate observa că S 5, S 4, S 3, S 1 sunt exact codurile de caractere B, A, C, H... Aceste simboluri sunt unite de faptul că toate vin pe primul loc, fiecare la nivelul său. Cu alte cuvinte, am găsit valoarea inițială a codului pentru fiecare lungime (sau nivel).
Acum să atribuim coduri restului simbolurilor. Codul primului caracter la nivelul i este S i, al doilea S i + 1, al treilea S i + 2 etc.
Să scriem codurile rămase pentru exemplul nostru:
| B= S 5 = 00000 bin | A= S 4 = 0001 bin | C= S 3 = 010 bin | H= S 1 = 1 bin |
| F= S 5 + 1 = 00001 bin | D= S 4 + 1 = 0010 bin | E= S 3 + 1 = 011 bin | |
| G= S 4 + 2 = 0011 bin |
Se poate observa că am primit exact aceleași coduri ca și cum am fi construit în mod explicit arborele canonic Huffman.
Trecerea unui arbore de cod
Pentru ca mesajul codificat să fie decodat, decodorul trebuie să aibă același arbore de cod (într-o formă sau alta) care a fost folosit pentru codificare. Prin urmare, împreună cu datele codificate, suntem forțați să salvăm arborele de cod corespunzător. Este clar că cu cât este mai compact, cu atât mai bine.
Există mai multe modalități de a rezolva această problemă. Cea mai evidentă soluție este să stocați arborele în mod explicit (adică ca un set ordonat de noduri și pointeri de un fel sau altul). Acesta este poate cel mai risipitor și ineficient mod. În practică, nu este folosit.
Poate fi salvată o listă de frecvențe simbol (adică dicționar de frecvență). Cu ajutorul său, decodorul poate reconstrui cu ușurință arborele de cod. Deși această metodă este mai puțin risipitoare decât cea anterioară, nu este cea mai bună.
În cele din urmă, poate fi folosită una dintre proprietățile codurilor canonice. După cum sa menționat mai devreme, codurile canonice sunt complet determinate de lungimile lor. Cu alte cuvinte, tot ce are nevoie decodorul este o listă de lungimi de cod de caractere. Având în vedere că, în medie, lungimea unui cod pentru un alfabet cu N caractere poate fi codificată în [(log 2 (log 2 N))] biți, obținem un algoritm foarte eficient. Ne vom opri asupra ei mai detaliat.
Să presupunem că dimensiunea alfabetului este N = 256 și comprimăm un fișier text simplu (ASCII). Cel mai probabil nu vom găsi toate N caracterele alfabetului nostru într-un astfel de fișier. Să setăm apoi lungimea codului caracterelor lipsă egală cu zero. În acest caz, lista salvată de lungimi de cod va conține un număr suficient de mare de zerouri (lungimi de cod ale caracterelor lipsă) grupate împreună. Fiecare astfel de grup poate fi comprimat folosind așa-numita codificare de grup - RLE (Run - Length - Encoding). Acest algoritm este extrem de simplu. În loc de o secvență de M elemente identice într-un rând, vom salva primul element din această secvență și numărul repetărilor sale, adică. (M-1). Exemplu: RLE ("AAAABBCDDDDDDD") = A3 B2 C0 D6.
Mai mult, această metodă poate fi oarecum extinsă. Putem aplica algoritmul RLE nu numai grupurilor de lungimi zero, ci și tuturor celorlalți. Acest mod de a trece un arbore de cod este comun și este folosit în majoritatea implementărilor moderne.
Implementare: SHCODEC
Anexă: biografia lui D. Huffman
 |
David Huffman s-a născut în 1925 în Ohio, SUA. Huffman și-a luat licența în Inginerie Electrică de la Ohio State University la vârsta de 18 ani. Apoi a servit în armată ca ofițer de sprijin radar pe un distrugător care a ajutat la dezamorsarea minelor în apele japoneze și chineze după al Doilea Război Mondial. Ulterior, a primit un master de la Universitatea Ohio și un doctorat de la Massachusetts Institute of Technology (MIT). Deși Huffman este cel mai bine cunoscut pentru dezvoltarea unei metode de construire a codurilor minim redundante, el a adus, de asemenea, contribuții importante în multe alte domenii (mai ales în electronică). A fost de mult timp șef al Departamentului de Informatică de la MIT. În 1974, deja profesor emerit, a demisionat. Huffman a primit o serie de premii valoroase. 1999 - Medalia Richard W. Hamming de la Institutul de Ingineri Electrici și Electronici (IEEE) pentru contribuții excepționale la teoria informației, Medalia Louis E. Levy de la Institutul Franklin pentru teza sa de doctorat privind circuitele secvențiale, Premiul W. Wallace McDowell, IEEE Computer Society Award, IEEE Gold Jubilee Technology Innovation Award în 1998. În octombrie 1999, la vârsta de 74 de ani, David Huffman a murit de cancer. |
