Po ogledu HBO-jeve drame "Silicon Valley" me je vedno zanimalo za algoritme stiskanja. Richard Hendricks in njegov sredinski algoritem za stiskanje v njem sta seveda lažna, a po temeljitem googlanju sem ugotovil, da v resničnem življenju obstaja tak genij za stiskanje algoritmov.
Yann Collet je leta 2011 izumil algoritem stiskanja LZ4. Seveda algoritem LZ4 ni tako izjemen kot middle out, vendar je znan po svoji neuničljivi hitrosti kompresije in hitrejši hitrosti dekompresije, kadar je določena hitrost kompresije zagotovljena.
Tukaj ne bom šel v podrobnosti o oceni hitrosti stiskanja, če vas zanima, lahko preberete ta primerjalni članek:Prijava do hiperpovezave je vidna.
Priložen je tudi github naslov LZ4:Prijava do hiperpovezave je vidna.
Ta članek se osredotoča na razlago načela algoritma stiskanja LZ4. Veliki bog je pred tem napisal razlago algoritma LZ4:Prijava do hiperpovezave je vidna.A ko sem prej študiral, sem menil, da ta članek ni ravno prijazen do začetnikov, zato sem začel pisati nov članek za začetnike, kot sem jaz.
Če povzamete v eno poved, je LZ4 LZ77, ki shranjuje slovar z razprševalno tabelo velikosti 16k in poenostavi iskanje.
LZ4 je algoritem za brezizgubno stiskanje, ki omogoča hitrost stiskanja > 500 MB/s na jedro, kar je mogoče skalirati z večjedrnimi procesorji. Ima izjemno hitre dekoderje s hitrostjo več GB/s na jedro, pogosto dosegajo omejitve hitrosti RAM-a na večjedrnih sistemih.
Hitrost je mogoče dinamično prilagajati z izbiro "pospeševalnega" faktorja, ki zamenja kompresijsko razmerje za hitrejšo hitrost. Po drugi strani pa je na voljo tudi LZ4_HC visokokompresijskega odvoda, ki poveča kompresijo na račun CPU časa. Vse različice imajo enako hitrost dekompresije.
Kaj torej je LZ77?
LZ77 kompresija in princip
LZ77 je algoritem, ki uporablja slovar za stiskanje. Preprosto povedano, gre za to, da program opazuje (poglej slovar), ali so trenutno prikazani podatki podvojeni s prejšnjimi, in če je tako, shranimo razdaljo (odmik) in dolžino podvojenih polj, da nadomestimo podvojena polja in stisnemo podatke.
ReferenčniPrijava do hiperpovezave je vidna.
Za niz črk A A B C B B A B C, ko se prebere druga A, program shrani (1,1) (1 števka iz prejšnje, dolžina 1), podobno pa program ob branju drugega B shrani (2,1) (razdalja 2, dolžina 1).
Če pa je niz daljši in program podatke ves čas beleži v slovar, iskanje podvojenih polj postane izjemno zamudno, saj v najslabšem primeru program z vsakim novim prebranim črko pregleda celoten slovar. LZ77 uporablja metodo drsnega okna za rešitev tega problema.
Podobno kot začetna točka TCP z drsnim oknom lahko drsno okno zmanjša območje predpomnilnika, da se prepreči hkratna obdelava preveč predpomnjenih podatkov. V LZ77 se slovar ne povečuje ves čas, temveč zavrže prve znake, dodane v slovar, ko presežejo največjo velikost, ki jo določa slovar, da se zagotovi, da je velikost slovarja vedno ohranjena na določeni največji velikosti.
Predpostavimo, da je dolžina v slovarju 3
| Slovar |
| A | A B C B B A B C
Izhod (0,0,A)
| A A | B C B B A B C
Izhod(1,1)
| A A B | C B B A B C
Izhod (0,0,B)
A | A B C | B B A B C
Izhod (0,0,C)
A A | B C B | B A B C
Izhod(2,1)
Drugi del drsnega okna je predpomnilnik, ki ga je treba iskati (Look Ahead buffer nima uradnega prevoda). Predpomnilnik, ki ga je treba iskati, je nekompresiran del dolžine, ki je najbližji slovarju. Algoritem LZ77 bo ujemal najdaljši niz v tem delu znaka, ki je enak slovarju. Prejšnji primer lahko obravnavamo kot vnaprejšnji medpomnilnik 1.
Predpostavimo, da je dolžina slovarja 5 in velikost predpomnilnika, ki ga želimo iskati, 3
| Slovar | Glej naprej medpomnilnik |
A | A B C B B | A B C |
Izhod(5,3)
Najdaljši niz, ki se ujema, je ABC
Popoln postopek stiskanja:
Predpostavimo, da je dolžina slovarja 5 in velikost predpomnilnika, ki ga želimo iskati, 3
| Slovar | Glej naprej medpomnilnik |
| A A B | C B B A B C
Izhod (0,0,A)
| A | A B C | B B A B C
Izhod(1,1)
| A A | B C B | B A B C
Izhod (0,0,B)
| A A B | C B B | A B C
Izhod (0,0,C)
| A A B C | B B A | B C
Izhod(2,1)
| A A B C B | B A B | C
Izhod(1,1)
A | A B C B B | A B C |
Izhod(5,3)
A A B C | B B A B C | 。。。 |
Ni potrebe po shranjevanju slovarja v izhodni datoteki kompresorja, saj program za dekompresijo obnovi slovar z ujemanjem izhodnih enot.
Proces dekompresije
Ena izmed velikih prednosti algoritma LZ77 je, da se zelo hitro dekompresira.
Če je prva ujemajoča enota (0,0,A), potem je izhod A.
Druga enota za ujemanje je (1,1), ki kopira prejšnji bit v izhodnem nizu in izpiše A, če je dolžina kopije 1.
。。。
Če je zadnja ujemajoča enota (5,3), poglejte nazaj 5 bitov v izhodnem nizu kopiranja, in če je dolžina kopije 3, potem izpišite A, B, C.
Najbolj časovno zahteven del stiskanja algoritma LZ77 je iskanje najdaljšega ujemajočega se znaka v predpomnilniku, ki ga je treba iskati v slovarju. Če sta slovar in predpomnilnik, ki ga je treba iskati, prekratka, so možnosti za iskanje ujemanja majhne. Zato je LZ4 spremenil algoritem ujemanja za LZ77.
Prvič, slovar algoritma LZ4 je zgoščevalna tabela. Ključ v slovarju je 4-bajtni niz, vsak ključ ustreza le eni reži, vrednost v reži pa je položaj tega niza.
Namesto iskanja po predpomnilniku LZ4 bere štiri bajte naenkrat iz vhodne datoteke in nato išče režo, ki ustreza nizu v zgoščeni tabeli, ki se v nadaljevanju imenuje sedanji niz.
Če ste dosegli zadnjih 12 znakov, jih vnesite neposredno v izhodno datoteko.
Če v reži ni dodeljena nobena vrednost, to pomeni, da se štirje bajti pojavijo prvič, te štiri bajte in položaje dodamo v zgoščevalno tabelo in nadaljujemo z iskanjem.
Če je v reži dodeljena vrednost, to pomeni, da smo našli ujemajočo vrednost.
Če vrednost v reži plus velikost drsnega okna < položaj trenutnega znaka, potem položaj ujemanja presega velikost bloka, program pa posodobi vrednost v zgoščeni reži na položaj trenutnega niza.
LZ4 bo preveril, ali je prišlo do konflikta zgoščevalcev. Če 4 bajti v reži niso enaki trenutnemu nizu, mora priti do konflikta zgoščevalnih točk. Avtorjev lastni xxhash je prav tako znan po svoji učinkovitosti, a konflikti so neizogibni. V primeru konflikta program posodobi vrednost v zgoščeni reži na trenutno pozicijo niza
Nazadnje lahko potrdimo, da je ujemanje veljavno, program pa bo nadaljeval z ugotavljanjem, ali so naslednji znaki v ujemajočem nizu enaki. Na koncu kopirajte vse znake od konca prejšnjega veljavnega ujemanja do začetka tega veljavnega ujemanja v stisnjeno datoteko in dodajte zaporedje ujemanja tega veljavnega ujemanja.
Collet pokliče ustrezne enote, ki jih izpiše LZ4 zaporedja, in tvorijo LZ4 stisnjeno datoteko. Podrobnosti so naslednje:
Žeton je dolg 1 bajt, pri čemer so prve 4 besede dobesedna dolžina, zadnje 4 besede pa dolžina ujemanja. Kot je bilo že omenjeno, bodo vsi znaki od konca prejšnje veljavne tekme do začetka te veljavne tekme kopirani v stisnjeno datoteko, te nekompresirane datoteke so dobesedne, njihova dolžina pa je dobesedna dolžina.
Dobesedno sledi odklon. Kot v LZ77, odstopanje in dolžina ujemanja označujeta dolžino trenutnega niza glede na njegovo ujemanje, dolžina ujemanja pa na dolžino ujemanja trenutnega niza z istim nizom v slovarju. Pri dekompresiji greš skozi to, da najdeš niz, ki ga je treba kopirati, in dolžino, ki jo je treba kopirati. Velikost odstopanja je fiksna.
Na sliki sta dobesedna dolžina+ in dolžina ujemanja+ – če dobesedna ali ujemajoča dolžina 4 besed v žetonu ni dovolj, se bosta še naprej povečevali na ustreznih mestih. 4 besede lahko predstavljajo 0-15, če jih je več, dodamo en bajt, torej 255 k velikosti, dokler bajt ni manjši od 255. V dolžini ujemanja 0 predstavlja 4 bajte.
Zadnjih 12 bajtov se konča dobesedno, ker je bilo kopirano neposredno.
Poglejmo si kodo (python je bolj abstrakten)
Povzetek Kljub vsemu temu še vedno nisem povzel, zakaj je LZ4 tako hiter. Najprej primerjajmo iskanje v slovarju med LZ77 in LZ4. Izvorni LZ77 išče slovarje tako, da išče največje ujemanje v predpomnilniku, ki ga je treba iskati, in v slovarju. To je problem iskanja največjega enakega niza v dveh nizih. Če ne uporabljamo dinamičnega programiranja, potem moramo v najslabšem primeru upoštevati vse podnize enega niza in jih nato povezati z drugim nizom. Če ×uporabljamo dinamično programiranje, bomo tabelo uporabili za shranjevanje najdaljšega ujemanja v dinamiki, kar nam bo omogočilo dokončanje ujemanja le v primeru O(m*n). In to je le za par iskalnih predpomnilnikov in slovarjev. V najslabšem primeru, če ni ujemanj, bo moral LZ77 šteti (dolžino celotne datoteke – dolžino predpomnilnika, ki ga je treba iskati) kot veliko takšnih težav z ujemanjem. LZ4 dejansko uporablja višjo raven dinamičnega programiranja: shrani 4 bajte in njihove položaje v zgoščevalno tabelo, nato pa vsakič ujema nove 4 bajte podatkov, da preveri, ali so vrednosti v zgoščeni tabeli veljavne. Ko najdete veljavno ujemajočo vrednost, če pogledate nadaljnje podatke obeh množic ujemajočih se vrednosti, lahko najdete tudi njeno najdaljše ujemanje. Ker vsak ključ v LZ4 zgoščeni tabeli ustreza le enemu mestu, je za iskanje in dodajanje ter spreminjanje zgoščevalne tabele potrebno le O(1). Če se po ujemanju najdejo več ujemanja, je potrebnih več skupinskih primerjav, vendar bodo te primerjave v tem času nadomestile več časa za iskanje zgoščenske tabele, zato je skupni čas algoritma LZ4 le O(n). Občudujem lepoto Colletovega algoritma! Da bi algoritem naredil še hitrejši, Collet nastavi privzeto velikost hash tabele na 16k, kar je priporočljivo, da ne presega 32k, da se lahko vključi v L1 predpomnilnik skoraj vseh procesorjev (Intel). Vsi vedo, da sta hitrost in razmerje pomnilnika v L1 predpomnilniku CPU-ja zelo različna, zato ni presenetljivo, da LZ4 leti hitro, poleg tega pa je enačba zgoščevanja, uporabljena v LZ4 hash tabeli, še vedno najhitrejša xxhash. Seveda ima takšna zasnova tudi svoje slabosti. Manjša kot je zgoščevalna tabela, manj ključev ima. To pomeni, da bo prišlo do več konfliktov zgoščevalnih točk, kar je neizogibno. Več zgoščevalnih trkov pomeni manj ujemanj. Manjša hash tabela pomeni tudi manjše drsno okno, kar pomeni, da bo več ujemanj zavrženih, ker so predaleč. Manj vžigalnic pomeni manjše kompresijsko razmerje, zato ima LZ4 manj izrazito kompresijsko razmerje. Looking Forward LZ4 ponuja širok nabor scenarijev uporabe. Tako kot je bil middle-out uporabljen v VR v Silicijevi dolini, lahko LZ4 poveča izrabo pasovne širine z manj IO procesorji na račun zelo nizke latence zaradi zelo hitre kompresije. Obstaja tudi majhna ugibanja, če je procesor z večjim predpomnilnikom na nivoju 1, ali lahko LZ4 poveča razmerje stiskanja brez kompromisa pri hitrosti?
Izvirno:Prijava do hiperpovezave je vidna. |
Objavljeno na 3. 01. 2022 13:54:23
|
|
|
|
