Codificare Huffman

Codificarea Huffman este un algoritm de compresie a datelor fără pierderi . Codificarea Huffman utilizează cod de lungime variabilă pentru a reprezenta un simbol sursă (de exemplu, un caracter dintr-un fișier). Codul este determinat dintr-o estimare a probabilităților de apariție a simbolurilor sursă, un cod scurt fiind asociat cu cele mai frecvente simboluri sursă.

Un cod Huffman este optim în sensul celei mai scurte lungimi pentru codificarea simbolurilor și o distribuție de probabilitate cunoscută. Metode mai complexe care realizează o modelare probabilistică a sursei fac posibilă obținerea unor rapoarte de compresie mai bune.

A fost inventat de David Albert Huffman și publicat în 1952.

Principiu

Principiul codificării Huffman se bazează pe crearea unei structuri de copac formate din noduri.

Să presupunem că propoziția care trebuie codificată este „ acesta este un exemplu de copac huffman ”. În primul rând, căutăm numărul de apariții al fiecărui personaj. În exemplul anterior, propoziția conține de 2 ori caracterul h și 7 spații. Fiecare personaj constituie una dintre frunzele arborelui căruia îi asociem o greutate egală cu numărul său de apariții.

Arborele este creat în felul următor, asociem de fiecare dată cele două noduri cu cea mai mică greutate, pentru a da un nou nod a cărui greutate este echivalentă cu suma greutăților copiilor săi. Reiterăm acest proces până când mai avem un singur nod: rădăcina. Apoi, de exemplu, codul 0 este asociat cu fiecare ramură care rulează spre stânga și codul 1 spre dreapta.

Pentru a obține codul binar al fiecărui caracter, întoarcem arborele de la rădăcină la frunze adăugând de fiecare dată la cod un 0 sau un 1 în funcție de ramura urmată. Propoziția „ acesta este un exemplu de copac huffman ” este apoi codificată pe 135 de biți în loc de 288 de biți (dacă codarea inițială a caracterelor este de 8 biți). Este necesar să porniți de la rădăcină pentru a obține codurile binare, deoarece în caz contrar, când dezarhivați, pornirea de la frunze poate provoca confuzie la decodare.

Pentru a codifica „ Wikipedia ”, obținem deci în binar: 101 11 011 11 100 010 001 11 000, sau 24 de biți în loc de 63 (9 caractere x 7 biți per caracter) folosind coduri ASCII (7 biți).

Diferite metode de construire a copacului

Există trei variante ale algoritmului lui Huffman, fiecare dintre ele definind o metodă de creare a arborelui:

static: fiecare octet are un cod predefinit de software. Arborele nu trebuie să fie transmis, dar comprimarea se poate face numai pe un singur tip de fișier (de exemplu: un text în franceză, unde frecvențele de apariție ale „e” sunt enorme; prin urmare, aceasta va avea o foarte scurtă cod, care amintește de alfabetul Morse );
semi-adaptiv: fișierul este citit mai întâi, astfel încât să se calculeze aparițiile fiecărui octet, apoi arborele este construit din greutățile fiecărui octet. Acest arbore va rămâne același până la sfârșitul compresiei. Această compresie va determina un câștig de biți mai mare sau egal cu codarea statică Huffman, dar va fi necesar, pentru decompresie, să transmită arborele, care va anula în general câștigul obținut;
adaptivă: aceasta este metoda care a priori oferă cele mai bune rate de compresie, deoarece folosește un arbore cunoscut (și, prin urmare, nu este transmis), care va fi apoi modificat dinamic pe măsură ce fluxul este comprimat conform simbolurilor întâlnite anterior. Cu toate acestea, această metodă reprezintă marele dezavantaj al necesității de a modifica arborele des, ceea ce implică un timp de execuție mai lung. Pe de altă parte, compresia este întotdeauna optimă și nu este necesar ca fișierul să fie cunoscut înainte de comprimare. În special, algoritmul este capabil să lucreze la fluxuri de date ( streaming ), deoarece nu este necesar să cunoaștem simbolurile viitoare.

Proprietăți

Un cod Huffman este cod sursă . Pentru o sursă , reprezentată de o variabilă aleatorie , de distribuție a probabilității , așteptarea lungimii unui cod este dată de $S$ $X$ $p$ $VS$

L (C) = \ sum_ {x \ in \ Omega} p (x) \ cdot l (x)

Unde este lungimea cuvântului de cod, codul asociat simbolului sursă și este setul de simboluri sursă. $l (x)$ $C (x)$ $X$ $\Omega$

Un cod Huffman este un cod prefix cu lungime variabilă . Este optim, în sensul celei mai scurte lungimi, pentru codarea simbolurilor . Adică, pentru un cod Huffman și pentru orice cod unic decodabil , atunci: $C ^ *$ $VS$

L (C ^ *) \ le L (C)

Limitări ale codificării Huffman

Putem arăta că pentru o sursă , entropia Shannon lungimea medie a unui cuvânt de cod obținut prin codificarea Huffman satisface: $X$ $H (X)$ $L$

H (X) \ le L <H (X) +1

Această relație arată că codificarea Huffman se apropie de entropia sursei și adică de codul optim, dar acest lucru se poate dovedi de fapt destul de neinteresant în cazul în care entropia sursei este puternică și unde o supratensiune de 1 bit devine semnificativ. În plus, codificarea Huffman necesită utilizarea unui număr întreg de biți pentru un simbol sursă, care se poate dovedi ineficient.

O soluție la această problemă este de a lucra pe blocuri de simboluri. Arătăm apoi că ne putem apropia de entropie: $nu$

H (X) \ le L <H (X) + \ frac {1} {n}

dar procesul de estimare a probabilităților devine mai complex și mai costisitor.

Mai mult, codificarea Huffman nu este adecvată în cazul unei surse ale cărei proprietăți statistice se modifică în timp, deoarece probabilitățile simbolurilor se schimbă și codificarea devine inadecvată. Soluția care constă în reestimarea probabilităților simbolului la fiecare iterație este impracticabilă din cauza complexității sale de timp. Tehnica devine apoi codare Huffman adaptivă : pentru fiecare simbol nou, tabelul de frecvențe este actualizat și arborele de codificare modificat, dacă este necesar. Decompresorul face același lucru pentru aceleași cauze ... rămâne sincronizat cu ceea ce făcuse compresorul.

În practică, atunci când vrem să abordăm entropia, preferăm o codare aritmetică care este optimă la nivelul de biți.

Metode mai complexe care realizează o modelare probabilistică a sursei și care profită de această redundanță suplimentară fac posibilă îmbunătățirea performanțelor de compresie ale acestui algoritm (vezi LZ77 , predicție prin recunoaștere parțială , ponderarea contextelor ).

Cod canonical

Pentru ca același set de simboluri să fie codificat, pot fi obținute mai multe coduri Huffman diferite.

Este posibil să transformați un cod Huffman într-un cod canonic Huffman care este unic pentru un set dat de simboluri de intrare. Principiul este de a ordona inițial simbolurile în ordine lexicală.

Notă: între două simboluri S1 și S2 care, într-un cod specific Huffman, sunt codificate de aceeași lungime, sunt întotdeauna codate aceeași lungime în codul Huffman canonic. În cazul în care două simboluri au aceeași probabilitate și două lungimi de cod diferite, este posibil ca trecerea de la un cod Huffman la un cod canonic Huffman să modifice lungimea acestor coduri, pentru a garanta atribuirea codului. primul simbol în ordine lexicografică.

Utilizări

Codificarea Huffman se bazează numai pe frecvența relativă a simbolurilor de intrare (șiruri de biți) fără distincție pentru originea lor (imagini, videoclipuri, sunete etc. ). Acesta este motivul pentru care este utilizat în general în a doua etapă de compresie, odată ce redundanța specifică media a fost demonstrată de alți algoritmi. Ne gândim în special la compresia JPEG pentru imagini , MPEG pentru videoclipuri și MP3 pentru sunet , care pot elimina elementele de prisos imperceptibile pentru oameni. Vorbim apoi de compresie neconservatoare (cu pierderi).

Alți așa-numiți algoritmi de compresie conservatori (fără pierderi), cum ar fi cei utilizați pentru compresia de fișiere, folosesc și Huffman pentru a comprima dicționarul rezultat. De exemplu, LZH ( Lha ) și deflate ( ZIP , gzip , PNG ) combină un algoritm de compresie a dicționarului ( LZ77 ) și codificarea entropiei Huffman.

Istorie

Codificarea a fost inventată de David Albert Huffman , în timpul tezei sale de doctorat la MIT . Algoritmul a fost publicat în 1952 în articolul O metodă pentru construirea codurilor de redundanță minimă , în Proceedings of the Institute of Radio Engineers .

Prima companie Macintosh Apple a folosit un Huffman bazat pe cod pentru reprezentarea textelor: cele mai frecvente 15 caractere ale unei limbi au fost codate pe 4 biți, iar cea de-a 16- a configurație a servit ca prefix la codarea altor octeți unici (care realizat uneori 4 biți, alteori 12 biți pe caracter vezi UTF-8 ). S-a găsit că această metodă simplă economisește 30% spațiu în medie cu textul într-un moment în care RAM era încă o componentă scumpă.

Vezi și tu

Articole similare

Codificarea entropiei
Codificare Shannon-Fano , similară cu codarea Huffman, dar în care metoda de calcul a codurilor diferă și poate duce la un arbore de codificare diferit.
Comprimarea datelor

linkuri externe

Bibliografie

(ro) DA Huffman, „ O metodă pentru construirea codurilor de redundanță minimă ” (PDF), Proceedings of the IRE,Septembrie 1952, pp 1098-1102
(ro) Thomas M. Cover, Joy A. Thomas, Elements of Information Theory , Wiley-Interscience,2006( ISBN 978-0-471-24195-9 ) [ detaliu ediții ]

Note și referințe

(fr) Acest articol este preluat parțial sau în totalitate din articolul din Wikipedia engleză intitulat „ Huffman coding ” ( vezi lista autorilor ) .

Mark Nelson ( tradus Soulard Hervé), Compresia datelor: text, imagini, sunete , Franța, Dunod ,1993, 420 p. ( ISBN 2-10-001681-4 ) , pagina 65.
Copertă, Thomas (2006) , p. 123-127.
DA Huffman, O metodă pentru construirea codurilor de redundanță minimă , Proceedings of the IRE, septembrie 1952, pp. 1098-1102.