Efter at have set HBO-dramaet "Silicon Valley" har jeg altid været interesseret i komprimeringsalgoritmer. Richard Hendricks og hans midter-ud-komprimeringsalgoritme i den er selvfølgelig falske, men efter at have googlet grundigt, fandt jeg ud af, at der findes sådan en komprimeringsalgoritme i virkeligheden.
Yann Collet opfandt LZ4-komprimeringsalgoritmen i 2011. Selvfølgelig er LZ4-algoritmen ikke lige så fantastisk som middle out, men den er kendt for sin uovervindelige komprimeringshastighed og hurtigere dekomprimeringshastighed, når en vis komprimeringshastighed kan garanteres.
Jeg vil ikke gå i detaljer her om evalueringen af dens kompressionshastighed; hvis du er interesseret, kan du læse denne sammenligningsartikel:Hyperlink-login er synlig.
Vedhæftet er også github-adressen til LZ4:Hyperlink-login er synlig.
Denne artikel fokuserer på at forklare princippet bag LZ4-komprimeringsalgoritmen. En stor gud skrev en forklaring af LZ4-algoritmen før:Hyperlink-login er synlig.Men da jeg studerede før, følte jeg, at denne artikel ikke var særlig venlig over for nybegyndere, så jeg startede en anden artikel for nybegyndere som mig.
Hvis du opsummerer det i én sætning, er LZ4 en LZ77, der gemmer en ordbog med en hashtabel på 16k og forenkler hentningen.
LZ4 er en tabsfri komprimeringsalgoritme, der tilbyder en komprimeringshastighed på > 500 MB/s pr. kerne, som kan skaleres med multi-core CPU'er. Den har ekstremt hurtige dekodere med hastigheder på flere GB/s pr. kerne, som ofte når RAM-hastighedsgrænser på flerkerne-systemer.
Hastigheden kan justeres dynamisk, hvor en "accelerations"-faktor vælges, der bytter kompressionsforholdet for højere hastighed. På den anden side leveres der også en højkomprimeret afledt LZ4_HC for at øge kompressionen på bekostning af CPU-tid. Alle versioner har samme dekompressionshastighed.
Så hvad er LZ77?
LZ77-kompression og princip
LZ77 er en algoritme, der anvender en ordbog til komprimering. På almindeligt dansk er det for at lade programmet observere (se i ordbogen), om de data, der ses, er duplikeret med det forrige, og hvis det er tilfældet, gemmer vi afstanden (offset) og længden af de duplikerede felter for at erstatte de dubletfelter og komprimere dataene.
henvisningHyperlink-login er synlig.
For en bogstavstreng A A B C B B A B C, når den anden A læses, gemmer programmet (1,1) (1 ciffer fra den forrige, længde 1), og på samme måde, når den anden B læses, gemmer programmet (2,1) (afstand 2, længde 1).
Men hvis strengen er længere, og programmet hele tiden registrerer dataene i ordbogen, bliver søgningen efter dubletter ekstremt tidskrævende, fordi programmet i værste fald gennemgår hele ordbogen for hvert nyt bogstav, der læses. LZ77 bruger en sliding window-metode til at løse dette problem.
Ligesom udgangspunktet for TCP ved brug af et glidende vindue kan et glidende vindue formindske cacheområdet for at undgå at behandle for meget cachet data på samme tid. I LZ77 øges ordbogen ikke hele tiden, men kasserer de første tegn, der tilføjes til ordbogen, når de overstiger den maksimale størrelse, der er angivet af ordbogen, for at sikre, at ordbogens størrelse altid holdes ved den angivne maksimale størrelse.
Antag, at ordbogslængden er 3
| ordbog |
| A | A B C B B A B C
Output (0,0,A)
| A A | B C B B A B C
Output(1,1)
| A A B | C B B A B C
Output (0,0,B)
A | A B C | B B A B C
Output (0,0,C)
A A | B C B | B A B C
Output(2,1)
Den anden del af glidende vinduet er cachen, der skal søges i (lookahead buffer har ingen officiel oversættelse). Cachen, der skal søges i, er den ukomprimerede del af længden, der ligger tættest på ordbogen. LZ77-algoritmen vil matche den længste streng i denne del af tegnet, som er den samme som i ordbogen. Det forrige eksempel kan betragtes som en fremadrettet buffer på 1.
Antag, at ordbogslængden er 5, og cache-størrelsen, der skal søges i, er 3
| ordbog | Se fremad buffer |
A | A B C B B | A B C |
Output(5,3)
Den længste streng, der matcher, er ABC
Fuldstændig kompressionsproces:
Antag, at ordbogslængden er 5, og cache-størrelsen, der skal søges i, er 3
| ordbog | Se fremad buffer |
| A A B | C B B A B C
Output (0,0,A)
| A | A B C | B B A B C
Output(1,1)
| A A | B C B | B A B C
Output (0,0,B)
| A A B | C B B | A B C
Output (0,0,C)
| A A B C | B B A | B C
Output(2,1)
| A A B C B | B A B | C
Output(1,1)
A | A B C B B | A B C |
Output(5,3)
A A B C | B B A B C | 。。。 |
Der er ikke behov for at gemme ordbogen i kompressorens outputfil, fordi dekompressionsprogrammet gendanner ordbogen ved at matche outputenhederne.
Dekompressionsproces
En af de store fordele ved LZ77-algoritmen er, at den er meget hurtig at dekomprimere.
Hvis den første matchende enhed er (0,0,A), så outputtes A.
Den anden matchende enhed er (1,1), som kopierer det forrige bit i output-strengen og udskriver A, hvis kopilængden er 1.
。。。
Hvis den sidste matchende enhed er (5,3), så kig tilbage 5 bit i kopi-output-strengen, og hvis kopilængden er 3, så output A, B, C.
Den mest tidskrævende del af komprimeringen af LZ77-algoritmen er at finde det længste matchende tegn i cachen, der skal søges i ordbogen. Hvis ordbogen og cachen, der skal søges i, er for korte, er chancerne for at finde et match små. Derfor har LZ4 ændret matchningsalgoritmen for LZ77.
For det første er ordbogen for LZ4-algoritmen en hash-tabel. Nøglen i ordbogen er en 4-byte streng, hver nøgle svarer kun til én slot, og værdien i sloten er positionen af denne streng.
I stedet for at søge i cachen læser LZ4 fire bytes ad gangen fra inputfilen og leder derefter efter den plads, der svarer til strengen i hashtabellen, som herefter kaldes den nuværende streng.
Hvis du har nået de sidste 12 tegn, læg dem direkte i outputfilen.
Hvis der ikke er nogen værdi tildelt i slotten, betyder det, at de fire bytes optræder første gang, tilføjer disse fire bytes og positioner til hashtabellen og fortsætter søgningen.
Hvis der er en tildeling i pladsen, betyder det, at vi har fundet en matchende værdi.
Hvis værdien i slotten plus størrelsen af slidervinduet < positionen af det aktuelle tegn, overstiger matchpositionen størrelsen af blokken, og programmet opdaterer værdien i hash-sloten til positionen af den aktuelle streng.
LZ4 vil tjekke, om der har været en hash-konflikt. Hvis de 4 bytes i slotten ikke er de samme som den aktuelle streng, må der være en hash-konflikt. Forfatterens egen xxhash er også kendt for sin effektivitet, men konflikter er uundgåelige. I tilfælde af konflikt opdaterer programmet også værdien i hash-slotten til strengens nuværende position
Endelig kan vi bekræfte, at matchet er gyldigt, og programmet vil fortsætte med at se, om de efterfølgende tegn i matchende streng er de samme. Til sidst kopieres alle tegn fra slutningen af det forrige gyldige match til begyndelsen af dette gyldige match til den komprimerede fil, og tilføjes matchsekvensen af dette gyldige match.
Collet kalder de matchende enheder, der udsendes af LZ4-sekvenser, og de udgør den komprimerede LZ4-fil. Detaljerne er som følger:
Tokenet er 1 byte langt, hvor de første 4 ord er den bogstavelige længde, og de sidste 4 ord er matchlængden. Som nævnt tidligere vil alle tegn fra slutningen af det forrige gyldige match til starten af dette gyldige match blive kopieret til en komprimeret fil, disse ukomprimerede filer er literale, og deres længde er literal længde.
Bogstaveligt talt efterfulgt af afvigelse. Som i LZ77 refererer afvigelse og matchlængde til længden af den aktuelle streng fra dens match, og matchlængden refererer til længden af matchlængden af den nuværende streng til samme streng i ordbogen. Ved dekompression går man igennem den for at finde strengen, der skal kopieres, og længden, der skal kopieres. Størrelsen af afvigelsen er fast.
I figuren er literal length+ og match length+, hvis de letterlige eller match-længde 4 ord i tokenet ikke er nok, vil de fortsætte med at stige i de tilsvarende positioner. 4 ord kan repræsentere 0-15, og hvis der er flere, tilføj en byte, det vil sige læg 255 til størrelsen, indtil byten er mindre end 255. I den matchende længde repræsenterer 0 4 bytes.
De sidste 12 bytes slutter bogstaveligt talt, fordi det blev kopieret direkte.
Lad os se på koden (python er mere abstrakt)
Resumé Når det er sagt, har jeg stadig ikke opsummeret, hvorfor LZ4 er så hurtig. Lad os først sammenligne ordbogssøgningen mellem LZ77 og LZ4. Den native LZ77 søger efter ordbøger ved at lede efter det største match i cachen, der skal søges i, og i ordbogen. Dette er et problem med at finde den største identiske streng i to strenge. Hvis vi ikke bruger dynamisk programmering, så er vi i værste fald nødt til at betragte alle delstrengene i én streng og derefter matche dem i en anden streng. Hvis ×vi bruger dynamisk programmering, vil vi bruge en tabel til at holde det længste match i den dynamiske sammenhæng, hvilket kun tillader os at fuldføre matchet i tilfælde af O(m*n). Og det er kun for et par søgecacher og ordbøger. I værste fald, hvis der ikke er nogen match, skal LZ77 tælle (længden af hele filen – længden af cachen, der skal søges i) som mange sådanne matchningsproblemer. LZ4 bruger faktisk et større niveau af dynamisk programmering: det gemmer 4 bytes og deres positioner i en hash-tabel og matcher derefter en ny 4 bytes data hver gang kun for at se, om værdierne i hashtabellen er gyldige. Efter at have fundet en gyldig matchende værdi, kan du ved at se på opfølgningsdataene for de to sæt matchende værdier også finde det længste match. Da hver nøgle i LZ4-hashtabellen kun svarer til 1 slot, kræver arbejdet med at finde, tilføje og ændre hashtabellen kun O(1). Hvis flere matches findes efter matching, kræves flere gruppesammenligninger, men i den samlede tid vil disse sammenligninger erstatte mere tid til at slå hashtabellen op, så den samlede tid for LZ4-algoritmen kun er O(n). Jeg må beundre skønheden i Collets algoritme! For at gøre algoritmen endnu hurtigere sætter Collet standardstørrelsen på hashtabellen til 16k, hvilket anbefales ikke at overstige 32k, så den kan lægges i L1-cachen på næsten alle CPU'er (Intel). Alle ved, at hastigheds- og hukommelsesforholdet i CPU L1-cache er meget forskelligt, så det er ikke overraskende, at LZ4 flyver hurtigt, for ikke at nævne at hash-ligningen, der bruges i LZ4's hash-tabel, stadig er den hurtigste xxhash. Selvfølgelig har et sådant design sine ulemper. Jo mindre hashtabellen er, desto færre nøgler har den. Det betyder, at flere hash-konflikter vil opstå, hvilket er uundgåeligt. Og flere hash-kollisioner betyder færre matches. Og en mindre hashtabel betyder også et mindre glidende vindue, hvilket betyder, at flere matches bliver kasseret, fordi de er for langt væk. Færre matches giver et lavere kompressionsforhold, hvilket er grunden til, at LZ4 har et mindre fremtrædende kompressionsforhold. Looking Ahead LZ4 har et bredt udvalg af anvendelsesscenarier. Ligesom middle out blev brugt i VR i Silicon Valley, kan LZ4 øge båndbreddeudnyttelsen ved at bringe færre IO'er på bekostning af meget lav latenstid på grund af sin meget hurtige komprimeringshastighed. Der er også en lille spekulation: Hvis der er en CPU med større cache på niveau 1, kan LZ4 så øge kompressionsforholdet uden at gå på kompromis med hastigheden?
Oprindelig:Hyperlink-login er synlig. |
Opslået på 03/01/2022 13.54.23
|
|
|
|
