Note de curs, clasele 11-12, 19 aprilie 2013

Algoritmi de compresie, continuare

Recapitulare

• Huffman static are două dezavantaje:
  1. trebuie să salveze arborele la început;
  2. trebuie să parcurgă fișierul de două ori, o dată pentru a construi arborele și o dată pentru codarea propriu-zisă.
• Metoda Shannon-Fano de construire a arborelui

Huffman dinamic

• Elimină cele două probleme ale algoritmului Huffman static
• Pornește cu un arbore vid, la care adaugă noduri pe măsură ce apar
• După fiecare caracter, modifică arborele astfel încât el să rămână arbore Huffman optim (să minimizeze $\sum f(i)l(i)$ pentru caracterele întâlnite până acum).
• Exemplu grafic
• Algoritmul Vitter de modificare (în linii mari)
• Avantaje la nivel local: caracterele care apar des capătă coduri mai scurte (apoi le pot lăsa locul altor caractere care apar des)
• Eficiență comparabilă cu Huffman static

LZW

• parte din clasa algoritmilor de compresie cu dicționar
• metoda generală:
  • din următoarele caractere de la intrare, găsește prefixul cel mai lung care există în dicționar
  • emite codul pentru el
  • adaugă la dicționar acel prefix + următorul caracter
• dicționarul este prepopulat cu tot alfabetul (șiruri de un caracter)
• codare fixă (de exemplu 12 biți) / variabilă
• decodorul este cu un pas în urmă:
  • dacă vede la intrare codurile X și Z, trebuie să insereze în dicționar șirul dict[X] + dict[Z][0].
  • dar dacă Z nu este în dicționar? Cazul cScSc.
• cum reprezentăm dicționarul?
  • cu trie -- Mihai Andreescu
  • cu indicele primelor caractere + codul ASCII al ultimului
  • folosim deci doar O(n) memorie, nu (potențial) O(n²)
• cum căutăm în dicționar?
  • cu trie -- urmărim arborele mergând spre frunze
  • cu o matrice de n linii și |Σ| coloane care ne spune indicele următorului șir
• cod special de golire a dicționarului, când începe să nu mai comprime prea bine
• compresorul și decompresorul trebuie să se pună de acord asupra lățimii codului, asupra formatului dicționarului și asupra packing order: little / big endian
• folosit în fișiere GIF și în compress
• probleme cu patentele, 1983 - 2003

LZ77 (și LZ78)

• în loc de dicționar folosește un sliding window -- o istorie a ultimilor 32 KB
• metoda generală:
  • din următoarele caractere de la intrare, găsește prefixul cel mai lung care apare în istorie
  • emite perechea <length, offset> cu semnificația „mergi offset caractere înapoi în istorie și copiază length caractere”
  • 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ă
• cum facem căutarea? KMP modificat
  • 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.
• 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 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
  • folosită în zip, gzip, formatul PNG etc.

Diverse

• despre compresia audio / video
• delta encoding (codarea diferențelor)
• cadre de sincronizare
• ce se întâmplă cu cadrul de sincronizare când derulez înainte / înapoi
• compromisuri între memoria folosită, timpul de comprimare, timpul de decomprimare, rata de comprimare