Etter å ha sett HBO-dramaet «Silicon Valley», har jeg alltid vært interessert i komprimeringsalgoritmer. Richard Hendricks og hans midt-ut-komprimeringsalgoritme i den er selvfølgelig falske, men etter å ha googlet grundig, fant jeg ut at det finnes et slikt kompresjonsalgoritme-geni i virkeligheten.
Yann Collet oppfant LZ4-komprimeringsalgoritmen i 2011. Selvfølgelig er ikke LZ4-algoritmen like fantastisk som middle out, men den er kjent for sin uovervinnelige komprimeringshastighet og raskere dekomprimeringshastighet når en viss komprimeringshastighet kan garanteres.
Jeg vil ikke gå i detalj her om evalueringen av kompresjonshastigheten, hvis du er interessert, kan du lese denne sammenligningsartikkelen:Innloggingen med hyperkoblingen er synlig.
Også vedlagt er github-adressen til LZ4:Innloggingen med hyperkoblingen er synlig.
Denne artikkelen fokuserer på å forklare prinsippet bak LZ4-komprimeringsalgoritmen. En stor gud skrev en forklaring av LZ4-algoritmen før:Innloggingen med hyperkoblingen er synlig.Men da jeg studerte før, følte jeg at denne artikkelen ikke var særlig vennlig for nybegynnere, så jeg startet en ny artikkel for nybegynnere som meg.
Hvis du oppsummerer det i én setning, er LZ4 en LZ77 som lagrer en ordbok med en hashtabell på 16k og forenkler hentingen.
LZ4 er en tapsfri komprimeringsalgoritme som tilbyr en komprimeringshastighet på > 500 MB/s per kjerne, som kan skaleres med flerkjernede CPU-er. Den har ekstremt raske dekodere med hastigheter på flere GB/s per kjerne, og når ofte RAM-hastighetsgrenser på flerkjernesystemer.
Hastigheten kan justeres dynamisk, ved å velge en «akselerasjons»-faktor som bytter kompresjonsforholdet mot høyere hastighet. På den annen side tilbys også en høykomprimeringsderivat LZ4_HC for å øke komprimeringen på bekostning av CPU-tid. Alle versjoner har samme dekomprimeringshastighet.
Så hva er LZ77?
LZ77-komprimering og prinsipp
LZ77 er en algoritme som bruker en ordbok for komprimering. Enkelt sagt er det for å la programmet observere (se i ordboken) om dataene som vises nå er duplisert med det forrige, og hvis det er tilfelle, lagrer vi avstanden (offset) og lengden på de dupliserte feltene for å erstatte de dupliserte feltene og komprimere dataene.
referanseInnloggingen med hyperkoblingen er synlig.
For en bokstavrekke A A B C B B B A B C, når den andre A leses, lagrer programmet (1,1) (1 siffer fra den forrige, lengde 1), og på samme måte, når den andre B leses, lagrer programmet (2,1) (avstand 2, lengde 1).
Men hvis strengen er lengre og programmet hele tiden registrerer dataene i ordboken, blir søket etter dupliserte felt ekstremt tidkrevende, fordi i verste fall går programmet gjennom hele ordboken for hver nye bokstav som leses. LZ77 bruker en glidende vindu-metode for å løse dette problemet.
På samme måte som utgangspunktet for TCP med et glidende vindu, kan et glidevindu krympe cache-området for å unngå å behandle for mye bufret data samtidig. I LZ77 øker ikke ordboken hele tiden, men forkaster de første tegnene som legges til i ordboken når de overstiger maksimal størrelse spesifisert av ordboken, for å sikre at ordbokens størrelse alltid opprettholdes på den spesifiserte maksimale størrelsen.
Anta at ordboklengden er 3
| Ordbok |
| A | A B C B B A B C
Utgang (0,0,A)
| A A | B C B B A B C
Output(1,1)
| A A B | C B B A B C
Utgang (0,0,B)
A | A B C | B B A B C
Utgang (0,0,C)
A A | B C B | B A B C
Output(2,1)
Den andre delen av det glidende vinduet er cachen som skal søkes i (look ahead buffer har ingen offisiell oversettelse). Cachen som skal søkes i, er den ukomprimerte delen av lengden som er nærmest ordboken. LZ77-algoritmen vil matche den lengste strengen i denne delen av tegnet som er den samme som i ordboken. Det forrige eksempelet kan betraktes som en fremover-buffer på 1.
Anta at ordboklengden er 5 og cache-størrelsen som skal søkes i er 3
| Ordbok | Se fremover buffer |
A | A B C B B | A B C |
Output(5,3)
Den lengste strengen som matcher er ABC
Fullstendig kompresjonsprosess:
Anta at ordboklengden er 5 og cache-størrelsen som skal søkes i er 3
| Ordbok | Se fremover buffer |
| A A B | C B B A B C
Utgang (0,0,A)
| A | A B C | B B A B C
Output(1,1)
| A A | B C B | B A B C
Utgang (0,0,B)
| A A B | C B B | A B C
Utgang (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 | 。。。 |
Det er ikke nødvendig å lagre ordboken i kompressorens utdatafil, fordi dekomprimeringsprogrammet gjenoppretter ordboken ved å matche utgangsenhetene.
Dekompresjonsprosessen
En av de store fordelene med LZ77-algoritmen er at den er svært rask å dekomprimere.
Hvis den første matchende enheten er (0,0,A), så er A utdata.
Den andre matchende enheten er (1,1), som kopierer forrige bit i utgangsstrengen, og gir ut A hvis kopilengden er 1.
。。。
Hvis den siste samsvarende enheten er (5,3), se tilbake 5 biter i kopiutdatastrengen, og hvis kopilengden er 3, så utdata A, B, C.
Den mest tidkrevende delen av komprimeringen av LZ77-algoritmen er å finne det lengste samsvarende tegnet i cachen som skal søkes i ordboken. Hvis ordboken og cachen som skal søkes i er for korte, er sjansen for å finne en match liten. Derfor har LZ4 endret matchingsalgoritmen for LZ77.
For det første er ordboken til LZ4-algoritmen en hashtabell. Nøkkelen i ordboken er en 4-byte streng, hver nøkkel tilsvarer bare én slot, og verdien i sloten er posisjonen til denne strengen.
I stedet for å søke i cachen, leser LZ4 fire bytes om gangen fra inndatafilen, og leter deretter etter plassen som tilsvarer strengen i hashtabellen, som heretter kalles den nåværende strengen.
Hvis du har nådd de siste 12 tegnene, legg dem direkte inn i utdatafilen.
Hvis det ikke er noen verdi tildelt i sloten, betyr det at de fire bytene vises for første gang, legg til disse fire bytene og posisjonene i hashtabellen, og fortsetter søket.
Hvis det er en tildeling i plassen, betyr det at vi har funnet en tilsvarende verdi.
Hvis verdien i sporet pluss størrelsen på skyvevinduet < posisjonen til det nåværende tegnet, overstiger matchposisjonen størrelsen på blokken, og programmet oppdaterer verdien i hash-plassen til posisjonen til den nåværende strengen.
LZ4 vil sjekke om det har vært en hash-konflikt. Hvis de 4 bytene i sporet ikke er de samme som den nåværende strengen, må det være en hash-konflikt. Forfatterens egen xxhash er også kjent for sin effektivitet, men konflikter er uunngåelige. Ved konflikt oppdaterer programmet også verdien i hash-plassen til den nåværende posisjonen til strengen
Til slutt kan vi bekrefte at matchen er gyldig, og programmet vil fortsette å se om de påfølgende tegnene i matchende streng er de samme. Til slutt, kopier alle tegn fra slutten av forrige gyldige match til starten av denne gyldige matchen til den komprimerte filen, og legg til matchsekvensen til denne gyldige matchen.
Collet kaller de matchende enhetene som LZ4-sekvensene leverer, og de utgjør den komprimerte LZ4-filen. Detaljene er som følger:
Tokenet er 1 byte langt, hvor de første 4 ordene er den bokstavelige lengden og de siste 4 ordene er matchlengden. Som nevnt tidligere, vil alle tegn fra slutten av forrige gyldige match til starten av denne gyldige matchen kopieres til en komprimert fil, disse ukomprimerte filene er literale, og lengden deres er literal lengde.
Bokstavelig talt etterfulgt av avvik. Som i LZ77 refererer avvik og matchlengde til lengden på den nåværende strengen fra dens match, og matchlengden refererer til lengden på matchlengden til den nåværende strengen til samme streng i ordboken. Ved dekomprimering går man gjennom den for å finne strengen som skal kopieres og lengden som skal kopieres. Størrelsen på avviket er fast.
I figuren er bokstavelig lengde+ og matchlengde+, at hvis bokstavelige eller match-lengde 4 ord i tokenet ikke er nok, vil de fortsette å øke i tilsvarende posisjoner. 4 ord kan representere 0-15, og hvis det er flere, legg til én byte, det vil si legg til 255 til størrelsen til byten er mindre enn 255. I matchende lengde representerer 0 4 byte.
De siste 12 bytene slutter bokstavelig talt fordi det ble kopiert direkte.
La oss se på koden (python er mer abstrakt)
Sammendrag Når det er sagt, har jeg fortsatt ikke oppsummert hvorfor LZ4 er så rask. La oss først sammenligne ordboksøket mellom LZ77 og LZ4. Den native LZ77 søker etter ordbøker ved å lete etter det største treffet i cachen som skal søkes i, og i ordboken. Dette er et problem med å finne den største identiske strengen i to strenger. Hvis vi ikke bruker dynamisk programmering, må vi i verste fall vurdere alle delstrengene i én streng og deretter matche dem i en annen streng. Hvis ×vi bruker dynamisk programmering, vil vi bruke en tabell for å holde den lengste matchen i den dynamiske, som bare lar oss fullføre matchen i tilfellet O(m*n). Og det er bare for et par søkecacher og ordbøker. I verste fall, hvis det ikke er noen treff, må LZ77 telle (lengden på hele filen – lengden på cachen som skal søkes i) som mange slike matchingsproblemer. LZ4 bruker faktisk et større nivå av dynamisk programmering: det lagrer 4 bytes og deres posisjoner i en hashtabell, og matcher deretter en ny 4 byte med data hver gang bare for å se om verdiene i hashtabellen er gyldige. Etter å ha funnet en gyldig matchende verdi, hvis du ser på oppfølgingsdataene for de to settene med matchende verdier, kan du også finne den lengste matchen. Siden hver nøkkel i LZ4-hashtabellen bare tilsvarer 1 plass, krever arbeidet med å finne, legge til og endre hashtabellen bare O(1). Hvis flere treff finnes etter matching, trengs flere gruppesammenligninger, men i total tid vil disse sammenligningene erstatte mer tid til å slå opp hashtabellen, så den totale tiden for LZ4-algoritmen er bare O(n). Jeg må beundre skjønnheten til Collets algoritme! For å gjøre algoritmen enda raskere, setter Collet standard hashtabellstørrelse til 16k, som anbefales å ikke overstige 32k, slik at den kan legges inn i L1-cachen til nesten alle CPU-er (Intel). Alle vet at hastighets- og minneforholdet til CPU L1-cache er veldig forskjellig, så det er ikke overraskende at LZ4 flyr fort, for ikke å nevne at hash-ligningen som brukes i LZ4s hashtabell fortsatt er den raskeste xxhashen. Selvfølgelig har et slikt design sine ulemper. Jo mindre hashtabellen er, desto færre nøkler har den. Dette betyr at flere hash-konflikter vil oppstå, noe som er uunngåelig. Og flere hash-kollisjoner betyr færre kamper. Og en mindre hashtabell betyr også et mindre glidende vindu, noe som betyr at flere matcher blir kastet fordi de er for langt unna. Færre treff gir et lavere kompresjonsforhold, og derfor har LZ4 et mindre fremtredende kompresjonsforhold. Looking Ahead LZ4 har et bredt spekter av bruksscenarier. Akkurat som middle out ble brukt i VR i Silicon Valley, kan LZ4 øke båndbreddeutnyttelsen ved å bringe færre IO-er på bekostning av svært lav forsinkelse på grunn av sin svært høye komprimeringshastighet. Det er også en liten spekulasjon: hvis det finnes en CPU med større cache på nivå 1, kan LZ4 øke komprimeringsforholdet uten å gå på bekostning av hastigheten?
Original:Innloggingen med hyperkoblingen er synlig. |
Publisert på 03.01.2022 13:54:23
|
|
|
|
