HBO:n draaman "Silicon Valley" katsomisen jälkeen olen aina ollut kiinnostunut pakkausalgoritmeista. Richard Hendricks ja hänen middle out -pakkausalgoritminsa ovat tietenkin feikkejä, mutta kun googlasin kovasti, huomasin, että todellisessa elämässä on tällainen pakkausalgoritmin nero.
Yann Collet keksi LZ4-pakkausalgoritmin vuonna 2011. Tietenkään LZ4-algoritmi ei ole yhtä mahtava kuin middle out, mutta se tunnetaan voittamattomasta pakkausnopeudestaan ja nopeammasta purkunopeudestaan, kun tietty pakkausnopeus on taattu.
En mene yksityiskohtiin sen pakkausnopeuden arvioinnista, jos olet kiinnostunut, voit lukea tämän vertailuartikkelin:Hyperlinkin kirjautuminen on näkyvissä.
Liitteenä on myös LZ4:n github-osoite:Hyperlinkin kirjautuminen on näkyvissä.
Tämä artikkeli keskittyy LZ4-pakkausalgoritmin periaatteen selittämiseen. Suuri jumala kirjoitti aiemmin selityksen LZ4-algoritmista:Hyperlinkin kirjautuminen on näkyvissä.Mutta kun opiskelin aiemmin, tunsin, ettei tämä artikkeli ollut kovin ystävällinen aloittelijoille, joten aloitin toisen artikkelin aloittelijoille kuten minä.
Jos tiivistät asian yhteen lauseeseen, LZ4 on LZ77, joka tallentaa sanakirjan 16k-kokoisella hajautustaulukolla ja yksinkertaistaa hakua.
LZ4 on häviötön pakkausalgoritmi, joka tarjoaa > 500 MB/s pakkausnopeuden per ydin, jota voidaan skaalata moniytimisillä suorittimilla. Siinä on erittäin nopeat dekooderit, joiden nopeus on useita GB/s per ydin, ja moniydinjärjestelmissä RAM-nopeusrajoitukset usein saavutetaan.
Nopeutta voidaan säätää dynaamisesti valitsemalla "kiihtyvyys"-kerroin, joka vaihtaa puristussuhteen nopeampaan nopeuteen. Toisaalta tarjolla on myös korkean kompression johdannainen LZ4_HC, joka lisää pakkausta prosessorin ajan kustannuksella. Kaikissa versioissa on sama dekompressionopeus.
Mikä siis on LZ77?
LZ77:n pakkaus ja periaate
LZ77 on algoritmi, joka soveltaa sanakirjaa pakkausta varten. Yksinkertaisesti sanottuna ohjelma voi tarkkailla (katso sanakirjaa), onko tällä hetkellä nähty data päällekkäin edellisen kanssa, ja jos on, tallennamme etäisyyden (siirtymän) ja kaksoiskenttien pituuden korvaamaan kaksoiskentät ja pakkaamaan datan.
viittausHyperlinkin kirjautuminen on näkyvissä.
Kirjainsarjalle A A B C B B B B B B C, kun toinen A luetaan, ohjelma tallentaa (1,1) (1 numero edellisestä, pituus 1), ja samoin, kun toinen B luetaan, ohjelma tallentaa (2,1) (etäisyys 2, pituus 1).
Mutta jos merkkijono on pidempi ja ohjelma tallentaa tiedot sanakirjaan jatkuvasti, kaksoiskenttien etsiminen vie erittäin paljon aikaa, koska pahimmassa tapauksessa ohjelma käy läpi koko sanakirjan jokaisen uuden kirjaimen lukemisen yhteydessä. LZ77 käyttää liukuvaa ikkunamenetelmää tämän ongelman ratkaisemiseen.
Samoin kuin TCP:n aloituspisteessä liukuvan ikkunan avulla, liukuva ikkuna voi pienentää välimuisti-aluetta välttääkseen liiallisen välimuistidatan käsittelyn samanaikaisesti. LZ77:ssä sanakirja ei kasva koko ajan, vaan hylkää ensimmäiset sanakirjaan lisätyt merkit, kun se ylittää sanakirjan määrittelemän maksimikoon, jotta sanakirjan koko pysyy aina määritellyn maksimikoon mukaisena.
Oletetaan, että sanakirjan pituus on 3
| sanakirja |
| A | A B C B B A B C
Lähtö (0,0,A)
| A A | B C B B A B C
Output(1,1)
| A A B | C B B A B C
Lähtö (0,0,B)
A | A B C | B B A B C
Lähtö (0,0,C)
A A | B C B | B A B C
Output(2,1)
Liukuvan ikkunan toinen osa on välimuisti, jota etsitään (look ahead bufferilla ei ole virallista käännöstä). Haettava välimuisti on pakkaamaton osa pituudesta, joka on lähimpänä sanakirjaa. LZ77-algoritmi vastaa tämän merkin osan pisimmän merkkijonon, joka on sama kuin sanakirjassa. Edellinen esimerkki voidaan pitää näkymän eteenpäin suuntautuvana puskurina 1.
Oletetaan, että sanakirjan pituus on 5 ja haettavan välimuistin koko on 3
| sanakirja | Katso eteenpäin Buffer |
A | A B C B B | A B C |
Lähtö(5,3)
Pisin säie, joka vastaa, on ABC
Täydellinen pakkausprosessi:
Oletetaan, että sanakirjan pituus on 5 ja haettavan välimuistin koko on 3
| sanakirja | Katso eteenpäin Buffer |
| A A B | C B B A B C
Lähtö (0,0,A)
| A | A B C | B B A B C
Output(1,1)
| A A | B C B | B A B C
Lähtö (0,0,B)
| A A B | C B B | A B C
Lähtö (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 |
Lähtö(5,3)
A A B C | B B A B C | 。。。 |
Sanakirjaa ei tarvitse tallentaa kompressorin lähtötiedostoon, koska purkuohjelma palauttaa sanakirjan sovittamalla ulostuloyksiköt.
Dekompressioprosessi
Yksi LZ77-algoritmin suurista eduista on, että sen purku on erittäin nopea.
Jos ensimmäinen vastaava yksikkö on (0,0,A), niin A on lähtö.
Toinen vastaavuusyksikkö on (1,1), joka kopioi edellisen bitin lähtöjonosta ja tuottaa A:n, jos kopiointipituus on 1.
。。。
Jos viimeinen vastaava yksikkö on (5,3), katsotaan 5 bittiä kopiointilähtömerkkijonossa, ja jos kopion pituus on 3, lähde A, B, C.
LZ77-algoritmin pakkausta vievin osa on löytää pisimmän vastaavan merkin välimuistista, jota haetaan sanakirjasta. Jos sanakirja ja haettava välimuisti ovat liian lyhyitä, osuman löytämisen mahdollisuudet ovat pienet. Siksi LZ4 on muuttanut LZ77:n vastaavuusalgoritmia.
Ensinnäkin LZ4-algoritmin sanakirja on hajautustaulukko. Sanakirjan näppäin on 4 tavun merkkijono, jossa jokainen avain vastaa vain yhtä paikkaa, ja slotin arvo on tämän merkkijonon sijainti.
Sen sijaan, että hakisi välimuistista, LZ4 lukee syötetiedostosta neljä tavua kerrallaan ja etsii sitten hajautustaulun merkkijonoa vastaavaa paikkaa, jota kutsutaan tästä eteenpäin nykyiseksi merkkijonoksi.
Jos olet päässyt viimeiset 12 merkkiä, laita ne suoraan tulostiedostoon.
Jos slotissa ei ole arvoa, se tarkoittaa, että neljä tavua ilmestyy ensimmäistä kertaa, lisätään nämä neljä tavua ja paikkoja hajautustaulukkoon ja jatketaan hakua.
Jos slotissa on sijoitus, se tarkoittaa, että olemme löytäneet vastaavan arvon.
Jos slotin arvo plus liukusäätimen koko < nykyisen merkin sijainti, osumispaikka ylittää lohkon koon, ja ohjelma päivittää hash-paikan arvon nykyisen merkkijonon sijaintiin.
LZ4 tarkistaa, onko hajautusristiriitaa ollut. Jos slotin 4 tavua eivät ole samat kuin nykyinen merkkijono, täytyy olla hajautusristiriita. Kirjoittajan oma xxhash tunnetaan myös tehokkuudestaan, mutta ristiriidat ovat väistämättömiä. Ristiriitojen sattuessa ohjelma päivittää myös hash-paikan arvon merkkijonon nykyiseen sijaintiin
Lopuksi voimme varmistaa, että osuma on pätevä, ja ohjelma jatkaa tarkistamista, ovatko seuraavat merkit vastaavassa merkkijonossa samat. Lopuksi kopioi kaikki merkit edellisen kelvollisen osuman lopusta tämän pätevän osuman alkuun pakattuun tiedostoon ja lisää tämän pätevän osuman vastaava sekvenssi.
Collet kutsuu LZ4-sekvenssin tuottamat vastaavat yksiköt, jotka muodostavat LZ4-pakatun tiedoston. Yksityiskohdat ovat seuraavat:
Token on yhden tavun pituinen, ja ensimmäiset neljä sanaa ovat kirjaimellisen pituuden ja viimeiset neljä sanaa sovituspituutta. Kuten aiemmin mainittiin, kaikki merkit edellisen kelvollisen osuman lopusta tämän kelvollisen vastaavuuden alkuun kopioidaan pakattuun tiedostoon, nämä pakkaamattomat tiedostot ovat kirjaimellisia ja niiden pituus on kirjaimellinen pituus.
Kirjaimellisesti seuraa poikkeama. Kuten LZ77:ssä, poikkeama ja ottelun pituus viittaavat nykyisen merkkijonon pituuteen sen osumasta, ja matchin pituus tarkoittaa nykyisen merkkijonon osumapituuden pituutta samaan merkkijonoon sanakirjassa. Dekompressiossa on käydä se läpi löytääksesi kopioitavan kielen ja kopioitavan pituuden. Poikkeaman suuruus on kiinteä.
Kuvassa literaalipituus+ ja match length+ ovat, että jos merkin kirjaimellinen tai match length 4 sanaa ei riitä, ne jatkavat kasvuaan vastaavissa paikoissa. 4 sanaa voi edustaa 0–15, ja jos niitä on enemmän, lisää yksi tavu, eli lisää tavu 255 kokoon, kunnes tavu on alle 255. Sovituspituudessa 0 edustaa 4 tavua.
Viimeiset 12 tavua päättyvät kirjaimellisesti, koska ne kopioidaan suoraan.
Katsotaanpa koodia (python on abstraktimpi)
Yhteenveto Kaiken tämän sanottuani en ole vieläkään tiivistänyt, miksi LZ4 on niin nopea. Vertaillaan ensin sanakirjahakua LZ77:n ja LZ4:n välillä. Natiivi LZ77 etsii sanakirjoja etsimällä suurinta osumia välimuistista ja sanakirjasta. Tämä on ongelma, jossa löydetään suurin identtinen merkkijono kahdesta säikeestä. Jos emme käytä dynaamista ohjelmointia, pahimmillaan meidän täytyy ottaa huomioon kaikki yhden merkkijonon alijonot ja sitten yhdistää ne toiseen merkkijonoon. Jos ×käytämme dynaamista ohjelmointia, käytämme taulukkoa pisimmän vastaavuuden säilyttämiseen dynamiikossa, mikä mahdollistaa vastaavuuden täydentämisen vain O(m*n):n tapauksessa. Ja se koskee vain kahta hakukätköä ja sanakirjaa. Pahimmassa tapauksessa, jos osumia ei ole, LZ77:n täytyy laskea (koko tiedoston pituus – haettavan välimuistin pituus) monina tällaisiin täsmävyysongelmiin. LZ4 käyttää itse asiassa laajempaa dynaamisen ohjelmoinnin tasoa: se tallentaa 4 tavua ja niiden sijainteja hajautustauluun, ja sitten yhdistää uuden 4 tavun datan joka kerta vain nähdäkseen, ovatko hajautustaulukon arvot päteviä. Kun löydät kelvollisen vastaavuusarvon, jos katsot kahden vastaavuusarvojoukon jatkodataa, löydät myös sen pisimmän osuman. Koska jokainen LZ4-hajautustaulukon avain vastaa vain yhtä paikkaa, hajautustaulukon löytäminen, lisääminen ja muokkaaminen vaatii vain O(1):n. Jos osumia löytyy, tarvitaan lisää ryhmävertailuja, mutta kokonaisajassa nämä vertailut korvaavat enemmän aikaa hajautustaulukon etsimiseen, joten LZ4-algoritmin kokonaisaika on vain O(n). Täytyy ihailla Colletin algoritmin kauneutta! Algoritmin nopeuttamiseksi Collet asettaa oletushajautustaulukon koon 16k, jota suositellaan ei ylitettävän 32k, jotta se voidaan sijoittaa lähes kaikkien suorittimien (Intel) L1-välimuistiin. Kaikki tietävät, että CPU L1:n välimuistin nopeus ja muistisuhde ovat hyvin erilaisia, joten ei ole yllättävää, että LZ4 lentää nopeasti, puhumattakaan siitä, että LZ4:n hash-taulukossa käytetty hash-yhtälö on edelleen nopein xxhash. Tietenkin tällaisella suunnittelulla on haittapuolensa. Mitä pienempi hash-taulukko, sitä vähemmän avaimia siinä on. Tämä tarkoittaa, että lisää hajautusristiriitoja syntyy, mikä on väistämätöntä. Ja enemmän hash-törmäyksiä tarkoittaa vähemmän osumia. Ja pienempi hajautustaulukko tarkoittaa myös pienempää liukuvaa ikkunaa, mikä tarkoittaa, että enemmän osumia hylätään, koska ne ovat liian kaukana. Vähemmän osumia tarkoittaa pienempää pakkaussuhdetta, minkä vuoksi LZ4:n pakkaussuhde on vähemmän näkyvä. Tulevaisuuteen katsottuna LZ4:llä on laaja valikoima sovellusskenaarioita. Aivan kuten keskimmäinen uloslähetys käytettiin VR:ssä Piilaaksossa, LZ4 voi lisätä kaistanleveyden käyttöä tuomalla vähemmän IO:ita erittäin alhaisen viiveen kustannuksella erittäin nopean pakkausnopeuden vuoksi. On myös pieni arvailu: jos suorittimella on suurempi välimuisti tasolla 1, voiko LZ4 nostaa pakkaussuhdetta tinkimättä nopeudesta?
Alkuperäinen:Hyperlinkin kirjautuminen on näkyvissä. |
Julkaistu 3.1.2022 13.54.23
|
|
|
|
