Note de curs, clasele 11-12, 22 mai 2014

Algoritmi de compresie

Generalități

Compresia fără pierderi nu merge pe orice fișier. Orice algoritm de compresie va micșora unele fișiere și va mări altele. De ce? Deoarece compresia este, în esență, o funcție care mapează fișiere la alte fișiere. Acea funcție este injectivă, căci nu putem avea două fișiere de intrare care să se comprime într-un același fișier de ieșire. De aceea, este imposibil ca toate fișierele de lungime n biți să se comprime în fișiere mai scurte de n biți. Prin același argument al numărării rezultă că, pentru orice fișier care se comprimă într-unul mai mic, trebuie să existe un fișier care se „comprimă” într-unul mai mare.

În particular, dacă rulăm orice algoritm de compresie pe un șir aleator de n biți, lungimea așteptată a rezultatului va fi de cel puțin n biți.

Acestea fiind zise, există clase particulare de fișiere pe care compresia se aplică foarte bine: text, executabile, anumite tipuri de date etc.

Tehnicile de compresie sunt compromisuri între:

• viteza de comprimare
• viteza de decomprimare
• rata de compresie
• memoria necesară
• volumul de informație pierdută (pentru audio/video)
• accesul aleator în fișiere comprimate este un bonus util (altfel este nevoie să decomprim tot fișierul ca să pot citi un octet)

Exemple:

• Dacă comprim o dată un fișier pe care apoi îl streamuiesc de un miliard de ori, îmi convine să aștept mai mult la comprimare dacă obțin o compresie mai bună.
• Dacă algoritmul de decomprimare a unui film este prea lent, s-ar putea ca filmul să nu poată fi văzut pe dispozitive mai lente (telefoane mobile etc.).
• Dacă comprimăm vocea umană peste un fir telefonic, nu avem nevoie de fidelitate de sală de concerte. Este acceptabil să tăiem toate frecvențele înalte și joase.

RLE (Run-length encoding)

Unul dintre cei mai naturali algoritmi, RLE înlocuiește șirurile consecutive de octeți egali prin numărul de cópii urmat de o copie a octetului. De exemplu, următorii 20 de octeți se pot comprima în 8 octeți:

 aaaaaaaabcccccddeeee -> (8)a(1)b(5)c(2)d(4)e

În această formă simplă, RLE comprimă „serii” de un singur octet pe doi octeți, ceea ce dăunează ratei de compresie. Am dori ca, dacă există un singur octet de un fel, să nu-l comprimăm. Dar atunci apar ambiguități la decomprimare: șirul comprimat

 abc

înseamnă „a, b, c” sau înseamnă „a de ord(b) ori, urmat de c”? Putem rezolva ambiguitatea introducând un octet special, un steguleț care arată că urmează o pereche (frecvență, caracter). Fie acest octet 255, atunci:

 aaaaaaaabcccccddeeee -> (255)(8)ab(255)(5)c(255)(2)d(255)(4)e

Două observații legate de steguleț:

• secvența steguleț-frecvență-caracter ocupă trei octeți, deci rentează să comprimăm doar seriile de minim 4 caractere
• stegulețul însuși trebuie compactat chiar dacă apare o singură dată, pentru a preveni ambiguitățile.

Contorul frecvenței are o limită superioară, de regulă 255, căci nu putem aloca pentru contor ba un octet, ba doi octeți.

RLE este folosit la faxuri (cele cu 1bpp se comprimă foarte bine) și la unele formate mai vechi de imagini.

Scurtă poveste despre COPY86M, încărcatul de pe bandă, RLE în timp real, folosirea memoriei grafice ca spațiu de stocare.

Huffman static

Ideea de bază a algoritmului lui Huffman este să asocieze caracterelor coduri mai scurte de un octet. Caracterele care apar mai frecvent vor primi coduri mai scurte. Este important ca niciun caracter să nu primească un cod care este prefix al codului altui caracter, altfel vor apărea ambiguități la decomprimare.

(exemplu de cod, de comprimare și de decomprimare)

Algoritmul lui Huffman face întâi o trecere prin fișier pentru a calcula frecvențele celor 256 de octeți. Apoi, el calculează un arbore binar strict în care muchiile stânga au codul 0, muchiile dreapta au codul 1, iar caracterele alfabetului stau în frunze. Codul comprimat al unui caracter urmează calea de la rădăcină spre frunza corespunzătoare caracterului.

(imagine cu frecvențele caracterelor și arborele Huffman rezultat; exemplu de comprimare și decomprimare)

Dându-se alfabetul $A={a_{1},a_{2},...,a_{n}}$ cu frecvențele $f(a_{1}),f(a_{2}),...,f(a_{n})$, un cod $C$ are costul

$B(C)=\sum _{i=1}^{n}f(a_{i})|C(a_{i})|$

Se poate demonstra că codul Huffman este optim, adică are costul mai mic decât al oricărui alt cod. Schiță de demonstrație:

• Pentru un arbore optim, arătăm că există un arbore cu același cost care plasează cele două caractere cu frecvențele minime ca frunze surori, la nivelul cel mai de jos al arborelui
• Apoi, prin inducție după n.

Generarea codului Hufmman se poate face:

• „naiv” cu un heap, în O(n log n)
• în O(n) (după sortare) cu două cozi, prin interclasare. Prima coadă conține inițial caracterele ordonate după frecvență. După combinarea a două noduri x și y, nodul rezultat (cu suma frecvențelor) este adăugat la cea de-a doua coadă.
• în O(n) (după sortare) cu o listă ordonată în care ținem minte pointerul ultimei inserări.

Dezavantaje:

• necesită stocarea arborelui, ceea ce umflă fișierul comprimat;
• necesită două parcurgeri ale datelor, ceea ce este lent, iar uneori este imposibil (de exemplu în cazul transmisiilor live)

Stocarea arborelui; Arborele Huffman canonic

Este necesară stocarea arborelui la începutul fișierului comprimat, pentru ca decompresorul să „înțeleagă” șirul comprimat. O metodă naivă parcurge arborele în preordine, emițând un bit '0' pentru noduri interne și '1' + codul caracterului pentru frunze. Această metodă necesită $2n-1+n\log n$ biți.

O metodă mai ingenioasă generează un arbore Huffman cu o structură aparte, care poate fi reprezentat în numai $n\log n$ biți (256 de octeți pentru cazul ASCII).

Pentru canonicalizare (vezi Wikipedia):

• sortăm caracterele după lungimea codului, apoi alfabetic
• atribuim caracterelor coduri noi, de aceeași lungime, dar minime din punct de vedere lexicografic.

Acum avem două metode de a stoca eficient acest arbore:

• enumerăm doar numărul de biți pentru fiecare caracter, în ordine alfabetică
• enumerăm, pentru fiecare lungime de cod, numărul de caractere cu acea lungime, apoi caracterele

Huffman dinamic (adaptiv)

Pentru a elimina cele două probleme ale algoritmului Huffman static, algoritmul adaptiv pornește cu un arbore cu un singur nod botezat NYT (not yet transmitted). Pe parcursul comprimării/decomprimării, următoarele proprietăți sunt respectate:

• Fiecare nod din arbore menține un total al aparițiilor caracterelor din subarborele său.
• La parcurgerea nodurilor de jos în sus și de la stânga la dreapta, totalurile întâlnite sunt ordonate crescător.

A doua proprietate se numește sibling property. La origine, ea era formulată invers: există o enumerare a nodurilor în ordine crescătoare a greutății astfel încât oricare două noduri surori să apară alăturat.

Procesul de comprimare/decomprimare este:

• Când întâlnește un simbol nou pentru prima oară, algoritmul împarte nodul NYT în două: un nod nou NYT și un nod pentru noul simbol.
• La fiecare simbol, algoritmul incrementează totalul pe frunza corespunzătoare și pe toți strămoșii ei.
• După incrementare, nodul este interschimbat cu ultimul nod (din ordonare) care are totalul egal cu al acelui nod.

Acest algoritm se numește FGK (Faller-Gallager-Knuth). Un al doilea algoritm, al lui Vitter, aplică o metodă diferită de promovare a nodurilor care generează arbori mai echilibrați.

Algoritmul Huffman adaptiv are eficiență comparabilă cu Huffman static. El oferă avantaje la nivel local, pe porțiuni de date: caracterele care apar des capătă coduri mai scurte (apoi le pot lăsa locul altor caractere care încep să apară des).

Algoritmul LZW (Lempel-Ziv-Welch)

Algoritmul LZW face parte din clasa algoritmilor de compresie cu dicționar. Mărimea dicționarului poate fi

• fixă, de exemplu 4096 de poziții, caz în care fiecare cod emis la ieșire va avea 12 biți;
• dinamică, pornind cu un singur bit și crescând pe măsură ce dicționarul se umple. Această metodă este utilă pentru fișiere relativ mici.

La inițializare, dicționarul conține tot alfabetul (șiruri de un caracter) pe pozițiile 0-255.

Pentru comprimare:

• citește caractere cât timp acel șir există în dicționar
• emite la ieșire codul pentru el
• adaugă la dicționar acel prefix + următorul caracter

Decompresorul este cu un pas în urmă:

• dacă vede la intrare codurile X și Z, emite șirul dict[X], apoi inserează în dicționar șirul dict[X] + dict[Z][0].
• X este garantat că există în dicționar. Dar dacă Z nu există în dicționar? Exemplu: cazul cSsSc, unde cS există în dicționar, dar cSc nu.

Reprezentarea dicționarului: prima structură care ne vine în minte este un trie. Totuși, există una mai eficientă. Știm că, pentru fiecare șir din dicționar, „părintele” obținut prin eliminarea ultimului caracter aparține și el dicționarului. Deci stocăm fiecare intrare prin indicele părintelui + codul ASCII al ultimului caracter. Aceasta rezultă în O(n) memorie.

Cum căutăm prin dicționar? Respectiv, pentru un șir p citit, cum știm dacă p mai există sau nu în arbore? Din nou, putem folosi un trie, dar din nou există o reprezentare mai compactă. Știm că citim caractere de la intrare cât timp șirul există un dicționar. Pentru a trece de la un șir de lungime k la k + 1, ținem o matrice cu n linii și |Σ| coloane care ne spune indicele următorului șir. Dacă M(i, c) = -1, iar la intrare vedem caracterul c, atunci noul șir nu mai există în dicționar.

În teorie, dicționarul nu se mai modifică odată ce se umple. Dacă natura fișierului se schimbă ulterior, algoritmul va începe să comprime prost. De aceea, compresorul poate decide să reseteze dicționarul. În acest caz, el va emite un cod special, pentru ca și decompresorul să știe să facă același lucru.

Algoritmul LZW este folosit în fișiere GIF, TIFF, PDF și în programul compress, o unealtă de UNIX.

El a fost acoperit de patente între 1983 și 2003. Într-o vreme, deținătorii (Unisys) chiar au încercat să impună taxe pentru folosirea LZW în GIF-uri. Această tentativă a generat controverse, proteste și, într-un final, formatul PNG, care are specificații libere de patente.

Algoritmul LZ77

Și acest algoritm este bazat pe dicționar. Principiul lui de bază este să rețină un sliding window -- o istorie a ultimilor (de exemplu) 32 KB. Apoi comprimă șiruri de caractere de la intrare emițând perechi de numere (lungime, distanță) cu semnificația: „mergi înapoi în fereastră distanță caractere și copiază lungime caractere.

Desigur, arta implementării acestui concept teoretic constă din:

• găsirea în istorie a unor șiruri cât mai lungi care să se potrivească cu cele văzute la intrare
• eficiența căutării

Fereastra celor 32 KB anteriori este implementată cu un buffer rotativ -- nimic special aici.

Cum căutăm șirul care urmează la intrare prin fereastra trecută? Ca orice căutare pe șiruri, cu algoritmul KMP. :-) Doar că el trebuie particularizat situației curente:

• funcția funcția π se calculează pe măsură ce este nevoie de ea;
• cel mai lung prefix este dat de starea maximă în care a ajuns algoritmul KMP.

Mai există și alte implementări

Alte considerente:

• unde nu există niciun caracter în istorie, sau codarea nu rentează, emite codul caracterului
• este necesar un bit care indică dacă urmează informație codată / necodată
• cu cât este mai mare fereastra, cu atât algoritmul este mai lent, dar rata de compresie este mai bună
• un exemplu exotic: length > offset pentru șirul Blah blah blah blah.
• decompresia este foarte rapidă, căci nu mai face KMP, ci doar copiază bucățile care îi sunt indicate
• oferă acces aleator la nivel de bloc: la fiecare 32 KB, golesc fereastra
  • dar rata de compresie scade ușor, căci scade lungimea medie a ferestrei în care putem căuta
  • în plus, această tehnică are nevoie de un index care să memoreze începutul fiecărui bloc în fișierul comprimat
• cea mai populară implementare este deflate, care este trece ieșirea de la LZ77 printr-un Huffman adaptiv

LZ77 (implementarea deflate) este folosită în zip, gzip, formatul PNG etc.