Codificare Huffman

De la Wikipedia, enciclopedia liberă.
Salt la navigare Salt la căutare
Codificarea Huffman a sintagmei „acesta este un exemplu de copac huffman” cu reprezentare binară și index de frecvență a literelor.

În teoria informației , codificarea Huffman se referă la un algoritm de codificare a simbolurilor utilizat pentru compresia datelor, bazat pe principiul găsirii sistemului optim pentru codificarea șirurilor pe baza frecvenței relative a fiecărui caracter. A fost dezvoltat în 1952 de David A. Huffman , doctorand la MIT și publicat în O metodă pentru construirea codurilor de redundanță minimă .

Codificarea Huffman folosește o metodă specifică pentru a alege reprezentarea fiecărui simbol, rezultând un cod fără prefixe (adică unde niciun șir binar fără simbol este prefixul șirului binar al niciunui alt simbol) care exprimă caracterul cel mai frecvent în drumul cât mai scurt posibil. Codificarea Huffman s-a dovedit a fi cel mai eficient sistem de compresie de acest tip: nicio altă mapare a simbolurilor în șiruri binare nu poate produce un rezultat mai scurt dacă frecvențele reale ale simbolurilor se potrivesc cu cele utilizate pentru a crea codul.

Pentru un set de simboluri a căror cardinalitate este o putere de două și cu o distribuție probabilistică uniformă, codarea Huffman este echivalentă cu codarea blocului binar simplu.

Istorie

În 1951, David A. Huffman și un coleg de-al său la cursul MIT Information Theory au primit alegerea între o teză scrisă sau un examen. Profesorul, Robert M. Fano , a atribuit o teză privind problema găsirii celui mai eficient cod binar. Huffman, incapabil să demonstreze vreun cod care era cel mai eficient, s-a resemnat la ideea de a fi nevoit să studieze pentru examen atunci când a venit cu ideea de a folosi un arbore binar ordonat în frecvență, așa că a repede a dovedit că această metodă a fost cea mai eficientă.

O idee similară fusese folosită anterior în codificarea Shannon-Fano (creată de Claude Shannon , inventatorul teoriei informației și Fano, lectorul lui Huffman), dar Huffman și-a remediat cel mai mare neajuns construind un copac ascendent în locul unui descendent.

Tehnica de bază

Această tehnică funcționează prin crearea unui arbore binar de simboluri:

  1. Sortați simbolurile, într-o listă, pe baza numărului de apariții ale acestora.
  2. Repetați pașii următori până când lista conține un singur simbol:
    1. Luați din listă cele două simboluri cu cea mai mică frecvență de numărare. Creați un copac Huffman care are aceste două elemente ca „copii” și creați un nod „părinte”
    2. Alocați părinților suma numărului de frecvențe al copiilor și plasați-o în listă pentru a menține ordinea.
    3. Ștergeți copiii din listă.
  3. Atribuiți un cuvânt cod fiecărui element pe baza căii care începe de la rădăcină.

Caracteristici principale

Frecvențele utilizate pot fi generice în domeniul aplicației pe baza mediilor precomputate sau pot fi frecvențele găsite în textul care trebuie comprimat (această variantă necesită ca tabelul de frecvențe să fie înregistrat împreună cu textul comprimat; există mai multe implementări care adoptă trucuri pentru a înregistra eficient aceste tabele).

Codificarea Huffman este optimă atunci când probabilitatea fiecărui simbol de intrare este o putere negativă de două. Codificările fără prefixe tind să fie ineficiente pentru alfabetele mici, atunci când probabilitățile se încadrează adesea între puterile a două. Extinderea simbolurilor adiacente în „cuvinte” înainte de codificarea Huffman poate ajuta. Cazurile limitative ale codificării Huffman sunt legate de secvența Fibonacci .

Codificarea aritmetică produce câștiguri ușoare față de cea a lui Huffman, dar aceste câștiguri sunt convenabile numai dacă algoritmul pentru codarea aritmetică este optim, deoarece codificarea banală necesită o complexitate de calcul mai mare. În plus , această versiune naivă este acoperită de un brevet IBM în conceptele sale de bază. Cu toate acestea, aceste brevete nu sunt valabile în afara SUA , cel puțin până la aprobarea finală a brevetelor software din Europa .

Variații

Codificare Huffman adaptivă

O variație numită adaptivă calculează frecvențele dinamic pe baza celor mai recente frecvențe reale din șirul sursă, similar familiei de algoritmi LZ .

Algoritmul lui Huffman un șablon

Adesea, ponderile utilizate în implementările Huffman reprezintă probabilități numerice, dar algoritmul în sine nu necesită acest lucru: necesită doar un mod de a ordona ponderile și de a le adăuga. Codificarea „șablon” a lui Huffman permite utilizarea ponderilor nenumerice (costuri, frecvențe și așa mai departe).

Codul Huffman bazat pe nr

Algoritmul Huffman bazat pe n folosește alfabetul {0, 1, ..., n-1} pentru a codifica mesajul și a construi un arbore bazat pe n.

Codificare Huffman cu costuri inegale pe scrisoare

În problema standard de codare Huffman, este dat un set de cuvinte și pentru fiecare cuvânt o frecvență pozitivă. Scopul este de a codifica fiecare cuvânt „p” cu un cuvânt cod „c” într-un alfabet dat. Codificarea Huffman cu cost per literă inegal este o generalizare în care literele alfabetului de codare pot avea lungimi neuniforme. Scopul este de a minimiza media ponderată a lungimii cuvintelor cod.

Aplicații

Astăzi, codificarea Huffman este adesea utilizată ca o completare a altor metode de compresie: exemple sunt Deflate (algoritmul PKZIP și succesorii săi ZIP și WinRar ) și codecuri multimedia precum JPEG și MP3 .

Alte proiecte

linkuri externe

Inginerie Portal de inginerie : accesați intrările Wikipedia care se ocupă de inginerie