Efter att ha sett HBO-dramat "Silicon Valley" har jag alltid varit intresserad av komprimeringsalgoritmer. Richard Hendricks och hans middle out-komprimeringsalgoritm i den är förstås fejk, men efter att ha googlat noggrant upptäckte jag att det finns ett sådant komprimeringsalgoritm-geni i verkliga livet.
Yann Collet uppfann LZ4-komprimeringsalgoritmen år 2011. Självklart är LZ4-algoritmen inte lika fantastisk som middle out, men den är känd för sin osårbara komprimeringshastighet och snabbare dekompressionshastighet när en viss komprimeringshastighet kan garanteras.
Jag kommer inte gå in på detaljer här om utvärderingen av dess komprimeringshastighet, om du är intresserad kan du läsa denna jämförelseartikel:Inloggningen med hyperlänken är synlig.
Även bifogad är github-adressen för LZ4:Inloggningen med hyperlänken är synlig.
Denna artikel fokuserar på att förklara principen för LZ4-komprimeringsalgoritmen. En stor gud skrev en förklaring av LZ4-algoritmen tidigare:Inloggningen med hyperlänken är synlig.Men när jag studerade tidigare kände jag att den här artikeln inte var särskilt vänlig mot nybörjare, så jag började på en annan artikel för nybörjare som jag.
Om du sammanfattar det i en mening är LZ4 en LZ77 som lagrar en ordbok med en hashtabell i storlek 16k och förenklar hämtningen.
LZ4 är en förlustfri komprimeringsalgoritm som erbjuder en komprimeringshastighet på > 500 MB/s per kärna, vilken kan skalas med flerkärniga CPU:er. Den har extremt snabba dekodare med hastigheter på flera GB/s per kärna, och når ofta RAM-hastighetsgränser på flerkärniga system.
Hastigheten kan justeras dynamiskt, där en "accelerationsfaktor" väljs som byter kompressionsförhållande mot högre hastighet. Å andra sidan tillhandahålls även en högkomprimerad derivata LZ4_HC för att öka kompressionen på bekostnad av CPU-tiden. Alla versioner har samma dekompressionshastighet.
Så vad är LZ77?
LZ77-kompression och princip
LZ77 är en algoritm som använder en ordbok för komprimering. På lekmannaspråk är det att låta programmet observera (titta i ordboken) om den data som för närvarande visas är duplicerad med den föregående, och om så är fallet sparar vi avståndet (offset) och längden på de dubblettfälten för att ersätta de dubblettfälten och komprimera datan.
hänvisningInloggningen med hyperlänken är synlig.
För en bokstavssträng A A B C B B A B C, när det andra A läses, sparar programmet (1,1) (1 siffra från det föregående, längd 1), och på samma sätt, när det andra B läses, sparar programmet (2,1) (avstånd 2, längd 1).
Men om strängen är längre och programmet hela tiden registrerar data i ordboken blir sökandet efter dubblettfält extremt tidskrävande, eftersom programmet i värsta fall går igenom hela ordboken vid varje ny bokstav som läses. LZ77 använder en sliding window-metod för att lösa detta problem.
Liknande utgångspunkten för TCP med ett glidande fönster kan ett glidande fönster krympa cacheområdet för att undvika att bearbeta för mycket cachad data samtidigt. I LZ77 ökar inte ordboken hela tiden, utan tar bort de första tecknen som läggs till i ordboken när de överskrider den maximala storlek som anges av ordboken, för att säkerställa att ordboksstorleken alltid hålls vid den angivna maximala storleken.
Antag att ordbokslängden är 3
| Ordbok |
| A | A B C B B A B C
Utgång (0,0,A)
| A A | B C B B A B C
Utdata(1,1)
| A A B | C B B A B C
Utgång (0,0,B)
A | A B C | B B A B C
Utgång (0,0,C)
A A | B C B | B A B C
Utdata(2,1)
Den andra delen av det glidande fönstret är cachen som ska sökas i (lookahead-bufferten har ingen officiell översättning). Cachen som ska sökas är den okomprimerade delen av längden som ligger närmast ordboken. LZ77-algoritmen matchar den längsta strängen i denna del av tecknet som är densamma som i ordboken. Det föregående exemplet kan betraktas som en framåtblicksbuffert på 1.
Antag att ordbokslängden är 5 och cache-storleken som ska sökas är 3
| Ordbok | Titta framåt Buffert |
A | A B C B B | A B C |
Utgång(5,3)
Den längsta strängen som matchar är ABC
Fullständig kompressionsprocess:
Antag att ordbokslängden är 5 och cache-storleken som ska sökas är 3
| Ordbok | Titta framåt Buffert |
| A A B | C B B A B C
Utgång (0,0,A)
| A | A B C | B B A B C
Utdata(1,1)
| A A | B C B | B A B C
Utgång (0,0,B)
| A A B | C B B | A B C
Utgång (0,0,C)
| A A B C | B B A | B C
Utdata(2,1)
| A A B C B | B A B | C
Utdata(1,1)
A | A B C B B | A B C |
Utgång(5,3)
A A B C | B B A B C | 。。。 |
Det finns inget behov av att spara ordboken i kompressorns utdatafil, eftersom dekompressionsprogrammet återställer ordboken genom att matcha utdataenheterna.
Dekompressionsprocessen
En av de stora fördelarna med LZ77-algoritmen är att den är mycket snabb att dekomprimera.
Om den första matchande enheten är (0,0,A), så är A utmatad.
Den andra matchande enheten är (1,1), som kopierar föregående bit i utdatasträngen och ger A om kopieringslängden är 1.
。。。
Om den sista matchande enheten är (5,3), titta då tillbaka 5 bitar i kopieringssträngen, och om kopieringslängden är 3, skriv ut A, B, C.
Den mest tidskrävande delen av komprimeringen av LZ77-algoritmen är att hitta det längsta matchande tecknet i cachen som ska sökas i ordboken. Om ordboken och cachen som ska sökas är för korta är chansen att hitta en träff liten. Därför har LZ4 ändrat matchningsalgoritmen för LZ77.
För det första är ordboken för LZ4-algoritmen en hashtabell. Nyckeln i ordboken är en 4-bytes sträng, varje nyckel motsvarar endast en plats, och värdet i platsen är positionen för denna sträng.
Istället för att söka i cachen läser LZ4 fyra byte åt gången från indatafilen och letar sedan efter platsen som motsvarar strängen i hashtabellen, som hädanefter kallas den nuvarande strängen.
Om du har nått de sista 12 tecknen, lägg dem direkt i utdatafilen.
Om inget värde tilldelas platsen betyder det att de fyra byten dyker upp för första gången, lägg till dessa fyra byte och positioner i hashtabellen och fortsätter sökandet.
Om det finns en tilldelning i platsen betyder det att vi har hittat ett matchande värde.
Om värdet i platsen plus storleken på reglagrfönstret < positionen för det aktuella tecknet, så överstiger matchningspositionen blockets storlek, och programmet uppdaterar värdet i hashplatsen till positionen för den aktuella strängen.
LZ4 kommer att kontrollera om det har varit en hashkonflikt. Om de 4 bytena i platsen inte är samma som den aktuella strängen måste det finnas en hashkonflikt. Författarens egen xxhash är också känd för sin effektivitet, men konflikter är oundvikliga. Vid en konflikt uppdaterar programmet även värdet i hashplatsen till strängens nuvarande position
Slutligen kan vi bekräfta att matchningen är giltig, och programmet kommer fortsätta att se om de efterföljande tecknen i matchningssträngen är desamma. Slutligen, kopiera alla tecken från slutet av föregående giltiga matchning till början av denna giltiga matchning till den komprimerade filen och lägg till matchsekvensen för denna giltiga matchning.
Collet anropar de matchande enheter som ges ut av LZ4-sekvenser, och de utgör den komprimerade LZ4-filen. Detaljerna är följande:
Token är 1 byte lång, där de första 4 orden är den bokstavliga längden och de sista 4 orden är matchningslängden. Som nämnts tidigare kommer alla tecken från slutet av föregående giltiga matchning till början av denna giltiga matchning att kopieras till en komprimerad fil, dessa okomprimerade filer är literala och deras längd är literal längd.
Bokstavligen följt av avvikelse. Precis som i LZ77 avser avvikelse och matchlängd längden på den aktuella strängen från dess matchning, och matchlängden avser längden på matchlängden för den aktuella strängen till samma sträng i ordboken. Vid dekompression går man igenom den för att hitta strängen som ska kopieras och längden som ska kopieras. Avvikelsens storlek är fast.
I figuren är bokstavlig längd+ och matchlängd+, om de bokstavliga eller matchande längden 4 ord i tokenen inte räcker, kommer de att fortsätta öka på motsvarande positioner. 4 ord kan representera 0–15, och om det finns fler, lägg till en byte, det vill säga lägg till 255 till storleken tills byten är mindre än 255. I matchande längd representerar 0 4 byte.
De sista 12 bytena slutar bokstavligen för att de kopierades direkt.
Låt oss titta på koden (python är mer abstrakt)
Sammanfattning Med allt detta sagt har jag fortfarande inte sammanfattat varför LZ4 är så snabb. Låt oss först jämföra ordbokssökningen mellan LZ77 och LZ4. Den inbyggda LZ77 söker efter ordböcker genom att leta efter den största träffen i cachen som ska sökas och i ordboken. Detta är ett problem att hitta den största identiska strängen i två strängar. Om vi inte använder dynamisk programmering måste vi i värsta fall betrakta alla delsträngar i en sträng och sedan matcha dem i en annan sträng. Om ×vi använder dynamisk programmering, kommer vi att använda en tabell för att hålla den längsta matchningen i den dynamiska, vilket endast tillåter oss att slutföra matchningen i fallet O(m*n). Och det gäller bara ett par sökcacher och ordböcker. I värsta fall, om det inte finns några träffar, måste LZ77 räkna (längden på hela filen – längden på cachen som ska sökas) som många sådana matchningsproblem. LZ4 använder faktiskt en större nivå av dynamisk programmering: den lagrar 4 byte och deras positioner i en hashtabell, och matchar sedan en ny 4 byte data varje gång bara för att se om värdena i hashtabellen är giltiga. Efter att ha hittat ett giltigt matchande värde, om du tittar på uppföljningsdata för de två uppsättningarna av matchande värden, kan du också hitta dess längsta matchning. Eftersom varje nyckel i LZ4-hashtabellen endast motsvarar 1 plats, kräver arbetet med att hitta, lägga till och modifiera hashtabellen endast O(1). Om fler träffar hittas efter matchning krävs fler gruppjämförelser, men under den totala tiden ersätter dessa jämförelser mer tid att slå upp hashtabellen, så den totala tiden för LZ4-algoritmen är bara O(n). Jag måste beundra skönheten i Collets algoritm! För att göra algoritmen ännu snabbare sätter Collet standardstorleken på en hashtabell till 16k, vilket rekommenderas att inte överstiga 32k, så att den kan läggas i L1-cachen hos nästan alla CPU:er (Intel). Alla vet att hastighets- och minnesförhållandet för CPU:s L1-cache skiljer sig mycket åt, så det är inte förvånande att LZ4 flyger snabbt, för att inte tala om att hashekvationen i LZ4:s hashtabell fortfarande är den snabbaste xxhash. Självklart har en sådan design sina nackdelar. Ju mindre hashtabell, desto färre nycklar har den. Detta innebär att fler hashkonflikter kommer att uppstå, vilket är oundvikligt. Och fler hashkollisioner betyder färre matcher. Och en mindre hashtabell innebär också ett mindre glidande fönster, vilket innebär att fler matcher kastas bort eftersom de är för långt bort. Färre matcher innebär ett lägre kompressionsförhållande, vilket är anledningen till att LZ4 har ett mindre framträdande kompressionsförhållande. Looking Ahead LZ4 har ett brett utbud av tillämpningsscenarier. Precis som middle out användes i VR i Silicon Valley kan LZ4 öka bandbreddsutnyttjandet genom att ta med färre IO:er till priset av mycket låg latens tack vare sin mycket höga komprimeringshastighet. Det finns också en liten spekulation: om det finns en CPU med större cache på nivå 1, kan LZ4 öka kompressionsförhållandet utan att kompromissa med hastigheten?
Original:Inloggningen med hyperlänken är synlig. |
Publicerad på 2022-01-03 13:54:23
|
|
|
|
