Po zhliadnutí HBO drámy "Silicon Valley" ma vždy zaujímali kompresné algoritmy. Richard Hendricks a jeho stredný kompresný algoritmus v ňom sú samozrejme falošné, ale po dôkladnom googlení som zistil, že taký génius kompresného algoritmu existuje aj v reálnom živote.
Yann Collet vynašiel kompresný algoritmus LZ4 v roku 2011. Samozrejme, algoritmus LZ4 nie je taký úžasný ako middle out, ale je známy svojou neporaziteľnou rýchlosťou kompresie a rýchlejšou dekompresiou, keď je zaručená určitá rýchlosť kompresie.
Nebudem tu podrobne rozoberať hodnotenie jeho rýchlosti kompresie, ak máte záujem, môžete si prečítať tento porovnávací článok:Prihlásenie na hypertextový odkaz je viditeľné.
Priložená je aj github adresa LZ4:Prihlásenie na hypertextový odkaz je viditeľné.
Tento článok sa zameriava na vysvetlenie princípu kompresného algoritmu LZ4. Veľký boh predtým napísal vysvetlenie algoritmu LZ4:Prihlásenie na hypertextový odkaz je viditeľné.Ale keď som predtým študoval, mal som pocit, že tento článok nie je veľmi priateľský k začiatočníkom, tak som začal písať ďalší článok pre začiatočníkov ako som ja.
Ak to zhrniete do jednej vety, LZ4 je LZ77, ktorý uchováva slovník s hashovacou tabuľkou veľkosti 16k a zjednodušuje vyhľadávanie.
LZ4 je algoritmus bezstratovej kompresie, ktorý ponúka rýchlosť kompresie > 500 MB/s na jadro, ktorú je možné škálovať pomocou viacjadrových procesorov. Má mimoriadne rýchle dekodéry s rýchlosťou niekoľkých GB/s na jadro, často dosahujúc limity RAM na viacjadrových systémoch.
Rýchlosť je možné dynamicky nastavovať, pričom sa vyberá "akceleračný" faktor, ktorý vymení kompresný pomer za vyššiu rýchlosť. Na druhej strane je k dispozícii aj derivácia s vysokou kompresiou LZ4_HC na zvýšenie kompresie na úkor času CPU. Všetky verzie majú rovnakú rýchlosť dekompresie.
Čo je teda LZ77?
Kompresia a princíp LZ77
LZ77 je algoritmus, ktorý aplikuje slovník na kompresiu. Laicky povedané, ide o to, aby program mohol sledovať (pozrieť sa do slovníka), či sú aktuálne zobrazené dáta zdvojené s predchádzajúcim, a ak áno, uložíme vzdialenosť (offset) a dĺžku duplicitných polí na nahradenie duplicitných polí a komprimovanie dát.
referenciaPrihlásenie na hypertextový odkaz je viditeľné.
Pre reťazec písmen A A B C B B A B C, keď sa prečíta druhé A, program uloží (1,1) (1 číslica z predchádzajúceho, dĺžka 1), a podobne, keď sa prečíta druhé B, program uloží (2,1) (vzdialenosť 2, dĺžka 1).
Ak je však reťazec dlhší a program neustále zaznamenáva údaje do slovníka, vyhľadávanie duplicitných polí sa stáva extrémne časovo náročným, pretože v najhoršom prípade program prechádza celý slovník s každým novým prečítaným písmenom. LZ77 používa metódu posuvného okna na vyriešenie tohto problému.
Podobne ako východiskový bod TCP s posuvným oknom, posuvné okno môže zmenšiť oblasť cache, aby sa predišlo spracovaniu príliš veľkého množstva cacheovaných dát naraz. V LZ77 sa slovník nezväčšuje neustále, ale vyhadzuje prvé znaky pridané do slovníka, keď prekročia maximálnu veľkosť určenú slovníkom, aby sa zabezpečilo, že veľkosť slovníka zostane vždy na špecifikovanej maximálnej veľkosti.
Predpokladajme, že dĺžka slovníka je 3
| Slovník |
| A | A B C B B A B C
Výstup (0,0,A)
| A A | B C B B A B C
Výstup(1,1)
| A A B | C B B A B C
Výstup (0,0,B)
A | A B C | B B A B C
Výstup (0,0,C)
A A | B C B | B A B C
Výstup(2,1)
Druhou časťou posuvného okna je cache, ktorý sa má prehľadávať (Look Ahead buffer nemá oficiálny preklad). Cache, ktoré sa má prehľadávať, je nekomprimovaná časť dĺžky najbližšia k slovníku. Algoritmus LZ77 priradí najdlhší reťazec v tejto časti znaku, ktorý je rovnaký ako slovník. Predchádzajúci príklad možno považovať za vyrovnávaciu pamäť s výhľadom dopredu vo výške 1.
Predpokladajme, že dĺžka slovníka je 5 a veľkosť cache, ktorú chceme prehľadať, je 3
| Slovník | Pozri sa dopredu buffer |
A | A B C B B | A B C |
Výstup(5,3)
Najdlhší reťazec, ktorý sa zhoduje, je ABC
Kompletný proces kompresie:
Predpokladajme, že dĺžka slovníka je 5 a veľkosť cache, ktorú chceme prehľadať, je 3
| Slovník | Pozri sa dopredu buffer |
| A A B | C B B A B C
Výstup (0,0,A)
| A | A B C | B B A B C
Výstup(1,1)
| A A | B C B | B A B C
Výstup (0,0,B)
| A A B | C B B | A B C
Výstup (0,0,C)
| A A B C | B B A | B C
Výstup(2,1)
| A A B C B | B A B | C
Výstup(1,1)
A | A B C B B | A B C |
Výstup(5,3)
A A B C | B B A B C | 。。。 |
Nie je potrebné ukladať slovník do výstupného súboru kompresora, pretože dekompresný program obnoví slovník porovnaním výstupných jednotiek.
Proces dekompresie
Jednou z veľkých výhod algoritmu LZ77 je, že sa dekomprimuje veľmi rýchlo.
Ak je prvá jednotka zhody (0,0,A), potom výstup je A.
Druhá zodpovedajúca jednotka je (1,1), ktorá kopíruje predchádzajúci bit vo výstupnom reťazci a vydáva A, ak je dĺžka kopírovania 1.
。。。
Ak je posledná zodpovedajúca jednotka (5,3), pozrite sa späť na 5 bitov v kopírovacom výstupnom reťazci, a ak je dĺžka kopírovania 3, potom výstup A, B, C.
Najnáročnejšou časťou kompresie algoritmu LZ77 je nájsť najdlhší zhodný znak v cache, ktorý sa vyhľadáva v slovníku. Ak sú slovník a cache na vyhľadávanie príliš krátke, šanca nájsť zhodu je malá. Preto LZ4 zmenil algoritmus párovania pre LZ77.
Po prvé, slovník algoritmu LZ4 je hash tabuľka. Kľúč v slovníku je 4-bajtový reťazec, každý kľúč zodpovedá len jednému slotu a hodnota v slote je pozícia tohto reťazca.
Namiesto prehľadávania cache LZ4 číta naraz štyri bajty zo vstupného súboru a potom hľadá slot zodpovedajúci reťazcu v hashovacej tabuľke, ktorý sa ďalej označuje ako súčasný reťazec.
Ak ste dosiahli posledných 12 znakov, vložte ich priamo do výstupného súboru.
Ak v slote nie je priradená žiadna hodnota, znamená to, že štyri bajty sa objavia prvýkrát, pridáte tieto štyri bajty a pozície do hashovacej tabuľky a pokračujte vo vyhľadávaní.
Ak je v slote priradenie, znamená to, že sme našli zodpovedajúcu hodnotu.
Ak hodnota v slote plus veľkosť okna posuvníka < pozíciou aktuálneho znaku, pozícia zhody prevyšuje veľkosť bloku a program aktualizuje hodnotu v hashovacom slote na pozíciu aktuálneho reťazca.
LZ4 skontroluje, či nedošlo ku konfliktu hashov. Ak 4 bajty v slote nie sú rovnaké ako aktuálny reťazec, musí dôjsť ku konfliktu hashov. Autorov vlastný xxhash je tiež známy svojou efektivitou, no konflikty sú nevyhnutné. V prípade konfliktu program tiež aktualizuje hodnotu v hashovacom slote na aktuálnu pozíciu reťazca
Nakoniec môžeme potvrdiť, že zhoda je platná, a program bude ďalej zisťovať, či sú nasledujúce znaky v zodpovedajúcom reťazci rovnaké. Nakoniec skopírujte všetky znaky z konca predchádzajúcej platnej zhody na začiatok tejto platnej zhody do komprimovaného súboru a pridajte zodpovedajúcu sekvenciu tejto platnej zhody.
Collet nazýva zodpovedajúce jednotky výstupom sekvencií LZ4 a tvoria komprimovaný súbor LZ4. Podrobnosti sú nasledovné:
Token je dlhý 1 bajt, pričom prvé 4 slová predstavujú doslovnú dĺžku a posledné 4 slová dĺžku zhody. Ako už bolo spomenuté, všetky znaky od konca predchádzajúcej platnej zhody po začiatok tejto platnej zhody budú skopírované do komprimovaného súboru, tieto nekomprimované súbory sú doslovné a ich dĺžka je doslovná dĺžka.
Doslova nasleduje odchýlka. Rovnako ako v LZ77, odchýlka a dĺžka zhody označujú dĺžku aktuálneho reťazca od jeho zhody a dĺžka zhody označuje dĺžku zhody prítomného reťazca s rovnakým reťazcom v slovníku. Pri dekompresii je to prejsť ním, aby ste našli reťazec na kopírovanie a dĺžku na kopírovanie. Veľkosť odchýlky je pevne stanovená.
Na obrázku literálna dĺžka+ a dĺžka zhody+ sú ak literál alebo dĺžka zhody 4 slov v žetóne nestačí, budú sa naďalej zvyšovať na príslušných pozíciách. 4 slová môžu predstavovať 0-15, a ak ich je viac, pridajte jeden bajt, teda 255 k veľkosti, kým bajt nebude menší ako 255. V zodpovedajúcej dĺžke 0 predstavuje 4 bajty.
Posledných 12 bajtov končí doslova preto, že bol priamo skopírovaný.
Pozrime sa na kód (python je abstraktnejší)
Zhrnutie Napriek všetkému som ešte nezhrnul, prečo je LZ4 taký rýchly. Najprv porovnajme vyhľadávanie v slovníku medzi LZ77 a LZ4. Natívny LZ77 vyhľadáva slovníky tak, že hľadá najväčšiu zhodu v cache a v slovníku. Toto je problém nájsť najväčší identický reťazec v dvoch reťazcoch. Ak nepoužijeme dynamické programovanie, v najhoršom prípade musíme zvážiť všetky podreťazce jedného reťazca a potom ich porovnať s iným reťazcom. Ak ×použijeme dynamické programovanie, použijeme tabuľku na uchovávanie najdlhšej zhody v dynamike, čo nám umožní dokončiť zhodu iba v prípade O(m*n). A to je len pre dvojicu vyhľadávacích cache a slovníkov. V najhoršom prípade, ak nie sú zhody, LZ77 bude musieť počítať (dĺžku celého súboru – dĺžku cache, ktorá sa má prehľadávať) ako veľa takýchto problémov s párovaním. LZ4 v skutočnosti používa vyššiu úroveň dynamického programovania: ukladá 4 bajty a ich pozície do hashovacej tabuľky a potom zakaždým porovnáva nové 4 bajty dát, aby sa overilo, či sú hodnoty v hash tabuľke platné. Po nájdení platnej hodnoty zhody, ak sa pozriete na následné dáta oboch sád zhodných hodnôt, môžete nájsť aj jej najdlhšiu zhodu. Keďže každý kľúč v LZ4 hash tabuľke zodpovedá iba jednému slotu, práca na hľadaní, pridávaní a úprave hash tabuľky vyžaduje len O(1). Ak sa po párovaní nájde viac zhôd, je potrebné viac skupinových porovnaní, ale v celkovom čase tieto porovnania nahradia viac času na vyhľadanie hash tabuľky, takže celkový čas LZ4 algoritmu je len O(n). Musím obdivovať krásu Colletovho algoritmu! Aby bol algoritmus ešte rýchlejší, Collet nastaví predvolenú veľkosť hash tabuľky na 16k, čo sa odporúča neprekročiť 32k, aby sa dala uložiť do L1 cache takmer všetkých CPU (Intel). Každý vie, že rýchlosť a pomer pamäte v L1 cache CPU sú veľmi odlišné, takže nie je prekvapením, že LZ4 letí rýchlo, nehovoriac o tom, že hash rovnica použitá v LZ4 hash tabuľke je stále najrýchlejšia xxhash. Samozrejme, takýto dizajn má aj svoje nevýhody. Čím menšia je hash tabuľka, tým menej kľúčov má. To znamená, že vznikne viac konfliktov hashov, čo je nevyhnutné. A viac hašovacích kolízií znamená menej zhôd. A menšia hashovacia tabuľka znamená aj menšie posuvné okno, čo znamená, že viac zhôd sa zahodí, pretože sú príliš ďaleko. Menej zápaliek znamená menší kompresný pomer, preto má LZ4 menej výrazný kompresný pomer. Looking Ahead LZ4 ponúka širokú škálu aplikačných scenárov. Rovnako ako sa middle-out používal vo VR v Silicon Valley, LZ4 môže zvýšiť využitie šírky pásma tým, že prinesie menej IO za cenu veľmi nízkej latencie vďaka veľmi rýchlej kompresii. Existuje aj malá špekulácia, ak je CPU s väčšou cache na úrovni 1, môže LZ4 zvýšiť kompresný pomer bez kompromisov v rýchlosti?
Originál:Prihlásenie na hypertextový odkaz je viditeľné. |
Zverejnené 3. 1. 2022 13:54:23
|
|
|
|
