Metodă simplă de codificare ( CODARE LUNGIME DE RUNARE), care este folosit cu succes de către arhivatorii populari.
Această metodă se bazează pe numărarea lungimii caracterelor repetate într-un rând și pe scrierea unor informații precum numărul de caractere și caracterul repetat în sine într-un fișier împachetat în loc de o secvență a acestor caractere. De exemplu, există un șir ca „ AAAAABBBCCCADDDEEL". Va fi împachetat într-o secvență ca" 5A3B3CADDEEL". După cum puteți vedea din exemplu, o secvență de 5 litere" A " a fost împachetat în două caractere " 5 " și " A ", iar secvențele " DD "," EE "," L "nu au fost împachetate deloc , deoarece nu există niciun câștig din înlocuirea acestor caractere cu o secvență de tip „lungime” + „litera”.
Când împachetați un fișier folosind această metodă, apar următoarele dificultăți: cum va distinge dezambalătorul 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 este întâlnit mai puțin decât celelalte 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” de către packer va fi convertită într-un prefix (8 biți), „A” (8 biți), număr (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 un cod prefix sunt scrieți în fișierul rezultat, iar prin acest semn, dezambalătorul va determina unde prefixul este un simbol și unde este informații de control. Sunt posibile modificări ale acestei metode, de exemplu:
1. Codificați cantitatea nu în opt biți, ci trei, patru și așa mai departe, ceea ce va crește procentul de împachetare, dar va limita în același timp 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ă de numărul egal cu 265. Se pune întrebarea cum se codifică 256 lungimi diferite în 3 biți. Se pare că este posibil, dar numai în intervalul de la 3 la 9, dacă lungimea caracterelor repetate este mai mare de 9, atunci trei biți sunt scriși „111” în cod binar, 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. Folosind metoda RLE (codare run-length - pachet de octeți repeți).
a) Luați un prefix 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, primul octet este octetul de prefix, astfel încât dezambalătorul să știe care octet este un prefix.
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 pentru modificarea 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țiProcent 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țiProcent 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țiProcent 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ți7, 0, „A”, „A”
3 biți 8 biți 8 biți 8 bițiProcent de compresie = 86 biți / (22 * 8) biți = 48,9%
Din aceste exemple, se poate observa că în funcție de conținutul datelor împachetate, unul sau altul algoritm este eficient, prin urmare, pentru a alege ce algoritm este mai eficient, este necesară verificarea acestora 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 este întâlnit în text, atunci un bit de control este scris în fișierul de ieșire, care este egal cu unul și acest caracter însuși. Dacă se întâlnește 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 aceasta luăm secvențele din exemplele anterioare.
1) Numărul de octeți repetați este codificat pe 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 luăm 3 biți pentru a codifica numărul de octeți repeți, în care puteți codifica 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 majoritatea covârșitoare. Prima opțiune a inclus secvențe care încep cu trei caractere.
Clasificarea de bază a algoritmilor de compresie reversibilă
Există multe practici de compresie fără pierderi care au, în general, eficiență diferită pentru diferite tipuri de date și pentru diferite dimensiuni. Cu toate acestea, aceste metode se bazează pe trei scheme de compresie clasice principale:
Codificarea seriei secvențe (RLE);
Metode statistice de compresie;
Dicţionar (euristic) compression methods.
Compresie prin codificare în serie: algoritm RLE
Cea mai cunoscută abordare simplă și algoritm pentru comprimarea informațiilor într-un mod reversibil este Run Length Encoding (RLE). Esența metodelor acestei abordări este de a înlocui șiruri sau serii de octeți care se repetă sau secvențele acestora cu un octet de codificare și un numărător al numărului de repetări ale acestora. Problema cu toate metodele analoge este de a determina modul în care algoritmul de decompresie ar putea distinge seria codificată din fluxul de octeți rezultat de altele - secvențele de octeți necodificate. Soluția problemei se obține de obicei prin plasarea de semne la începutul șirurilor codificate. Astfel de etichete pot fi, de exemplu, valori caracteristice de biți în primul octet al unei rulări codificate, valori ale primului octet al unei rulări codificate etc. Aceste metode, de regulă, sunt destul de eficiente pentru comprimarea imaginilor grafice raster (BMP, PCX, TIF, GIF), deoarece acestea din urmă conțin destul de multe serii lungi de secvențe repetate de octeți. Dezavantajul metodei RLE este raportul de compresie destul de scăzut sau costul codificării fișierelor cu un număr mic de serii și, chiar mai rău, cu un număr mic de octeți repeți într-o serie.
Algoritmul RLE se bazează pe ideea de a detecta secvențele de date repetate și de a le înlocui cu o structură mai simplă, care specifică codul de date și rata de repetiție. De exemplu, să presupunem că vi se oferă o secvență de date care este supusă comprimării: 1 1 1 1 2 2 3 4 4 4 ... Algoritmul RLE propune înlocuirea acestuia cu următoarea structură: 1 4 2 2 3 1 4 3 unde primul număr al fiecărei perechi de numere este codul de date și al doilea este rata de repetiție. Dacă se alocă 1 octet pentru a stoca fiecare element de date al secvenței de intrare, atunci întreaga secvență va ocupa 10 octeți de memorie, în timp ce secvența de ieșire (versiunea comprimată) va ocupa 8 octeți de memorie. Este clar că algoritmul RLE va oferi un efect de compresie mai bun atunci când lungimea secvenței de date repetitive este mai mare. În cazul exemplului de mai sus, dacă secvența de intrare arată astfel: 1 1 1 1 1 1 3 4 4 4, atunci raportul de compresie va fi de 60%. În acest sens, eficiența mai mare a algoritmului RLE se realizează la comprimarea datelor grafice (în special pentru imaginile monocrome).
Algoritmi euristici (dicționar). compresie (LZ, LZW) caută linii în fișier care sunt repetate și construiește un dicționar de fraze care au fost deja întâlnite. De obicei, astfel de algoritmi au o serie de parametri specifici (dimensiunea tamponului, lungimea maximă a frazei etc.), a căror selecție depinde de experiența autorului lucrării, iar acești parametri sunt selectați astfel încât să se obțină cea mai optimă raportul dintre timpul de funcționare al algoritmului, raportul de compresie și lista fișierelor care se micșorează bine.
Algoritmi statistici(Huffman, Shannon-Fano, aritmetică) Algoritmii statistici folosesc un model de date statistice, iar calitatea compresiei informațiilor depinde direct de cât de bun este acest model. Luarea în considerare a proprietăților statistice ale datelor în cel mai simplu caz înseamnă utilizarea codurilor neuniforme pentru codare - simbolurile care apar frecvent sunt codificate în coduri scurte și rar - în coduri lungi. Adică, astfel de algoritmi au nevoie de cunoștințe despre probabilitățile de apariție a caracterelor în imagine, a căror estimare poate fi, în cazul simplu, frecvența de apariție a caracterelor în datele de intrare. De obicei, aceste probabilități sunt necunoscute. Scopul codificării este de a converti fluxul de intrare într-un flux de biți de lungime minimă, ceea ce se realizează prin reducerea entropiei (haosului) fluxului de intrare luând în considerare frecvențele simbolului.
Lungimea codului care reprezintă caractere din alfabetul fluxului trebuie să fie proporțională cu cantitatea de informații din fluxul de intrare, iar lungimea simbolurilor fluxului în biți nu poate fi un multiplu de 8 sau chiar variabilă. Dacă se cunoaște distribuția de probabilitate a frecvențelor de apariție a simbolurilor din alfabetul fluxului de intrare, atunci se poate construi un model de codificare optim. Cu toate acestea, datorită existenței unui număr mare de formate de fișiere diferite, sarcina devine mult mai complicată. distribuția de frecvență a simbolurilor de date nu este cunoscută dinainte. În acest caz, sunt utilizate două abordări.
Primul constă în vizualizarea fluxului de intrare și codificarea construirii pe baza statisticilor colectate (aceasta necesită două treceri prin fișier - una pentru vizualizarea și colectarea informațiilor statistice, a doua pentru codificare, ceea ce limitează oarecum sfera unor astfel de algoritmi, deoarece, astfel, elimină posibilitatea de codare cu o singură trecere „din mers”, care este utilizată în sistemele de telecomunicații, unde cantitatea de date nu este uneori cunoscută, iar retransmisia sau analiza lor poate dura un timp nerezonabil de lung). Într-un astfel de caz, schema statistică a codificării utilizate este scrisă în fluxul de ieșire. Această tehnică este cunoscută sub numele de codare Huffman statică. Un tabel de simboluri este transferat cu fișierul comprimat. Astfel de algoritmi sunt destul de buni la comprimarea majorității fișierelor, dar este necesar un transfer suplimentar al tabelului de frecvență a simbolurilor, precum și necesitatea a două treceri ale fișierului sursă pentru a colecta statistici și a comprima.
Metoda a doua- metoda de codificare adaptivă. Principiul său este de a schimba schema de codare în funcție de natura modificărilor din fluxul de intrare. Adaptive - încep să lucreze cu un tabel inițial fix de frecvențe de simbol (de obicei toate simbolurile sunt la început la fel de probabile) și în acest proces acest tabel se modifică în funcție de simbolurile care se găsesc în fișier. Avantaje: algoritm cu o singură trecere, nu necesită transferul unui tabel de frecvențe de simboluri, comprimă o clasă largă de fișiere destul de eficient. Această abordare are un algoritm cu o singură trecere și nu necesită stocarea informațiilor despre codificarea utilizată într-o formă explicită. Codarea adaptivă poate oferi un raport de compresie mai mare decât codarea statică, deoarece modificările frecvențelor fluxului de intrare sunt luate în considerare mai pe deplin. Această tehnică este cunoscută sub numele de codare dinamică Huffman.
Având în vedere acest lucru, algoritmii statistici pot fi împărțiți în trei clase:
1. Neadaptative - folosesc probabilități fixe, predeterminate de simboluri. Tabelul de probabilitate simbol nu este transmis împreună cu fișierul, deoarece este cunoscut în prealabil. Dezavantaj: zonă îngustă de utilizare pentru un anumit tabel de frecvență, pentru care se obține un raport de compresie acceptabil.
2. Semi-adaptativ - un tabel de frecvențe simbol este construit pentru fiecare fișier și fișierul este comprimat pe baza acestuia. Un tabel de simboluri este transferat cu fișierul comprimat. Astfel de algoritmi sunt destul de buni la comprimarea majorității fișierelor, dar este necesar un transfer suplimentar al tabelului de frecvență a simbolurilor, precum și necesitatea a două treceri ale fișierului sursă pentru a colecta statistici și a comprima.
3. Adaptive - încep să lucreze cu un tabel inițial fix de frecvențe de simbol (de obicei toate simbolurile sunt la început la fel de probabile) iar în procesul de lucru acest tabel se modifică în funcție de simbolurile care se găsesc în fișier. Avantaje: algoritm cu o singură trecere, nu necesită transferul unui tabel de frecvențe de simboluri, comprimă o clasă largă de fișiere destul de eficient.
Algoritmul Huffman se bazează pe ideea de codificare în grupuri de biți. În primul rând, se efectuează o analiză de frecvență a secvenței de date de intrare, adică se stabilește frecvența de apariție a fiecărui simbol găsit în acesta. După aceea, caracterele sunt sortate în funcție de frecvența descrescătoare a apariției.
Ideea de bază este următoarea: cu cât apare mai des un caracter, cu atât este codificat mai puțini biți. Rezultatul codificării este introdus în dicționarul necesar pentru decodare. Să ne uităm la un exemplu simplu pentru a ilustra modul în care funcționează algoritmul Huffman.
În codarea statică Huffman, simbolurile de intrare (siruri de biți de diferite lungimi) sunt asociate cu șiruri de biți și, de asemenea, lungime variabilă - codurile lor. Lungimea codului fiecărui simbol este luată proporțional cu logaritmul binar al frecvenței acestuia, luată cu semnul opus. Și setul comun al tuturor simbolurilor diferite întâlnite formează alfabetul fluxului. Această codificare este un prefix, ceea ce face ușoară decodarea în fluxul de rezultate, deoarece, cu codificarea prefixului, codul oricărui caracter nu este un prefix al codului oricărui alt caracter - alfabetul este unic.
Chiar și în urmă cu 10-15 ani, arhivele erau folosite în principal pentru a economisi spațiu pe hard disk și pentru a încăpea cantitatea maximă de 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 nici 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 este pur și simplu nepractică, deoarece necesită mult timp. Într-adevăr, astăzi cantitatea de date de pe unitățile utilizatorilor este măsurată în terabytes. Acum imaginați-vă cât timp va dura să arhivați un terabyte de date. 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 acest fel. Marea majoritate a utilizatorilor, printre alte programe, au arhivare instalate sau folosesc arhivatorul încorporat în sistemul de operare Windows (nu luăm în considerare alte sisteme de operare în această publicație).
Cert este că scopul arhivatorilor s-a schimbat. Astăzi sunt folosite în principal pentru încărcarea datelor pe Web. Majoritatea driverelor de pe site-urile producătorilor sunt așezate în arhive, iar majoritatea programelor de pe 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ă, cele mai comune sunt trei arhivare: WinRAR, WinZip și 7-Zip, prezentate în ambele versiuni pe 32 și 64 de biți. Le vom compara în acest articol. Cu toate acestea, mai întâi vom analiza 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 faptul că printr-o oarecare transformare a setului inițial de biți de informație, la ieșire, se obține un anumit set de dimensiuni mai mici. Mai mult, toți algoritmii de conversie 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 inițiale de biți în care secvența de ieșire de o dimensiune mai mică nu permite ca secvența de intrare să fie reconstruită cu acuratețe. Algoritmi 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 ireversibili de compresie a datelor nu sunt utilizați în arhivare și, prin urmare, nu îi vom lua în considerare în viitor.
Algoritmii reversibile de comprimare a datelor vă permit să reconstruiți cu acuratețe secvența originală de date 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 necesar pentru a arhiva o anumită cantitate de date) și calitatea compresiei (valoarea care arată cât de mult este comprimată secvența de date prin aplicarea recomprimarii 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 și luarea în considerare a acestora este, de asemenea, inclusă în sarcina noastră. Prin urmare, vom vorbi doar la nivel calitativ despre mai mulți algoritmi care vă permit să vă faceți o idee generală despre metodele de compresie a informațiilor.
Algoritmul RLE
Una dintre cele mai vechi și simple metode de comprimare a informațiilor este algoritmul RLE (Run Length Encoding), adică un algoritm pentru codificarea unei 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 al numărului 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, contorul este indicat de cei din cei doi biți superiori ai octetului citit. De exemplu, dacă primii doi biți sunt 11, atunci cei 6 biți rămași sunt alocați unui contor, care poate lua valori de la 1 la 64. În consecință, o serie de 64 de biți repeți poate fi determinată cu doar doi octeți, adică este, comprimat de 32 de ori.
Există o altă variantă de implementare a acestui algoritm, când atributul 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 numai 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 crește dimensiunea fișierului.
Metoda RLE este, în general, foarte eficientă pentru comprimarea graficelor bitmap (BMP, PCX, TIF, GIF) deoarece acestea conțin atât de multe serii lungi de secvențe repetitive de octeți.
Restricționarea alfabetului informațional
O altă metodă destul de simplă de comprimare a informațiilor poate fi numită limitarea alfabetului informațional. Imediat, observăm că un astfel de algoritm nu a fost implementat în practică, dar prezentarea acestei metode va ajuta la înțelegerea mai bună a metodei codurilor de lungime variabilă.
În cele ce urmează, sub alfabetul informațional, ne referim la setul de caractere folosit pentru a codifica secvența informațională. De exemplu, să presupunem că există un mesaj text. Un tabel ASCII de 256 de caractere este folosit pentru a codifica fiecare literă a acestui mesaj. În acest caz, exact 8 biți (1 octet) sunt alocați pentru codificarea fiecărui caracter. În acest caz, alfabetul informațional 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ăugați semne de punctuație, semne de paragraf și linii noi, 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 într-un fel alfabetul informațional, datorită căruia putem reduce adâncimea de biți a fiecărui caracter care urmează să fie colocat. 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 implicate doar 30 de caractere (inclusiv caractere newline), atunci puteți utiliza un tabel de codificare pe 5 biți care conține 32 de caractere, iar apoi raportul de compresie al mesajului text va deveni și mai mare. . Într-adevăr, dacă mesajul original folosește codificarea caracterelor de 8 biți, iar cel comprimat folosește 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. Ideea 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 beneficiul utilizării unui alfabet limitat este redus la zero.
Metoda alfabetului mărginit are și alte dezavantaje. Dacă mesajul informativ original conține un număr mare de caractere diferite, atunci nu va fi posibilă reducerea capacității de cifre a caracterelor alfabetului, iar această metodă pur și simplu nu va funcționa. Să presupunem, de exemplu, că mesajul de date 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 permite doar codificarea a 128 de caractere. Prin urmare, pentru 129 de caractere, va trebui să reveniți la 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 ipotetice de limitare a alfabetului pe care am luat-o în considerare este că folosește un cod uniform atunci când toate simbolurile 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 codare în care lungimea codului caracterelor depinde de frecvența apariției acestuia în mesajul de informare. Adică dacă în mesajul de informare original se regăsesc mai des unele caractere decât altele, atunci este optim să se folosească coduri scurte pentru ele, iar pentru cele rare, altele mai lungi.
Ca exemplu ipotetic, luați în considerare următorul mesaj informațional: "Avion prăbușit" 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 face posibilă formarea a 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 caracterul „a” folosim un cod cu o lungime de 2 biți, pentru caracterul „t” - o lungime de 3 biți, iar pentru caracterele rămase - o lungime de 4 biți, atunci cu siguranță putem economisi bani. Este necesar doar să înțelegeți cum să construiți exact coduri de lungime variabilă și cât de exact ar trebui să depindă lungimea codului de frecvența de apariție a simbolului în mesajul de informare.
Dacă toate caracterele introduc mesajul de informare cu aceeași frecvență (la fel de probabilă), atunci cu un alfabet informativ de N caractere, pentru a codifica fiecare caracter, exact log 2 N pic. De fapt, acesta este cazul unui cod uniform.
Dacă simbolurile au probabilități diferite de apariție într-un mesaj de informare, atunci, conform teoriei lui K. Shannon, un simbol cu o probabilitate de apariție egală cu p este optim și, ceea ce este deosebit de important, este teoretic permisă asocierea unui cod de lungime. – log 2 p... Revenind la exemplul nostru cu mesajul informativ „accident de avion” și având în vedere că probabilitatea de apariție a simbolului „a” (p (a)) este 5/14, probabilitatea de apariție a simbolului „t” este 2 /14, iar probabilitatea apariției tuturor celorlalte simboluri este 1 / 14, obținem că: pentru caracterul „a” lungimea optimă a codului este –log 2 (5/14) = 1,48 biți; pentru simbolul „t” - –log 2 (2/14) = 2,8 biți, iar pentru toate celelalte simboluri este –log 2 (1/14) = 3,8. Deoarece în cazul nostru lungimea codului poate avea doar o valoare întreagă, atunci, rotunjind, obținem că pentru caracterul „a” este optim să folosim un cod cu lungimea de 2 biți, pentru caracterul „t” - o lungime de 3 biți, iar în rest - o lungime de 4 biți.
Să calculăm raportul de compresie 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 de avion”. Când utilizați coduri de lungime variabilă, sunt necesari 5 × 2 biți + 2 × 3 biți + 7 × 4 biți = 44 de biți, deci raportul de compresie este de 1,27.
Acum să ne uităm la algoritmi 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 vă permite să obțineți coduri de lungime întreagă. Caracteristica principală a codurilor de prefix este că în cadrul fiecăruia dintre sistemele lor, codurile mai scurte în lungime 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. Lăsați codul 0 să specifice caracterul „a”, codul 10 - caracterul „m”, iar codul 11 - caracterul „ p". Apoi cuvântul „cadru” este codificat cu secvența 110100. Să încercăm să decodificăm această secvență. Deoarece primul bit este 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 corespunde în mod unic caracterului „a”. Astfel, proprietatea codurilor de prefix 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 construirea de arbori de cod (pentru un sistem binar). Fiecare nod intern al unui astfel de arbore binar are două margini de ieșire, cu o margine corespunzătoare caracterului binar „0”, iar cealaltă - „1”. Pentru certitudine, putem fi de acord că marginea stângă ar trebui să fie asociată cu simbolul „0”, iar marginea dreaptă - simbolul „1”.
Deoarece nu pot exista cicluri în arbore, puteți crea î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 astfel de 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 sub formă de arbore a codurilor de prefix constă în faptul că structura arborescentă face posibilă generarea de coduri de lungime variabilă care îndeplinesc condiția principală a codurilor de prefix, adică condiția ca coduri mai scurte. nu coincid cu începutul codurilor mai lungi.
Până acum, ne-am uitat doar la ideea codurilor de prefix cu lungime variabilă. În ceea ce privește algoritmii de obținere a codurilor de prefix, sunt destul de mulți dintre ei, dar cele mai cunoscute sunt două metode: Shannon-Fano și Huffman.
Algoritmul Shannon-Fano
Acest algoritm de obținere a codurilor de prefix a fost propus independent de R. Fano și K. Shannon, constă în următoarele. La primul pas, toate simbolurile secvenței de informații inițiale sunt sortate în probabilitate descrescătoare sau crescătoare a apariției lor (frecvența apariției lor), după care rândul ordonat de simboluri este împărțit în două părți într-un loc, astfel încât în fiecare dintre ei suma frecvențelor simbolului este aproximativ aceeași. Ca o demonstrație, luați în considerare cuvântul deja familiar nouă "Avion prăbușit" .
Dacă simbolurile 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 secvență: (a (5), t (2), în (1) și (1), până la ( 1), c (1), p (1), o (1), f (1)) (frecvența de repetare a simbolului din cuvânt este indicată între paranteze). Î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 „b”, în urma cărora se formează două secvențe: (a (5), t (2)) și (în (1) și (1) ), la (1), c (1), p (1), o (1), φ (1)). În plus, sumele frecvenței de repetare a simbolurilor din prima și a doua secvențe vor fi aceleași și egale cu 7.
În primul pas de împărțire a unei secvențe de caractere, obținem prima cifră a codului fiecărui caracter. Regula este simplă: pentru acele caractere care apar î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 diviziuni). 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 individuale, acestea nu mai sunt împărțite și pentru simbolul „a” obținem codul 00, iar pentru simbolul „t” - codul 01.
Secvența (în (1), u (1), la (1), c (1), p (1), o (1), f (1)) poate fi împărțită fie în secvențe (în (1), și (1), k (1)) și (c (1), p (1), o (1), φ (1)), sau pe (în (1), u (1), k (1) ), (c (1)) și (p (1), o (1), φ (1)).
În primul caz, sumele ratelor de repetare a simbolurilor din prima și a doua secvență vor fi 3 și, respectiv, 4, iar în al doilea caz, 4 și, respectiv, 3. Din motive de claritate, vom folosi prima opțiune.
Pentru caracterele din noua secvență rezultată (în (1) și (1), până la (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 ), φ (1)) - 11.
În exemplul nostru (Fig. 2 și 3) se obține următorul sistem de coduri de prefix: "a" - 00, "t" - 01, "b" - 100, "u" - 1010, "k" - 1011, " c" - 1100, "p" - 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 de avion”
î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 prevede construirea arborelui de codificare de sus în jos, acest algoritm implică construirea arborelui de codificare în ordine inversă, adică de jos în sus (de la nodurile frunzei până la rădăcină). nodul).
În prima etapă, ca și în algoritmul Shannon-Fano, secvența originală de caractere este sortată în ordinea descrescătoare a frecvenței de repetare a caracterelor (elementele secvenței). Pentru exemplul de mai sus cu cuvântul "Avion prăbușit" obținem următoarea succesiune sortată de elemente: (a (5), t (2), în (1), u (1), k (1), c (1), p (1), o (1), φ (1)).
În plus, ultimele două elemente ale secvenței sunt înlocuite cu un nou element S1, căruia i se atribuie o repetabilitate egală cu suma repetabilității elementelor originale. Apoi, elementele secvenței sunt sortate din nou în funcție de repetabilitatea lor. În cazul nostru, ultimele două elemente o (1) și φ (1) sunt înlocuite cu elementul S1 (2), iar succesiunea nou sortată va lua forma: (a (5), m (2), S1 ( 2), în (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 repetabilitate totală și resortarea ulterioară a secvenței în conformitate cu repetabilitatea elementelor, ajungem la o situație în care în secvență rămâne un singur element ( Fig. 4).
Orez. 4. Demonstrarea algoritmului Huffman
folosind exemplul cuvântului „accident de avion”
Concomitent cu înlocuirea elementelor și resortarea secvenței, se construiește un arbore de cod binar. Algoritmul de construcție a arborelui este foarte simplu: operația de combinare (înlocuire) a două elemente ale secvenței generează un nou nod în 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 de secvență obținut prin înlocuire (Fig. 5). În acest caz, marginii din stânga a arborelui de coduri i se poate atribui valoarea „0”, iar celei din dreapta - „1”. Aceste valori vor servi în continuare ca elemente de cod prefix.
Orez. 5. Construirea unui arbore de cod
în algoritmul Huffman
(înlocuind elementele „o” și „f”
element nou S1)
Completați arborele de cod Huffman pentru un cuvânt "Avion prăbușit" , prezentat în Fig. 6.
Orez. 6. Completați arborele de cod pentru cuvântul „accident de avion”
construit de algoritmul 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 simbolurile alfabetului nostru de informații:
Dacă acum încearcă să scrii un cuvânt "Avion prăbușit" în codificarea Huffman, obținem secvența 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 de avion”. 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ă un cod 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 optim Huffman este cel mai comun algoritm de generare a codului de lungime variabilă și este încorporat în majoritatea utilităților de compresie și arhivare a informațiilor.
Codare aritmetică
După cum am observat deja, conform criteriului lui Shannon, codul optim este acela în care este alocat 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 un algoritm de codare aritmetică.
Ideea din spatele codificării aritmetice este că, în loc să codifice caractere individuale, codul este atribuit simultan întregii secvențe de informații. Este evident că lungimea codului pentru un caracter individual poate să nu fie un număr întreg. De aceea această metodă de codare este mult mai eficientă decât codarea prefixului și este mai în concordanță cu criteriul lui Shannon.
Ideea din spatele algoritmului de codare aritmetică este următoarea. Ca în toate metodele de codare considerate mai devreme, 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)
