Pēc HBO drāmas "Silīcija ieleja" noskatīšanās mani vienmēr ir interesējuši saspiešanas algoritmi. Ričards Hendrikss un viņa vidusdaļas saspiešanas algoritms, protams, ir viltoti, bet pēc Google grūti es atklāju, ka reālajā dzīvē ir šāds kompresijas algoritma ģēnijs.
Yann Collet izgudroja LZ4 saspiešanas algoritmu 2011. gadā. Protams, LZ4 algoritms nav tik satriecošs kā vidus, taču tas ir pazīstams ar savu neuzvaramo saspiešanas ātrumu un ātrāku dekompresijas ātrumu, kad var garantēt noteiktu saspiešanas ātrumu.
Es šeit neiedziļināšos sīkāk par tā saspiešanas ātruma novērtējumu, ja jūs interesē, varat izlasīt šo salīdzinājuma rakstu:Hipersaites pieteikšanās ir redzama.
Pievienota arī LZ4 github adrese:Hipersaites pieteikšanās ir redzama.
Šajā rakstā galvenā uzmanība pievērsta LZ4 saspiešanas algoritma principa izskaidrošanai. Liels dievs iepriekš uzrakstīja LZ4 algoritma skaidrojumu:Hipersaites pieteikšanās ir redzama.Bet, kad es mācījos iepriekš, es jutu, ka šis raksts nav ļoti draudzīgs iesācējiem, tāpēc es sāku citu rakstu iesācējiem, piemēram, man.
Ja jūs to apkopojat vienā teikumā, LZ4 ir LZ77, kas glabā vārdnīcu ar 16k izmēra jaucējtabulu un vienkāršo izgūšanu.
LZ4 ir bezzudumu saspiešanas algoritms, kas piedāvā saspiešanas ātrumu > 500 MB/s uz kodolu, ko var mērogot ar daudzkodolu procesoriem. Tam ir ārkārtīgi ātri dekoderi ar ātrumu vairāki GB / s uz kodolu, bieži sasniedzot RAM ātruma ierobežojumus daudzkodolu sistēmās.
Ātrumu var dinamiski regulēt, izvēloties "paātrinājuma" koeficientu, kas maina saspiešanas pakāpi ātrākam ātrumam. No otras puses, tiek nodrošināta arī augstas kompresijas atvasinājuma LZ4_HC, lai palielinātu saspiešanu uz CPU laika rēķina. Visām versijām ir vienāds dekompresijas ātrums.
Tātad, kas ir LZ77?
LZ77 saspiešana un princips
LZ77 ir algoritms, kas saspiešanai izmanto vārdnīcu. Nespeciālistu izteiksmē tas ir ļaut programmai novērot (apskatīt vārdnīcu), vai pašlaik redzamie dati ir dublēti ar iepriekšējo, un, ja tā, mēs saglabājam attālumu (nobīdi) un dublikātu lauku garumu, lai aizstātu dublikātus un saspiestu datus.
AtsauceHipersaites pieteikšanās ir redzama.
Burtu virknei A A B C B B B A B C, kad tiek lasīts otrais A, programma saglabā (1,1) (1 cipars no iepriekšējā, garums 1), un līdzīgi, kad tiek lasīts otrais B, programma saglabā (2,1) (attālums 2, garums 1).
Bet, ja virkne ir garāka un programma visu laiku ieraksta datus vārdnīcā, dublikātu lauku meklēšana kļūst ārkārtīgi laikietilpīga, jo sliktākajā gadījumā programma iet cauri visai vārdnīcai ar katru jauno izlasīto burtu. LZ77 izmanto bīdāmo logu metodi, lai atrisinātu šo problēmu.
Līdzīgi kā TCP sākumpunkts, izmantojot bīdāmo logu, bīdāmais logs var samazināt kešatmiņas apgabalu, lai vienlaikus izvairītos no pārāk daudz kešatmiņas datu apstrādes. LZ77 vārdnīca visu laiku nepalielinās, bet izmet pirmās vārdnīcai pievienotās rakstzīmes, kad tā pārsniedz vārdnīcas norādīto maksimālo lielumu, lai nodrošinātu, ka vārdnīcas lielums vienmēr tiek saglabāts norādītajā maksimālajā lielumā.
Pieņemsim, ka vārdnīcas garums ir 3
| vārdnīca |
| A | A B C B B A B C
Jauda (0,0,A)
| A A | B C B B A B C
Izeja(1,1)
| A A B | C B B A B C
Izeja (0,0,B)
A | A B C | B B A B C
Jauda (0,0,C)
A A | B C B | B A B C
Izeja(2,1)
Otra bīdāmā loga daļa ir meklējamā kešatmiņa (skaties uz priekšu buferim nav oficiāla tulkojuma). Meklējamā kešatmiņa ir nesaspiestā garuma daļa, kas ir vistuvāk vārdnīcai. LZ77 algoritms atbildīs garākajai virknei šajā rakstzīmes daļā, kas ir tāda pati kā vārdnīca. Iepriekšējo piemēru var uzskatīt par nākotnes buferi 1.
Pieņemsim, ka vārdnīcas garums ir 5 un meklējamās kešatmiņas lielums ir 3
| vārdnīca | Nākotnes rezerve |
A | A B C B B | A B C |
Izeja(5,3)
Garākā virkne, kas atbilst, ir ABC
Pilnīgs saspiešanas process:
Pieņemsim, ka vārdnīcas garums ir 5 un meklējamās kešatmiņas lielums ir 3
| vārdnīca | Nākotnes rezerve |
| A A B | C B B A B C
Jauda (0,0,A)
| A | A B C | B B A B C
Izeja(1,1)
| A A | B C B | B A B C
Izeja (0,0,B)
| A A B | C B B | A B C
Jauda (0,0,C)
| A A B C | B B A | B C
Izeja(2,1)
| A A B C B | B A B | C
Izeja(1,1)
A | A B C B B | A B C |
Izeja(5,3)
A A B C | B B A B C | 。。。 |
Nav nepieciešams saglabāt vārdnīcu kompresora izvades failā, jo dekompresijas programma atjauno vārdnīcu, saskaņojot izvades vienības.
Dekompresijas process
Viena no lielākajām LZ77 algoritma priekšrocībām ir tā, ka tas ir ļoti ātri atspiežams.
Ja pirmā atbilstošā vienība ir (0,0,A), tad A ir izeja.
Otrā atbilstības vienība ir (1,1), kas kopē iepriekšējo bitu izvades virknē, un izvada A, ja kopijas garums ir 1.
。。。
Ja pēdējā atbilstošā vienība ir (5,3), tad apskatiet 5 bitus kopēšanas izvades virknē, un, ja kopijas garums ir 3, tad izvadi A, B, C.
LZ77 algoritma saspiešanas laikietilpīgākā daļa ir garākās atbilstošās rakstzīmes atrašana kešatmiņā, kas jāmeklē vārdnīcā. Ja meklējamā vārdnīca un kešatmiņa ir pārāk īsa, izredzes atrast atbilstību ir niecīgas. Tāpēc LZ4 ir mainījis LZ77 atbilstības algoritmu.
Pirmkārt, LZ4 algoritma vārdnīca ir jaucējtabula. Vārdnīcas atslēga ir 4 baitu virkne, katra atslēga atbilst tikai vienam slotam, un vērtība slotā ir šīs virknes pozīcija.
Tā vietā, lai meklētu kešatmiņu, LZ4 vienlaikus nolasa četrus baitus no ievades faila un pēc tam meklē slotu, kas atbilst virknei jaucējtabulā, kas turpmāk tiek saukta par pašreizējo virkni.
Ja esat sasniedzis pēdējās 12 rakstzīmes, ievietojiet tās tieši izvades failā.
Ja slotā nav piešķirta vērtība, tas nozīmē, ka četri baiti parādās pirmo reizi, pievienojiet šos četrus baitus un pozīcijas jaucējtabulā un turpiniet meklēšanu.
Ja slotā ir piešķiršana, tas nozīmē, ka mēs esam atraduši atbilstošu vērtību.
Ja vērtība slotā un slīdņa loga lielums < pašreizējās rakstzīmes pozīciju, tad atbilstības pozīcija pārsniedz bloka lielumu, un programma atjaunina vērtību jaucējslotā uz pašreizējās virknes pozīciju.
LZ4 pārbaudīs, vai nav bijis jaucējkonflikts. Ja 4 baiti slotā nav tādi paši kā pašreizējā virkne, ir jābūt jaucējkonfliktam. Autora paša xxhash ir pazīstams arī ar savu efektivitāti, taču konflikti ir neizbēgami. Konflikta gadījumā programma arī atjaunina vērtību jaucējslotā uz pašreizējo virknes pozīciju
Visbeidzot, mēs varam apstiprināt, ka atbilstība ir derīga, un programma turpinās redzēt, vai nākamās rakstzīmes atbilstības virknē ir vienādas. Visbeidzot, kopējiet visas rakstzīmes no iepriekšējās derīgās atbilstības beigām līdz šīs derīgās atbilstības sākumam saspiestajā failā un pievienojiet šīs derīgās atbilstības atbilstošo secību.
Collet izsauc atbilstošās vienības, ko izvada LZ4 secības, un tās veido LZ4 saspiesto failu. Sīkāka informācija ir šāda:
Marķieris ir 1 baitu garš, pirmie 4 vārdi ir burtiskā garums un pēdējie 4 vārdi ir atbilstības garums. Kā minēts iepriekš, visas rakstzīmes no iepriekšējās derīgās atbilstības beigām līdz šīs derīgās atbilstības sākumam tiks kopētas saspiestā failā, šie nesaspiestie faili ir burtiski, un to garums ir burtisks garums.
Burtiski seko novirze. Tāpat kā LZ77, novirze un atbilstības garums attiecas uz pašreizējās virknes garumu no tās atbilstības, un atbilstības garums attiecas uz pašreizējās virknes atbilstības garumu tai pašai virknei vārdnīcā. Dekompresijā ir jāiet cauri, lai atrastu kopējamo virkni un kopējamo garumu. Novirzes lielums ir fiksēts.
Attēlā burtiskais garums+ un atbilstības garums+ ir, ja burtiskā vai atbilstības garuma 4 vārdi žetonā nav pietiekami, tie turpinās palielināties attiecīgajās pozīcijās. 4 vārdi var apzīmēt 0-15, un, ja ir vairāk, pievienojiet vienu baitu, tas ir, pievienojiet 255 lielumam, līdz baits ir mazāks par 255. Atbilstošajā garumā 0 apzīmē 4 baitus.
Pēdējie 12 baiti beidzas burtiski, jo tie tika kopēti tieši.
Apskatīsim kodu (python ir abstraktāks)
Kopsavilkums To visu sakot, es joprojām neesmu apkopojis, kāpēc LZ4 ir tik ātrs. Vispirms salīdzināsim vārdnīcas meklēšanu starp LZ77 un LZ4. Vietējā LZ77 meklē vārdnīcas, meklējot lielāko atbilstību meklējamajā kešatmiņā un vārdnīcā. Tā ir problēma, atrodot lielāko identisku virkni divās virknēs. Ja mēs neizmantojam dinamisko programmēšanu, tad sliktākajā gadījumā mums ir jāapsver visas vienas virknes apakšvirknes un pēc tam jāsaskaņo tās citā virknē. Ja ×mēs izmantojam dinamisko programmēšanu, mēs izmantosim tabulu, lai saglabātu garāko atbilstību dinamikā, kas ļaus mums pabeigt atbilstību tikai O(m*n) gadījumā. Un tas attiecas tikai uz pāris meklēšanas kešatmiņām un vārdnīcām. Sliktākajā gadījumā, ja nav atbilstības, tad LZ77 būs jāskaita (visa faila garums - meklējamās kešatmiņas garums) kā daudzas šādas atbilstības problēmas. LZ4 faktiski izmanto lielāku dinamiskās programmēšanas līmeni: tas saglabā 4 baitus un to pozīcijas jaucējtabulā un pēc tam katru reizi saskaņo jaunus 4 baitus datu tikai, lai redzētu, vai jaucējtabulā esošās vērtības ir derīgas. Pēc derīgas atbilstības vērtības atrašanas, aplūkojot divu atbilstošo vērtību kopu sekojuma datus, varat atrast arī tās garāko atbilstību. Tā kā katra LZ4 jaucējtabulas atslēga atbilst tikai 1 slotam, jaucējtabulas atrašanai, pievienošanai un modificēšanai ir nepieciešams tikai O(1). Ja pēc saskaņošanas tiek atrastas vairāk atbilstības, ir nepieciešami vairāk grupu salīdzinājumu, bet kopējā laikā šie salīdzinājumi aizstās vairāk laika, lai meklētu jaucējtabulu, tāpēc LZ4 algoritma kopējais laiks ir tikai O(n). Man ir jāapbrīno Collet algoritma skaistums! Lai algoritms būtu vēl ātrāks, Collet iestata noklusējuma jaucējtabulas lielumu uz 16k, kas nav ieteicams pārsniegt 32k, lai to varētu ievietot gandrīz visu CPU (Intel) L1 kešatmiņā. Ikviens zina, ka CPU L1 kešatmiņas ātrums un atmiņas attiecība ir ļoti atšķirīga, tāpēc nav pārsteidzoši, ka LZ4 lido ātri, nemaz nerunājot par to, ka LZ4 jaucējtabulā izmantotais jaucējvienādojums joprojām ir ātrākais xxhash. Protams, šādam dizainam ir trūkumi. Jo mazāka jaucējtabula, jo mazāk atslēgu tai ir. Tas nozīmē, ka radīsies vairāk jaucējkonfliktu, kas ir neizbēgami. Un vairāk jaucējkodu sadursmju nozīmē mazāk atbilstību. Un mazāka jaucējtabula nozīmē arī mazāku bīdāmo logu, kas nozīmē, ka vairāk sērkociņu tiks izmesti, jo tie ir pārāk tālu. Mazāk sērkociņu nozīmē mazāku saspiešanas pakāpi, tāpēc LZ4 ir mazāk pamanāma saspiešanas pakāpe. Skatoties uz priekšu LZ4 ir plašs pielietojuma scenāriju klāsts. Tāpat kā vidusdaļa tika izmantota VR Silīcija ielejā, LZ4 var palielināt joslas platuma izmantošanu, nodrošinot mazāk IO uz ļoti zema latentuma rēķina, pateicoties ļoti ātrajam saspiešanas ātrumam. Ir arī neliels pieņēmums, ja ir CPU ar lielāku kešatmiņu 1. līmenī, vai LZ4 var palielināt saspiešanas pakāpi, neapdraudot ātrumu?
Sākotnējā:Hipersaites pieteikšanās ir redzama. |
Publicēts 03.01.2022 13:54:23
|
|
|
|
