Pärast HBO draama "Silicon Valley" vaatamist on mind alati huvitanud tihendusalgoritmid. Richard Hendricks ja tema keskmine väljakompressiooni algoritm selles on muidugi võltsid, kuid pärast Google'i rasket otsimist avastasin, et päriselus on selline tihendusalgoritmi geenius.
Yann Collet leiutas LZ4 tihendusalgoritmi 2011. aastal. Muidugi pole LZ4 algoritm nii hea kui keskmine välja, kuid see on tuntud oma võitmatu kompressioonikiiruse ja kiirema dekompressioonikiiruse poolest, kui teatud kompressioonimäär on garanteeritud.
Ma ei hakka siin selle tihenduskiiruse hindamisest detailidesse laskuma, kui oled huvitatud, võid lugeda seda võrdlusartiklit:Hüperlingi sisselogimine on nähtav.
Lisaks on lisatud LZ4 githubi aadress:Hüperlingi sisselogimine on nähtav.
See artikkel keskendub LZ4 tihendusalgoritmi põhimõtte selgitamisele. Suur jumal kirjutas varem LZ4 algoritmi seletuse:Hüperlingi sisselogimine on nähtav.Aga kui ma varem õppisin, tundsin, et see artikkel pole algajatele eriti sõbralik, nii et alustasin uut artiklit algajatele nagu mina.
Kui selle ühe lausega kokku võtta, on LZ4 LZ77, mis salvestab sõnastiku 16k suurusega räsi tabeliga ja lihtsustab otsingut.
LZ4 on kaotusteta kompressioonialgoritm, mis pakub tihenduskiirust > 500 MB/s tuuma kohta, mida saab skaleerida mitmetuumaliste protsessoritega. Sellel on äärmiselt kiired dekoodrid, mille kiirus on mitu GB/s tuuma kohta, sageli saavutades RAM-i kiiruse piirangud mitmetuumalistes süsteemides.
Kiirust saab dünaamiliselt reguleerida, valides "kiirendustegur", mis vahetab kompressioonisuhte kiirema kiiruse vastu. Teisalt on olemas ka kõrge kompressiooniga tuletis LZ4_HC mis suurendab kompressiooni protsessori aja arvelt. Kõigil versioonidel on sama dekompressioonikiirus.
Mis siis on LZ77?
LZ77 kompressioon ja põhimõte
LZ77 on algoritm, mis rakendab tihendamiseks sõnastikku. Lihtsustatult öeldes tähendab see programmi jälgimist (sõnastikku), kas praegu nähtav info on eelmisega dubleeritud, ja kui jah, siis salvestame duplikaatväljade kauguse (nihke) ja pikkuse, et asendada duplikaatväljad ja tihendada andmed.
viideHüperlingi sisselogimine on nähtav.
Tähejada A A B C B B B A B C puhul, salvestab programm teise A lugemisel (1,1) (1 number eelmisest, pikkus 1) ja samamoodi, kui loetakse teine B tähe, salvestab programm (2,1) (kaugus 2, pikkus 1).
Kuid kui string on pikem ja programm salvestab andmed kogu aeg sõnaraamatusse, muutub duplikaatväljade otsimine äärmiselt ajamahukaks, sest halvimal juhul läbib programm iga uue tähe lugemisega kogu sõnastiku. LZ77 kasutab selle probleemi lahendamiseks liugakna meetodit.
Sarnaselt TCP alguspunktile liugakna kasutamisel võib liugaken vähendada vahemälu pindala, et vältida liiga suure vahemällu salvestatud andmete töötlemist samaaegselt. LZ77-s ei suurene sõnastik kogu aeg, vaid viskab välja esimesed lisatud tähemärgid, kui see ületab sõnaraamatu määratud maksimaalse suuruse, et tagada sõnastiku suurus alati määratud maksimaalsel suurusel.
Oletame, et sõnaraamatu pikkus on 3
| sõnastik |
| A | A B C B B A B C
Väljund (0,0,A)
| A A | B C B B A B C
Väljund(1,1)
| A A B | C B B A B C
Väljund (0,0,B)
A | A B C | B B A B C
Väljund (0,0,C)
A A | B C B | B A B C
Väljund(2,1)
Teine osa liugaknast on vahemälu, mida otsida (look ahead puhvril pole ametlikku tõlget). Otsitav vahemälu on sõnastikule kõige lähemal oleva tihendamata osa pikkusest. LZ77 algoritm vastab selle märgi osa pikima stringile, mis on sama mis sõnastikul. Eelmist näidet võib pidada tuleviku puhvriks väärtusega 1.
Oletame, et sõnastiku pikkus on 5 ja otsitav vahemälu suurus on 3
| sõnastik | Vaata ette, puhver |
A | A B C B B | A B C |
Väljund(5,3)
Pikim keel, mis sobib, on ABC
Täielik tihendusprotsess:
Oletame, et sõnastiku pikkus on 5 ja otsitav vahemälu suurus on 3
| sõnastik | Vaata ette, puhver |
| A A B | C B B A B C
Väljund (0,0,A)
| A | A B C | B B A B C
Väljund(1,1)
| A A | B C B | B A B C
Väljund (0,0,B)
| A A B | C B B | A B C
Väljund (0,0,C)
| A A B C | B B A | B C
Väljund(2,1)
| A A B C B | B A B | C
Väljund(1,1)
A | A B C B B | A B C |
Väljund(5,3)
A A B C | B B A B C | 。。。 |
Sõnastikku ei ole vaja salvestada kompressori väljundfaili, sest dekompressiooniprogramm taastab sõnastiku, sobitades väljundühikud.
Dekompressiooniprotsess
Üks LZ77 algoritmi suurimaid eeliseid on see, et selle dekompressioon on väga kiire.
Kui esimene sobitav ühik on (0,0,A), siis on väljund A.
Teine sobivusühik on (1,1), mis kopeerib väljundstringi eelmise biti ja väljastab A, kui kopeerimise pikkus on 1.
。。。
Kui viimane sobiv ühik on (5,3), siis vaata tagasi 5 bitti koopia väljundstringis ja kui koopia pikkus on 3, siis väljund A, B, C.
LZ77 algoritmi tihendamise kõige ajamahukam osa on leida vahemälus kõige pikem sobiv tähemärk, mida otsida sõnastikust. Kui otsitav sõnaraamat ja vahemälu on liiga lühikesed, on vaste leidmise tõenäosus väike. Seetõttu on LZ4 muutnud sobitusalgoritmi LZ77 jaoks.
Esiteks on LZ4 algoritmi sõnastik räsi tabel. Sõnastiku võti on 4-baidine string, iga võti vastab ainult ühele pesale, ja pesa väärtus näitab selle stringi asukohta.
Vahemälust otsimise asemel loeb LZ4 sisendfailist korraga neli baiti ja otsib seejärel räsitabelis sobivat sloti, mis vastab stringile, mida edaspidi nimetatakse käesolevaks stringiks.
Kui oled jõudnud viimase 12 tähemärgini, pane need otse väljundfaili.
Kui pesas pole väärtust määratud, tähendab see, et neli baiti ilmuvad esimest korda, lisan need neli baiti ja positsiooni räsitabelisse ning jätkan otsingut.
Kui slotis on määramine, tähendab see, et oleme leidnud sobiva väärtuse.
Kui pesa väärtus pluss liuguri akna suurus < praeguse tähemärgi asukoht, siis sobituspositsioon ületab ploki suuruse ning programm uuendab hash-pesa väärtuse praeguse stringi asukohaks.
LZ4 kontrollib, kas on olnud räsi konflikt. Kui pesas olevad 4 baiti ei ole samad mis praegune string, peab tekkima räsi konflikt. Autori enda xxhash on samuti tuntud oma tõhususe poolest, kuid konfliktid on vältimatud. Konflikti korral uuendab programm ka räsi pesa väärtuse stringi praegusele asukohale
Lõpuks saame kinnitada, et sobitus on kehtiv, ning programm jätkab kontrollimist, kas järgnevad märgid sobivas stringis on samad. Lõpuks kopeeri kõik tegelased eelmise kehtiva sobituse lõpust selle sobiva sobituse algusesse tihendatud faili ja lisa selle sobiva sobituse järjestus.
Collet nimetab LZ4 poolt väljastatud sobitusühikuid jadadeks, mis moodustavad LZ4 tihendatud faili. Üksikasjad on järgmised:
Token on 1 bait pikk, kus esimesed 4 sõna on sõna otsene pikkus ja viimased 4 sõna sobituse pikkus. Nagu varem mainitud, kopeeritakse kõik märgid eelmise kehtiva sobituse lõpust kuni selle sobituse alguseni tihendatud faili, need tihendamata failid on sõnasõnalised ja nende pikkus on literaalne pikkus.
Sellele järgneb sõna otseses mõttes kõrvalekalle. Nagu LZ77-s, viitavad kõrvalekalle ja sobituspikkus praeguse stringi pikkusele selle sobitusest ning sobituspikkus viitab praeguse stringi sobituspikkusele sama stringiga sõnaraamatus. Dekompressioonis tuleb selle läbi minna, et leida kopeeritav keel ja kopeeritav pikkus. Kõrvalekalde suurus on fikseeritud.
Joonisel on literaalne pikkus+ ja sobituspikkus+ – kui täpne või sobituspikkus 4 sõna tokenis ei ole piisavad, siis need jätkavad vastavates positsioonides suurenemist. 4 sõna võib esindada 0-15 ja kui neid on rohkem, lisa üks bait ehk lisa 255 kuni bait on väiksem kui 255. Sobituspikkuses tähistab 0 4 baiti.
Viimased 12 baiti lõppevad sõna otseses mõttes, sest see on otse kopeeritud.
Vaatame koodi (python on abstraktsem)
Kokkuvõte Kõike seda öeldes pole ma siiani kokku võtnud, miks LZ4 on nii kiire. Võrdleme esmalt sõnastiku otsingut LZ77 ja LZ4 vahel. Natiivse LZ77 otsib sõnastikke, otsides suurimat vastet vahemälus ja sõnastikust. See on probleem suurima identse nööri leidmisel kahes stringis. Kui me ei kasuta dünaamilist programmeerimist, siis halvimal juhul peame arvestama ühe stringi kõiki alamstringe ja seejärel sobitama need teise stringiga. Kui ×kasutame dünaamilist programmeerimist, kasutame tabelit, et hoida dünaamika pikimat sobitust, mis võimaldab sobituse lõpule viia ainult O(m*n) puhul. Ja see on ainult paar otsinguvahemälu ja sõnaraamatut. Halvimal juhul, kui vasteid pole, peab LZ77 arvestama (kogu faili pikkust – otsitava vahemälu pikkust) paljude selliste sobitusprobleemide hulka. LZ4 kasutab tegelikult suuremat dünaamilist programmeerimist: see salvestab 4 baiti ja nende asukohad räsitabelisse ning seejärel sobitab iga kord uue 4 baiti andmeid, et näha, kas räsitabeli väärtused on kehtivad. Pärast kehtiva sobivusväärtuse leidmist, kui vaatad kahe vastavuse komplekti järelandmeid, leiad ka selle pikima vaste. Kuna iga võti LZ4 räsitabelis vastab ainult ühele pesale, vajab räsitabeli leidmine, liitmine ja muutmine vaid O(1). Kui pärast sobitamist leitakse rohkem vasteid, on vaja rohkem grupivõrdlusi, kuid kogu aja jooksul asendavad need võrdlused rohkem aega räsitabeli otsimiseks, nii et LZ4 algoritmi koguaeg on ainult O(n). Ma pean imetlema Colleti algoritmi ilu! Algoritmi veelgi kiiremaks muutmiseks seab Collet vaikimisi räsitabeli suuruseks 16k, mida soovitatakse mitte ületada 32k, et seda saaks panna peaaegu kõigi protsessorite (Intel) L1 vahemälu. Kõik teavad, et CPU L1 vahemälu kiirus ja mälu suhe on väga erinevad, seega pole üllatav, et LZ4 liigub kiiresti, rääkimata sellest, et LZ4 räsi tabelis kasutatav räsi võrrand on endiselt kiireim xxhash. Loomulikult on sellisel disainil ka puudusi. Mida väiksem on räsi tabel, seda vähem on võtmeid. See tähendab, et tekivad rohkem räsi konfliktid, mis on vältimatu. Ja rohkem räsi kokkupõrkeid tähendab vähem vasteid. Ja väiksem räsi tabel tähendab ka väiksemat libiseva akent, mis tähendab, et rohkem vasteid visatakse ära, kuna need on liiga kaugel. Vähem sobitusi tähendab väiksemat kompressioonisuhet, mistõttu LZ4-l on vähem silmatorkav tihendussuhe. Tulevikku vaadates: LZ4-l on lai valik rakendusvõimalusi. Nii nagu Silicon Valley VR-is kasutati keskmist välja, suudab LZ4 suurendada ribalaiuse kasutust, tuues vähem IO-sid, kuid väga madala latentsuse arvelt, tänu väga kiirele tihenduskiirusele. On ka väike oletus: kui on protsessor, millel on suurem vahemälu tasemel 1, kas LZ4 suudab kompressioonisuhet tõsta ilma kiirust ohverdamata?
Originaal:Hüperlingi sisselogimine on nähtav. |
Postitatud 03.01.2022 13:54:23
|
|
|
|
