Na het kijken van het HBO-drama "Silicon Valley" ben ik altijd geïnteresseerd geweest in compressie-algoritmen. Richard Hendricks en zijn midden-uit-compressie-algoritme zijn natuurlijk nep, maar na hard googelen ontdekte ik dat er zo'n compressiealgoritme in het echte leven bestaat.
Yann Collet vond het LZ4-compressie-algoritme uit in 2011. Natuurlijk is het LZ4-algoritme niet zo geweldig als middle out, maar het staat bekend om zijn onoverwinnelijke compressiesnelheid en snellere decompressiesnelheid wanneer een bepaalde compressiesnelheid gegarandeerd is.
Ik zal hier niet in detail treden over de evaluatie van de compressiesnelheid; als je geïnteresseerd bent, kun je dit vergelijkende artikel lezen:De hyperlink-login is zichtbaar.
Ook bijgevoegd is het github-adres van LZ4:De hyperlink-login is zichtbaar.
Dit artikel richt zich op het uitleggen van het principe van het LZ4-compressiealgoritme. Een grote god schreef eerder een uitleg van het LZ4-algoritme:De hyperlink-login is zichtbaar.Maar toen ik eerder studeerde, vond ik dat dit artikel niet erg vriendelijk was voor beginners, dus begon ik een ander artikel voor beginners zoals ik.
Als je het in één zin samenvat, is LZ4 een LZ77 die een woordenboek opslaat met een hashtabel van 16k en het ophalen vereenvoudigt.
LZ4 is een verliesvrij compressie-algoritme dat een compressiesnelheid van > 500 MB/s per core biedt, die kan worden opgeschaald met multi-core CPU's. Het heeft extreem snelle decoders met snelheden van meerdere GB/s per core, die vaak de RAM-snelheidslimieten bereiken op multi-core systemen.
De snelheid kan dynamisch worden aangepast, waarbij een "versnellingsfactor" wordt gekozen die compressieverhouding inruilt voor hogere snelheid. Aan de andere kant wordt ook een afgeleide LZ4_HC met hoge compressie geboden om de compressie te verhogen ten koste van CPU-tijd. Alle versies hebben dezelfde decompressiesnelheid.
Dus wat is LZ77?
LZ77-compressie en principe
LZ77 is een algoritme dat een woordenboek toepast voor compressie. In gewone taal is het om het programma te laten observeren (in het woordenboek te kijken) of de data die momenteel wordt gezien is gedupliceerd met de vorige, en zo ja, slaan we de afstand (offset) en de lengte van de dubbele velden op om de dubbele velden te vervangen en comprimeren we de data.
referentieDe hyperlink-login is zichtbaar.
Voor een reeks letters A A B C B B A B C, slaat het programma bij het lezen van de tweede A (1,1) (1 cijfer van de vorige, lengte 1) op, en op dezelfde manier, wanneer de tweede B wordt gelezen, slaat het programma (2,1) op (afstand 2, lengte 1).
Maar als de string langer is en het programma de data voortdurend in het woordenboek opneemt, wordt het zoeken naar dubbele velden extreem tijdrovend, omdat het programma in het ergste geval bij elke nieuwe gelezen letter het hele woordenboek doorloopt. LZ77 gebruikt een sliding window-methode om dit probleem op te lossen.
Vergelijkbaar met het beginpunt van TCP met een sliding window, kan een sliding window het cachegebied verkleinen om te voorkomen dat te veel gecachte data tegelijk verwerkt wordt. In LZ77 wordt het woordenboek niet voortdurend vergroot, maar wordt de eerste tekens die aan het woordenboek worden toegevoegd weggegooid wanneer deze de maximale grootte overschrijden die door het woordenboek is gespecificeerd, zodat de grootte van het woordenboek altijd op de opgegeven maximale grootte wordt gehouden.
Stel dat de woordenboeklengte 3 is
| Woordenboek |
| 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)
Het andere deel van het schuifvenster is de cache die doorzocht moet worden (look-ahead buffer heeft geen officiële vertaling). De cache die doorzocht moet worden, is het ongecomprimeerde deel van de lengte dat het dichtst bij het woordenboek ligt. Het LZ77-algoritme zal de langste string in dit deel van het teken matchen die hetzelfde is als het woordenboek. Het vorige voorbeeld kan worden beschouwd als een vooruitkijkbuffer van 1.
Stel dat de woordenboeklengte 5 is en de cachegrootte die doorzocht moet worden 3 is
| Woordenboek | Vooruit Buffer |
A | A B C B B | A B C |
Output(5,3)
De langste reeks die overeenkomt is ABC
Volledig compressieproces:
Stel dat de woordenboeklengte 5 is en de cachegrootte die doorzocht moet worden 3 is
| Woordenboek | Vooruit 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 | 。。。 |
Het is niet nodig het dictionary op te slaan in het uitvoerbestand van de compressor, omdat het decompressieprogramma het woordenboek herstelt door de outputunits te matchen.
Decompressieproces
Een van de grote voordelen van het LZ77-algoritme is dat het zeer snel te decomprimeren is.
Als de eerste overeenkomende eenheid (0,0,A) is, dan wordt A uitgevoerd.
De tweede matching-eenheid is (1,1), die het vorige bit in de uitvoerstring kopieert en A uitvoert als de kopieerlengte 1 is.
。。。
Als de laatst overeenkomende eenheid (5,3) is, kijk dan 5 bits terug in de kopieeruitvoerstring, en als de kopieerlengte 3 is, geef dan A, B, C uit.
Het meest tijdrovende deel van de compressie van het LZ77-algoritme is het vinden van het langst overeenkomende teken in de cache dat in het woordenboek moet worden doorzocht. Als het woordenboek en de cache die doorzocht moet worden te kort zijn, is de kans klein dat je een match vindt. Daarom heeft LZ4 het matching-algoritme voor LZ77 veranderd.
Ten eerste is het woordenboek van het LZ4-algoritme een hashtabel. De sleutel in het woordenboek is een string van 4 bytes, elke sleutel komt overeen met slechts één slot, en de waarde in de slot is de positie van deze string.
In plaats van de cache te doorzoeken, leest LZ4 vier bytes tegelijk uit het invoerbestand en zoekt vervolgens naar de slot die overeenkomt met de string in de hashtabel, die hierna de huidige string wordt genoemd.
Als je de laatste 12 tekens hebt bereikt, plaats ze dan direct in het uitvoerbestand.
Als er geen waarde in de slot is toegewezen, betekent dit dat de vier bytes voor het eerst verschijnen, deze vier bytes en posities aan de hashtabel toevoegen en doorgaan met zoeken.
Als er een opdracht in de gleuf zit, betekent dat dat we een overeenkomende waarde hebben gevonden.
Als de waarde in de sleuf plus de grootte van het schuifvenster de positie van het huidige teken <, dan overschrijdt de matchpositie de grootte van het blok, en werkt het programma de waarde in de hash-sleuf bij naar de positie van de huidige string.
LZ4 controleert of er een hashconflict is geweest. Als de 4 bytes in de sleuf niet hetzelfde zijn als de huidige string, moet er een hashconflict zijn. De eigen xxhash van de auteur staat ook bekend om zijn efficiëntie, maar conflicten zijn onvermijdelijk. In geval van een conflict werkt het programma ook de waarde in de hashslot bij naar de huidige positie van de string
Ten slotte kunnen we bevestigen dat de match geldig is, en het programma blijft controleren of de volgende tekens in de overeenkomstige string hetzelfde zijn. Kopieer tenslotte alle tekens van het einde van de vorige geldige overeenkomst naar het begin van deze geldige overeenkomst naar het gecomprimeerde bestand, en voeg de overeenkomstige reeks van deze geldige overeenkomst toe.
Collet roept de matching-units aan die door LZ4-sequenties worden uitgevoerd, en zij vormen het LZ4-gecomprimeerde bestand. De details zijn als volgt:
Het token is 1 byte lang, waarbij de eerste 4 woorden de letterlijke lengte zijn en de laatste 4 woorden de matchlengte. Zoals eerder vermeld, worden alle tekens van het einde van de vorige geldige match tot het begin van deze geldige match gekopieerd naar een gecomprimeerd bestand, deze niet-gecomprimeerde bestanden zijn letterlijk en hun lengte is letterlijke lengte.
Letterlijk gevolgd door afwijking. Net als in LZ77 verwijzen deviatie en matchlengte naar de lengte van de huidige string ten opzichte van de match, en de matchlengte naar de lengte van de matchlengte van de huidige string naar dezelfde string in het woordenboek. Bij decompressie moet je erdoorheen gaan om de te kopiëren string en de lengte te vinden die gekopieerd moet worden. De grootte van de afwijking is vast.
In de figuur zijn letterlijke lengte+ en matchlengte+ als de letterlijke of matchlengte 4 woorden in het token niet voldoende zijn, deze blijven toenemen op de overeenkomstige posities. 4 woorden kunnen 0-15 vertegenwoordigen, en als er nog meer zijn, voeg dan één byte toe, dat wil zeggen, voeg 255 toe aan de grootte totdat de byte kleiner is dan 255. In de overeenkomstige lengte staat 0 voor 4 bytes.
De laatste 12 bytes eindigen letterlijk omdat het direct gekopieerd is.
Laten we naar de code kijken (python is abstracter)
Samenvatting Na dit alles heb ik nog steeds niet samengevat waarom de LZ4 zo snel is. Laten we eerst de woordenboekzoektocht tussen LZ77 en LZ4 vergelijken. De native LZ77 zoekt naar woordenboeken door te zoeken naar de grootste match in de te zoeken cache en in het woordenboek. Dit is een probleem waarbij je de grootste identieke string in twee strings moet vinden. Als we geen dynamische programmering gebruiken, dan moeten we in het slechtste geval alle substrings van één string overwegen en ze vervolgens in een andere string matchen. Als ×we dynamische programmering gebruiken, gebruiken we een tabel om de langste match in de dynamische te bewaren, waardoor we de match alleen kunnen voltooien in het geval van O(m*n). En dat is alleen voor een paar zoekcaches en woordenboeken. In het slechtste geval, als er geen matches zijn, zal LZ77 (de lengte van het gehele bestand - de lengte van de te doorzoeken cache) als veel van zulke matchingproblemen moeten tellen. LZ4 gebruikt eigenlijk een groter niveau van dynamische programmering: het slaat 4 bytes en hun posities op in een hashtabel, en matcht telkens een nieuwe 4 bytes aan data om te zien of de waarden in de hashtabel geldig zijn. Na het vinden van een geldige matchingwaarde kun je, als je naar de follow-upgegevens van de twee sets matching values kijkt, ook de langste match vinden. Aangezien elke sleutel van de LZ4-hashtabel slechts 1 slot heeft, vereist het zoeken en toevoegen van de hashtabel slechts O(1). Als er na het matchen meer matches worden gevonden, zijn meer groepsvergelijkingen nodig, maar in de totale tijd zullen deze vergelijkingen meer tijd kosten om de hashtabel op te zoeken, dus de totale tijd van het LZ4-algoritme is slechts O(n). Ik moet de schoonheid van Collet's algoritme bewonderen! Om het algoritme nog sneller te maken, stelt Collet de standaard hashtabel in op 16k, wat wordt aanbevolen niet hoger dan 32k te zijn, zodat het in de L1-cache van bijna alle CPU's (Intel) kan worden geplaatst. Iedereen weet dat de snelheid en geheugenverhouding van de CPU L1-cache heel verschillend zijn, dus het is niet verrassend dat LZ4 snel vliegt, om nog maar te zwijgen van het feit dat de hashvergelijking in de hashtabel van LZ4 nog steeds de snelste xxhash is. Natuurlijk heeft zo'n ontwerp ook zijn nadelen. Hoe kleiner de hashtabel, hoe minder sleutels hij heeft. Dit betekent dat er meer hashconflicten zullen optreden, wat onvermijdelijk is. En meer hashbotsingen betekenen minder matches. En een kleinere hashtabel betekent ook een kleiner schuifvenster, wat betekent dat er meer matches worden weggegooid omdat ze te ver weg zijn. Minder matches betekenen een lagere compressieverhouding, waardoor de LZ4 een minder prominente compressieverhouding heeft. Looking Ahead LZ4 biedt een breed scala aan toepassingsscenario's. Net zoals middle out in VR werd gebruikt in Silicon Valley, kan LZ4 het bandbreedtegebruik verhogen door minder IO's te brengen, ten koste van zeer lage latentie vanwege de zeer hoge compressiesnelheid. Er is ook een kleine speculatie: als er een CPU is met een grotere cache op niveau 1, kan de LZ4 dan de compressieverhouding verhogen zonder de snelheid te verminderen?
Origineel:De hyperlink-login is zichtbaar. |
Geplaatst op 03-01-2022 13:54:23
|
|
|
|
