După ce am urmărit drama HBO "Silicon Valley", am fost mereu interesat de algoritmii de compresie. Richard Hendricks și algoritmul său de compresie middle out din el sunt, desigur, falși, dar după ce am căutat intens, am descoperit că există un astfel de geniu al algoritmului de compresie în viața reală.
Yann Collet a inventat algoritmul de compresie LZ4 în 2011. Desigur, algoritmul LZ4 nu este la fel de grozav ca Middle Out, dar este cunoscut pentru viteza sa de compresie invincibilă și viteza de decompresie mai rapidă atunci când se poate garanta o anumită rată de compresie.
Nu voi intra în detalii aici despre evaluarea vitezei sale de compresie; dacă sunteți interesați, puteți citi acest articol comparativ:Autentificarea cu hyperlink este vizibilă.
De asemenea, atașată este adresa github a LZ4:Autentificarea cu hyperlink este vizibilă.
Acest articol se concentrează pe explicarea principiului algoritmului de compresie LZ4. Un mare zeu a scris o explicație a algoritmului LZ4 înainte:Autentificarea cu hyperlink este vizibilă.Dar când învățam înainte, am simțit că acest articol nu este foarte prietenos cu începătorii, așa că am început un alt articol pentru începători ca mine.
Dacă rezumi într-o singură propoziție, LZ4 este un LZ77 care stochează un dicționar cu un tabel hash de dimensiunea 16k și simplifică recuperarea.
LZ4 este un algoritm de compresie fără pierderi care oferă o viteză de compresie de > 500 MB/s per nucleu, ce poate fi scalată cu procesoare multi-core. Are decodoare extrem de rapide, cu viteze de câțiva GB/s per nucleu, atingând adesea limitele de viteză a memoriei RAM pe sistemele multi-core.
Viteza poate fi ajustată dinamic, selectând un factor de "accelerație" care schimbă raportul de compresie pentru viteză mai mare. Pe de altă parte, este oferită și o derivată cu compresie ridicată LZ4_HC pentru a crește compresia în detrimentul timpului CPU. Toate versiunile au aceeași viteză de decompresie.
Deci, ce este LZ77?
Compresia și principiul LZ77
LZ77 este un algoritm care aplică un dicționar pentru compresie. În termeni simpli, este pentru a permite programului să observe (să se uite în dicționar) dacă datele văzute în prezent sunt duplicate cu cele anterioare, iar dacă da, salvăm distanța (offset) și lungimea câmpurilor duplicate pentru a înlocui câmpurile duplicate și a comprima datele.
referințăAutentificarea cu hyperlink este vizibilă.
Pentru un șir de litere A A B C B B A B B C, când este citit al doilea A, programul salvează (1,1) (1 cifră din cea precedentă, lungimea 1), iar similar, când al doilea B este citit, programul salvează (2,1) (distanța 2, lungimea 1).
Dar dacă șirul este mai lung și programul înregistrează datele în dicționar tot timpul, căutarea câmpurilor duplicate devine extrem de consumatoare de timp, pentru că în cel mai rău caz programul parcurge întregul dicționar cu fiecare literă nouă citită. LZ77 folosește o metodă cu fereastră glisantă pentru a rezolva această problemă.
Similar cu punctul de pornire al TCP folosind o fereastră glisantă, o fereastră glisantă poate micșora suprafața cache-ului pentru a evita procesarea prea multor date stocate în cache simultan. În LZ77, dicționarul nu crește tot timpul, ci elimină primele caractere adăugate în dicționar atunci când acesta depășește dimensiunea maximă specificată de dicționar, pentru a asigura că dimensiunea dicționarului este menținută întotdeauna la dimensiunea maximă specificată.
Să presupunem că lungimea dicționarului este 3
| Dicționar |
| A | A B C B B A B C
Producție (0,0,A)
| A A | B C B B A B C
Producție (1,1)
| A A B | C B B A B C
Producție (0,0,B)
A | A B C | B B A B C
Producție (0,0,C)
A A | B C B | B A B C
Ieșire(2,1)
Cealaltă parte a ferestrei glisante este cache-ul care trebuie căutat (buffer-ul de tip "look forward" nu are o traducere oficială). Cache-ul care trebuie căutat este partea necomprimată a lungimii cea mai apropiată de dicționar. Algoritmul LZ77 va potrivi cel mai lung șir din această parte a caracterului care este același cu dicționarul. Exemplul anterior poate fi considerat ca un buffer de anticipare de 1.
Să presupunem că lungimea dicționarului este 5 și dimensiunea cache-ului ce trebuie căutată este 3
| Dicționar | tampon de anticipare |
A | A B C B B | A B C |
Ieșire(5,3)
Cel mai lung șir care se potrivește este ABC
Proces complet de compresie:
Să presupunem că lungimea dicționarului este 5 și dimensiunea cache-ului ce trebuie căutată este 3
| Dicționar | tampon de anticipare |
| A A B | C B B A B C
Producție (0,0,A)
| A | A B C | B B A B C
Producție (1,1)
| A A | B C B | B A B C
Producție (0,0,B)
| A A B | C B | A B C
Producție (0,0,C)
| A A B C | B B A | B C
Ieșire(2,1)
| A A B C B | B A B | C
Producție (1,1)
A | A B C B B | A B C |
Ieșire(5,3)
A A B C | B B A B C | 。。。 |
Nu este nevoie să salvezi dicționarul în fișierul de ieșire al compresorului, deoarece programul de decompresie restaurează dicționarul prin potrivirea unităților de ieșire.
Procesul de decompresie
Unul dintre marile avantaje ale algoritmului LZ77 este că se decomprimă foarte rapid.
Dacă prima unitate potrivită este (0,0,A), atunci A este de ieșire.
A doua unitate potrivită este (1,1), care copiază biții anteriori din șirul de ieșire și produce A dacă lungimea copierii este 1.
。。。
Dacă ultima unitate corespunzătoare este (5,3), atunci uită-te înapoi cu 5 biți în șirul de ieșire de copiere, iar dacă lungimea de copie este 3, atunci ieși A, B, C.
Partea cea mai consumatoare de timp a compresiei algoritmului LZ77 este găsirea celui mai lung caracter corespunzător din cache care trebuie căutat în dicționar. Dacă dicționarul și cache-ul de căutat sunt prea scurte, șansele de a găsi o potrivire sunt mici. Prin urmare, LZ4 a schimbat algoritmul de potrivire pentru LZ77.
În primul rând, dicționarul algoritmului LZ4 este un tabel hash. Cheia din dicționar este un șir de 4 octeți, fiecare cheie corespunzând unui singur slot, iar valoarea din slot este poziția acestui șir.
În loc să caute în cache, LZ4 citește patru octeți simultan din fișierul de intrare, apoi caută slotul corespunzător șirului din tabelul hash, care de acum înainte va fi denumit șirul actual.
Dacă ai ajuns la ultimele 12 caractere, pune-le direct în fișierul de ieșire.
Dacă nu există nicio valoare atribuită în slot, înseamnă că cei patru octeți apar pentru prima dată, adaugă acești patru octeți și poziții în tabelul hash și continuă căutarea.
Dacă există o atribuire în slot, înseamnă că am găsit o valoare potrivită.
Dacă valoarea din slot plus dimensiunea ferestrei de slider < poziția caracterului curent, atunci poziția de potrivire depășește dimensiunea blocului, iar programul actualizează valoarea din slotul de hash la poziția șirului curent.
LZ4 va verifica dacă a existat un conflict de hash. Dacă cei 4 octeți din slot nu sunt aceiași cu șirul curent, trebuie să existe un conflict de hash. Xxhash-ul propriu al autorului este cunoscut și pentru eficiența sa, dar conflictele sunt inevitabile. În caz de conflict, programul actualizează și valoarea din slotul de hash la poziția curentă a șirului
În final, putem confirma că potrivirea este validă, iar programul va continua să vadă dacă caracterele următoare din șirul corespunzător sunt aceleași. În final, copiați toate caracterele de la sfârșitul potrivirii valide anterioare la începutul acestei potriviri valide în fișierul comprimat și adăugați secvența de potrivire a acestei potriviri valide.
Collet numește unitățile corespunzătoare generate de secvențele LZ4, iar acestea alcătuiesc fișierul comprimat LZ4. Detaliile sunt următoarele:
Jetonul are o lungime de 1 octet, primele 4 cuvinte având lungimea literală, iar ultimele 4 cuvinte lungimea potrivirii. După cum s-a menționat anterior, toate caracterele de la sfârșitul potrivirii valabile anterioare până la începutul acestei potriviri valide vor fi copiate într-un fișier comprimat, aceste fișiere necomprimate sunt literale, iar lungimea lor este literală.
Literalmente urmat de deviație. Ca și în LZ77, deviația și lungimea potrivirii se referă la lungimea șirului curent față de potrivirea sa, iar lungimea potrivirii se referă la lungimea lungimii potrivirii șirului curent cu același șir în dicționar. În decompresie înseamnă să treci prin el pentru a găsi șirul de copiat și lungimea de copiat. Magnitudinea deviației este fixă.
În figură, lungimea literală+ și lungimea potrivirii+ sunt dacă literalul sau lungimea potrivirii 4 cuvinte din jeton nu este suficientă, ele vor continua să crească în pozițiile corespunzătoare. 4 cuvinte pot reprezenta 0-15, iar dacă mai sunt alții, se adaugă un octet, adică se adaugă 255 la dimensiune până când octetul devine mai mic de 255. În lungimea de potrivire, 0 reprezintă 4 octeți.
Ultimii 12 octeți se termină literalmente pentru că au fost copiați direct.
Să ne uităm la cod (python este mai abstract)
Rezumat: După toate acestea, încă nu am rezumat de ce LZ4 este atât de rapid. Să comparăm mai întâi căutarea din dicționar între LZ77 și LZ4. LZ77 nativ caută dicționare căutând cea mai mare potrivire în cache-ul de căutat și în dicționar. Aceasta este o problemă de a găsi cel mai mare șir, identic, în două șiruri. Dacă nu folosim programare dinamică, în cel mai rău caz trebuie să luăm în considerare toate subșirurile unui șir și apoi să le potrivim într-un alt șir. Dacă × folosim programare dinamică, vom folosi un tabel pentru a menține cea mai lungă potrivire în dinamică, ceea ce ne va permite să finalizăm potrivirea doar în cazul lui O(m*n). Și asta doar pentru o pereche de cache-uri de căutare și dicționare. În cel mai rău caz, dacă nu există potriviri, atunci LZ77 va trebui să numere (lungimea întregului fișier - lungimea cache-ului ce urmează a fi căutat) ca multe astfel de probleme de potrivire. LZ4 folosește de fapt un nivel mai mare de programare dinamică: stochează 4 octeți și pozițiile lor într-un tabel hash, apoi potrivește de fiecare dată 4 octeți noi de date doar pentru a vedea dacă valorile din tabelul hash sunt valide. După ce găsești o valoare validă de potrivire, dacă te uiți la datele ulterioare ale celor două seturi de valori de potrivire, poți găsi și cea mai lungă potrivire. Deoarece fiecare cheie a tabelului hash LZ4 corespunde doar unui singur slot, munca de găsire, adăugare și modificare a tabelului de hash necesită doar O(1). Dacă se găsesc mai multe potriviri după potrivire, sunt necesare mai multe comparații de grup, dar în timpul total, aceste comparații vor înlocui timpul suplimentar pentru căutarea tabelului hash, astfel încât timpul total al algoritmului LZ4 este doar O(n). Trebuie să admir frumusețea algoritmului lui Collet! Pentru a face algoritmul și mai rapid, Collet setează dimensiunea implicită a tabelului hash la 16k, recomandată să nu depășească 32k, astfel încât să poată fi introdusă în cache-ul L1 al aproape tuturor procesoarelor (Intel). Toată lumea știe că viteza și raportul memoriei cache-ului L1 al CPU-ului sunt foarte diferite, așa că nu este surprinzător că LZ4 zboară rapid, ca să nu mai vorbim că ecuația hash folosită în tabelul hash LZ4 este încă cea mai rapidă xxhash. Desigur, un astfel de design are dezavantajele sale. Cu cât tabelul hash este mai mic, cu atât are mai puține chei. Aceasta înseamnă că vor apărea mai multe conflicte de hash, ceea ce este inevitabil. Și mai multe coliziuni de hash înseamnă mai puține potriviri. Iar un tabel hash mai mic înseamnă și o fereastră glisantă mai mică, ceea ce înseamnă că mai multe potriviri vor fi eliminate pentru că sunt prea departe. Mai puține potriviri reprezintă un raport de compresie mai mic, motiv pentru care LZ4 are un raport de compresie mai puțin proeminent. Privind în viitor LZ4 are o gamă largă de scenarii de aplicare. Așa cum middle out a fost folosit în VR în Silicon Valley, LZ4 poate crește utilizarea lățimii de bandă aducând mai puține IO-uri, cu prețul unei latențe foarte scăzute datorită vitezei sale de compresie foarte mari. Există și o mică presupunere: dacă există un CPU cu un cache mai mare la nivelul 1, poate LZ4 să crească raportul de compresie fără a compromite viteza?
Original:Autentificarea cu hyperlink este vizibilă. |
Postat pe 03.01.2022 13:54:23
|
|
|
|
