Codul Huffman

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită la 8 ianuarie 2019; verificările necesită 27 de modificări .

Algoritmul Huffman este un algoritm lacom pentru codificarea optimă a prefixelor unui alfabet cu redundanță minimă . A fost dezvoltat în 1952 de studentul absolvent al MIT , David Huffman , în timp ce scria lucrarea sa de curs . Utilizat în prezent în multe programe de compresie a datelor .

Spre deosebire de algoritmul Shannon-Fano , algoritmul Huffman rămâne întotdeauna optim pentru alfabetele secundare m 2 cu mai mult de două caractere.

Această metodă de codificare constă din doi pași principali:

Construirea unui arbore de cod optim.
Construirea unei mapări cod-simbol bazată pe arborele construit.

Algoritmul clasic Huffman

Ideea algoritmului este următoarea: cunoscând probabilitățile de apariție a caracterelor în mesaj, este posibil să se descrie procedura de construire a codurilor de lungime variabilă constând dintr-un număr întreg de biți. Este mai probabil ca caracterelor să li se atribuie coduri mai scurte. Codurile Huffman au proprietatea de prefix (adică niciun cuvânt de cod nu este un prefix al altuia), care le permite să fie decodificate fără ambiguitate.

Algoritmul clasic Huffman primește un tabel cu frecvențele caracterelor din mesaj ca intrare. În plus, pe baza acestui tabel, este construit un arbore de codificare Huffman (arbore H). [unu]

Caracterele alfabetului de intrare formează o listă de noduri libere. Fiecare frunză are o pondere, care poate fi egală fie cu probabilitatea, fie cu numărul de apariții ale caracterului din mesajul care urmează să fie comprimat.
Sunt selectate două noduri de arbore libere cu cele mai mici greutăți.
Părintele lor este creat cu o greutate egală cu greutatea lor totală.
Părintele este adăugat la lista de noduri libere, iar cei doi copii ai săi sunt eliminați din această listă.
Un arc care iese de la părinte este setat la bitul 1, celălalt la bitul 0. Valorile biților ramurilor care provin de la rădăcină nu depind de greutățile copiilor.
Pașii începând de la al doilea se repetă până când un singur nod liber rămâne în lista nodurilor libere. Va fi considerată rădăcina copacului.

Să presupunem că avem următorul tabel de frecvențe absolute:

Simbol	DAR	B	LA	G	D
Frecvența absolută	cincisprezece	7	6	6	5

Acest proces poate fi gândit ca construirea unui arbore a cărui rădăcină este simbolul cu suma probabilităților simbolurilor combinate obținute prin combinarea simbolurilor din ultimul pas, n 0 descendenți ai săi sunt simbolurile din pasul precedent și așa mai departe .

Pentru a determina codul pentru fiecare dintre caracterele incluse în mesaj, trebuie să trecem de la frunza arborelui corespunzătoare caracterului curent până la rădăcina acestuia, acumulând biți pe măsură ce ne deplasăm prin ramurile arborelui (prima ramură din cale). corespunde bitului cel mai puțin semnificativ). Secvența de biți astfel obținută este codul caracterului dat, scris în ordine inversă.

Pentru un anumit tabel de caractere, codurile Huffman vor arăta astfel.

Simbol	DAR	B	LA	G	D
Codul	0	100	101	110	111

Deoarece niciunul dintre codurile primite nu este un prefix al celuilalt, ele pot fi decodificate fără ambiguitate atunci când le citesc din flux. În plus, simbolul cel mai frecvent al mesajului A este codificat cu cel mai mic număr de biți, iar cel mai rar simbol D este codificat cu cel mai mare.

În acest caz, lungimea totală a mesajului, constând din simbolurile date în tabel, va fi de 87 de biți (o medie de 2,2308 biți per simbol). Folosind codificarea uniformă, lungimea totală a mesajului ar fi de 117 biți (exact 3 biți pe caracter). Rețineți că entropia unei surse care generează independent simboluri cu frecvențele specificate este de ~2,1858 biți pe simbol, adică redundanța codului Huffman construit pentru o astfel de sursă, înțeleasă ca diferența dintre numărul mediu de biți pe simbol și entropia, este mai mică de 0,05 biți pe un simbol.

Algoritmul clasic Huffman are o serie de dezavantaje semnificative. În primul rând, pentru a recupera conținutul mesajului comprimat, decodorul trebuie să cunoască tabelul de frecvență utilizat de encoder. Prin urmare, lungimea mesajului comprimat este mărită cu lungimea tabelului de frecvență care trebuie trimis înaintea datelor, ceea ce poate anula orice efort de comprimare a mesajului. În plus, necesitatea de a avea statistici complete de frecvență înainte de a începe codificarea efectivă necesită două treceri prin mesaj: una pentru construirea modelului de mesaj (tabel de frecvență și H-tree), cealaltă pentru codificarea efectivă. În al doilea rând, redundanța de codare dispare doar în acele cazuri în care probabilitățile simbolurilor codificate sunt puteri inverse de 2. În al treilea rând, pentru o sursă cu entropie care nu depășește 1 (de exemplu, pentru o sursă binară), aplicarea directă a codului Huffman. este inutil.

Compresie adaptivă

Compresia adaptivă vă permite să nu transferați modelul de mesaj împreună cu acesta și să vă limitați la o singură trecere prin mesaj atât în timpul codificării, cât și al decodării.

În crearea unui algoritm de codare adaptiv Huffman, cele mai mari dificultăți apar la dezvoltarea unei proceduri de actualizare a modelului cu următorul caracter. Teoretic, s-ar putea insera pur și simplu construcția completă a arborelui de codificare Huffman în cadrul acestei proceduri, totuși, un astfel de algoritm de compresie ar avea performanțe inacceptabil de scăzute, deoarece construirea unui arbore H este prea multă muncă și este nerezonabil să o faci atunci când procesează. fiecare personaj. Din fericire, există o modalitate de a modifica un arbore H deja existent pentru a reflecta procesarea unui nou caracter. Cei mai cunoscuți algoritmi de reconstrucție sunt algoritmul Voller-Gallagher-Knuth (FGK) și algoritmul Witter.

Toți algoritmii pentru reconstruirea arborelui la citirea următorului caracter includ două operații:

Primul este de a crește greutatea nodurilor copacilor. În primul rând, creștem cu una greutatea foii corespunzătoare caracterului citit. Apoi creștem greutatea părintelui pentru a o aduce în concordanță cu noile greutăți ale copiilor. Acest proces continuă până când ajungem la rădăcina copacului. Numărul mediu de incremente de greutate este egal cu numărul mediu de biți necesari pentru a codifica un caracter.

A doua operație - permutarea nodurilor arborelui - este necesară atunci când o creștere a greutății unui nod duce la o încălcare a proprietății de ordonare, adică atunci când greutatea crescută a nodului a devenit mai mare decât greutatea următorului nod în Ordin. Dacă continuăm să procesăm creșterea în greutate, îndreptându-ne către rădăcina copacului, atunci copacul nu va mai fi un copac Huffman.

Pentru a păstra ordinea arborelui de codare, algoritmul funcționează după cum urmează. Fie ca noua greutate crescută a nodului să fie W+1. Apoi începem să ne mișcăm de-a lungul listei în direcția creșterii greutății până când găsim ultimul nod cu greutatea W. Să rearanjam nodurile curente și cele găsite între ele în listă, restabilind astfel ordinea în arbore (în acest caz, părinții). ale fiecăruia dintre noduri se vor schimba de asemenea). Aceasta finalizează operațiunea de schimb.

După permutare, operația de creștere a greutății nodurilor continuă în continuare. Următorul nod care urmează să fie crescut în greutate de către algoritm este noul părinte al nodului a cărui creștere în greutate a cauzat permutarea.

Codurile canonice Huffman

Problema cu algoritmul convențional de compresie Huffman este non-determinismul. Pentru secvențe similare, pot apărea arbori diferiți, iar un arbore fără o serializare adecvată poate corespunde unor secvențe diferite. Pentru a evita utilizarea codurilor canonice Huffman.

Acest algoritm nu construiește un arbore Huffman [2] .

Constă din două etape:

Calcularea lungimii codului pentru un caracter
Alcătuirea codului.

Calculul lungimii

Calculați frecvența pentru fiecare caracter
Sortați-le în ordine lexicografică.
Să scriem frecvența fiecărei litere în matrice.
În stânga, atribuim o matrice de aceeași lungime, dar cu numere de serie din matricea din dreapta. Matricea din stânga este obținută ca o listă de pointeri către elementele din partea dreaptă.
În partea stângă facem o piramidă care nu crește . Dar heap-ul nu va fi după valoarea elementelor de matrice, ci de valoarea elementului de matrice referit.
Elementul din stânga indică caracterul din matricea din dreapta cu frecvența cea mai joasă. Poate fi eliminat astfel:
1. Nu atingeți jumătatea dreaptă
2. Înlocuim primul element al tabloului cu elementul din dreapta al matricei din stânga, se presupune că deplasăm limita de separare.
3. Verificăm condițiile pentru corectitudinea piramidei, dacă ceva nu este în regulă, atunci trebuie să repetăm „hipizarea”.
4. Primul element din partea stângă a matricei este eliminat și elementul eliminat anterior este combinat. Suma frecvențelor lor este scrisă la limita dintre matricea din stânga și din dreapta.
5. În locul elementului șters din partea stângă, se scrie indexul matricei acolo unde a fost adăugată suma frecvențelor la ultimul pas.
6. Datorită faptului că două elemente au fost combinate, este necesar să se schimbe valorile acestor elemente ale matricei cu o referință la părintele în care au fost plasate.
Repetăm, nu va mai rămâne 1 element în grămada.
În partea dreaptă a matricei, avem link-uri către elemente care combină 2 caractere. Prin urmare, trecem prin matrice prin legături, incrementând nivelul de imersiune.
Numărul de clicuri pe linkuri va fi lungimea codului Huffman.

Compilarea codului

Aranjați elementele în ordine lexicografică.
Să facem un tabel format din blocuri, începând cu cea mai mare lungime de cod. Fiecare bloc va conține elemente cu aceeași lungime de cod.
Primul caracter al tabelului este codificat cu zerouri.
În fiecare bloc, caracterele vor fi în ordine lexicografică.
Codurile din bloc vor fi binare și diferă cu 1.
Când treceți la următorul bloc, biții de cod ai celui mai recent caracter sunt tăiați și se adaugă 1.

Model Bigram

Există o variantă a algoritmului Huffman care utilizează context. În acest caz, dimensiunea contextului este egală cu unul (bigramă - două caractere, trigramă - trei și așa mai departe). Aceasta este o metodă de a construi un cod de prefix pentru modele de ordin superior, nu mai este o sursă fără memorie. Folosește rezultatul operației (operației anterioare) pe litera anterioară împreună cu litera curentă. Este construit pe baza unui lanț Markov cu adâncime de dependență . [3] $r=1$

Algoritm

Un tabel este construit sub forma unui pătrat - distribuția probabilității pe bigrame. Se calculează imediat schema de pornire, cu ajutorul căreia va fi codificată doar prima literă. Rândurile din tabel, de exemplu, sunt literele anterioare, iar coloanele sunt cele curente.
Probabilitățile sunt calculate pentru arborele de cod pentru contexte.
Contextele de lungime sunt folosite pentru a construi arborii de cod rămași, cu ajutorul cărora toate celelalte caractere (cu excepția primului) vor fi codificate. $r=1$
Se realizează codificarea, primul caracter este codificat conform schemei de pornire, toate caracterele ulterioare sunt codificate pe baza arborilor de cod pentru contexte (caracterul anterior).

Decodarea se realizează într-un mod similar: din schema de cod de pornire, obținem primul context, apoi mergem la arborele de cod corespunzător. Mai mult, decodorul are nevoie de un tabel de distribuție a probabilității.

Exemplu

Să presupunem că mesajul care trebuie codificat este „abcabcabc” . Cunoaștem dinainte tabelul de frecvență a simbolurilor (pe baza altor date, cum ar fi statisticile dicționarului).

	A	b	c	Sumă
A	${\tfrac {3}{16}}$	${\tfrac {1}{16}}$	${\tfrac {1}{16}}$	${\tfrac {5}{16}}$
b	${\tfrac {1}{8))$	${\tfrac {1}{16}}$	${\tfrac {1}{8))$	${\tfrac {5}{16}}$
c	${\tfrac {1}{8))$	${\tfrac {1}{8))$	${\tfrac {1}{8))$	${\tfrac {6}{16}}$

Avem o schemă de pornire: . Sortați în ordine descrescătoare: și construiți un arbore de cod Huffman. $(a={\tfrac {5}{16}},b={\tfrac {5}{16}},c={\tfrac {6}{16}})$ $(c={\tfrac {6}{16}},a={\tfrac {5}{16}},b={\tfrac {5}{16}})$

Pentru contextul " a " avem:

$p(a/a)=p(a,a)/p(a)={\tfrac {3}{16}}\div {\tfrac {5}{16}}={\tfrac {3} {5}}$ ,
$p(b/a)=p(b,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 {5}}$ ,
$p(c/a)=p(c,a)/p(a)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1 {5}}$ .

Pentru contextul „ b ” avem:

$p(a/b)=p(a,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2 {5}}$ ,
$p(b/b)=p(b,b)/p(b)={\tfrac {1}{16}}\div {\tfrac {5}{16}}={\tfrac {1} {5}}$ ,
$p(c/b)=p(c,b)/p(b)={\tfrac {1}{8}}\div {\tfrac {5}{16}}={\tfrac {2} {5}}$ .

Pentru contextul „ c ” avem:

$p(a/c)=p(a,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 {3}}$ ,
$p(b/c)=p(b,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 {3}}$ ,
$p(c/c)=p(c,c)/p(c)={\tfrac {1}{8}}\div {\tfrac {6}{16}}={\tfrac {1 {3}}$ .

Notă: aici p(x, y) nu este egal cu p(y, x) .

Construim arbori de cod pentru fiecare context. Efectuăm codificare și avem un mesaj codificat: (00, 10, 01, 11, 10, 01, 11, 10, 01).

00 - din codul literei "a" pentru schema de pornire,
10 - din codul literei „b” pentru contextul „a” ,
01 - din codul literei "c" pentru contextul "b" ,
11 - din codul literei „a” pentru contextul „c” .

Overflow

Pe măsură ce algoritmul de compresie rulează, greutatea nodurilor din arborele de codificare Huffman crește constant. Prima problemă apare atunci când greutatea rădăcinii copacului începe să depășească capacitatea celulei în care este depozitat. De obicei, aceasta este o valoare de 16 biți și, prin urmare, nu poate fi mai mare de 65535. O a doua problemă care merită mai multă atenție poate apărea mult mai devreme, când dimensiunea celui mai lung cod Huffman depășește capacitatea celulei care este utilizată pentru a-l transmite. fluxul de ieșire. Decodorului nu îi pasă cât de mult decodifică codul, deoarece se mișcă de sus în jos de-a lungul arborelui de codificare, alegând câte un bit din fluxul de intrare. Codificatorul, pe de altă parte, trebuie să înceapă de la frunza copacului și să se deplaseze până la rădăcină, colectând biții de transmis. Acest lucru se întâmplă de obicei cu o variabilă de tip întreg, iar când lungimea codului Huffman depășește dimensiunea tipului întreg în biți, are loc o depășire.

Se poate dovedi că codul Huffman pentru mesajele cu același alfabet de intrare va avea lungimea maximă dacă frecvențele simbolurilor formează șirul Fibonacci . Un mesaj cu frecvențe simboluri egale cu numerele Fibonacci până la Fib(18) este o modalitate excelentă de a testa modul în care funcționează un program de compresie Huffman.

Scalarea greutăților nodurilor unui arbore Huffman

Ținând cont de cele de mai sus, algoritmul de actualizare a arborelui Huffman ar trebui modificat în felul următor: pe măsură ce greutatea crește, trebuie verificat pentru atingerea maximului permis. Dacă am atins maximul, atunci trebuie să „scalăm” greutatea, de obicei, împărțind greutatea frunzelor la un număr întreg, de exemplu, 2, și apoi recalculând greutatea tuturor celorlalte noduri.

Cu toate acestea, la împărțirea greutății la jumătate, există o problemă asociată cu faptul că, după efectuarea acestei operațiuni, copacul își poate schimba forma. Acest lucru se explică prin faptul că la împărțirea numerelor întregi, partea fracțională este aruncată.

Un arbore Huffman organizat corespunzător după scalare poate avea o formă semnificativ diferită de cea originală. Acest lucru se datorează faptului că scalarea are ca rezultat o pierdere a preciziei statisticilor. Dar odată cu colectarea de noi statistici, consecințele acestor „greșeli” practic dispar. Scalarea greutății este o operațiune destul de costisitoare, deoarece duce la necesitatea reconstruirii întregului arbore de codare. Dar, deoarece nevoia de el apare relativ rar, atunci o poți suporta.

Scaling Benefits

Scalarea greutății nodurilor arborelui la anumite intervale dă un rezultat neașteptat. Deși există o pierdere a preciziei statistice cu scalarea, testele arată că scalarea are ca rezultat o performanță de compresie mai bună decât dacă scalarea ar fi întârziată. Acest lucru poate fi explicat prin faptul că simbolurile actuale ale fluxului compresibil sunt mai „asemănătoare” cu predecesorii lor apropiați decât cu cele care au apărut mult mai devreme. Scalare are ca rezultat o scădere a influenței simbolurilor „vechi” asupra statisticilor și o creștere a influenței simbolurilor „recente” asupra acesteia. Acest lucru este foarte greu de cuantificat, dar, în principiu, scalarea are un efect pozitiv asupra gradului de compresie a informațiilor. Experimentele cu scalarea în diferite puncte ale procesului de comprimare arată că gradul de comprimare depinde puternic de momentul scalării greutății, dar nu există o regulă pentru alegerea momentului optim de scalare pentru un program axat pe comprimarea oricărui tip de informație.

Aplicație

Codarea Huffman este utilizată pe scară largă în compresia datelor, inclusiv compresia foto și video ( JPEG , MPEG ), în arhivele populare ( PKZIP , LZH etc.), în protocoalele de transfer de date HTTP ( Deflate ), MNP5 și MNP7 și altele.

Modificări

În 2013, a fost propusă o modificare a algoritmului Huffman, care permite codificarea caracterelor cu un număr fracționar de biți - ANS [4] [5] . Pe baza acestei modificări, algoritmii de compresie Zstandard (Zstd, Facebook, 2015—2016) [6] și LZFSE (Apple, OS X 10.11, iOS 9, 2016) [7] [8] [9] [10] sunt implementate .

Note

↑ D. Mastryukov. Monitor 7-8.93 Arhivat 17 mai 2018 la Wayback Machine
↑ Algoritmul este detaliat cu exemple în Managing Gigabytes de Witten, Moffat, Bell la pagina 68.
↑ Shmuel T. Klein și Dana Shapira. Codarea Huffman cu frecvențe nesortate (2008). Data accesului: 2 ianuarie 2016. Arhivat din original pe 4 martie 2016. (nedefinit)
↑ Copie arhivată . Preluat la 2 ianuarie 2016. Arhivat din original la 5 martie 2016. (nedefinit)
↑ Copie arhivată . Preluat la 2 ianuarie 2016. Arhivat din original la 11 septembrie 2016. (nedefinit)
↑ Facebook a publicat implementarea algoritmului de compresie Zstandard 1.0 Arhivat 2 septembrie 2016 pe Wayback Machine / Opennet.ru, 09.01.2016
↑ Apple a deschis implementarea algoritmului de compresie fără pierderi LZFSE
↑ Apple deschide noul său algoritm de compresie LZFSE . Consultat la 1 septembrie 2016. Arhivat din original pe 11 septembrie 2016. (nedefinit)
↑ Comprimarea datelor
↑ GitHub - lzfse/lzfse: bibliotecă de compresie LZFSE și instrument de linie de comandă . Preluat la 1 septembrie 2016. Arhivat din original la 28 noiembrie 2020. (nedefinit)

Literatură

Thomas H. Cormen, Charles I. Leiserson, Ronald L. Rivest, Clifford Stein. Algoritmi: constructie si analiza = Introduction to Algorithms. - Ed. a II-a. — M .: Williams , 2006. — 1296 p. — ISBN 0-07-013151-1 .
D. Salomon. Comprimarea datelor, imaginilor și sunetului. - M . : Technosfera, 2004. - 368 p. - 3000 de exemplare. — ISBN 5-94836-027-X .
Ian H. Witten, Alistair Moffat, Timothy C. Bell. Gestionarea gigaocteților: comprimarea și indexarea documentelor și imaginilor. - 1999. - 551 p. — ISBN 1558605703 .
Levitin A. V. Capitolul 9. Greedy Methods: The Huffman Algorithm // Algoritmi. Introducere în dezvoltare și analiză - M . : Williams , 2006. - S. 392-398. — 576 p. — ISBN 978-5-8459-0987-9

Markov A. A. Introducere în teoria codificării. — M .: Nauka, 1982. — 192 p.

Link -uri

Metode de compresie

Teorie

informație	propriu Reciproc Entropie Entropia condiționată Complexitate Redundanţă
Unități	Pic Nat Ciuguli Hartley Formula Hartley

Fara pierderi

Compresie entropică	Sisteme numerice asimetrice Algoritmul Huffman Algoritmul adaptiv Huffman Algoritmul Shannon-Fano algoritmul lui Shannon Codare aritmetică ( Interval ) Codurile Golomb Delta Cod universal Elias Fibonacci
Dicţionar Methods	RLE Dezumfla LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Alte	RLE CTW BWT MTF PPM DMC

Audio

Teorie	Convoluţie PCM Alianta Prelevarea de probe teorema lui Kotelnikov
Metode	LPC LAR LSP WLPC CELP ACELP O lege μ-legea ADPCM MDCT transformata Fourier Model psihoacustic
Alte	Compresor audio Compresia vorbirii Codarea benzii

Imagini

Termeni	spațiu de culoare Pixel Subeșantionarea de saturație Artefacte de compresie
Metode	RLE DPCM fractal wavelet EZW SPIHT LP PrEP PCL
Alte	Rata de biți Imagine de testare standard PSNR Cuantizarea

Video

Termeni	Caracteristicile video Cadru Tipuri de cadre Calitate video
Metode	Compensarea mișcării PrEP Cuantizarea wavelet
Alte	Codec video Teoria distorsiunii ratei CBR ABR VBR