Metodă simplă de codificare ( CODIFICAREA LUNGIMELOR DE RUNERE), care este folosit cu succes de arhivatorii populari.

Această metodă se bazează pe numărarea lungimii caracterelor repetate într-un rând și scrierea în fișierul împachetat în loc de o secvență a acestor caractere, tastați informații: numărul de caractere și caracterul repetat în sine. De exemplu, există un șir ca „ AAAAABBBCCCADDDEEL". Se va împacheta într-o secvență ca " 5A3B3CADDEEL". După cum se poate vedea din exemplu, secvența de 5 litere "A" a fost împachetată în două caractere "5" și "A", iar secvențele "DD", "EE", "L" nu au fost deloc împachetate. , deoarece nu există niciun câștig din înlocuirea acestor caractere într-o secvență de tip „lungime”+„litera”.

Când implementați împachetarea unui fișier folosind această metodă, apar dificultăți, cum ar fi modul în care dezambalătorul va distinge informațiile de control dintr-un fișier împachetat de datele despachetate. De exemplu, ca în cazul discutat mai sus, va distinge despachetatorul caracterul de control „5” de un caracter dezambalat cu același cod? Există două opțiuni pentru a rezolva această problemă:

(eu). Găsiți un simbol care apare mai puțin decât restul sau care nu apare deloc în fișierul împachetat și utilizați-l ca control. Să-l numim prefix pentru comoditate în următoarea explicație. Acum secvența „AAAAA” va fi convertită de către packer în prefix (8 biți), „A” (8 biți), cantitate (8 biți), adică 5 octeți vor fi înlocuiți cu trei. Dacă se întâlnește un bit cu un cod prefix în fișierul sursă în timpul împachetarii, atunci doi octeți cu codul prefix sunt scrieți în fișierul rezultat, iar prin această caracteristică, dezambalătorul va determina unde prefixul este un simbol și unde este controlul informație. Sunt posibile modificări ale acestei metode, de exemplu:

1. Numărul de codificați nu cu opt biți, ci cu trei, patru și așa mai departe, ceea ce va crește procentul de împachetare, dar va limita lungimea maximă a caracterelor repetate care pot fi împachetate în cazul codificării cu trei biți (de la 3 la 10, adică .000=3, ...,111=10), iar dacă lungimea este mai mare de 10 caractere, atunci împachetați zece caractere fiecare.

2. O a doua modificare este posibilă, atunci când numărul de caractere repetate este codificat nu cu opt biți, ci cu trei biți, iar lungimea caracterelor repetate este limitată la 265. Se pune întrebarea cum se codifică 256 de lungimi diferite în 3 biți. Se pare că este posibil, dar numai intervalul este de la 3 la 9, dacă lungimea caracterelor repetate este mai mare de 9, atunci „111” în codul binar este scris în trei biți, care este egal cu „7”. Aceasta înseamnă că lungimea adevărată a secvenței este în octetul următor (8 biți sunt alocați pentru lungimi de la 10 la 256 de caractere).

Aici sunt cateva exemple:

Avem secvențe:

a) „AAAAABBBBBBBBBBCCAAAAAAAAAAAAAA”

b) „CBBBBBBBBBBEEEEEEEEEEA”

Să le împachetăm:

1. Prin metoda RLE (codare run-length - pachet de octeți repeți).

a) Luați prefixul egal cu „D”, obținem:
„D”, „D”, „A”, 5, „D”, „B”, 10, „C”, „D”, „A”, 15.

Procent de compresie = 12 octeți/32 octeți = 37,5%

Într-un fișier împachetat, octetul de prefix este primul octet, astfel încât dezambalătorul să știe care octet este prefixul.

b) Luați un prefix egal cu „A”, deși, de fapt, packerul nu va face acest lucru, deoarece nu există multe caractere în această secvență, astfel încât arhivatorul va lua un caracter neutilizat ca prefix.

Secvență ambalată:
„A”, „C”, „A”, „B”, 10, „A”, „E”, 10, „A”, „A”

Procent de compresie = 10 octeți/22 octeți = 45,5%

2. Acum să împachetăm aceleași linii conform modificării 1 a metodei RLE cu aceleași valori de prefix pentru a analiza eficiența.

„D”, „D”, „A”, 2, „D”, „B”, 7,
8 biți 8 biți 8 biți 3 biți 8 biți 8 biți 3 biți

„D”, „A”, 7, „D”, „A”, 2
8 biți 8 biți 3 biți 8 biți 8 biți 3 biți

Procent de compresie=84 biți/(22*8) biți = 32,8%

„A” , „C” , „A” , „B” , 7 , „A” , „E” , 7 , „A”, „A”
8 biți 8 biți 8 biți 8 biți 4 biți 8 biți 8 biți 3 biți 8 biți 8 biți

Procent de compresie=70 biți/(22*8) biți = 39,8%

3. Acum să verificăm eficacitatea ultimei modificări:

a) Secvență de pachete:

„D”, „D”, „A”, 2, „D”, „B”, 7, 0
8 biți 8 biți 8 biți 3 biți 8 biți 8 biți 3 biți 8 biți

„D”, „A”, 7, 5
8 biți 8 biți 3 biți 8 biți

Procent de compresie = 81 biți/(32*8) biți = 31,6%

b) Secvență de pachete:

„A” , „C” , „A” , „B” , 7 , 0 , „A” , „E”
8 biți 8 biți 8 biți 8 biți 3 biți 8 biți 8 biți 8 biți

7 , 0 , "A" , "A"
3 biți 8 biți 8 biți 8 biți

Procent de compresie = 86 biți/(22*8) biți = 48,9%

Aceste exemple arată că, în funcție de conținutul datelor împachetate, fie unul, fie celălalt algoritm este eficient, așa că pentru a alege ce algoritm este mai eficient, trebuie să le testați pe diferite tipuri de fișiere.

(II). A doua opțiune pentru înregistrarea informațiilor de control pentru unpacker este următoarea: dacă un singur caracter apare în text, atunci un bit de control este egal cu unul și acest caracter însuși este scris în fișierul de ieșire. Dacă există o secvență de octeți repeți, de exemplu „AAAAAA”, atunci informațiile împachetate vor arăta astfel: 0 (1 bit), octet A (8 biți), număr (3-8 biți);

Să dăm un exemplu pentru claritate. Pentru a face acest lucru, luați secvențe din exemplele anterioare.

1) Numărul de octeți repetați este codificat în 8 biți.

a) 0, "A", 5, 0, "B", 10, 1, "C", 1, "C", 0, "A", 15
1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b. 1b. 8b. 1b. 8b. 8b.

Procent de compresie = 71 biți/256 biți = 27,7%

b) 1, "C", 0, "B", 10, 0, "E", 10, 1, "A"
1b. 8b. 1b. 8b. 8b. 1b. 8b. 8b. 1b. 8b.

Procent de compresie = 52 biți/176 biți = 29,5%

2) Acum să luăm 3 biți pentru a codifica numărul de octeți repeți, în care pot fi codificate valori de la 2 la 8 (0 - 6), dacă lungimea secvenței care se repetă este mai mare, atunci acești trei biți conțin „111” (7 zecimale), iar lungimea adevărată este în octetul următor (lungimea de la 9 la 264).

a) 0, „A”, 3, 0, „B”, 7, 1, 0, „C”, 0, 0, „A”, 7, 6
1b. 8b. 3b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 1b. 8b. 3b. 8b.

Procent de compresie = 64 biți/256 biți = 20,3%

b) 1, „C”, 0, „B”, 7, 1, 0, „E”, 7, 1, 1, „A”
1b. 8b. 1b. 8b. 3b. 8b. 1b. 8b. 3b. 8b. 1b. 8b.

Procent de compresie = 58 biți / 176 biți = 33%

Dacă cantitatea este codificată pe 4 biți (2..16), atunci

1 , "C", 0 , "B" , 8 , 0 , "E" , 8 , 1 , "A"
1b. 8b. 1b. 8b. 4b. 1b. 8b. 4b. 1b. 8b.

Procent de compresie = 44 de biți / 176 de biți = 25%

După cum puteți vedea din exemple, a doua opțiune de împachetare este mai eficientă, deoarece comprimă secvențele care încep cu două caractere, care sunt de obicei marea majoritate. Prima variantă a împachetat secvențe începând de la trei caractere.

• tutorial

Cu mult timp în urmă, când eram încă un școlar naiv, am devenit dintr-o dată teribil de curios: cum ocupă magic datele din arhive mai puțin spațiu? Mergând pe dialup-ul meu fidel, am început să navighez pe internet în căutarea unui răspuns și am găsit multe articole cu o prezentare destul de detaliată a informațiilor care mă interesau. Dar niciunul dintre ele nu părea ușor de înțeles atunci - listele de coduri păreau litere chinezești, iar încercările de a înțelege terminologia neobișnuită și diverse formule nu au avut succes.

Prin urmare, scopul acestui articol este de a oferi o idee despre cei mai simpli algoritmi de compresie celor ale căror cunoștințe și experiență nu le permit încă să înțeleagă imediat mai multă literatură profesională sau al căror profil este complet departe de astfel de subiecte. Acestea. Voi vorbi „pe degetele mele” despre unii dintre cei mai simpli algoritmi și voi da exemple de implementare a acestora fără liste de coduri lungi de un kilometru.

Vă voi avertiza imediat că nu voi lua în considerare detaliile implementării procesului de codificare și nuanțe precum căutarea eficientă a aparițiilor unui șir. Articolul va atinge doar algoritmii înșiși și modalitățile de prezentare a rezultatului muncii lor.

RLE - Compactitatea uniformității

Exemplu de implementare

Pentru mulți, va fi mult mai familiar să vedeți aceste date ca un dump hexadecimal:
0000: 00 00 00 00 00 00 04 02 00 04 04 04 04 04 04 04
0010: 50 50 50 50 00 02 02 02 02 FF FF FF FF 00 00

Reflectând, am decis că ar fi bine să comprimăm cumva astfel de seturi pentru a economisi spațiu. Pentru a face acest lucru, le-am analizat și am identificat un model: de foarte multe ori există subsecvențe formate din aceleași elemente. Desigur, RLE este perfect pentru asta!

Să ne codificăm datele folosind cunoștințele nou obținute: 6x0, 4, 2, 0, 7x4, 4x80, 0, 4x2, 5x255, 2x0.

Este timpul să prezentăm cumva rezultatul nostru într-o formă prietenoasă cu computerul. Pentru a face acest lucru, în fluxul de date, trebuie să separăm cumva octeții unici de șirurile codificate. Deoarece întregul interval de valori ale octeților este utilizat de datele noastre, nu va fi posibil să alocam pur și simplu intervale de valori pentru scopurile noastre.

Există cel puțin două moduri de ieșire din această situație:

1. Ca indicator al unui lanț comprimat, selectați o valoare de un octet și, în cazul unei coliziuni cu date reale, scăpați de ele. De exemplu, dacă folosim valoarea 255 în scopuri „oficiale”, atunci când această valoare este întâlnită în datele de intrare, va trebui să scriem „255, 255” și să folosim maxim 254 după indicator.
2. Structurați datele codificate, indicând numărul de elemente nu numai repetate, ci și ulterioare. Atunci vom ști în prealabil unde sunt datele.

Deci acum avem două tipuri de secvențe: șiruri de elemente unice (cum ar fi „4, 2, 0”) și șiruri de elemente identice (cum ar fi „0, 0, 0, 0, 0, 0”). Să alocăm un bit în octeții „serviciu” pentru tipul de secvență: 0 - elemente simple, 1 - identice. Luați pentru asta, să zicem, cel mai semnificativ bit de octet.

În cei 7 biți rămași, vom stoca lungimile secvențelor, adică. lungimea maximă a secvenței codificate este de 127 de octeți. Am putea aloca, să zicem, doi octeți în scopuri de service, dar în cazul nostru secvențele atât de lungi sunt extrem de rare, așa că este mai ușor și mai economic să le împărțim pur și simplu în altele mai scurte.

Se pare că în fluxul de ieșire vom scrie mai întâi lungimea secvenței și apoi fie o valoare repetată, fie un lanț de elemente nerepetate de lungimea specificată.

Primul lucru care ar trebui să vă atragă atenția este că în această situație avem câteva valori nefolosite. Nu pot exista secvențe de lungime zero, așa că putem crește lungimea maximă la 128 de octeți scăzând unul din lungime la codificare și adăugând la decodificare. Deci putem codifica lungimi de la 1 la 128 în loc de lungimi de la 0 la 127.

Al doilea lucru de remarcat este că nu există secvențe de elemente identice de lungime unitară. Prin urmare, atunci când codificăm, vom scădea încă una din lungimea unor astfel de secvențe, crescând astfel lungimea lor maximă la 129 (lungimea maximă a unui lanț de elemente individuale este încă 128). Acestea. lanțurile de elemente identice pot avea o lungime de la 2 la 129.

Să ne codificăm din nou datele, dar acum într-o formă pe înțelesul computerului. Vom scrie octeții de serviciu ca , unde T este tipul secvenței și L este lungimea. Vom lua imediat în considerare că scriem lungimile în formă modificată: la T=0 scădem una din L, la T=1 - doi.

0, , 4, 2, 0, , 4, , 80, , 0, , 2, , 255, , 0

Să încercăm să decodificăm rezultatul nostru:

• . T=1, atunci următorul octet va fi repetat L+2 (4+2) ori: 0, 0, 0, 0, 0, 0.
• . T=0, deci citiți L+1 (2+1) octeți: 4, 2, 0.
• . T=1, repeta următorul octet de 5+2 ori: 4, 4, 4, 4, 4, 4, 4.
• . T=1, repeta următorul octet de 2+2 ori: 80, 80, 80, 80.
• . T=0, citiți 0+1 octeți: 0.
• . T=1, repeta octet de 2+2 ori: 2, 2, 2, 2.
• . T=1, repeta octet de 3+2 ori: 255, 255, 255, 255, 255.
• . T=1, repetă octetul de 0+2 ori: 0, 0.

Și acum ultimul pas: salvați rezultatul ca o matrice de octeți. De exemplu, o pereche împachetată într-un octet ar arăta astfel:

Ca rezultat, obținem următoarele:
0000: 84 00 02 04 02 00 85 04 82 80 00 00 82 02 83 FF
0010: 80 00

Într-un mod atât de simplu, pe acest exemplu de date de intrare, am obținut 18 octeți din 32. Un rezultat bun, mai ales când te gândești că poate fi mult mai bine pe lanțuri mai lungi.

Posibile îmbunătățiri

Eficiența suplimentară poate fi obținută prin utilizarea tehnicilor de codare euristică. De exemplu, să codificăm următorul lanț în felul nostru: „ABBA”. Obținem „ , A, , B, , A” - adică. Am transformat 4 octeți în 6, am umflat datele originale de până la o dată și jumătate! Și cu cât sunt mai multe secvențe eterogene alternative atât de scurte, cu atât mai multe date redundante. Dacă luăm în considerare acest lucru, atunci am putea codifica rezultatul ca „, A, B, B, A” - am cheltui doar un octet în plus.

LZ77 - concizie în repetare

Ideea principală este de a codifica secvențe identice de elemente. Adică, dacă un lanț de elemente apare de mai multe ori în datele de intrare, atunci toate aparițiile sale ulterioare pot fi înlocuite cu „legături” la prima instanță.

Ca și restul algoritmilor acestei familii a familiei, LZ77 folosește un dicționar care stochează secvențe întâlnite anterior. Pentru a face acest lucru, el aplică principiul așa-numitului. „fereastră glisantă”: zona întotdeauna înaintea poziției curente de codare în care putem adresa link-uri. Această fereastră este un dicționar dinamic pentru acest algoritm - fiecărui element din ea corespunde două atribute: poziția în fereastră și lungimea. Deși în sens fizic, aceasta este doar o bucată de memorie pe care am codificat-o deja.

Exemplu de implementare

„Compresia și decompresia lasă o impresie. Ha, ha, ha, ha, ha!"

Iată cum va arăta în memorie (codare ANSI):
0000: 54 68 65 20 63 6F 6D 70 72 65 73 73 69 6F 6E 20 Compresia
0010: 61 6E 64 20 74 68 65 20 64 65 63 6F 6D 70 72 65 și decompresia
0020: 73 73 69 6F 6E 20 6C 65 61 76 65 20 61 6E 20 69 ssion lasă un i
0030: 6D 70 72 65 73 73 69 6F 6E 2E 20 48 61 68 61 68 Hahah
0040: 61 68 61 68 61 21 ahaha!

Încă nu ne-am decis cu privire la dimensiunea ferestrei, dar vom fi de acord că este mai mare decât dimensiunea șirului codificat. Să încercăm să găsim toate șirurile de caractere care se repetă. Un șir este o secvență de caractere mai lungă de unu. Dacă lanțul face parte dintr-un lanț care se repetă mai lung, îl vom ignora.

„Comprimarea și t de leave[an] i . Hah!"

Pentru o mai mare claritate, să ne uităm la diagramă, unde putem vedea corespondența secvențelor repetate și primele lor apariții:

Poate singurul punct neclar aici este secvența „Hahahahaha!”, deoarece șirul de caractere „ahahaha” corespunde șirului scurt „ah”. Dar nu este nimic neobișnuit aici, am folosit un truc care permite algoritmului să funcționeze uneori ca RLE descris mai devreme.

Faptul este că la despachetare, vom citi numărul specificat de caractere din dicționar. Și întrucât întreaga secvență este periodică, adică. datele din el se repetă cu o anumită perioadă, iar simbolurile primei perioade vor fi chiar înainte de poziția de despachetare, apoi putem recrea întregul lanț din ele, pur și simplu copiend simbolurile perioadei precedente în următoarea.

Am rezolvat. Acum să înlocuim repetițiile găsite cu referințe la dicționar. Vom scrie linkul în formatul , unde P este poziția primei apariții a șirului în șir, L este lungimea acestuia.

„Compresia și t de leave i . Hah!"

Dar nu uitați că avem de-a face cu o fereastră glisantă. Pentru o mai bună înțelegere, astfel încât legăturile să nu depindă de dimensiunea ferestrei, vom înlocui pozițiile absolute cu diferența dintre ele și poziția curentă de codificare.

„Compresia și t de leave i . Hah!"

Acum trebuie doar să scădem P din poziția curentă de codificare pentru a obține poziția absolută în șir.

Este timpul să decideți asupra dimensiunii ferestrei și a lungimii maxime a frazei codificate. Deoarece avem de-a face cu text, este rar ca în el să existe secvențe repetate deosebit de lungi. Deci, să alocăm, să zicem, 4 biți pentru lungimea lor - o limită de 15 caractere este suficientă pentru noi.

Dar dimensiunea ferestrei depinde deja de cât de adânc vom căuta aceleași lanțuri. Deoarece avem de-a face cu texte mici, va fi corect să suplimentăm numărul de biți pe care îi folosim la doi octeți: vom aborda link-uri într-un interval de 4096 de octeți, folosind 12 biți pentru aceasta.

Știm din experiența cu RLE că nu toate valorile pot fi folosite. Evident, legătura poate avea o valoare minimă de 1, prin urmare, pentru a ne adresa înapoi în intervalul 1..4096, trebuie să scădem unul din link la codificare și să adăugăm înapoi la decodare. La fel și cu lungimile secvențelor: în loc de 0..15 vom folosi intervalul 2..17, deoarece nu lucrăm cu lungimi zero, iar caracterele individuale nu sunt secvențe.

Deci, să ne imaginăm textul nostru codificat, ținând cont de aceste modificări:

„Compresia și t de leave i . Hah!"

Acum, din nou, trebuie să separăm cumva lanțurile comprimate de restul datelor. Cea mai obișnuită modalitate este de a utiliza din nou structura și de a indica direct unde sunt comprimate datele și unde nu. Pentru a face acest lucru, vom împărți datele codificate în grupuri de opt elemente (caractere sau legături), iar înaintea fiecăreia dintre aceste grupuri vom introduce câte un octet, în care fiecare bit corespunde tipului de element: 0 pentru un caracter și 1 pentru un legătură.

Ne împărțim în grupuri:

• "The Comp"
• "iertare"
• "și t de"
• "părăsi"
• "i. hah"

„(0,0,0,0,0,0,0,0) Resiunea comp(0,0,0,0,0,0,0,0) (0,0,0,0,0,1 ,0,0) și t de(1,0,0,0,0,0,1,0) lasă (0,1,0,0,0,0,0,1) i . Hah(0)!"

Astfel, dacă întâlnim bitul 0 în timpul despachetării, atunci pur și simplu citim caracterul în fluxul de ieșire, dacă bitul este 1, citim linkul și, prin referință, citim secvența din dicționar.

Acum trebuie doar să grupăm rezultatul într-o matrice de octeți. Să fim de acord că folosim biți și octeți în ordine de la mare la scăzut. Să vedem cum sunt împachetate legăturile în octeți folosind un exemplu:

Ca rezultat, fluxul nostru comprimat va arăta astfel:

0000:00 54 68 65 20 63 6f 6d 70 00 72 65 73 73 69 6f #The com#presio
0010: 6e 20 04 61 6e 64 20 74 01 31 64 65 82 01 5a 6c n #și t##de###l
0020: 65 61 76 65 01 b1 20 41 69 02 97 2e 20 48 61 68 streașină## #i##. Hah
0030: 00 15 00 21 00 00 00 00 00 00 00 00 00 00 00 00 ###!

Posibile îmbunătățiri

„Goooooong lung. Cea mai mult legată.”

Să găsim secvențe numai pentru cuvântul „looooooower”:

„Goooooong lung. Cel legat.”

Pentru a codifica un astfel de rezultat, avem nevoie de patru octeți per legătură. Cu toate acestea, ar fi mai economic să faceți acest lucru:

„Goooooong lung. Eu am fost legat.”

Atunci am cheltui cu un octet mai puțin.

În loc de concluzie

Avantajul lor este simplitatea și viteza, iar algoritmii mai complexi și eficienți se pot baza pe principiile și combinațiile lor.

Sper că esența acestor algoritmi enunțați în acest fel va ajuta pe cineva să înțeleagă elementele de bază și să înceapă să caute spre lucruri mai serioase.

Date care sunt acceptate de majoritatea formatelor de fișiere bitmap: TIFF, BMP și PCX. RLE este potrivit pentru comprimarea oricărui tip de date, indiferent de conținutul lor de informații, dar conținutul datelor afectează raportul de compresie. Deși majoritatea algoritmilor RLE nu pot oferi rapoarte de compresie mari pentru metode mai complexe, acest instrument este ușor de implementat și rapid de executat, ceea ce îl face o alternativă bună.

Pe ce se bazează algoritmul de compresie RLE?

RLE funcționează prin reducerea dimensiunii fizice a unui șir repetat de caractere. Acest șir, numit run, este de obicei codificat ca doi octeți. Primul octet reprezintă numărul de caractere din rulare și se numește contor de rulare. În practică, o rulare codificată poate include de la 1 la 128 și 256 de simboluri. Contorul conține de obicei numărul de caractere minus unu (o valoare în intervalul 0 la 127 și 255). Al doilea octet este valoarea caracterului din rulare, care este conținută în intervalul de valori de la 0 la 255 și se numește valoarea de rulare.

Fără compresie, o rulare de caractere de 15 caractere necesită de obicei 15 octeți pentru a stoca:

AAAAAAAAAAAAAAA.

În aceeași linie, după codarea RLE, sunt necesari doar doi octeți: 15A.

Codificarea 15A generată pentru a denota un șir de caractere se numește pachet RLE. În acest cod, primul octet, 15, este contorul de rulări și conține numărul necesar de repetări. Al doilea octet, A, este valoarea de rulare și conține valoarea reală repetată în rulare.

O nouă explozie este generată de fiecare dată când caracterul de început este schimbat sau de fiecare dată când numărul de caractere dintr-o rulare depășește numărul maxim. Să presupunem că un șir de 15 caractere, conform condițiilor, conține 4 caractere diferite:

Folosind codificarea cu lungimea șirului, poate fi comprimat în patru pachete de doi octeți:

Odată codificat după lungimea șirului, un șir de 15 octeți ar necesita doar opt octeți de date pentru a reprezenta șirul, spre deosebire de cei 15 octeți inițiali. În acest caz, codificarea în timpul rulării a dat un raport de compresie de aproape 2 la 1.

Particularități

Execuțiile lungi sunt rare în unele tipuri de date. De exemplu, textul simplu ASCII conține rareori porțiuni lungi. În exemplul anterior, ultima rulare (conținând caracterul t) avea doar un caracter. Execuția cu 1 caracter încă funcționează. Atât numărul de rulări, cât și valoarea de rulare trebuie scrise pentru fiecare rulare în 2 caractere. Pentru a codifica un kilometraj utilizând algoritmul RLE, sunt necesare informații formate din cel puțin două caractere. În acest sens, lansarea personajelor individuale ocupă de fapt mai mult spațiu. Din aceleași motive, datele constând în întregime din execuții de 2 caractere rămân neschimbate după codificarea RLE.

Schemele algoritmului de compresie RLE sunt simple și rapide, dar eficiența lor depinde de tipul de date de imagine care sunt codificate. O imagine alb-negru care este în mare parte albă, cum ar fi paginile unei cărți, va codifica foarte bine datorită cantității mari de date adiacente care au aceeași culoare. Cu toate acestea, o imagine cu multe culori, cum ar fi o fotografie, nu se va codifica la fel de bine. Acest lucru se datorează faptului că complexitatea unei imagini este exprimată ca un număr mare de culori diferite. Și din cauza acestei complexități, vor exista relativ puține runde de aceeași culoare.

Opțiuni de codare a lungimii

Există mai multe opțiuni de codare în timpul execuției. Datele imaginii sunt de obicei codificate într-un proces secvenţial care tratează conţinutul vizual ca un flux 1D, mai degrabă decât o hartă de date 2D. În procesarea secvențială, bitmap-ul este codificat începând din colțul din stânga sus și este direcționat de la stânga la dreapta pe fiecare linie de scanare către colțul din dreapta jos al bitmap-ului. Dar schemele RLE alternative pot fi, de asemenea, scrise pentru a codifica datele de-a lungul unei hărți de bit de-a lungul coloanelor pentru compresie în plăci 2D sau chiar pentru a codifica pixelii în diagonală în zig-zag. Variante ciudate ale RLE pot fi utilizate în aplicații foarte specializate, dar sunt în general destul de rare.

Algoritm de codificare cu eroare de lungime de rulare

O altă opțiune rar întâlnită este algoritmul de codare RLE cu eroare de lungime de rulare. Aceste instrumente efectuează de obicei compresie fără pierderi, dar eliminarea datelor în timpul procesului de codificare, de obicei prin reducerea la zero a unuia sau doi biți mai puțin semnificativi în fiecare pixel, poate crește rapoartele de compresie fără a afecta negativ calitatea imaginilor complexe. Acest program de algoritm RLE funcționează bine numai cu imagini din lumea reală care conțin multe variații subtile ale valorilor pixelilor.

Codare încrucișată

Cross-coding este combinația de linii de scanare care apare atunci când procesul de compresie pierde distincția dintre liniile originale. Dacă datele individuale ale liniilor sunt combinate de algoritmul de codare de repetare RLE, punctul în care o linie de scanare este oprită și alta este pierdută este vulnerabil și dificil de detectat.

Uneori apare codificarea încrucișată, ceea ce complică procesul de decodare prin adăugarea unui cost de timp. Pentru formatele de fișiere cu imagini raster, această metodă are ca scop organizarea imaginii raster de-a lungul liniilor de scanare. În timp ce multe specificații de format de fișiere afirmă în mod explicit că datele de linie trebuie codificate individual, multe aplicații codifică aceste imagini ca un flux continuu, ignorând limitele liniilor.

Cum se codifică o imagine folosind algoritmul RLE?

Codificarea individuală a liniilor de scanare este avantajoasă atunci când o aplicație trebuie să folosească doar o porțiune a unei imagini. Să presupunem că o fotografie conține 512 linii de scanare și trebuie afișate doar liniile de la 100 la 110. Dacă nu știm unde au început și s-au terminat liniile de scanare cu date de imagine codificate, aplicația noastră ar trebui să decodeze liniile de la 1 la 100 înainte de a găsi zece linii care sunt necesare. Dacă tranzițiile dintre liniile de scanare ar fi marcate cu un marcator delimitator ușor de recunoscut, aplicația ar putea pur și simplu să citească datele codificate, numărând markerii până când ajungea la liniile de care avea nevoie. Dar această abordare ar fi destul de ineficientă.

Opțiune alternativă

O altă opțiune pentru determinarea punctului de pornire al oricărei linii de scanare anume dintr-un bloc de date codificate este construirea unui tabel de linii de scanare. Această structură de tabel conține de obicei câte un element pentru fiecare linie de scanare din imagine și fiecare element conține valoarea offset a liniei de scanare corespunzătoare. Pentru a găsi primul pachet RLE al liniei de scanare 10, tot ce trebuie să facă decodorul este să găsească valorile poziției offset stocate în a zecea intrare a tabelului de căutare a liniei de scanare. Tabelul de scanare poate conține, de asemenea, numărul de octeți utilizați pentru a codifica fiecare linie. Folosind această metodă pentru a găsi primul pachet RLE al liniei de scanare 10, decodorul dvs. va concatena valorile primelor 9 intrări din tabelul liniei de scanare. Prima rafală pentru linia de scanare 10 va începe la acest decalaj de octeți de la începutul datelor de imagine codificate RLE.

Unități

Părțile algoritmilor de codificare a lungimii care diferă sunt deciziile care sunt luate pe baza tipului de date care sunt decodificate (de exemplu, lungimea rulării datelor). Schemele RLE utilizate pentru comprimarea graficelor bitmap sunt de obicei clasificate în clase în funcție de tipul de elemente atomice (adică cele mai fundamentale) pe care le codifică. Cele trei clase utilizate de majoritatea formatelor de fișiere grafice sunt biți, octeți și pixeli RLE.

Calitatea compresiei

Nivelurile de biți ale schemelor RLE codifică rulări de mai mulți biți într-o linie de scanare și ignoră granițele de octeți și cuvinte. Doar imaginile monocrome (alb-negru), pe 1 bit, conțin destui biți pentru a face această clasă de codificare RLE eficientă. O schemă tipică RLE la nivel de biți codifică de la unu la 128 de biți într-un pachet de un octet. Cei șapte biți cei mai puțin semnificativi conțin numărul de rulări minus unu, iar bitul cel mai semnificativ conține valoarea de rulare a biților egală cu 0 sau 1. O rulare mai lungă de 128 de pixeli este împărțită în mai multe pachete codificate RLE.

Excepții

Schemele RLE la nivel de octeți codifică rulări ale acelorași valori de octeți, ignorând anumite limite de biți și cuvinte din șirul de scanare. Cea mai comună schemă RLE la nivel de octeți codifică rulări de octeți în pachete de 2 octeți. Primul octet conține un numărător de la 0 la 255, iar al doilea octet conține valoarea de pornire a octetului. De asemenea, este obișnuit să se suplimenteze o schemă de codificare pe doi octeți cu capacitatea de a stoca porțiuni literale, nescrise de octeți în fluxul de date codificat.

Într-o astfel de schemă, cei mai puțin semnificativi șapte biți ai primului octet conțin numărul de rulări minus unu, iar bitul cel mai semnificativ al primului octet este indicatorul de tip de declanșare care urmează octetul de numărare a rulărilor. Dacă bitul cel mai semnificativ este setat la 1, acesta denotă o rulare codificată. Execuțiile codificate sunt decodificate prin citirea valorii de rulare și repetarea acesteia de mai multe ori, indicat de numărul de cicluri. Dacă bitul cel mai semnificativ este setat la 0, este afișat o rulare literală, ceea ce înseamnă că următorii octeți de numărare a rulărilor sunt citiți literal din datele imaginii codificate. Octetul contorului de rulare conține apoi o valoare în intervalul de la 0 la 127 (contorul de rulări minus unu). Schemele RLE la nivel de octet sunt bune pentru datele de imagine care sunt stocate ca un octet per pixel.

Schemele RLE la nivel de pixel sunt utilizate atunci când doi sau mai mulți octeți consecutivi de date de imagine sunt utilizați pentru a stoca valorile unui singur pixel. La nivel de pixel, biții sunt ignorați și octeții sunt numărați doar pentru a identifica fiecare valoare de pixel. Mărimea pachetelor codificate depinde de mărimea valorilor pixelilor codificați. Numărul de biți sau octeți per pixel este stocat în antetul fișierului imagine. Începutul datelor de imagine stocate ca valori de pixeli de 3 octeți este codificat într-un pachet de 4 octeți, cu un număr de operațiuni de un octet urmat de trei octeți de octeți. Metoda de codificare rămâne aceeași ca și în cazul octetului RLE.

Prima versiune a algoritmului

Acest algoritm este extrem de ușor de implementat. Codificarea de grup - din limba engleză Run Length Encoding (RLE) - este unul dintre cei mai vechi și mai simpli algoritmi de arhivare a graficelor. Imaginea din ea (ca în mai mulți algoritmi descriși mai jos) este trasă într-un lanț de octeți de-a lungul liniilor rasterului. Are loc compresia în sine în RLE datorită faptului că în imaginea originală există lanțuri de octeți identici. Înlocuirea lor cu perechi<счетчик повторений, значение>reduce redundanța datelor.

Algoritm decompresie arata cam asa:

initializare(...);
do(
dacă (este contor(octet)) (
contor = Low6bits(byte)+1;
pentru(i=1 pentru a contracara)
De
}
altceva(
DecompressedFile.WriteByte(octet)
) while(ImageFile.EOF());

În acest algoritm, semnul contorului (contorului) este cel din primii doi biți ai fișierului citit:

În consecință, restul de 6 biți sunt cheltuiți pe contor, care poate lua valori de la 1 la 64. Transformăm un șir de 64 de octeți repeți în doi octeți, adică. comprima de 32 de ori.

Un exercitiu: Faceți un algoritm comprimare pentru prima versiune a algoritmului RLE.

Întrebare pentru autocontrol: Sugerați două sau trei exemple de imagini „rele” pentru algoritmul RLE. Explicați de ce fișierul comprimat este mai mare decât fișierul original.

A doua versiune a algoritmului

A doua variantă a acestui algoritm are un raport maxim de arhivare mai mare și mărește mai puțin dimensiunea fișierului sursă.

Algoritmul de decompresie pentru acesta arată astfel:

initializare(...);
do(
octet = ImageFile.ReadNextByte();
contor = Low7bits(byte)+1;
dacă(dacă se repetă semn(octet)) (
valoare = ImageFile.ReadNextByte();
pentru (i=1 pentru a contracara)
CompressedFile.WriteByte(valoare)
}
altceva(
pentru(i=1 pentru a contracara)(
valoare = ImageFile.ReadNextByte();
CompressedFile.WriteByte(valoare)
}
CompressedFile.WriteByte(octet)
) while(ImageFile.EOF());

Un semn de repetiție în acest algoritm este o unitate în ordinea înaltă a octetului corespunzător:

După cum se poate calcula ușor, în cel mai bun caz, acest algoritm comprimă fișierul de 64 de ori (și nu de 32 de ori, ca în versiunea anterioară), în cel mai rău caz crește cu 1/128. Indicatorii medii ai gradului de compresie a acestui algoritm sunt la nivelul indicatorilor primei variante.

Un exercitiu: Scrieți un algoritm de compresie pentru a doua versiune a algoritmului RLE.

Caracteristicile algoritmului RLE:

Raport de compresie: Prima opțiune: 32, 2, 0,5. A doua varianta: 64, 3, 128/129.(cea mai bună, medie, cea mai slabă cotă)

Clasa de imagine: Algoritmul se concentrează pe imagini cu un număr mic de culori: grafică de afaceri și științifică.

Simetrie: Aproximativ una.

Caracteristici caracteristice: Aspectele pozitive ale algoritmului, probabil, pot fi atribuite doar faptului că nu necesită memorie suplimentară pentru arhivare și dezarhivare și funcționează, de asemenea, rapid. O caracteristică interesantă a codării de grup este că gradul de arhivare pentru unele imagini poate fi crescut semnificativ doar prin schimbarea ordinii culorilor în paleta de imagini.

Numele algoritmului a fost dat de primele litere ale numelor dezvoltatorilor săi - Lempel, Ziv și Welch. Comprimarea în el, spre deosebire de RLE, este deja realizată datorită acelorași lanțuri de octeți.

Algoritmul LZ

Există o familie destul de mare de algoritmi de tip LZ care diferă, de exemplu, în metoda de căutare a lanțurilor repetate. Una dintre variantele destul de simple ale acestui algoritm, de exemplu, presupune că fluxul de intrare conține fie o pereche<счетчик, смещение относительно текущей позиции>, sau doar<счетчик>octeții „săriți” și valorile octeților înșiși (ca în a doua versiune a algoritmului RLE). Când deschid fermoarul pentru un cuplu<счетчик, смещение>copiat<счетчик>octeți din matricea de ieșire rezultată din dezarhivarea în<смещение>octeți înainte și<счетчик>(adică, un număr egal cu contorul) valorile octeților „săriți” sunt pur și simplu copiate în matricea de ieșire din fluxul de intrare. Acest algoritm este asimetric în timp, deoarece necesită o căutare completă a tamponului atunci când se caută subșiruri identice. Ca urmare, este dificil pentru noi să setăm un tampon mare din cauza creșterii puternice a timpului de compresie. Totuși, potențial construcția unui algoritm în care<счетчик>și pe<смещение>Vor fi alocați 2 octeți (bitul înalt al octetului înalt al contorului este un semn al repetiției șirurilor / copierii fluxului), ne va oferi posibilitatea de a comprima toate subșirurile repetate până la 32Kb într-un buffer de 64Kb.

În acest caz, vom obține o creștere a dimensiunii fișierului în cel mai rău caz cu 32770/32768 (în doi octeți este scris că următorii 2 15 octeți ar trebui rescriși în fluxul de ieșire), ceea ce nu este rău deloc. Raportul maxim de compresie va fi în limita de 8192 de ori. În limită, deoarece obținem compresia maximă transformând un buffer de 32Kb în 4 octeți și nu vom acumula imediat un buffer de această dimensiune. Totuși, subșirul minim pentru care ne este benefic să comprimăm ar trebui să fie în general de cel puțin 5 octeți, ceea ce determină valoarea scăzută a acestui algoritm. Avantajele LZ includ simplitatea extremă a algoritmului de decompresie.

Un exercitiu: Sugerați o altă variantă a algoritmului LZ în care perechea<счетчик, смещение>Vor fi alocați 3 octeți și calculați principalele caracteristici ale algoritmului dvs.

Varianta algoritmului considerată mai jos va folosi un arbore pentru a reprezenta și stoca lanțuri. Evident, aceasta este o restricție destul de puternică asupra tipului de lanțuri și nu toate sublanțurile identice din imaginea noastră vor fi folosite în timpul compresiei. Cu toate acestea, în algoritmul propus, este avantajos să comprimați lanțurile egale formate din 2 octeți.

Procesul de compresie pare destul de simplu. Citim secvențial caracterele fluxului de intrare și verificăm dacă există un astfel de șir în tabelul de șiruri pe care l-am creat. Dacă există o linie, atunci citim următorul caracter, iar dacă nu există nicio linie, introducem codul pentru linia găsită anterioară în flux, punem linia în tabel și începem din nou căutarea.

Funcția InitTable() șterge tabelul și pune toate rândurile cu o singură lungime în el.

InitTable();
CompressedFile.WriteCode(ClearCode);
CurStr=șir gol;
while(nu ImageFile.EOF())( //Până la sfârșitul fișierului
C=ImageFile.ReadNextByte();
if(CurStr+C este în tabel)
CurStr=CurStr+C;//Lipiți un caracter pe un șir
altceva(
code=CodeForString(CurStr);//cod-nu un octet!
AddStringToTable(CurStr+C);
CurStr=C; // Un singur șir de caractere
}
}
cod=CodeForString(CurStr);
CompressedFile.WriteCode(cod);
CompressedFile.WriteCode(CodeEndOfInformation);

După cum sa menționat mai sus, funcția InitTable() inițializează tabelul de șiruri astfel încât acesta să conțină toate șirurile de caractere posibile. De exemplu, dacă comprimăm datele de octeți, atunci vor exista 256 de astfel de rânduri în tabel („0”, „1”, ..., „255”). Valorile 256 și 257 sunt rezervate pentru codul clar (ClearCode) și codul pentru sfârșitul informațiilor (CodeEndOfInformation). În versiunea considerată a algoritmului, este utilizat un cod de 12 biți și, în consecință, valorile ​​de la 258 la 4095 rămân pentru codurile pentru linii. Liniile adăugate sunt scrise în tabel secvenţial, cu indexul rândului din tabel devenind codul acestuia.

Funcția ReadNextByte() citește un caracter dintr-un fișier. Funcția WriteCode() scrie un cod (nu este egal ca dimensiune cu un octet) în fișierul de ieșire. Funcția AddStringToTable() adaugă un nou rând la tabel prin alocarea unui cod. În plus, această funcție gestionează situația de depășire a tabelului. În acest caz, codul rândului anterior găsit și codul de curățare sunt scrise în flux, după care tabelul este șters de funcția InitTable(). Funcția CodeForString() găsește un șir într-un tabel și returnează codul pentru acel șir.

Exemplu:

Să comprimăm secvența 45, 55, 55, 151, 55, 55, 55. Apoi, conform algoritmului descris mai sus, vom plasa mai întâi codul de curățare în fluxul de ieșire<256>, apoi adăugați „45” la șirul inițial gol și verificați dacă există un șir „45” în tabel. Deoarece, în timpul inițializării, am introdus toate liniile unui caracter în tabel, șirul „45” este în tabel. Apoi, citim următorul caracter 55 din fluxul de intrare și verificăm dacă șirul „45, 55” este în tabel. Nu există încă un astfel de rând în tabel. Introducem șirul „45, 55” în tabel (cu primul cod gratuit 258) și scriem codul în flux<45>. Vă puteți imagina pe scurt arhivarea astfel:

• „45” - este în tabel;
• „45, 55” - nr. Adăugați la tabel<258>„45, 55”. Pentru a transmite în flux:<45>;
• „55, 55” - nr. La masă:<259>„55, 55”. Pentru a transmite în flux:<55>;
• „55, 151” - nr. La masă:<260>„55, 151”. Pentru a transmite în flux:<55>;
• „151, 55” - nr. La masă:<261>„151, 55”. Pentru a transmite în flux:<151>;
• „55, 55” - este în tabel;
• „55, 55, 55” - nr. La tabel: „55, 55, 55”<262>. Pentru a transmite în flux:<259>;

Particularitatea LZW este că pentru decompresie nu trebuie să salvăm tabelul de șiruri într-un fișier pentru decompresie. Algoritmul este construit în așa fel încât să putem restabili tabelul de șiruri folosind doar fluxul de cod.

Știm că pentru fiecare cod, trebuie să adăugăm o linie la tabel, constând din linia deja prezentă acolo și caracterul cu care începe următoarea linie din flux.

Algoritmul de decompresie care efectuează această operație este următorul:

cod=File.ReadCode();
while(cod != CodeEndOfInformation)(
if(cod = ClearCode) (
InitTable();
cod=File.ReadCode();
if(cod = CodeEndOfInformation)
(termină lucrul);
ImageFile.WriteString(StrFromTable(cod));
cod_vechi=cod;
}
altceva(
if(InTable(cod)) (
ImageFile.WriteString(FromTable(cod));
AddStringToTable(StrFromTable(cod_vechi)+
FirstChar(StrFromTable(cod)));
cod_vechi=cod;
}
altceva(
OutString= StrFromTable(cod_vechi)+
FirstChar(StrFromTable(cod_vechi));
ImageFile.WriteString(OutString);
AddStringToTable(OutString);
cod_vechi=cod;
}
}
}

Aici funcția ReadCode() citește următorul cod din fișierul decomprimat. Funcția InitTable() efectuează aceleași acțiuni ca în timpul compresiei, adică. șterge tabelul și pune toate liniile unui caracter în ea. Funcția FirstChar() ne oferă primul caracter al unui șir. Funcția StrFromTable() returnează un rând dintr-un tabel prin cod. Funcția AddStringToTable() adaugă un nou rând la tabel (prin atribuirea primului cod liber). Funcția WriteString() scrie un șir într-un fișier.

Observație 1 . După cum puteți vedea, codurile scrise în flux cresc treptat. Până când codul 512 apare în tabel, de exemplu, pentru prima dată, toate codurile vor fi mai mici decât 512. În plus, în timpul compresiei și decompresiei, codurile din tabel sunt adăugate la procesarea aceluiași simbol, adică. se întâmplă „sincron”. Putem folosi această proprietate a algoritmului pentru a crește raportul de compresie. Până când caracterul 512 este adăugat la tabel, vom scrie coduri de 9 biți în fluxul de biți de ieșire, iar imediat când adăugăm 512, coduri de 10 biți. În consecință, decompresorul va trebui, de asemenea, să accepte toate codurile fluxului de intrare ca pe 9 biți până când codul 512 este adăugat la tabel, după care va percepe toate codurile de intrare ca pe 10 biți. Vom face același lucru atunci când adăugăm în tabel codurile 1024 și 2048. Această tehnică vă permite să creșteți raportul de compresie cu aproximativ 15%:

Nota 2. Când comprimăm o imagine, este important pentru noi să asigurăm viteza de căutare a rândurilor din tabel. Putem profita de faptul că fiecare subșir următor este cu un caracter mai lung decât precedentul, în plus, linia anterioară a fost deja găsită de noi în tabel. Prin urmare, este suficient să creați o listă de referințe la șiruri care încep cu un subșir dat, iar întregul proces de căutare în tabel se va reduce la căutarea în șirurile conținute în listă pentru șirul anterior. Este clar că o astfel de operație poate fi efectuată foarte rapid.

De asemenea, rețineți că, în realitate, este suficient să păstrăm în masă doar câteva<код предыдущей подстроки, добавленный символ>. Aceste informații sunt destul de suficiente pentru ca algoritmul să funcționeze. Deci o matrice de la 0 la 4095 cu elemente<код предыдущей подстроки; добавленный символ; список ссылок на строки, начинающиеся с этой строки>rezolvă problema căutării, deși foarte lent.

În practică, un tabel hash este folosit pentru a stoca un tabel, la fel de rapid ca în cazul listelor, dar mai compact în memorie. Tabelul este format din 8192 (2 13) elemente. Fiecare element conține<код предыдущей подстроки; добавленный символ; код этой строки>. Cheia de căutare pe 20 de biți este formată folosind primele două elemente stocate în tabel ca un singur număr (cheie). Cei 12 biți inferiori ai acestui număr sunt dați pentru cod, iar următorii 8 biți pentru valoarea simbolului.

Aici este folosită ca funcție hash:

Index(cheie)= ((tasta >> 12) ^ cheie) & 8191;

Unde >> este o deplasare pe biți la dreapta (tasta >> 12 - obținem valoarea caracterului), ^ este o operație logică exclusivă pe biți și o operație logică pe biți AND.

Astfel, pentru un număr numărat de comparații, obținem codul dorit sau un mesaj că nu există un astfel de cod în tabel.

Să calculăm cele mai bune și cele mai slabe rapoarte de compresie pentru acest algoritm. Cel mai bun coeficient, evident, va fi obținut pentru un lanț de octeți identici de mare lungime (adică pentru o imagine de 8 biți, toate punctele care au, pentru certitudine, culoarea 0). În același timp, în rândul 258 al tabelului vom scrie șirul „0, 0”, în rândul 259 - „0, 0, 0”, ... în rândul 4095 - un șir de 3839 (=4095-256 ) zerouri. În acest caz, vor intra în flux 3840 de coduri (verificați conform algoritmului!), inclusiv codul de curățare. Prin urmare, calculând suma progresiei aritmetice de la 2 la 3839 (adică lungimea lanțului comprimat) și împărțind-o la 3840*12/8 (coduri de 12 biți sunt scrise în flux), obținem cel mai bun raport de compresie .

Un exercitiu: Calculați valoarea exactă a celui mai bun raport de compresie. O sarcină mai dificilă: calculați același coeficient, ținând cont de observația 1.

Un exercitiu: Scrieți un algoritm pentru generarea unor astfel de lanțuri. Încercați să comprimați fișierul obținut în acest mod cu arhivare standard (zip, arj, gz). Dacă obțineți compresie, atunci algoritmul de generare este scris incorect.

LZW este implementat în formatele GIF și TIFF.

Caracteristicile algoritmului LZW:

Rate de compresie: Aproximativ 1000, 4, 5/7 (cele mai bune, medii, cele mai proaste rapoarte). Comprimarea de 1000 de ori se realizează numai pe imagini cu o singură culoare care sunt un multiplu de aproximativ 7 MB.

Clasa de imagine: LZW se concentrează pe imagini pe 8 biți construite pe un computer. Compresele datorate acelorași sublanțuri din flux.

Simetrie: Aproape simetric, sub rezerva implementării optime a operației de căutare a rândurilor în tabel.

Caracteristici: Situația în care algoritmul mărește imaginea este extrem de rară. LZW este universal - variantele sale sunt utilizate în arhivatoarele convenționale.

Algoritmul clasic Huffman

Unul dintre algoritmii clasici cunoscuți încă din anii 60. Utilizează numai frecvența de apariție a octeților identici în imagine. Mapează caracterele din fluxul de intrare care apar de mai multe ori la un șir de biți mai scurt. Și, dimpotrivă, rar - un lanț de lungime mai mare. Pentru a colecta statistici, este nevoie de două treceri peste imagine.

Mai întâi, să introducem câteva definiții.

Definiție. Fie alfabetul Y =( A 1, ..., a r ) format dintr-un număr finit de litere. O secvență finită de caractere din Y

vom suna cuvântîn alfabetul Y și numărul n - lungimea cuvântului A. Lungimea unui cuvânt se notează ca la).

Fie dat alfabetul W, W =( b 1 , ..., b q ). Prin B notează cuvântul în alfabetul W și prin S (W)este mulțimea tuturor cuvintelor nevide din alfabetul W .

Lăsa S =S(Y) -setul tuturor cuvintelor nevide din alfabetul Y și S"- un subset al setului S. Să fie și maparea F, care fiecare cuvânt A, A? S(Y), se potrivește cu cuvântul

B=F(A), B ? S(W) .

Cuvânt LA vom suna codul mesajului A, și trecerea de la cuvânt A la codul lui - codificare.

Definiție. Luați în considerare corespondența dintre literele alfabetului Y și unele cuvinte ale alfabetului W:

A 1 - B 1 ,
A 2 - B 2 ,
. . .
A r- B r

Această corespondență se numește sistemși notat cu S. Definește codificarea după cum urmează: fiecare cuvânt de la S" (W)=S (W)se potrivește cu un cuvânt numit cod de cuvânt A. Cuvinte B 1 ... B r numit coduri elementare. Acest tip de codare se numește codificare alfabetică.

Definiție. Lasă cuvântul LA are forma

B=B"B"

Apoi cuvântul B" numit start sau prefix de cuvânt B, a B" - sfârşitul unui cuvânt B. În acest caz, cuvântul L gol și cuvântul însuși B sunt considerate începutul și sfârșitul unui cuvânt B .

Definiție . Schema S are proprietatea prefixului, dacă pentru oricareiși j(1? i , j? r, eu? j) cuvânt B inu este un prefix de cuvânt B j .

Teorema 1. Dacă schema S are proprietatea prefixului, atunci codificarea alfabetică va fi unu-la-unu.

Să presupunem că ni se dă alfabetul Y =( A 1 ,..., A r} (r >1 ) și un set de probabilități p 1 , . . . , p r apariția simbolurilor A 1 ,..., A r. Să fie dat, în continuare, alfabetul W, W =( b 1 , ..., b q} (q >1 ). Apoi este posibil să se construiască o serie întreagă de scheme S de codificare alfabetică

a 1 - B 1 ,
. . .
A r- B r

având proprietatea unicităţii reciproce.

Pentru fiecare circuit, puteți introduce o lungime medie l mier , definit ca așteptarea matematică a lungimii codului elementar:

- lungimea cuvintelor.

Lungime l mier arată de câte ori crește lungimea medie a cuvântului la codificarea cu schema S .

Se poate arăta că l mier atinge minimul său l * pe unele S și este definită ca

Definiție . Codurile definite de schema S cul cf = l * , sunt numite coduri cu redundanță minimă, sau codurile Huffman.

Codurile cu redundanță minimă dau, în medie, creșterea minimă a lungimii cuvintelor cu codificarea corespunzătoare.

În cazul nostru, alfabetul Y =( A 1 ,..., A r) specifică simbolurile fluxului de intrare, iar alfabetul W =(0,1), adică. este format doar din zero și unu.

Algoritmul pentru construirea circuitului S poate fi reprezentat astfel:

Pasul 1. Aranjam toate literele alfabetului de intrare în ordinea descrescătoare a probabilității. Numărând toate cuvintele care se potrivesc B idin alfabetul W =(0,1) sunt goale.

Pasul 2 Combinând două personaje un i r-1și un i rcel mai putin probabil pi r-1și pi rla un pseudo personaj A"{un i r-1 aer ) cu probabilitate pi r-1+pi r. Adăugați 0 la începutul cuvântului B i r-1(B i r-1=0B i r-1 ), și 1 la începutul cuvântului B i r(B i r=1B i r).

Pasul 3 Eliminarea dintr-o listă de caractere ordonate un i r-1și un i r, pune un pseudo-simbol acolo A"{un i r-1 aer ). Efectuăm pasul 2, adăugând, dacă este necesar, 1 sau zero pentru toate cuvintele B i, corespunzătoare pseudo-caracterelor, până când 1 pseudo-caracter rămâne în listă.

Exemplu: Să presupunem că avem 4 litere în alfabetul Y =( A 1 ,..., A 4 } (r =4 ), p 1 =0.5, p 2 =0.24,p 3 =0.15,p 4 =0,11. Apoi procesul de construire a circuitului poate fi reprezentat după cum urmează:

Efectuând acțiunile corespunzătoare pasului 2, obținem un pseudo-caracter cu o probabilitate de 0,26 (și atribuim 0 și 1 cuvintelor corespunzătoare). Repetând aceste acțiuni pentru lista modificată, obținem un pseudo-simbol cu ​​o probabilitate de 0,5. Și în sfârșit, în ultimul pas, obținem o probabilitate totală de 1.

Pentru a restabili cuvintele de codificare, trebuie să urmărim săgețile de la caracterele inițiale până la sfârșitul arborelui binar rezultat. Deci, pentru un simbol cu ​​o probabilitate p 4 , obținem B 4 =101, pentru p 3 obținem B 3 =100, pentru p 2 obținem B 2 =11, pentru p 1 obținem B 1 =0. Ce înseamnă schema: A 1 - 0,
A 2 - 11
A 3 - 100
A 4 - 101 Această schemă este un cod prefix care este un cod Huffman. Personajul care apare cel mai frecvent în flux A 1 vom codifica cel mai scurt cuvânt 0 și cel mai puțin frecvent A 4 cuvânt lung 101.

Pentru o secvență de 100 de caractere în care personajul A 1 se va întâlni de 50 de ori, simbol A 2 - de 24 de ori, simbol A 3 - de 15 ori, și simbolul A 4 - De 11 ori, acest cod vă va permite să obțineți o secvență de 176 de biți ( ). Acestea. în medie vom cheltui 1,76 biți pe simbol de flux.

Pentru dovezi ale teoremei, precum și pentru faptul că circuitul construit definește de fapt un cod Huffman, vezi .

După cum a devenit clar din cele de mai sus, algoritmul clasic Huffman necesită scrierea unui tabel de corespondență de caractere codificate și lanțuri de codare într-un fișier.

În practică, se folosesc soiurile sale. Astfel, în unele cazuri este rezonabil fie să folosiți un tabel constant, fie să îl construiți „adaptativ”, adică. în proces de arhivare/dezarhivare. Aceste trucuri ne scutesc de două treceri peste imagine și de nevoia de a stoca tabelul împreună cu fișierul. Codarea tabelului fix este folosită ca ultimul pas în arhivarea JPEG și în algoritmul CCITT Grupul 3 discutat mai jos.

Caracteristicile algoritmului clasic Huffman:

Raport de compresie: 8, 1,5, 1 (cea mai bună, medie, cea mai slabă cotă).

Clasa de imagine: Aproape niciodată aplicat imaginilor pure. Utilizat de obicei ca unul dintre pașii de compresie în circuitele mai complexe.

Simetrie: 2 (datorită faptului că necesită două treceri prin matricea de date comprimate).

Caracteristici: Singurul algoritm care nu mărește dimensiunea datelor originale în cel mai rău caz (cu excepția necesității de a stoca tabelul de căutare împreună cu fișierul).

O modificare similară a algoritmului este utilizată la comprimarea imaginilor alb-negru (un bit per pixel). Numele complet al acestui algoritm este CCITT Group 3. Aceasta înseamnă că acest algoritm a fost propus de al treilea grup de standardizare al Comitetului Consultativ Internațional pentru Telegrafie și Telefonie (Comitetul Consultativ Internațional pentru Telegrafie și Telefonie). Secvențele de puncte albe și negre consecutive din el sunt înlocuite cu un număr egal cu numărul lor. Și această serie, la rândul său, este comprimată conform lui Huffman cu o masă fixă.

Definiție: Se numește un set de puncte de imagine consecutive de aceeași culoare serie.Lungimea acestui set de puncte se numeste lungimea seriei.

Tabelul de mai jos definește două tipuri de coduri:

• Codurile de completare a seriei- setați de la 0 la 63 în trepte de 1.
• Coduri compuse (suplimentare).- sunt setate de la 64 la 2560 în trepte de 64.

În practică, în acele cazuri în care imaginea este dominată de negru, inversăm imaginea înainte de comprimare și scriem informații despre aceasta în antetul fișierului.

Algoritmul de compresie arată astfel:

pentru (pe toate liniile imaginii) (
Convertiți șirul într-un set de lungimi de rulare;
pentru (pe toată seria) (
dacă (serie albă) (
L= lungimea seriei;
în timp ce(L > 2623) ( // 2623=2560+63
L=L-2560;
WriteWhiteCodeFor(2560);
}
dacă (L > 63) (
L2=MaximumConstCodeLessL(L);
L=L-L2;
WriteWhiteCodeFor(L2);
}
WriteWhiteCodeFor(L);
//Acesta este întotdeauna un cod de ieșire
}
altceva(
[Cod similar cu seria albă,
cu deosebirea că sunt scrise
coduri negre]
}
}
// Sfârșitul liniei imaginii
}

Deoarece seria alb-negru alternează, codul pentru seria albă și codul pentru seria neagră vor funcționa alternativ.

În ceea ce privește expresiile regulate, vom obține pentru fiecare linie a imaginii noastre (suficient de lungă, începând cu un punct alb) un flux de biți de ieșire de forma:

((<Б-2560>)*[<Б-сст.>]<Б-зв.>(<Ч-2560>)*[<Ч-сст.>]<Ч-зв.>) +

[(<Б-2560>)*[<Б-сст.>]<Б-зв.>]

Unde ()* - se repetă de 0 sau de mai multe ori, () + .- se repetă de 1 sau de mai multe ori, - include de 1 sau 0 ori.

Pentru exemplul de mai sus: 0, 3, 556, 10... algoritmul va genera următorul cod:<Б-0><Ч-3><Б-512><Б-44><Ч-10>, sau, conform tabelului, 00110101 10 0110010100101101 0000100 (diferitele coduri din fir sunt evidențiate pentru comoditate). Acest cod are proprietatea codurilor de prefix și poate fi pliat cu ușurință într-o secvență de lungimi de rulare. Este ușor de calculat că pentru șirul dat de 569 de biți, avem un cod de 33 de biți, adică. raportul de compresie este de aproximativ 17 ori.

Întrebare: De câte ori va crește dimensiunea fișierului în cel mai rău caz? De ce? (Răspunsul dat în specificațiile algoritmului nu este complet, deoarece pot exista valori mai mari ale celui mai slab raport de compresie. Găsiți-le.)

Un exercitiu: Având în vedere un șir de imagine scris ca lungimi de rulare - 442, 2, 56, 3, 23, 3, 104, 1, 94, 1, 231, 120 de octeți ((442+2+..+231)/8). Calculați raportul de compresie al acestui șir folosind algoritmul CCITT Group 3.

Tabelul codurilor de completare:

Tabel de coduri compus:

Acest algoritm este implementat în format TIFF.

Caracteristicile algoritmului CCITT Grupa 3

Chiar și acum 10-15 ani, arhivatoarele erau folosite în principal pentru a economisi spațiu pe hard disk și pentru a încadra cât mai multe date pe o dischetă. Cu toate acestea, vremurile s-au schimbat. Nimeni nu a folosit dischete ca mijloc de transfer și stocare a informațiilor de mult timp, iar costul unităților a devenit atât de mic încât nimeni nu se gândește măcar la comprimarea datelor pentru a economisi spațiu. În plus, volumele de date au devenit atât de mari încât arhivarea și dezarhivarea lor pentru a economisi spațiu pur și simplu nu este practică, deoarece este nevoie de mult timp. Ei bine, într-adevăr, astăzi cantitatea de date de pe unitățile utilizatorilor este măsurată în terabytes. Acum imaginați-vă cât de mult ar dura să arhivați un terabyte de date. Acest lucru va dura nu una sau chiar două ore, ci cel puțin 10-12 ore, adică computerul va trebui lăsat pornit toată noaptea.

S-ar părea că arhivatorii de astăzi ar trebui să-și piardă treptat relevanța. Dar nu se întâmplă nimic de genul acesta. Marea majoritate a utilizatorilor, printre alte programe, au arhivare instalate sau folosesc un arhivator încorporat în sistemul de operare Windows (nu luăm în considerare alte sisteme de operare în această publicație).

Cert este că numirea arhivarilor s-a schimbat. Astăzi sunt folosite în principal pentru postarea datelor pe Web. Majoritatea driverelor de pe site-urile producătorilor sunt așezate în arhive, iar majoritatea programelor din diverse resurse sunt, de asemenea, arhivate. Apropo, utilizatorul însuși, înainte de a încărca orice date în rețea (de exemplu, în resursele de partajare a fișierelor), împachetează datele într-o arhivă.

În ceea ce privește piața rusă, avem trei cele mai comune arhivare: WinRAR, WinZip și 7-Zip, prezentate în ambele versiuni pe 32 și 64 de biți. Pe ei îi vom compara în acest articol. Cu toate acestea, mai întâi să luăm în considerare pe scurt câteva aspecte teoretice ale muncii arhivatorilor.

Algoritmi de compresie a informațiilor

Esența oricărui algoritm de compresie a informațiilor constă în obținerea, printr-o transformare a setului inițial de biți de informație, a unui set de dimensiuni mai mici la ieșire. Mai mult, toți algoritmii de transformare a datelor pot fi împărțiți condiționat în două clase: reversibili și ireversibili.

Un algoritm ireversibil de compresie a informațiilor înseamnă o astfel de transformare a secvenței de biți inițiale, în care secvența de ieșire de o dimensiune mai mică nu permite ca secvența de intrare să fie restaurată exact. Algoritmii de compresie ireversibili sunt utilizați, de exemplu, în legătură cu datele grafice, video și audio, iar acest lucru duce întotdeauna la o pierdere a calității acestora. Desigur, algoritmii pentru compresia ireversibilă a datelor nu sunt utilizați în arhivare și, prin urmare, nu îi vom lua în considerare în continuare.

Algoritmii reversibile de comprimare a datelor vă permit să restaurați exact secvența de date inițială din secvența comprimată. Acești algoritmi sunt folosiți în arhivare. Caracteristicile comune tuturor algoritmilor de compresie sunt raportul de compresie (raportul dintre volumele secvenței de date originale și comprimate), rata de compresie (timpul petrecut arhivând o anumită cantitate de date) și calitatea compresiei (o valoare care indică cât de mult). secvența de date este comprimată prin aplicarea recomprimării acesteia după același algoritm sau alt algoritm).

Teoria compresiei informației, cunoscută și sub numele de teoria codificării economice a informațiilor discrete, este o ramură destul de complexă a științei matematice. Desigur, prezentarea chiar și a elementelor de bază depășește cu mult scopul acestui articol și, prin urmare, vom lua în considerare doar superficial diverși algoritmi de compresie a informațiilor, fără a intra în detalii. În plus, astăzi au fost dezvoltați o mulțime de algoritmi de compresie a datelor, iar luarea în considerare a acestora face, de asemenea, parte din sarcina noastră. Prin urmare, vom vorbi doar la nivel calitativ despre mai mulți algoritmi care ne permit să ne facem o idee generală despre metodele de comprimare a informațiilor.

Algoritmul RLE

Una dintre cele mai vechi și simple metode de compresie a informațiilor este algoritmul RLE (Run Length Encoding), adică algoritmul pentru codificarea serii de secvențe. Această metodă este foarte simplu de implementat și este unul dintre algoritmii de arhivare, iar esența ei este înlocuirea unei serii (grup) de octeți repeți cu un octet de codificare și un numărător pentru numărul de repetări ale acestora. Adică, un grup de octeți identici va fi înlocuit cu o pereche:<счетчик повторений, значение>, ceea ce reduce redundanța datelor.

În acest algoritm, semnul contorului este cel din primii doi biți ai octetului citit. De exemplu, dacă primii doi biți sunt 11, atunci cei 6 biți rămași sunt alocați contorului, care poate lua valori de la 1 la 64. În consecință, o serie de 64 de biți repeți poate fi definită cu doar doi octeți, adică este, comprimat de 32 de ori.

Există o altă implementare a acestui algoritm, când semnul contorului este 1 în primul octet al contorului. În acest caz, contorul poate lua o valoare maximă de 127 - și, prin urmare, raportul maxim de compresie va fi 64.

Este clar că algoritmul RLE este eficient doar atunci când există un număr mare de grupuri lungi de octeți identici. Dacă octeții nu sunt repeți, atunci utilizarea metodei RLE duce la o creștere a dimensiunii fișierului.

Metoda RLE este în general foarte eficientă pentru comprimarea graficelor bitmap (BMP, PCX, TIF, GIF) deoarece acestea conțin serii foarte lungi de secvențe de octeți care se repetă.

Restricție alfabetică a informațiilor

O altă modalitate destul de simplă de comprimare a informațiilor poate fi numită restricția alfabetului informațional. Observăm imediat că în practică un astfel de algoritm nu este implementat, dar prezentarea acestei metode va ajuta la înțelegerea mai bună a metodei codurilor de lungime variabilă.

În cele ce urmează, prin alfabet informațional vom înțelege setul de simboluri folosite pentru codificarea secvenței informaționale. De exemplu, să presupunem că există un mesaj text. Fiecare literă a acestui mesaj este codificată folosind un tabel ASCII format din 256 de caractere. În acest caz, exact 8 biți (1 octet) sunt alocați pentru codificarea fiecărui caracter. În acest caz, alfabetul de informații este format din toate 256 de caractere ale tabelului de codificare ASCII.

Este clar că nu toate cele 256 de caractere ale tabelului ASCII pot fi folosite în mesajul text original. De exemplu, dacă vorbim despre un mesaj text în limba rusă, în care nu există numere, atunci sunt suficiente 64 de caractere (33 de litere mici și 31 de litere mari). Dacă adăugăm la aceasta semne de punctuație, semne de paragraf și semne de linie nouă, devine clar că numărul de caractere nu va depăși 100. În acest caz, puteți utiliza codificarea caracterelor nu pe 8, ci pe 7 biți, care vă permite să obțineți un tabel de 128 de caractere. Adică, limităm, așa cum ar fi, alfabetul informațional, datorită căruia putem reduce adâncimea de biți a fiecărui caracter colat. Puteți merge mai departe - pentru a determina cu exactitate numărul de caractere utilizate într-un mesaj text. Dacă, de exemplu, se dovedește că în mesaj sunt folosite doar 30 de caractere (inclusiv liniile noi), atunci poate fi utilizat un tabel de codare de 5 biți care conține 32 de caractere, iar atunci raportul de compresie al mesajului text va deveni și mai mare. Într-adevăr, dacă în mesajul original este folosită codificarea caracterelor pe 8 biți, iar în mesajul comprimat este folosită codificarea caracterelor pe 5 biți, atunci raportul de compresie va fi 8/5.

În ciuda simplității aparente a metodei de limitare a alfabetului, în practică nu este folosit. Faptul este că metoda descrisă nu permite decodarea corectă a mesajului original fără a transfera informații suplimentare. Într-adevăr, fără a cunoaște tabelele de codificare folosite pentru comprimarea informațiilor, este imposibil să o decodați. Adică, împreună cu secvența de informații codificate, este necesar să se transmită tabele de codificare. Este clar că în acest caz câștigul din utilizarea unui alfabet limitat este redus la zero.

Metoda cu alfabet restricționat are și alte dezavantaje. Dacă mesajul de informare original conține un număr mare de caractere diferite, atunci nu va fi posibilă reducerea adâncimii de biți a reprezentării caracterelor alfabetice, iar această metodă pur și simplu nu va funcționa. Să presupunem, de exemplu, că mesajul informativ original conține 129 de caractere dintr-un alfabet de 256 de caractere. În acest caz, nu va fi posibilă utilizarea codării de caractere pe 7 biți, deoarece 7 biți vor codifica doar 128 de caractere. Prin urmare, pentru 129 de caractere, va trebui să utilizați aceeași codare de 8 biți ca în alfabetul original de 256 de caractere.

Coduri de lungime variabilă

Unul dintre principalele dezavantaje ale metodei de restricție alfabetică ipotetică pe care am luat-o în considerare este că folosește un cod uniform atunci când toate caracterele alfabetului informațional au aceeași lungime (8,7 biți sau mai puțin). Ar fi mai logic să se folosească un astfel de sistem de codificare în care lungimea codului caracterelor depinde de frecvența apariției acestuia în mesajul de informare. Adică, dacă în mesajul informațional original unele caractere apar mai des decât altele, atunci este optim ca aceștia să folosească coduri scurte, iar pentru caracterele care apar rar, să folosească coduri mai lungi.

Ca exemplu ipotetic, luați în considerare următorul mesaj informațional: "accident aerian" , care conține 14 caractere. Să presupunem că avem un alfabet de 14 caractere care ne permite să codificăm acest mesaj. Dacă se folosește un cod uniform, atunci sunt necesari 4 biți pentru fiecare caracter al alfabetului (o lungime a codului de 4 biți va forma 16 caractere). Cu toate acestea, este ușor de observat că în mesajul nostru informativ simbolul „a” apare de cinci ori, simbolul „t” - de două ori, iar restul simbolurilor - o dată. Dacă pentru simbolul „a” folosim un cod de 2 biți, pentru simbolul „t” - 3 biți, iar pentru restul caracterelor - 4 biți, atunci cu siguranță putem salva. Este necesar doar să înțelegeți cum să construiți exact coduri de lungime variabilă și cum exact lungimea codului ar trebui să depindă de frecvența simbolului din mesajul de informare.

Dacă toate caracterele sunt incluse în mesajul de informații cu aceeași frecvență (echiprobabil), atunci cu un alfabet informațional de N caractere, fiecare caracter va trebui să fie codificat exact jurnalul 2 N pic. De fapt, acesta este un caz de cod uniform.

Dacă simbolurile au probabilități diferite de a apărea în mesajul de informare, atunci, conform teoriei lui K. Shannon, simbolul, a cărui probabilitate este egală cu p, este optim și, ceea ce este deosebit de important, este teoretic posibil să asociați un cod de lungime -log 2 p. Revenind la exemplul nostru cu mesajul informativ „accident aerian” și având în vedere că probabilitatea de apariție a caracterului „a” (p(a)) este 5/14, probabilitatea de apariție a caracterului „t” este 2 /14, iar probabilitatea de apariție a tuturor celorlalte caractere este 1 /14, obținem că: pentru caracterul „a”, lungimea optimă a codului este -log 2 (5/14) = 1,48 biți; pentru caracterul „t” - -log 2 (2/14) = 2,8 biți, iar pentru toate celelalte caractere este -log 2 (1/14) = 3,8. Deoarece în cazul nostru lungimea codului poate avea doar o valoare întreagă, atunci, rotunjind în sus, obținem că pentru simbolul „a” este optim să folosim un cod de 2 biți, pentru simbolul „t” - 3 biți și pentru restul - 4 biți.

Să calculăm raportul de compresie atunci când folosim această codificare. Dacă s-ar folosi un cod uniform bazat pe un alfabet de 14 caractere, atunci ar fi necesari 56 de biți pentru a codifica cuvântul „accident aerian”. Când utilizați coduri de lungime variabilă, vor fi necesari 5×2 biți + 2×3 biți + 7×4 biți = 44 de biți, adică raportul de compresie va fi de 1,27.

Acum luați în considerare algoritmii pentru obținerea codurilor de lungime variabilă.

codificarea prefixului

Cea mai simplă metodă de obținere a codurilor de lungime variabilă este așa-numita codare de prefix, care permite obținerea de coduri cu lungime întreagă. Caracteristica principală a codurilor de prefix este că, în cadrul fiecăruia dintre sistemele lor, codurile mai scurte nu coincid cu începutul (prefixul) codurilor mai lungi. Această proprietate a codurilor de prefix este cea care face foarte ușor decodarea informațiilor.

Să explicăm această proprietate a codurilor de prefix cu un exemplu specific. Să existe un sistem de trei coduri de prefix: (0, 10, 11). După cum puteți vedea, codul mai scurt 0 nu coincide cu începutul codurilor mai lungi 10 și 11. Fie că codul 0 specifică caracterul „a”, codul 10 caracterul „m”, iar codul 11 ​​caracterul „p”. Apoi cuvântul „cadru” este codificat de secvența 110100. Să încercăm să decodificăm această secvență. Deoarece primul bit este un 1, primul caracter poate fi doar „m” sau „p” și este determinat de valoarea celui de-al doilea bit. Deoarece al doilea bit este 1, primul caracter este „p”. Al treilea bit este 0 și se potrivește în mod unic cu caracterul „a”. Al patrulea bit este 1, adică trebuie să vă uitați la valoarea următorului bit, care este 0, apoi al treilea caracter este „m”. Ultimul bit este 0, care se potrivește în mod unic cu caracterul „a”. Astfel, proprietatea codurilor de prefix, care constă în faptul că codurile mai scurte nu pot coincide cu începutul codurilor mai lungi, face posibilă decodarea fără ambiguitate a unui mesaj de informare codificat cu coduri de prefix de lungime variabilă.

Codurile de prefix sunt obținute de obicei prin arbori de coduri de construcție (pentru sistemul binar). Fiecare nod intern al unui astfel de arbore binar are două margini de ieșire, cu o margine corespunzătoare simbolului binar „0”, iar cealaltă - „1”. Pentru certitudine, putem fi de acord că marginii din stânga ar trebui să primească simbolul „0”, iar marginea dreaptă - simbolul „1”.

Deoarece nu pot exista cicluri într-un arbore, poate exista întotdeauna o singură rută de la nodul rădăcină la nodul frunză. Dacă marginile arborelui sunt numerotate, atunci fiecare astfel de rută corespunde unei secvențe binare unice. Setul tuturor acestor secvențe va forma un sistem de coduri de prefix.

Pentru exemplul considerat al unui sistem de trei coduri de prefix: (0, 10, 11), care definesc simbolurile „a”, „m” și „p”, arborele de coduri este prezentat în Fig. unu.

Orez. 1. Arborele de cod pentru sistem
din trei coduri de prefix: (0, 10, 11)

Comoditatea reprezentării arborescente a codurilor de prefix constă în faptul că structura arborescentă face posibilă formarea de coduri de lungime variabilă care îndeplinesc condiția principală a codurilor de prefix, adică condiția ca codurile mai scurte să nu coincidă cu începutul codurilor mai lungi.

Până acum, am luat în considerare doar ideea codurilor de prefix cu lungime variabilă. În ceea ce privește algoritmii de obținere a codurilor de prefix, aceștia pot fi dezvoltați destul de mult, dar cele mai cunoscute sunt două metode: Shannon-Fano și Huffman.

Algoritmul Shannon-Fano

Acest algoritm pentru obținerea codurilor de prefix a fost propus independent de R. Fano și K. Shannon, este după cum urmează. La primul pas, toate simbolurile secvenței de informații inițiale sunt sortate în probabilități descrescătoare sau crescătoare ale apariției lor (frecvențele de apariție a lor), după care seria ordonată de simboluri dintr-un loc este împărțită în două părți, astfel încât în ​​fiecare dintre ele suma frecvențelor simbolului este aproximativ aceeași. Ca o demonstrație, luați în considerare cuvântul deja familiar "accident aerian" .

Dacă caracterele care alcătuiesc un anumit cuvânt sunt sortate în ordinea descrescătoare a frecvenței lor de apariție, atunci obținem următoarea succesiune: (a(5), m(2), b(1), u(1), k( 1), c(1), p(1), o(1), f(1)) (în paranteze este indicată frecvența de repetare a unui simbol într-un cuvânt). În continuare, trebuie să împărțim această secvență în două părți, astfel încât în ​​fiecare dintre ele suma frecvențelor simbolurilor să fie aproximativ aceeași (pe cât posibil). Este clar că secțiunea va trece între simbolurile „t” și „c”, în urma cărora se formează două secvențe: (a (5), t (2)) și (în (1), u (1). ), k (1), c(1), p(1), o(1), φ(1)). Mai mult, sumele frecvențelor de repetare a simbolurilor din prima și a doua secvență vor fi aceleași și egale cu 7.

La primul pas de împărțire a unei secvențe de caractere, obținem prima cifră a codului fiecărui caracter. Regula aici este simplă: pentru acele caractere care sunt în secvența din stânga, codul va începe cu „0”, iar pentru cele din dreapta - cu „1”.

În special, secvența (a(5), m(2)) se va împărți în două caractere separate: a(5) și m(2) (nu există alte opțiuni de împărțire). Apoi, a doua cifră a codului pentru simbolul „a” este „0”, iar pentru simbolul „t” - „1”. Deoarece, ca urmare a împărțirii secvenței, am primit elemente separate, acestea nu mai sunt împărțite și pentru caracterul „a” obținem codul 00, iar pentru caracterul „t” - codul 01.

Sirul (in(1), u(1), k(1), c(1), p(1), o(1), f(1)) poate fi impartit fie in secvente (in(1), u(1), k(1)) și (c(1), p(1), o(1), φ(1)), sau pe (v(1), u(1), k(1) ), (c(1)) și (p(1), o(1), φ(1)).

În primul caz, suma frecvențelor simbolurilor din prima și a doua secvență va fi 3 și, respectiv, 4, iar în al doilea caz, 4 și, respectiv, 3. Pentru certitudine, folosim prima opțiune.

Pentru caracterele din noua secvență rezultată (v(1), u(1), k(1)) (aceasta este secvența din stânga), primele două cifre ale codului vor fi 10, iar pentru secvența (c( 1), p(1), o(1), f(1)) - 11.

În exemplul nostru (Fig. 2 și 3), se obține următorul sistem de coduri de prefix: "a" - 00, "t" - 01, "c" - 100, "i" - 1010, "k" - 1011, "s" - 1100, "r" - 1101, "o" - 1110, "f" - 1111. După cum puteți vedea, codurile mai scurte nu sunt începutul codurilor mai lungi, adică proprietatea principală a codurilor de prefix este îndeplinită .

Orez. 2. Demonstrarea algoritmului Shannon-Fano

Orez. 3. Arborele de cod pentru cuvântul „accident aerian”
în algoritmul Shannon-Fano

Algoritmul Huffman

Algoritmul Huffman este un alt algoritm pentru obținerea codurilor de prefix cu lungime variabilă. Spre deosebire de algoritmul Shannon-Fano, care construiește arborele de cod de sus în jos, acest algoritm construiește arborele de cod în ordine inversă, adică de jos în sus (de la nodurile frunză la nodul rădăcină).

În prima etapă, ca și în algoritmul Shannon-Fano, succesiunea inițială de simboluri este sortată în ordinea descrescătoare a frecvenței de repetare a simbolurilor (elementele secvenței). Pentru exemplul discutat anterior cu cuvântul "accident aerian" obținem următoarea succesiune sortată de elemente: (a(5), m(2), b(1), u(1), k(1), c(1), p(1), o(1), f(1)).

În continuare, ultimele două elemente ale secvenței sunt înlocuite cu un nou element S1, căruia i se atribuie o recurență egală cu suma recurențelor elementelor originale. Apoi se realizează o nouă sortare a elementelor secvenței în funcție de recurența lor. În cazul nostru, ultimele două elemente o(1) și f(1) sunt înlocuite cu elementul S1(2), iar succesiunea nou sortată va lua forma: (a(5), m(2), S1( 2), c(1), u(1), k(1), c(1), p(1)).

Continuând această procedură de înlocuire a ultimelor două elemente ale secvenței cu un nou element cu recurență totală și resortarea ulterioară a secvenței în conformitate cu recurența elementelor, vom ajunge la o situație în care în secvență rămâne un singur element ( Fig. 4).

Orez. 4. Demonstrarea algoritmului Huffman
pe exemplul cuvântului „accident aerian”

Concomitent cu înlocuirea elementelor și resortarea secvenței, se construiește un arbore binar de cod. Algoritmul pentru construirea unui arbore este foarte simplu: operația de combinare (înlocuire) a două elemente dintr-o secvență generează un nou element nod pe arborele de cod. Adică dacă priviți arborele de jos în sus, marginile arborelui de cod provin întotdeauna din elementele înlocuite și converg către un nou element nod corespunzător elementului secvenței obținute prin înlocuire (Fig. 5). În acest caz, marginii din stânga a arborelui de coduri i se poate atribui valoarea „0”, iar marginea dreaptă - „1”. Aceste valori vor servi ulterior ca elemente ale codului de prefix.

Orez. 5. Construirea unui arbore de cod
în algoritmul Huffman
(înlocuind elementele „o” și „f”
element nou S1)

Arborele complet de coduri Huffman pentru un cuvânt "accident aerian" prezentată în fig. 6.

Orez. 6. Arborele de cod complet pentru cuvântul „accident aerian”,
construit conform algoritmului Huffman

Mergând de-a lungul marginilor arborelui de coduri de sus în jos, este ușor să obțineți coduri de prefix pentru toate caracterele alfabetului nostru informațional:

Acum, dacă încerci să scrii un cuvânt "accident aerian" în codificarea Huffman, obținem o secvență de 41 de biți 0 1101 11000 0 11001 0 111 0 1010 111 1011 1000 1001 0. Este interesant de remarcat că atunci când folosim codurile de prefix Shannon-Fano, obținem și o secvență de 41 biți. cuvântul „accident aerian”. Adică, într-un exemplu specific, eficiența de codare a lui Huffman și Shannon-Fano este aceeași. Dar dacă luăm în considerare faptul că alfabetul informațional real este de 256 de caractere (și nu 14, ca în exemplul nostru), iar secvențele de informații reale sunt fișiere de orice conținut și lungime, atunci se pune întrebarea despre codul de prefix optim, adică , codul care vă permite să obțineți lungimea minimă a secvenței de ieșire.

Se poate dovedi că sistemul de coduri obținut cu ajutorul algoritmului Huffman este cel mai bun dintre toate sistemele posibile de coduri de prefix în sensul că lungimea secvenței de informații codificate rezultată este minimă. Adică algoritmul Huffman este optim.

Principalul dezavantaj al algoritmului Huffman este complexitatea procesului de construire a unui sistem de coduri. Cu toate acestea, algoritmul Huffman optim este cel mai comun algoritm de generare a codului cu lungime variabilă și este încorporat în majoritatea utilităților pentru comprimarea și arhivarea informațiilor.

Codare aritmetică

După cum am observat deja, conform criteriului Shannon, codul optim este acela în care este atribuit un cod de lungime –log 2 pentru fiecare caracter. p pic. Și dacă, de exemplu, probabilitatea unui anumit caracter este 0,2, atunci lungimea optimă a codului său va fi -log 2 0,2 ​​= 2,3 biți. Este clar că codurile de prefix nu pot oferi o astfel de lungime a codului și, prin urmare, nu sunt optime. În general, lungimea codului determinată de criteriul Shannon este doar o limită teoretică. Singura întrebare este ce metodă de codare vă permite să vă apropiați cât mai mult de această limită teoretică. Codurile de prefix cu lungime variabilă sunt eficiente și destul de ușor de implementat, dar există metode de codare mai eficiente, în special algoritmul de codare aritmetică.

Ideea codificării aritmetice este că, în loc de a codifica caractere individuale, codul este atribuit simultan întregii secvențe de informații. În același timp, este evident că lungimea codului pentru un caracter individual poate să nu fie un număr întreg. De aceea, această metodă de codificare este mult mai eficientă decât codificarea cu prefix și este mai consistentă cu criteriul Shannon.

Ideea algoritmului de codare aritmetică este următoarea. Ca în toate metodele de codificare considerate anterior, fiecare simbol al secvenței de informații originale este caracterizat de probabilitatea sa. Secvenței inițiale necodificate i se atribuie o jumătate de interval)