Compresia datelor

Introducere

Compresia datelor este procesul prin care se urmărește micșorarea redundanței mesajului generat de o sursă, pentru a reduce resursele necesare memorării sau transmiterii acestui mesaj. Obiectivul fundamental este reducerea numărului de simboluri binare necesar pentru reprezentarea mesajului.

Redundanța

Definiție

Redundanța cuantifică excesul de simboluri folosite de un cod față de minimul teoretic (entropia). Se definește prin:

R = 1 - η = 1 - H(X) / (L · log₂(D))

unde:

• H(X) = entropia sursei (biți/simbol)
• L = lungimea medie a cuvintelor de cod
• D = numărul de simboluri din alfabetul codului
• η = eficiența codului

Redundanța surselor naturale

Pentru un alfabet de n simboluri cu repartiție non-uniformă, redundanța sursei este:

R_sursă = 1 - H(X) / log₂(n)

unde log₂(n) este entropia maximă (repartiție uniformă). Redundanța sursei arată cât de departe este sursa de distribuția echiprobabilă.

Exemplu

Fie o sursă cu n = 4 simboluri echiprobabile:

H(X) = log₂(4) = 2 biți/simbol
R_sursă = 1 - 2/2 = 0 (nu există redundanță)

Fie acum o sursă cu 4 simboluri non-echiprobabile, H(X) = 1.75 biți/simbol:

R_sursă = 1 - 1.75/2 = 0.125 (12.5% redundanță)

Eficiența codului

Eficiența unui cod măsoară cât de bine codifică sursa în raport cu limita teoretică:

η = H(X) / (L · log₂(D))

Pentru coduri binare (D = 2):

η = H(X) / L

Limite teoretice ale compresiei

Limita inferioară (prima teoremă Shannon)

Din prima teoremă a lui Shannon, lungimea medie minimă a unui cod este:

L_min = H(X) / log₂(D)

Aceasta este limita absolută a compresiei — nu se poate comprima sub entropia sursei fără pierdere de informație.

Clasificarea algoritmilor de compresie

Compresie fără pierderi

Algoritmii de compresie fără pierderi sunt reversibili: prin decompresie se obține mesajul original întocmai. Aceștia se bazează pe eliminarea redundanței sursei.

Tipuri de coduri de compresie (după lungimea subșirurilor):

Codurile Huffman și Shannon-Fano sunt de tip bloc-variabil.

Rata de compresie

Rata de compresie exprimă câte ori s-a micșorat mesajul:

r = dimensiune_originală / dimensiune_comprimată

sau ca procentaj de reducere:

% reducere = (1 - 1/r) × 100

Exemplu practic: calculul redundanței unui text

Datele problemei

Fie un text format din N = 15 182 caractere, cu un alfabet de L = 28 caractere distincte. După analiza frecvenței de apariție a caracterelor se calculează entropia:

H(A) = -Σ P(aᵢ) · log₂ P(aᵢ) = 4.0354 biți/caracter

Entropia maximă

H_max = log₂(28) = 4.8074 biți/caracter

Redundanța sursei

R_sursă = 1 - H(A) / H_max = 1 - 4.0354 / 4.8074 = 0.1606 (16.06%)

Textul are o redundanță de 16.06% — aceasta este cantitatea de informație care poate fi eliminată prin compresie fără pierderi.

Codarea Huffman a textului

Aplicând algoritmul Huffman se obține lungimea medie:

L = 4.0714 biți/caracter

Eficiența codului Huffman:

η = H(A) / L = 4.0354 / 4.0714 = 0.9912 (99.12%)

Redundanța codului:

R_cod = 1 - η = 0.0088 (0.88%)

Comparație

Verificarea primei teoreme Shannon:

H(A) ≤ L < H(A) + 1
4.0354 ≤ 4.0714 < 5.0354  ✓

Rata de compresie

Față de codarea uniformă (5 biți/caracter, deoarece ⌈log₂(28)⌉ = 5):

r = 5 / 4.0714 ≈ 1.228
% reducere = (1 - 1/1.228) × 100 ≈ 18.6%

Puncte cheie pentru examen

• Redundanța sursei: R = 1 - H(X)/log₂(n) — cât de departe este sursa de echiprobabilitate
• Redundanța codului: R = 1 - η = 1 - H(X)/(L·log₂(D)) — cât de departe este codul de limita entropiei
• Eficiența: η = H(X)/(L·log₂(D)); pentru cod binar: η = H(X)/L
• Limita compresiei fără pierderi: nu se poate comprima sub H(X) biți/simbol
• Algoritmii fără pierderi (Huffman, Shannon-Fano) sunt reversibili
• Algoritmii cu pierderi (JPEG, MP3) acceptă diferențe față de original
• Rata de compresie: r = dimensiune_originală / dimensiune_comprimată
• Codurile bloc-variabil (Huffman, Shannon-Fano) sunt cele mai utilizate în compresie fără pierderi