Pažiūrėjęs HBO dramą "Silicio slėnis", visada domėjausi glaudinimo algoritmais. Richard Hendricks ir jo vidurio iš suspaudimo algoritmas jame, žinoma, yra netikras, bet po Google sunku, aš pastebėjau, kad yra toks suspaudimo algoritmas genijus realiame gyvenime.
Yann Collet išrado LZ4 glaudinimo algoritmą 2011 m. Žinoma, LZ4 algoritmas nėra toks nuostabus kaip vidurinis, tačiau jis žinomas dėl savo nenugalimo suspaudimo greičio ir didesnio dekompresijos greičio, kai galima garantuoti tam tikrą suspaudimo greitį.
Čia nesigilinsiu į jo suspaudimo greičio įvertinimą, jei jus domina, galite perskaityti šį palyginimo straipsnį:Hipersaito prisijungimas matomas.
Taip pat pridedamas LZ4 github adresas:Hipersaito prisijungimas matomas.
Šiame straipsnyje pagrindinis dėmesys skiriamas LZ4 glaudinimo algoritmo principo paaiškinimui. Didysis dievas anksčiau parašė LZ4 algoritmo paaiškinimą:Hipersaito prisijungimas matomas.Bet kai studijavau anksčiau, pajutau, kad šis straipsnis nėra labai draugiškas pradedantiesiems, todėl pradėjau kitą straipsnį pradedantiesiems, tokiems kaip aš.
Jei apibendrinsite vienu sakiniu, LZ4 yra LZ77, kuriame saugomas žodynas su 16k dydžio maišos lentele ir supaprastinamas paieška.
LZ4 yra be nuostolių glaudinimo algoritmas, siūlantis > 500 MB/s suspaudimo greitį vienam branduoliui, kurį galima keisti naudojant kelių branduolių procesorius. Jis turi itin greitus dekoderius, kurių greitis yra keli GB/s vienam branduoliui, dažnai pasiekiantys RAM greičio ribas kelių branduolių sistemose.
Greitis gali būti dinamiškai reguliuojamas, pasirenkant "pagreičio" koeficientą, kuris pakeičia suspaudimo laipsnį didesniam greičiui. Kita vertus, taip pat pateikiamas didelio suspaudimo išvestinis LZ4_HC, skirtas padidinti suspaudimą procesoriaus laiko sąskaita. Visos versijos turi vienodą dekompresijos greitį.
Taigi, kas yra LZ77?
LZ77 suspaudimas ir principas
LZ77 yra algoritmas, kuris glaudinimui taiko žodyną. Kalbant paprastai, tai yra leisti programai stebėti (pažvelgti į žodyną), ar šiuo metu matomi duomenys yra dubliuojami su ankstesniu, ir jei taip, mes išsaugome atstumą (poslinkį) ir pasikartojančių laukų ilgį, kad pakeistume pasikartojančius laukus ir suspaustume duomenis.
NuorodaHipersaito prisijungimas matomas.
Raidžių eilutei A A B C B B B A B C, kai skaitoma antroji A, programa išsaugo (1,1) (1 skaitmuo iš ankstesnio, ilgis 1), o panašiai, kai skaitomas antrasis B, programa išsaugo (2,1) (atstumas 2, ilgis 1).
Bet jei eilutė yra ilgesnė ir programa visą laiką įrašo duomenis į žodyną, pasikartojančių laukų paieška užima labai daug laiko, nes blogiausiu atveju programa pereina per visą žodyną su kiekviena nauja perskaityta raide. LZ77 šiai problemai išspręsti naudoja stumdomo lango metodą.
Panašiai kaip TCP naudojant slankųjį langą, stumdomas langas gali sumažinti talpyklos sritį, kad vienu metu nebūtų apdorojama per daug talpykloje saugomų duomenų. LZ77 žodynas nuolat nedidėja, bet atmeta pirmuosius į žodyną įtrauktus simbolius, kai jis viršija žodyne nurodytą maksimalų dydį, kad žodyno dydis visada būtų išlaikytas nurodytu maksimaliu dydžiu.
Tarkime, kad žodyno ilgis yra 3
| žodynas |
| A | A B C B B A B C
Išeiga (0,0,A)
| A A | B C B B A B C
Išvestis(1,1)
| A A B | C B B A B C
Išėjimas (0,0,B)
A | A B C | B B A B C
Išeiga (0,0,C)
A A | B C B | B A B C
Išvestis(2,1)
Kita slankiojo lango dalis yra talpykla, kurioje reikia ieškoti (žiūrėkite į priekį buferis neturi oficialaus vertimo). Talpykla, kurioje reikia ieškoti, yra nesuspausta dalis, kurios ilgis yra arčiausiai žodyno. LZ77 algoritmas atitiks ilgiausią eilutę šioje simbolio dalyje, kuri yra tokia pati kaip žodynas. Ankstesnis pavyzdys gali būti laikomas 1 perspektyviniu buferiu.
Tarkime, kad žodyno ilgis yra 5, o talpyklos dydis, kurio reikia ieškoti, yra 3
| žodynas | Žvilgsnis į ateitį |
A | A B C B B | A B C |
Išėjimas(5,3)
Ilgiausia atitinkama eilutė yra ABC
Visas glaudinimo procesas:
Tarkime, kad žodyno ilgis yra 5, o talpyklos dydis, kurio reikia ieškoti, yra 3
| žodynas | Žvilgsnis į ateitį |
| A A B | C B B A B C
Išeiga (0,0,A)
| A | A B C | B B A B C
Išvestis(1,1)
| A A | B C B | B A B C
Išėjimas (0,0,B)
| A A B | C B B | A B C
Išeiga (0,0,C)
| A A B C | B B A | B C
Išvestis(2,1)
| A A B C B | B A B | C
Išvestis(1,1)
A | A B C B B | A B C |
Išėjimas(5,3)
A A B C | B B A B C | 。。。 |
Nereikia išsaugoti žodyno kompresoriaus išvesties faile, nes dekompresijos programa atkuria žodyną, suderindama išvesties vienetus.
Dekompresijos procesas
Vienas iš didžiausių LZ77 algoritmo privalumų yra tai, kad jis labai greitai išskleidžiamas.
Jei pirmasis atitinkamas vienetas yra (0,0,A), tada A yra išvestis.
Antrasis atitikimo vienetas yra (1,1), kuris nukopijuoja ankstesnį išvesties eilutės bitą, ir išveda A, jei kopijavimo ilgis yra 1.
。。。
Jei paskutinis atitinkantis vienetas yra (5,3), tada peržiūrėkite 5 bitus kopijavimo išvesties eilutėje, o jei kopijavimo ilgis yra 3, tada išvestis A, B, C.
Daugiausiai laiko reikalaujanti LZ77 algoritmo glaudinimo dalis yra ilgiausio atitinkančio simbolio paieška talpykloje, kurios reikia ieškoti žodyne. Jei žodynas ir talpykla, kurioje reikia ieškoti, yra per trumpi, tikimybė rasti atitikmenį yra maža. Todėl LZ4 pakeitė LZ77 atitikimo algoritmą.
Pirma, LZ4 algoritmo žodynas yra maišos lentelė. Žodyno raktas yra 4 baitų eilutė, kiekvienas raktas atitinka tik vieną lizdą, o lizdo reikšmė yra šios eilutės padėtis.
Užuot ieškojęs talpykloje, LZ4 vienu metu nuskaito keturis baitus iš įvesties failo, o tada ieško lizdo, atitinkančio maišos lentelės eilutę, kuri toliau vadinama dabartine eilute.
Jei pasiekėte paskutinius 12 simbolių, įdėkite juos tiesiai į išvesties failą.
Jei lizde nėra priskirtos reikšmės, tai reiškia, kad keturi baitai pasirodo pirmą kartą, pridėkite šiuos keturis baitus ir pozicijas į maišos lentelę ir tęskite paiešką.
Jei lizde yra priskyrimas, tai reiškia, kad radome atitinkančią vertę.
Jei lizdo vertė plius slankiklio lango dydis < dabartinio simbolio padėtį, tada atitikimo pozicija viršija bloko dydį, ir programa atnaujina maišos lizdo reikšmę į dabartinės eilutės padėtį.
LZ4 patikrins, ar nebuvo maišos konflikto. Jei 4 baitai lizde nesutampa su dabartine eilute, turi būti maišos konfliktas. Paties autoriaus xxhash taip pat žinomas dėl savo efektyvumo, tačiau konfliktai neišvengiami. Kilus konfliktui, programa taip pat atnaujina maišos lizdo reikšmę į dabartinę eilutės padėtį
Galiausiai galime patvirtinti, kad atitiktis galioja, ir programa toliau matys, ar vėlesni atitikimo eilutės simboliai yra vienodi. Galiausiai nukopijuokite visus simbolius nuo ankstesnės galiojančios atitikties pabaigos iki šios galiojančios atitikties pradžios į suglaudintą failą ir įtraukite šios galiojančios atitikties atitikimo seką.
Collet iškviečia atitinkamus vienetus, išvestus iš LZ4 sekų, ir jie sudaro LZ4 suspaustą failą. Išsami informacija yra tokia:
Žetonas yra 1 baito ilgio, pirmieji 4 žodžiai yra pažodinis ilgis, o paskutiniai 4 žodžiai yra rungtynių ilgis. Kaip minėta anksčiau, visi simboliai nuo ankstesnio galiojančio atitikimo pabaigos iki šio galiojančio atitikmens pradžios bus nukopijuoti į suspaustą failą, šie nesuspausti failai yra pažodiniai, o jų ilgis yra pažodinis ilgis.
Pažodžiui po to nukrypimas. Kaip ir LZ77, nuokrypis ir atitikties ilgis nurodo dabartinės eilutės ilgį nuo jos atitikmens, o atitikties ilgis reiškia dabartinės eilutės atitikties ilgį su ta pačia žodyno eilute. Dekompresijoje reikia pereiti per jį, kad surastumėte kopijuojamą eilutę ir ilgį, kurį reikia kopijuoti. Nuokrypio dydis yra fiksuotas.
Paveikslėlyje pažodinis ilgis+ ir rungtynių ilgis+ yra jei pažodinio arba rungtynės ilgio 4 žodžių žetone nepakanka, jie ir toliau didės atitinkamose pozicijose. 4 žodžiai gali reikšti 0–15, o jei jų yra daugiau, pridėkite vieną baitą, tai yra, pridėkite 255 prie dydžio, kol baitas bus mažesnis nei 255. Atitinkančiame ilgyje 0 reiškia 4 baitus.
Paskutiniai 12 baitų baigiasi tiesiogine prasme, nes jie buvo nukopijuoti tiesiogiai.
Pažvelkime į kodą (python yra abstraktesnis)
Santrauka Visa tai pasakęs, vis dar neapibendrinau, kodėl LZ4 yra toks greitas. Pirmiausia palyginkime žodyno paiešką tarp LZ77 ir LZ4. Vietinis LZ77 ieško žodynų ieškodamas didžiausio atitikmens talpykloje, kurioje reikia ieškoti, ir žodyne. Tai yra didžiausios identiškos eilutės dviejose eilutėse radimo problema. Jei nenaudojame dinaminio programavimo, blogiausiu atveju turime atsižvelgti į visas vienos eilutės eilutes ir tada suderinti jas kitoje eilutėje. Jei ×naudojame dinaminį programavimą, naudosime lentelę, kad išlaikytume ilgiausią atitikmenį dinamikoje, o tai leis mums užbaigti atitikmenį tik O(m*n) atveju. Ir tai tik pora paieškos talpyklų ir žodynų. Blogiausiu atveju, jei nėra atitikmenų, tada LZ77 turės suskaičiuoti (viso failo ilgis - ieškomos talpyklos ilgis) kaip daug tokių atitikimo problemų. LZ4 iš tikrųjų naudoja didesnį dinaminio programavimo lygį: jis saugo 4 baitus ir jų pozicijas maišos lentelėje, o tada kiekvieną kartą suderina naujus 4 baitus duomenų, kad pamatytų, ar maišos lentelės reikšmės yra galiojančios. Suradę galiojančią atitinkančią vertę, pažvelgę į dviejų atitinkančių verčių rinkinių tolesnius duomenis, taip pat galite rasti ilgiausią atitiktį. Kadangi kiekvienas LZ4 maišos lentelės raktas atitinka tik 1 lizdą, maišos lentelės paieškai, pridėjimui ir modifikavimui reikia tik O(1). Jei po suderinimo randama daugiau atitikmenų, reikia daugiau grupių palyginimų, tačiau per visą laiką šie palyginimai pakeis daugiau laiko maišos lentelės paieškai, todėl bendras LZ4 algoritmo laikas yra tik O(n). Turiu žavėtis Collet algoritmo grožiu! Kad algoritmas būtų dar greitesnis, "Collet" nustato numatytąjį maišos lentelės dydį į 16k, kuris nerekomenduojamas viršyti 32k, kad jį būtų galima įdėti į beveik visų procesorių (Intel) L1 talpyklą. Visi žino, kad procesoriaus L1 talpyklos greitis ir atminties santykis labai skiriasi, todėl nenuostabu, kad LZ4 skraido greitai, jau nekalbant apie tai, kad LZ4 maišos lentelėje naudojama maišos lygtis vis dar yra greičiausia xxhash. Žinoma, toks dizainas turi savo trūkumų. Kuo mažesnė maišos lentelė, tuo mažiau raktų ji turi. Tai reiškia, kad atsiras daugiau maišos konfliktų, o tai neišvengiama. O daugiau maišos susidūrimų reiškia mažiau atitikmenų. Mažesnė maišos lentelė taip pat reiškia mažesnį slankiojantį langą, o tai reiškia, kad daugiau atitikmenų bus atmesta, nes jie yra per toli. Mažiau atitikmenų reiškia mažesnį suspaudimo laipsnį, todėl LZ4 suspaudimo laipsnis yra ne toks ryškus. Žvelgiant į ateitį LZ4 turi platų taikymo scenarijų spektrą. Lygiai taip pat, kaip vidurio išėjimas buvo naudojamas VR Silicio slėnyje, LZ4 gali padidinti pralaidumo panaudojimą, suteikdamas mažiau IO labai mažos delsos sąskaita dėl labai didelio glaudinimo greičio. Taip pat yra šiek tiek spėlionių, jei yra procesorius su didesne talpykla 1 lygyje, ar LZ4 gali padidinti suspaudimo laipsnį nepakenkiant greičiui?
Originalus:Hipersaito prisijungimas matomas. |
Paskelbta 2022-01-03 13:54:23
|
|
|
|
