Când scrieți sau transferați date, este adesea util să reduceți dimensiunea datelor care sunt procesate. Tehnologia care atinge acest obiectiv se numește compresie de date. Există multe metode de comprimare a datelor, fiecare dintre acestea fiind caracterizată de propria sa zonă de aplicare, în care oferă cele mai bune sau, dimpotrivă, cele mai proaste rezultate.

Metoda de codare a lungimii de rulare

Metoda de codare a lungimii de rulare oferă cele mai bune rezultate dacă datele care trebuie comprimate constau din secvențe lungi de aceleași valori. În esență, o astfel de metodă de codare constă doar în înlocuirea unor astfel de secvențe cu o valoare de cod care determină valoarea repetată și numărul repetărilor sale într-o serie dată. De exemplu, pentru a scrie informațiile codificate că secvența de biți constă din 253 de biți, urmate de 118 zerouri și încă 87 de biți, va necesita mult mai puțin spațiu decât pentru a enumera toți acești 458 de biți.

Exemplu. Folosind metoda de codificare a lungimii seriei, secvența: 11111111110000000000000000 - poate fi reprezentată astfel: 10.

Metoda de codificare relativă

În unele cazuri, informațiile pot consta în blocuri de date, fiecare dintre ele fiind doar puțin diferit de cel precedent. Un exemplu ar fi cadrele succesive ale unei imagini video. Pentru astfel de cazuri, se utilizează metoda de codificare relativă. Această abordare presupune înregistrarea diferențelor care există între blocurile succesive de date, în loc să scriem aceste blocuri în sine, adică. fiecare bloc este codificat în ceea ce privește relația sa cu blocul anterior.

Exemplu. Folosind metoda de codificare relativă, succesiunea de cifre este: 1476; 1473; 1480; 1477 - poate fi reprezentat sub următoarea formă: 1476; -3; +7; -3.

Codare dependentă de frecvență

Această metodă de comprimare a datelor implică utilizarea codării dependente de frecvență, în care lungimea unui model de biți care reprezintă un element de date este invers proporțională cu frecvența de utilizare a acestui element. Astfel de coduri sunt incluse în grupul de coduri de lungime variabilă, adică elementele de date din aceste coduri sunt reprezentate prin modele de biți de diferite lungimi. Dacă luăm text în limba engleză codificat folosind o metodă dependentă de frecvență, atunci caracterele care apar cel mai frecvent [e, t, a, i] vor fi reprezentate prin modele de biți scurte, iar acele caractere care apar mai puțin frecvent vor fi reprezentate de modele de biți mai lungi. . Rezultatul este o reprezentare mai scurtă a întregului text decât cu un cod normal precum Unicode sau ASCII. Construcția algoritmului care este utilizat în mod obișnuit în dezvoltarea codurilor dependente de frecvență este creditată lui David Huffman, motiv pentru care astfel de coduri sunt adesea denumite coduri Huffman. Cele mai multe coduri dependente de frecvență utilizate astăzi sunt coduri Huffman.

Exemplu. Să fie necesară codificarea secvenței αγααβααγααβαλαβαβαβαβαα cu o metodă dependentă de frecvență: αγααβααγααβαλαβαβαβαβαα, care constă din patru simboluri α, β, γ și λ. Mai mult, în această secvență α apare de 15 ori, β - 6 ori, γ - de 2 ori și λ - 1 dată.

Să alegem, în conformitate cu metoda Huffman, următorul cod binar pentru a reprezenta caracterele:

α - 1
β-01
γ-001
λ - 000

Metoda Lempel-Ziv

Această metodă poartă numele creatorilor săi, Abraham Lempel și Jacob Ziv. Sistemele de codare Lempel-Ziv folosesc tehnologia de codificare adaptivă a vocabularului. În acest context, termenul de vocabular înseamnă setul de blocuri din care este construit un mesaj comprimat. Dacă textul în limba engleză este comprimat, blocurile pot fi caractere alfabetice. Dacă trebuie să reduceți dimensiunea datelor care sunt stocate în computer, atunci zerourile și unurile pot deveni blocuri de construcție. În procesul de codificare adaptivă a vocabularului, conținutul vocabularului se poate schimba. De exemplu, atunci când comprimați text în limba engleză, poate fi util să adăugați în dicționar terminația ing și articolul the. În acest caz, spațiul ocupat de copiile viitoare ale terminației și articolului poate fi redus prin scrierea lor ca referințe unice în loc de o combinație de trei referințe diferite. Sistemele de codare Lempel-Ziv folosesc metode sofisticate și extrem de eficiente pentru adaptarea vocabularului în timpul codificării sau compresiei. În special, în orice moment al procesului de codificare, dicționarul va consta din acele combinații care au fost deja codificate [comprimate].

Ca exemplu, luați în considerare modul în care un mesaj poate fi comprimat folosind un anumit sistem Lempel-Ziv cunoscut sub numele de LZ77. Procesul începe aproape cu o rescrie a părții inițiale a mesajului, dar la un moment dat se face o tranziție la reprezentarea segmentelor viitoare folosind triplete, fiecare dintre ele va consta din două numere întregi urmate de un caracter de text. Fiecare triplet descrie modul în care este construită următoarea parte a mesajului. De exemplu, lăsați textul despachetat să arate astfel:

αβααβλβ

Șirul αβααβλβ este partea deja dezambalată a mesajului. Pentru a dezarhiva restul textului mesajului, trebuie mai întâi să extindeți linia, anexând la aceasta partea care apare deja în el. Primul număr din triplet specifică câte caractere se numără înapoi în șir pentru a găsi primul caracter al segmentului adăugat. În acest caz, este necesar să numărăm înapoi 5 caractere și vom ajunge la al doilea caracter a din stânga șirului deja despachetat. Al doilea număr din triplet specifică numărul de caractere consecutive din dreapta începutului care alcătuiesc segmentul de adăugat. În exemplul nostru, acest număr este 4, ceea ce înseamnă că segmentul adăugat va fi ααβλ. O copiem la sfârșitul liniei și obținem noua valoare a părții despachetate a mesajului: αβααβλβααβλ.

În cele din urmă, ultimul element [în cazul nostru, caracterul α] trebuie plasat la sfârșitul șirului extins, rezultând un mesaj complet decomprimat: αβααβλβααβλα.

Compresia imaginii

Formatul bitmap utilizat în convertoarele de imagini digitale moderne codifică imaginea într-un format de trei octeți per pixel, ceea ce duce la crearea de fișiere bitmap voluminoase și incomode. Multe scheme de compresie au fost dezvoltate special pentru acest format, concepute pentru a reduce spațiul pe disc ocupat de astfel de fișiere. O astfel de schemă este formatul GIF dezvoltat de CompuServe. Metoda pe care o folosește este de a reduce numărul de nuanțe per pixel la 256, prin care culoarea fiecărui pixel poate fi reprezentată cu un octet în loc de trei. Folosind un tabel numit paletă de culori, fiecare dintre nuanțele de culoare permise ale unui pixel este asociată cu o combinație de culori roșu-verde-albastru. Schimbând paleta folosită, puteți modifica culorile care apar în imagine.

De obicei, una dintre culorile din paleta GIF este luată ca simbol pentru „transparență”. Aceasta înseamnă că în zonele imaginii umplute cu această culoare este afișată culoarea fundalului pe care se află. Datorită acestui fapt și ușurinței relative de utilizare a imaginilor, formatul GIF a devenit larg răspândit în acele jocuri pe computer în care multe imagini diferite se mișcă pe ecran.

Un alt exemplu de sistem de compresie a imaginilor este formatul JPEG. Este un standard dezvoltat de Joint Photographic Experts Group [de unde și numele acestui standard] în cadrul organizației ISO. Formatul JPEG s-a dovedit a fi o metodă eficientă de prezentare a fotografiilor color. Din acest motiv, acest standard este utilizat de producătorii de camere digitale moderne. Ar trebui de așteptat că va avea un impact semnificativ asupra domeniului imaginii digitale în viitor.

De fapt, standardul JPEG include mai multe moduri de a reprezenta o imagine, fiecare având propriul scop. De exemplu, atunci când este necesară fidelitatea maximă a imaginii, formatul JPEG oferă un mod „fără pierderi”, al cărui nume indică direct că procedura de codificare a imaginii va fi efectuată fără nicio pierdere de informații. În acest mod, spațiul este economisit prin amintirea diferențelor dintre pixeli succesivi, mai degrabă decât luminozitatea fiecărui pixel în mod individual. Conform teoriei, în majoritatea cazurilor, gradul de diferență dintre pixelii vecini poate fi codificat în modele de biți mai scurte decât valorile reale de luminozitate ale pixelilor individuali. Diferențele existente sunt codificate cu un cod de lungime variabilă care este utilizat pentru a reduce și mai mult utilizarea memoriei.

Din păcate, atunci când se utilizează modul „fără pierderi”, fișierele de imagine raster generate sunt atât de mari încât nu sunt procesate cu greu prin metode moderne de tehnologie și, prin urmare, sunt rareori utilizate în practică. Majoritatea aplicațiilor existente folosesc o altă metodă standard de format JPEG, modul „de bază”. În acest mod, fiecare dintre pixeli este reprezentat și de trei componente, dar în acest caz este deja o componentă de luminozitate și două componente de culoare. Aproximativ, dacă creăm o imagine numai din componentele luminozității, atunci vom vedea o versiune alb-negru a imaginii, deoarece aceste componente reflectă doar nivelul de iluminare al pixelului.

Semnificația acestei separări între culoare și luminozitate se explică prin faptul că ochiul uman este mai sensibil la schimbările de luminozitate decât culoarea. Luați în considerare, de exemplu, două dreptunghiuri albastre colorate uniform, care sunt exact aceleași, cu excepția faptului că unul dintre ele are un punct mic luminos, în timp ce celălalt are un punct mic verde de aceeași luminozitate ca fundalul albastru. Va fi mai ușor pentru ochi să detecteze un punct luminos, mai degrabă decât unul verde. Modul „de bază” al JPEG exploatează această caracteristică prin codificarea componentei de luminanță a fiecărui pixel, dar făcând o medie a valorii componentelor de culoare pentru blocuri de patru pixeli și scriind componentele de culoare numai pentru acele blocuri. Ca rezultat, randarea finală a imaginii păstrează schimbările bruște de luminozitate, dar lasă schimbările de culoare clare neclare. Avantajul acestei scheme este că fiecare bloc de patru pixeli este reprezentat de doar șase valori [patru lumi și două culori], mai degrabă decât cele douăsprezece necesare cu o schemă de trei pe pixel.

Introducere.

Comprimarea reduce cantitatea de spațiu necesară pentru stocarea fișierelor pe computer și

timpul necesar pentru a transmite informații pe un canal specificat

lățime de bandă. Este o formă de codificare. Alte scopuri de codare

sunt căutarea și corectarea erorilor, precum și criptarea. procesul de căutare și

corectarea erorilor este opusul compresiei - crește redundanța datelor,

când nu trebuie să fie prezentate într-o formă care poate fi citită de om. Îndepărtarea

din redundanța textului, compresia promovează criptarea, ceea ce face dificilă căutarea

cifrează printr-o metodă statistică accesibilă crackerului.

Să luăm în considerare compresia reversibilă sau compresia fără interferență, unde inițiala

textul poate fi restabilit exact din starea comprimată. ireversibilă sau

compresia dăunătoare este utilizată pentru a înregistra digital semnale analogice precum

vorbirea umană sau desenele. Compresia reversibilă este deosebit de importantă pentru texte

scrise în limbaje naturale și artificiale, pentru că în acest caz

greșelile sunt de obicei inacceptabile. Deși domeniul principal de aplicare

dintre metodele luate în considerare este comprimarea textelor, care reflectă și terminologia noastră,

totuși, această tehnică poate fi utilizată în alte cazuri, inclusiv reversibile

codificarea secvenţelor de date discrete.

Există multe motive întemeiate pentru a aloca resursele computerului în termeni de comprimare

performanţă, pentru că transfer de date mai rapid și spațiu redus pentru

stocarea lor economisește o mulțime de bani și de multe ori se îmbunătățește

indicatoare de calculator. Compresia va rămâne probabil în centrul atenției din cauza tuturor

cantități crescânde de date stocate și transmise către computer, în plus, poate fi

poate fi folosit pentru a depăși unele limitări fizice, cum ar fi,

de exemplu, lățimea de bandă relativ mică a canalelor telefonice.

APLICAREA ARBOCILOR DE EXPANDARE PENTRU COMPRESIA DATELOR.

Algoritmii de compresie pot îmbunătăți eficiența stocării și transmiterii datelor

prin reducerea redundanţei acestora. Algoritmul de compresie preia

text sursă ca intrare și produce textul comprimat corespunzător,

când algoritmul de desfășurare are text comprimat ca intrare și primește de la

emite textul original al sursei. Majoritatea algoritmilor de compresie

considerați textul sursă ca un set de șiruri formate din litere ale alfabetului

text original.

Redundanța în reprezentarea șirului S este L(S) - H(S), unde L(S) este lungimea

reprezentări în biți și H(S) - entropie - o măsură a conținutului de informații, de asemenea

exprimată în biți. Algoritmi care se pot comprima fără pierderi de informații

șir la mai puțini biți decât entropia sa nu există. Dacă de la

din textul sursă extrage o literă dintr-un set aleatoriu,

folosind alfabetul A, atunci entropia este găsită prin formula:

H(S) = C(S) p(c) log ---- ,

unde C(S) este numărul de litere din șir, p(c) este probabilitatea statică

apariția unei litere C. Dacă frecvența de apariție este utilizată pentru a estima p(c)

fiecare literă c din șirul S, apoi H(C) se numește autoentropia șirului S. În acest

articolul H(S) va fi folosit pentru a desemna autoentropia unui șir luat din

sursă statică.

Arborii în expansiune descriu de obicei forme de ordonare lexicografică

arbori binari de căutare, dar arborii utilizați în comprimarea datelor s-ar putea să nu

fi în ordine constantă. Eliminarea ordinii duce la

simplificarea semnificativă a operațiunilor de expansiune de bază. Primit ca urmare

algoritmii sunt extrem de rapizi și compacti. Când utilizați coduri Huffman,

extinderea conduce la un algoritm de compresie adaptat local care

remarcabil de simplu și rapid, deși nu realizează o compresie optimă.

Când se aplică codurilor aritmetice, rezultatul compresiei este aproape de

optime și aproximativ optime în timp.

CODURI DE PREFIX.

Majoritatea algoritmilor de comprimare a datelor studiați pe scară largă se bazează pe coduri

Huffman. În codul Huffman, fiecare literă a textului sursă este reprezentată în arhivă

cod de lungime variabilă. Literele mai frecvente sunt reprezentate de coduri scurte,

mai puțin frecvente – lungi. Codurile utilizate în textul condensat trebuie să respecte

proprietățile prefixului și anume: codul folosit în textul comprimat nu poate fi

prefixul oricărui alt cod.

Codurile de prefix pot fi găsite printr-un arbore în care fiecare frunză

se potrivește cu o literă din alfabetul sursă. Figura 1 prezintă arborele de cod

prefix pentru un alfabet de 4 litere. Codul de prefix pentru o literă poate fi citit prin

parcurgerea arborelui de la rădăcină la această literă, unde 0 corespunde alegerii ramurii sale stângi,

și 1 - dreapta. Arborele de cod Huffman este un arbore cu greutate egală în care fiecare

frunza are o pondere egală cu frecvența de apariție a literei în textul sursă și

nodurile interne nu au propria greutate. Arborele din exemplu va fi optim dacă

frecvențele literelor A, B, C și D vor fi 0,125, 0,125, 0,25 și respectiv 0,5.

Codurile Huffman obișnuite necesită informații prealabile despre frecvența apariției

litere în textul original, ceea ce duce la necesitatea unei vizualizări duble - una

pentru a obține valorile frecvenței literelor, celălalt pentru a efectua compresia în sine. LA

Ulterior, valorile acestor frecvențe trebuie combinate cu textul comprimat în sine pentru a

să îi permită implementarea în viitor. Compresia adaptivă în curs

într-un singur pas, pentru că se bazează codul folosit pentru fiecare literă a textului sursă

la frecvențele tuturor celorlalte litere ale alfabetului, cu excepția acestuia. Fundamente pentru eficient

Implementările adaptive ale codului Huffman au fost stabilite de Gallagher, a publicat Knuth

versiune practică a unui astfel de algoritm, iar Witter a dezvoltat-o.

Codul Witter adaptat optim se află întotdeauna în intervalul de un bit per

scrisoarea sursă cu privire la codul Huffman static optim, care este de obicei

este câteva procente din H. În plus, codurile Huffman statice sunt întotdeauna

se află la maximum un bit per scrisoare de text simplu de la H (ei ajung la aceasta

limitează numai când pentru toate literele p(C) = 2). Există algoritmi de compresie

care pot depăși aceste limitări. Algoritmul Ziv-Lempell, de exemplu,

atribuie cuvinte dintr-o arhivă cu lungime fixă ​​liniilor de text sursă

lungime variabilă și compresie aritmetică pot fi folosite pentru a codifica

literele sursă chiar și fracțiuni de bit.

Aplicați extensia codurilor de prefix.

Copacii în expansiune au fost descriși pentru prima dată în 1983 și mai detaliat

considerate în 1985. Iniţial au fost înţelese ca un tip de autoechilibrare

arbori binari de căutare și, de asemenea, s-a demonstrat că permit

cea mai rapidă implementare a cozilor prioritare. Dacă nodul arborelui în expansiune

disponibil, este extins. Aceasta înseamnă că nodul disponibil devine

rădăcină, toate nodurile din stânga formează un nou subarboresc din stânga, nodurile din dreapta -

nou subarbore din dreapta. Expansiunea se realizează prin traversarea arborelui din vechime

root la nodul țintă în timp ce faceți modificări locale, deci prețul

dilatarea este proporţională cu lungimea drumului parcurs.

Tarjan și Slayton au arătat că arborii în expansiune sunt optimi din punct de vedere static.

Cu alte cuvinte, dacă codurile nodurilor disponibile sunt luate în funcție de static

distribuția probabilității, apoi viteza de acces la arborele în expansiune și

echilibrat static, optimizat prin această distribuție, va fi

diferă unul de celălalt printr-un factor constant, vizibil la un nivel suficient

serii lungi de accese. Din moment ce arborele Huffman este un exemplu

arbore echilibrat static, apoi atunci când utilizați extensia de compresie

date, dimensiunea textului comprimat se va afla într-un anumit coeficient de la

dimensiunea arhivei obţinute folosind codul Huffman.

După cum a fost descris inițial, extensia se aplică copacilor care stochează

datele sunt în noduri interne, nu în frunze. Arborele de coduri de prefix poartă toate

datele lor numai în frunze. Există, totuși, o opțiune de extensie numită

semi-extensie care este aplicabilă arborelui cod prefix. Cu el, ținta

nodul nu este mutat la rădăcină și descendenții săi nu sunt modificați,

în schimb, drumul de la rădăcină la țintă este pur și simplu înjumătățit. Jumătate de expansiune ajunge

aceleaşi limite teoretice în cadrul unui coeficient constant ca

extensie.

În cazul unei parcurgeri în zig-zag a arborelui lexicografic, ținând ca

prelungiri, iar semiprelungirile devin mai complicate, în contrast cu traseul direct de-a lungul

marginea stângă sau dreaptă a arborelui până la nodul țintă. Acest caz simplu este prezentat în

Figura 2. Impactul semi-extensiei asupra traseului de la rădăcină (nodul w) la frunză

nodul A este de a schimba fiecare pereche de interne după altele

alte noduri, în urma cărora lungimea căii de la rădăcină la nodul frunzei este redusă cu

de 2 ori. În procesul de semi-expansiune, nodurile fiecărei perechi, mai îndepărtate de rădăcină,

sunt incluse în noua cale (nodurile x și z), și altele mai apropiate din aceasta

sunt excluse (nodurile w și y).

Păstrarea ordinii lexicografice în arborele de cod prin operația de semiexpansiune

prefixul este opțional. Important doar în operațiunile de cod

prefixul este o potrivire exactă a arborelui utilizat de rutina de compresie

arborele utilizat de procedura de implementare. Orice modificare permisă

între litere succesive, se efectuează numai dacă

ambele proceduri fac aceleași modificări în aceeași ordine.

Lipsa suportului pentru ordinea lexicografică simplifică foarte mult implementarea

operațiuni de semiexpansiune prin eliminarea carcasei zig-zag. Ar putea fi

Teoria și strategia reprezentării datelor

Comprimarea datelor este utilizată pe scară largă într-o mare varietate de contexte de programare. Toate sistemele de operare și limbajele de programare populare au numeroase instrumente și biblioteci pentru a lucra cu diferite metode de comprimare a datelor.

Alegerea corectă a instrumentelor de compresie și a bibliotecilor pentru o anumită aplicație depinde de caracteristicile datelor și de scopul aplicației în sine: streaming de date sau lucrul cu fișiere; modele și modele așteptate în date; importanța relativă a utilizării CPU și a memoriei, lățimea de bandă și cerințele de stocare și alți factori.

Ce se înțelege prin compresia datelor? Pe scurt, compresia elimină din date redundanţă; în ceea ce privește teoria informației, compresia crește entropia textului comprimat. Cu toate acestea, ambele afirmații sunt în esență adevărate în esență, în virtutea definiției conceptelor în sine. Redundanța poate fi exprimată în multe forme diferite. Un tip este o secvență de biți repeți (11111111). Al doilea este o secvență de octeți repeți (XXXXXXX). Mai des, însă, redundanța se manifestă la o scară mai mare și este exprimată fie prin modele din setul de date luat în ansamblu, fie prin secvențe de lungimi diferite care au caracteristici comune. În esență, scopul comprimării datelor este de a căuta transformări algoritmice ale reprezentărilor de date care vor produce reprezentări mai compacte ale seturilor de date „tipice”. Această descriere poate părea oarecum vagă, dar vom încerca să-i dezvăluim esența cu exemple practice.

Compresie fără pierderi și cu pierderi

De fapt, există două abordări fundamental diferite ale compresiei datelor: compresia cu pierderi și compresia fără pierderi. Acest articol este în principal despre metodele de compresie fără pierderi, dar este bine să începeți prin a învăța diferențele. Compresie fără pierderi implică transformarea reprezentării setului de date astfel încât să puteți apoi exact reproduce setul de date original prin transformare inversă (despachetare). Compresie cu pierderi este o vizualizare care vă permite să reproduceți ceva „foarte asemănător” cu setul de date original. Avantajul utilizării metodelor de compresie cu pierderi este că acestea produc adesea reprezentări de date mult mai compacte decât metodele de compresie fără pierderi. Cel mai frecvent, metodele de compresie cu pierderi sunt folosite pentru a procesa imagini, fișiere de sunet și videoclipuri. Compresia cu pierderi în aceste zone poate fi adecvată datorită faptului că o persoană percepe un model de biți al unei imagini/sunete digitale nu cu acuratețe „biți”, ci mai degrabă evaluează muzica sau imaginea în ansamblu.

Din punctul de vedere al datelor „obișnuite”, compresia cu pierderi este o opțiune nefericită. Nu avem nevoie de un program care să facă „despre” ce și nu exact ceea ce a fost solicitat de fapt. Același lucru este valabil și pentru bazele de date, care trebuie să stocheze exact datele care au fost încărcate în ele. Cel puțin, nu va funcționa pentru majoritatea problemelor (și cunosc foarte puține cazuri practice de utilizare pentru compresia cu pierderi în afara datelor care descriu în sine experiența senzorială a lumii reale (cum ar fi imaginile și sunetele)).

Exemplu de set de date

În acest articol, va fi folosită o reprezentare ipotetică special pregătită a datelor. Să luăm un exemplu ușor de înțeles. În Greenfield, Massachusetts, SUA, prefixele numerelor de telefon sunt 772- , 773- , și 774- . (Notă pentru cititorii din afara SUA: în SUA, numerele de telefon locale au șapte cifre și sunt reprezentate în mod tradițional ca ###-####; prefixele sunt atribuite în funcție de locația geografică.) De asemenea, să presupunem că dintre cele trei prefixe, primul este cel mai des folosit. Părțile sufixului pot fi orice alte cifre cu probabilitate aproximativ egală. Setul de date care ne interesează se află în „lista tuturor numerelor de telefon care sunt în uz activ în prezent”. Puteți încerca să găsiți un motiv pentru care acest lucru ar putea fi interesant din punct de vedere al programării, dar în acest caz nu este important.

Inițial, setul de date care ne interesează are o reprezentare standard: un raport cu mai multe coloane (poate generat ca urmare a unei interogări sau a unui proces de compilare). Primele rânduri ale acestui raport ar putea arăta astfel:

Tabelul 1. Raport pe mai multe coloane

Comprimarea spațiului gol

Comprimarea spațiilor goale poate fi caracterizată mai general ca „înlăturarea a ceea ce nu ne interesează”. Chiar dacă această metodă este din punct de vedere tehnic o metodă de compresie cu pierderi, este totuși utilă pentru multe tipuri de reprezentări de date pe care le întâlnim în lumea reală. De exemplu, chiar dacă HTML este mult mai lizibil într-un editor de text prin adăugarea de indentări și spațiere între rânduri, niciunul dintre aceste „spații goale” nu afectează modul în care documentul HTML este redat într-un browser Web. Dacă știți sigur că un anumit document HTML este destinat exclusiv unui browser web (sau pentru un fel de robot/crawler), atunci ar putea fi o idee bună să eliminați toate spațiile goale, astfel încât documentul să se transfere mai rapid și să ocupe mai puțin spatiu de depozitare. Tot ceea ce eliminăm atunci când comprimăm spațiile goale nu poartă cu adevărat nicio sarcină funcțională.

În cazul exemplului prezentat, doar o mică parte a informațiilor poate fi eliminată din raportul descris. Șirul de simboluri „=" de-a lungul marginii de sus a raportului nu conține niciun conținut funcțional; același lucru este valabil și pentru caracterele „-” în numere și spații dintre numere. Toate acestea sunt utile persoanei care citește raportul original, dar nu contează dacă considerăm aceste caractere drept „date”. Ceea ce eliminăm nu este un „spațiu gol” în sensul tradițional, dar este în esență.

Comprimarea spațiului gol este extrem de „ieftin” în ceea ce privește implementarea. Întrebarea este doar să citiți fluxul de date și să excludeți câteva valori specifice din fluxul de ieșire. În multe cazuri, pasul de „despachetare” nu este furnizat deloc. Cu toate acestea, chiar dacă am dori să recreăm ceva apropiat de fluxul de date original, ar necesita doar o cantitate mică de resurse de CPU sau memorie. Datele recuperate nu se vor potrivi neapărat cu datele originale; depinde de ce reguli și restricții au fost conținute în original. O pagină HTML introdusă de un om într-un editor de text este probabil să conțină spații conform anumitor reguli. Același lucru este valabil și pentru instrumentele automate, care creează adesea indentări și spații „rezonabile” în codul HTML. În cazul formatului de raport rigid prezentat în exemplul nostru, nu există niciun motiv pentru care prezentarea inițială să nu poată fi recreată de vreun „despachetător de formatare”.

Codarea grupului

Random Encoding (RLE) este cea mai simplă dintre tehnicile de compresie fără pierderi utilizate în mod obișnuit. La fel ca compresia spațiului liber, nu costă mult, mai ales pentru decodare. Ideea din spatele acestei metode este că multe reprezentări ale datelor constau în mare parte din șiruri de octeți repeți. Exemplul nostru de raport este o astfel de vizualizare a datelor. Începe cu un șir de caractere „=" repetate și are șiruri împrăștiate în raport care constau doar din spații. În loc să reprezinte fiecare caracter cu propriul octet, metoda RLE implică (uneori sau întotdeauna) specificarea numărului de ori de repetat, urmată de caracterul care trebuie repetat de numărul specificat de ori.

Dacă formatul de date procesat este dominat de octeți repeți, atunci poate fi adecvat și eficient să se utilizeze un algoritm în care unul sau mai mulți octeți indică numărul de repetări, urmat de caracterul repetat. Cu toate acestea, dacă există șiruri de caractere cu o singură lungime, acestea vor necesita doi (sau mai mulți) octeți pentru codificare. Cu alte cuvinte, un singur caracter ASCII „X” al fluxului de intrare ar putea necesita un flux de biți de ieșire de 00000001 01011000. Pe de altă parte, pentru a codifica o sută de caractere „X” consecutive, ar fi folosit același număr de biți: 01100100 01011000 , ceea ce este destul de eficient.

Variantele RLE folosesc adesea utilizarea selectivă a octeților pentru a indica numărul de repetări, în timp ce restul octeților pur și simplu se reprezintă pe ei înșiși. Pentru a face acest lucru, trebuie rezervată cel puțin o valoare de un octet, care poate fi eliminată din ieșire dacă este necesar. De exemplu, în exemplul nostru de raport cu numărul de telefon, știm că toate informațiile din fluxul de intrare constă din caractere ASCII simple. În special, toate astfel de caractere au primul bit al valorii ASCII setat la 0. Am putea folosi acest prim bit al ASCII pentru a indica faptul că octetul indică numărul de repetări și nu un caracter obișnuit. Următorii șapte biți ai octetului iterator ar putea fi folosiți pentru a indica numărul de repetări, iar următorul octet ar putea conține caracterul repetat. Deci, de exemplu, am putea reprezenta șirul „YXXXXXXX” astfel:

Acest exemplu nu explică cum să renunți la valorile octetilor iteratorului și nici nu permite mai mult de 127 de repetări ale unui singur caracter. Cu toate acestea, diferite variații ale RLE, dacă este necesar, rezolvă aceste probleme.

Codare Huffman

Codarea Huffman tratează tabelul de simboluri ca un întreg set de date. Comprimarea se realizează prin găsirea „greutăților” fiecărui caracter din setul de date. Unele caractere sunt folosite mai des decât altele, așa că codarea Huffman sugerează că caracterele frecvente ar trebui să fie codificate în mai puțini biți decât caracterele mai rare. Există diverse opțiuni pentru codarea Huffman, dar opțiunea originală (și cea mai frecvent utilizată) implică găsirea celui mai comun caracter și codificarea acestuia cu un bit, de exemplu, 1. Și dacă 0 apare în secvența codificată, aceasta înseamnă că un alt caracter este situat în acest loc, codificat cu un număr mare de biți.

Să ne imaginăm că am aplicat codificarea Huffman la codificarea exemplului nostru (presupunând că am supus deja raportul la compresia spațiului liber). Am putea obține următorul rezultat:

Tabelul 2. Rezultatele codării Huffman

Setul de caractere original (format din numere) poate fi ușor codificat (fără compresie) ca secvențe de 4 biți (nibbles). Codarea Huffman de mai sus va folosi până la 5 biți pentru caractere în cel mai rău caz, ceea ce este evident mai rău decât codificarea cu nibbles. Cu toate acestea, în cel mai bun caz, tot ce aveți nevoie este 1 pic; în același timp, se știe că este cel mai bun caz care va fi folosit cel mai des (deoarece acest caracter se găsește cel mai des în date). Deci, am putea codifica un anumit număr de telefon ca acesta:

Când se codifică folosind nibbles, reprezentarea unui număr de telefon ar dura 28 de biți, în cazul nostru, codificarea durează 19 biți. Se adaugă spații la exemplu doar pentru o mai bună înțelegere; prezența lor în caracterele codificate nu este necesară, deoarece este întotdeauna posibil să se determine din tabelul de coduri dacă sfârșitul caracterului codificat a fost atins sau nu (cu toate acestea, este încă necesar să se țină evidența poziției curente în date ).

Codarea Huffman este încă foarte „ieftin” de decodat în ceea ce privește timpul CPU. Cu toate acestea, necesită o căutare în cartea de coduri, deci nu poate fi la fel de „ieftin” ca RLE. Codarea Huffman este destul de costisitoare, deoarece necesită o scanare completă a datelor și construirea unui tabel de frecvență a simbolurilor. În unele cazuri, atunci când utilizați codarea Huffman, este adecvată o „comandă rapidă”. Codarea Huffman standard este aplicată setului de date care este codat, cu tabelul de simboluri primul în ieșire. Totuși, dacă nu se transmite un singur set de date, ci un format întreg cu aceleași modele de apariție a caracterelor, atunci poate fi utilizat tabelul global Huffman. Cu un astfel de tabel, putem codifica căutările în executabilele noastre, ceea ce face compresia și decompresia mult mai ieftine (cu excepția eșantionării globale și a codificării inițiale). De exemplu, dacă știm că setul nostru de date va fi proză engleză, atunci frecvențele literelor sunt bine cunoscute și constante în diferite seturi de date.

compresie Lempel-Ziv

Probabil cea mai semnificativă metodă de compresie fără pierderi este algoritmul Lempel-Ziv. Acest articol se va concentra pe varianta LZ78, dar LZ77 și alte variante funcționează într-un mod similar. Ideea din spatele algoritmului LZ78 este de a codifica o secvență de streaming de octeți folosind un fel de tabel dinamic. La începutul compresiei fluxului de biți, tabelul LZ este umplut cu setul de caractere real, împreună cu câteva sloturi goale. Algoritmul folosește tabele de diferite dimensiuni, dar în acest exemplu cu numere de telefon (cu spații libere comprimate) este folosit un tabel de 32 de elemente (acest lucru este suficient pentru acest exemplu, dar poate să nu fie suficient pentru alte tipuri de date). În primul rând, umplem primele zece sloturi cu caracterele alfabetului utilizat (numerele). Pe măsură ce sosesc noi octeți, valoarea din tabel corespunzătoare celei mai lungi secvențe de potrivire este mai întâi dedusă, iar apoi o secvență de lungime N + 1 este scrisă în următorul slot disponibil. În cel mai rău caz, folosim 5 biți în loc de 4 pentru un singur caracter, dar în cele mai multe cazuri ne putem descurca cu 5 biți pentru mai multe caractere. Să luăm în considerare un exemplu despre modul în care funcționează acest algoritm (slotul tabelului este indicat între paranteze drepte):

Până acum nu am beneficiat de asta, dar să trecem la următorul număr de telefon:

Operațiile de mai sus ar trebui să fie suficiente pentru a demonstra funcționarea modelului. Deși nu s-a realizat încă o compresie vizibilă, se poate observa deja că am reutilizat sloturile 11 și 16, codând câte două caractere cu câte un caracter de ieșire. În plus, am acumulat deja secvența de octeți extrem de utilă 772 în slotul 18, care va apărea ulterior în mod repetat în flux.

Algoritmul LZ78 umple un tabel de simboluri cu intrări utile (probabil), apoi scrie acel tabel, îl șterge și începe unul nou. Într-o astfel de situație, un tabel de 32 de caractere poate să nu fie suficient, deoarece va fi șters înainte de a putea folosi în mod repetat secvențe precum 772 și altele asemenea. Cu toate acestea, este mai ușor să ilustrați funcționarea algoritmului folosind un tabel mic.

În seturile de date tipice, variantele metodei Lempel-Ziv realizează rate de compresie semnificativ mai mari decât metodele Huffman și RLE. Pe de altă parte, versiunile metodei Lempel-Ziv cheltuiesc resurse semnificative pe iterații, iar tabelele lor pot ocupa mult spațiu de memorie. Majoritatea instrumentelor și bibliotecilor de compresie existente folosesc o combinație a metodelor Lempel-Ziv și Huffman.

Enunțarea corectă a problemei

Alegând algoritmul potrivit, puteți obține un câștig semnificativ chiar și în comparație cu metode mai optimizate, dar neadecvate. În mod similar, alegerea reprezentării corecte a datelor este adesea mai importantă decât alegerea metodelor de compresie (care sunt întotdeauna un fel de post-optimizare a caracteristicilor dorite). Exemplul de set de date simplu oferit în acest articol este o ilustrare excelentă a unei situații în care regândirea unei probleme este o soluție mai bună decât utilizarea orice a metodelor de compresie date.

Este necesar să aruncăm o altă privire asupra problemei pe care o prezintă datele. Deoarece acesta nu este un set de date general și există premise clare pentru acesta, problema poate fi reformulată. Se știe că există maximum 30.000 de numere de telefon (între 7.720.000 și 7.749.999), dintre care unele sunt active, iar altele nu. Nu ne confruntăm cu sarcina de a afișa o reprezentare completă a tuturor numerelor active. Trebuie doar să indicăm, folosind o valoare booleană, dacă numărul dat este activ sau nu. Gândindu-ne la problemă în acest fel, putem pur și simplu să alocăm 30.000 de biți în memorie și stocare și să folosim fiecare bit pentru a indica dacă numărul de telefon corespunzător este activ (da sau nu). Ordinea biților în bitmap poate corespunde numerelor de telefon sortate în ordine crescătoare (de la cel mai mic la cel mai mare).

Această soluție bitmap este ideală din orice punct de vedere. Este nevoie de exact 3750 de octeți pentru a reprezenta setul de date; diferite metode de compresie vor folosi cantități diferite, în funcție de numărul de numere de telefon din cadran și de eficacitatea compresiei. Totuși, dacă 10.000 din cele 30.000 de numere de telefon posibile sunt active și chiar dacă cea mai eficientă metodă de compresie necesită câțiva octeți per număr de telefon, atunci bitmap-ul câștigă. În ceea ce privește cerințele de resurse CPU, bitmap-ul nu numai că depășește oricare dintre metodele de compresie discutate, dar depășește și metoda convențională de reprezentare a numerelor de telefon ca șiruri de caractere (fără compresie). Traversarea bitmap-ului și creșterea contorului numărului de telefon curent pot fi efectuate eficient chiar și în memoria cache încorporată a procesoarelor moderne.

Din acest exemplu simplu, puteți înțelege că nu orice problemă are o astfel de soluție ideală așa cum am discutat mai sus. Multe probleme necesită o cantitate semnificativă de memorie, lățime de bandă, spațiu de stocare și utilizarea procesorului; și în majoritatea acestor cazuri, tehnicile de compresie pot atenua sau reduce aceste cerințe. Dar concluzia mai importantă este că, înainte de a aplica tehnici de compresie, merită să verificați din nou dacă este ales conceptul potrivit pentru a reprezenta datele.

Dedicat memoriei lui Claude Shannon.

Metode de compresie a informațiilor

Toate metodele de compresie a informațiilor pot fi împărțite în două clase mari care nu se suprapun: compresie cu pierderi și compresie fără pierderi.

Compresie cu pierderiînseamnă că după despachetarea arhivei se va obține un document ușor diferit de original. Cu cât compresia este mai mare, cu atât pierderile sunt mai mari. Astfel de metode sunt folosite atunci când câteva procente din informații pot fi sacrificate pentru fotografii, date video și muzică. Odată cu pierderea a mai multe procente de informații, compresia se realizează de câteva zeci de ori, 10 - 15 pentru muzică și
20 - 30 pentru materiale foto și video.

Algoritmii din această clasă includ algoritmi JPEGși MPEG. Algoritm JPEG folosit pentru comprimarea imaginilor statice (grafice). Fișierele grafice comprimate de acest algoritm au extensia JPG. Algoritm MPEG folosit pentru a comprima videoclipuri și muzică. Fișierele comprimate au extensia MPG pentru video și MP3 pentru muzica.

Algoritmii de compresie cu pierderi sunt utilizați numai în scopuri de consum, adică pentru vizualizarea graficelor și ascultarea muzicii. Dacă aceste date sunt supuse prelucrării ulterioare (editării), atunci ar trebui aplicați algoritmi fără pierdere de informații.

Compresie fără pierderiînseamnă că după despachetare se va obține un fișier care se potrivește exact cu fișierul original. Această metodă este folosită pentru a comprima documente text, distribuții de software, pentru a crea copii de rezervă ale informațiilor stocate pe un disc, la transferul de date pe medii externe, la trimiterea prin e-mail etc.

Metodele de compresie care nu permit pierderea de informații se bazează pe eliminarea redundanței informaționale.

algoritmi HAFMAN bazată pe recodificarea informațiilor. La codificarea datelor conform tabelului ASCII, se folosește același număr de biți pentru a codifica orice caracter - 8. Dar există caractere care apar frecvent, cum ar fi A sau O și care sunt rare. Programele pentru comprimarea informațiilor au propriul lor tabel de conversie a caracterelor, cu un număr mai mic de biți, și îl atribuie unui fișier comprimat.

Algoritmi sau Metode RLE (Run Length Encoding). pe baza identificării secvenţelor repetate. În documentele text, secvențele repetate sunt rare, dar în tabele este destul de comună, de exemplu, repetarea aceluiași număr. În acest caz, în loc de succesiune, pun coeficientul și această cifră.

Secvențe mari repetate ale acelorași octeți se găsesc în graficele care sunt redate în culori netede, cum ar fi în desenele animate.

Comprimarea datelor hard disk-ul poate fi nu se bazează pe eliminarea redundanței, ci pe principiile plasării datelor pe disc. În sistemul de fișiere FAT, dimensiunea clusterului poate fi de până la 32 KB. Când scrieți date, fișierul ocupă întotdeauna întregul cluster, indiferent de dimensiunea fișierului. Astfel, la comprimare, puteți scrie date aproape unul de celălalt.

Programe - arhivatorii permit (set standard de funcții):

Creați un fișier de arhivă, adică puneți un grup de fișiere într-un singur fișier;

Despachetați arhiva, adică plasați toate fișierele de arhivă în folderul specificat;

Extrageți fișierele selectate din arhivă în directorul specificat;

Vizualizați conținutul arhivei;

Adăugați fișiere noi;

Actualizați fișierele din arhivă;

Ștergeți fișierele din arhivă;

Creați arhive autoextractibile;

Creați arhive cu mai multe volume;

Arhivă autoextractabilă- acesta este un fișier de arhivă care poate fi dezambalat fără un program de arhivare. În acest scop, la arhivă este adăugat un bloc de program special, care efectuează despachetarea. Arhiva are extensia EXE. Ele sunt folosite, de regulă, pentru a crea distribuții de software.

Fișierul normal de arhivă are Cuprins, care conține următoarele informații pentru fiecare fișier:

Nume fișier, eventual nume foldere;

Data și ora ultimei modificări a dosarului;

Dimensiunea fișierului de pe disc în arhivă, raportul de compresie;

Cod de control ciclic, care este utilizat pentru a verifica integritatea arhivei;

Compoziția informațiilor depinde de program - arhivator.

Există programe larg cunoscute pentru arhivarea datelor în Windows. winzipși winrar.

Programele au o interfață ușor de utilizat, efectuează un set standard de funcții și vă permit să vizualizați fișierul înainte de a despacheta. Echipă INFO oferă informații despre arhivă: câte fișiere, raportul de compresie etc.

Echipă ADAUGĂ (ADĂUGAȚI) vă permite atât să creați o arhivă nouă, cât și să adăugați la arhivă.

Metoda de actualizare:

- Adăugați și înlocuiți(Adăugați și înlocuiți fișiere) - toate fișierele selectate sunt incluse în arhivă, dacă fișierul există, acesta este înlocuit cu unul nou;

Utilizatorii moderni se confruntă destul de des cu problema lipsei de spațiu liber pe hard disk. Mulți, în încercarea de a elibera cel puțin spațiu liber, încearcă să ștergă toate informațiile inutile de pe hard disk. Utilizatorii mai avansați folosesc algoritmi speciali de compresie pentru a reduce cantitatea de date. În ciuda eficienței acestui proces, mulți utilizatori nu au auzit niciodată de el. Să încercăm să ne dăm seama ce se înțelege prin compresie de date, ce algoritmi pot fi utilizați pentru aceasta.

Astăzi, compresia informațiilor este o procedură destul de importantă care este necesară pentru fiecare utilizator de computer. Astăzi, orice utilizator își poate permite să achiziționeze o unitate de date modernă, care oferă posibilitatea de a utiliza o cantitate mare de memorie. Astfel de dispozitive, de regulă, sunt echipate cu canale de mare viteză pentru difuzarea informațiilor. Cu toate acestea, este de remarcat faptul că în fiecare an cantitatea de informații necesare utilizatorilor devine din ce în ce mai mare. Cu doar 10 USD în urmă cu ani, dimensiunea unui film video standard nu depășea 700 USD Mb. În prezent, volumul filmelor la calitate HD poate ajunge la câteva zeci de gigabytes.

Când este necesară compresia datelor?

Nu ar trebui să vă așteptați la multe de la procesul de comprimare a informațiilor. Dar totuși, există situații în care compresia informațiilor este pur și simplu necesară și extrem de utilă. Să luăm în considerare câteva dintre aceste cazuri.

Transmitere prin email.

Foarte des există situații în care trebuie să trimiteți o cantitate mare de date prin e-mail. Comprimarea poate reduce semnificativ dimensiunea fișierelor transferate. Acei utilizatori care folosesc dispozitive mobile pentru a trimite informații vor aprecia în special avantajele acestei proceduri.

Publicarea datelor pe site-uri și portaluri de internet.

Procedura de compresie este adesea folosită pentru a reduce volumul documentelor utilizate pentru publicare pe diverse resurse de pe Internet. Acest lucru vă permite să economisiți semnificativ traficul.

Economisirea spațiului liber pe disc.

Când nu este posibil să adăugați noi medii de stocare la sistem, puteți utiliza procedura de compresie pentru a economisi spațiu pe disc. Se întâmplă că bugetul utilizatorului este extrem de limitat și nu există suficient spațiu liber pe hard disk. Aici vine în ajutor procedura de compresie.

Pe lângă situațiile enumerate mai sus, există încă un număr mare de cazuri în care procesul de comprimare a datelor poate fi foarte util. Am enumerat doar cele mai comune.

Metode de compresie a informațiilor

Toate metodele existente de comprimare a informațiilor pot fi împărțite în două categorii principale. Acestea sunt compresie fără pierderi și compresie cu pierderi. Prima categorie este relevantă numai atunci când este nevoie de restaurare a datelor cu acuratețe ridicată fără a pierde un singur bit din informațiile originale. Singurul caz în care este necesar să se utilizeze această abordare specială este comprimarea documentelor text.

În cazul în care nu este nevoie specială de restaurarea cât mai precisă a informațiilor comprimate, este necesar să se prevadă posibilitatea utilizării algoritmilor cu anumite pierderi de compresie.

Compresie fără pierderi

Aceste metode de comprimare a informațiilor prezintă interes în primul rând, deoarece sunt utilizate la transferul unor cantități mari de informații prin e-mail, la eliberarea unei lucrări finalizate către un client sau la crearea unor copii de rezervă ale informațiilor stocate pe un computer. Aceste metode de comprimare a informației nu permit pierderea informației, întrucât se bazează doar pe eliminarea redundanței acesteia, în timp ce informația are redundanță aproape întotdeauna, dacă aceasta din urmă nu ar exista, nu ar fi nimic de comprimat.

Exemplul 1

Să luăm un exemplu simplu. Limba rusă include $33$ litere, $10$ cifre și aproximativ $15$ mai multe semne de punctuație și alte caractere speciale. Pentru un text scris doar cu majuscule rusești (de exemplu, ca în telegrame), 60$ de valori diferite ar fi suficient. Cu toate acestea, fiecare caracter este de obicei codificat ca un octet care conține, după cum știm, 8 biți și poate fi exprimat în coduri diferite de $256$. Acesta este unul dintre primii factori care caracterizează redundanța. Pentru textul telegrafic, 6$ biți pe caracter ar fi de ajuns.

Exemplul 2

Să luăm în considerare un alt exemplu. În codificarea internațională a caracterelor ASCII, același număr de biți ($8$) este alocat pentru a codifica orice caracter, în timp ce toată lumea știe de mult și bine că are sens să codifice cele mai frecvente caractere cu mai puține caractere. Deci, de exemplu, în codul Morse, literele „E” și „T”, care sunt foarte frecvente, sunt codificate cu un semn $1$ (respectiv, acestea sunt un punct și o liniuță). Și astfel de litere rare precum „Yu” ($ - -$) și „C” ($- - $) sunt codificate prin semne $4$.

Observația 1

Codificarea ineficientă este al doilea factor care caracterizează redundanța. Programele care comprimă informații pot introduce propria lor codificare și poate fi diferită pentru diferite fișiere și o atribuie fișierului comprimat sub forma unui tabel (dicționar), din care programul de decomprimare va citi informații despre cum este fișierul dat. au codificat anumite simboluri sau grupurile acestora.

Algoritmii bazați pe recodificarea informațiilor se numesc algoritmi Huffman.

Algoritmul Huffman

În acest algoritm, informațiile sunt comprimate prin codificare statistică sau pe baza unui dicționar care a fost creat anterior. Conform algoritmului statistic Huffman, fiecărui simbol de intrare i se atribuie un cod specific. În acest caz, caracterul cel mai des folosit are codul cel mai scurt, iar caracterul cel mai rar folosit are unul mai lung. Ca exemplu, diagrama arată distribuția frecvenței utilizării literelor individuale ale alfabetului englez (Fig. 1). O astfel de distribuție poate fi construită și pentru limba rusă. Tabelele de codificare sunt create în avans și au o dimensiune limitată. Acest algoritm oferă cea mai mare performanță și cea mai mică latență. Pentru a obține rapoarte mari de compresie, metoda statistică necesită cantități mari de memorie.

Figura 1. Distribuția literelor engleze în funcție de frecvența lor de utilizare

Cantitatea de compresie este determinată de redundanța matricei procesate de biți. Fiecare dintre limbile naturale are o anumită redundanță. Dintre limbile europene, rusă are cel mai înalt nivel de redundanță. Acest lucru poate fi judecat după dimensiunea traducerii în limba rusă a textului în limba engleză. De obicei este cu aproximativ 30$\%$ mai mult. Dacă vorbim despre un text poetic, redundanța poate fi de până la $2$ ori mai mare.

Observația 2

Cea mai mare dificultate a codurilor este necesitatea de a avea tabele de probabilitate pentru fiecare tip de date care trebuie comprimate. Aceasta nu este o problemă dacă se știe că textul în engleză sau rusă este comprimat. În acest caz, pur și simplu oferim codificatorului și decodorului un arbore de cod adecvat pentru textul în engleză sau rusă. În cazul general, când probabilitatea caracterelor pentru datele de intrare este necunoscută, codurile Huffman statice funcționează ineficient.

Soluția la această problemă este analiza statistică a datelor codificate, efectuată în timpul primei treceri prin date și compilarea unui arbore de cod pe baza acestuia. În acest caz, codificarea reală este efectuată prin a doua trecere.

Un alt dezavantaj al codurilor este că lungimea minimă a unui cuvânt cod pentru ele nu poate fi mai mică de unu, în timp ce entropia mesajului poate fi de $0,1$ sau $0,01$ biți/litera. În acest caz, codul devine în esență redundant. Problema este rezolvată prin aplicarea algoritmului la blocuri de caractere, dar apoi procedura de codificare/decodare devine mai complicată și arborele de cod se extinde semnificativ, care trebuie salvat în cele din urmă împreună cu codul.

Aceste coduri nu țin cont de relațiile dintre caractere care sunt prezente în aproape orice text.

Observația 3

Astăzi, în era informațională, în ciuda faptului că aproape fiecare utilizator are acces la canale de mare viteză pentru transmisia de date și medii de volum mare, problema compresiei datelor rămâne relevantă. Există situații în care compresia datelor este pur și simplu o operațiune necesară. Acest lucru se aplică în special transmiterii de date prin e-mail și postării de informații pe Internet.