Definiția 1: Fie A = 1, a2 ,. , a> este o alfabet de n simboluri diferite, W = 1, w2 ,. , wn> este setul corespunzător de greutăți întregi pozitive. Apoi setul de coduri binare C = 1, c2 ,. , cn>, astfel încât:
(1) ci nu este un prefix pentru cj. pentru i ≠ j
(2) este minimal (| ci | lungimea codului este ci)
Se numește codul prefix redundant minim sau altfel codul Huffman.
1. Proprietatea (1) se numește proprietatea prefixului. Acesta permite codificarea în mod unic a codurilor de lungime variabilă.
2. Suma din proprietate (2) poate fi tratată ca mărimea datelor codificate în biți. În practică, acest lucru este foarte convenabil, deoarece Permite estimarea raportului de compresie fără a recurge direct la codificare.
3. În viitor, pentru a evita neînțelegerile, un cod este un șir de biți de o anumită lungime, iar sub codul minim redundant sau codul Huffman există o mulțime de coduri (șiruri de biți) care corespund anumitor simboluri și care posedă anumite proprietăți.
Se știe că pentru orice cod prefix binar există un anumit copac binar.
Definiția 2: Un arbore binar care corespunde codului Huffman va fi numit arbore Huffman.
Problema construirii codului Huffman este echivalentă cu problema construirii copacului corespunzător. Dăm schema generală pentru construirea unui copac Huffman:
literele sunt aranjate în ordinea descrescătoare a probabilităților lor. Adăugați probabilitățile ultimelor două litere, iar seria este rescrisă din nou luând în considerare noua probabilitate (sumă). Apoi repetați operația până când se dovedește 1. Litera inferioară este întotdeauna codată cu zero, iar litera superioară este întotdeauna zero.
Pentru construirea combinațiilor de coduri, este construit un arbore de cod. Deplasând în jos arborele de cod, puteți scrie pentru fiecare literă combinația de coduri corespunzătoare.
Codul Huffman, ca și Shannon-Fano, este un prefix, adică într-un astfel de cod, nici o combinație nu este aceeași cu începutul unei combinații mai lungi, iar acest lucru permite o decodare neechivocă fără introducerea simbolurilor de separare.
Numărul mediu de cifre:
După cum vedem, valoarea numărului mediu de cifre sa dovedit a fi destul de aproape de entropie, prin urmare, codul poate fi considerat eficient. Pentru comparație, puteți calcula valoarea K pentru un cod uniform:
Fie o variabilă aleatoare X (x1, x2, x3, x4, x5, x6, x7, x8) având opt stări cu distribuție de probabilitate
Toate literele sunt scrise în ordinea descrescătoare a probabilităților lor, apoi sunt împărțite în grupuri echiprobabile, care sunt notate cu 0 și 1, apoi împărțite din nou în grupuri echiprobabile etc.
să construiască un arbore Huffman pentru mesajul S = "A H F B H C E H E H C E A H D C E H H H H H H D E G H G G H H H H".
Să avem următorul tabel de coduri de prefix:
Este necesară decodarea mesajului: 00100010000111010101110000110
NOTĂ. Decodificarea este efectuată prin repetarea ciclică a următoarelor acțiuni:
1. Tăiați caracterul din stânga din mesajul curent, atașați la cuvântul de cod de lucru;
2. Comparați cuvântul codului de lucru cu tabela de cod; dacă nu există nici o potrivire, mergeți la (1);
3. decodarea cuvântului de cod de lucru;
4. verificați dacă există mai multe semne în mesaj; dacă da, mergeți la (1).
Să fie un alfabet primar A. constând din șase caractere a1 ... a6 cu probabilități de apariție în mesaj, respectiv 0,3; 0,2; 0,2; 0,15; 0,1; 0.05.
Construiți codul Huffman
Se codifică ansamblul de mesaje X = x1, x2 cu codul binar Shannon-Fano. x8 dacă toate mesajele codate sunt la fel de probabile. Arătați natura optimă a codului primit.
Determinați numărul de elemente din cuvântul de cod dacă numărul total de combinații N = 512 este cunoscut și baza de cod este 2.
Câte numere binare pot fi reprezentate de un cod pe 7 biți?
Având un set de simboluri x1, x2, x3, x4 cu următoarele statistici, respectiv: 0.28; 0,14; 0,48; 0.10. Codificați simbolurile utilizând metoda Shannon-Fano și determinați eficiența codului.
Articole similare
Trimiteți-le prietenilor: