Po zhlédnutí seriálu HBO "Silicon Valley" mě vždy zajímaly kompresní algoritmy. Richard Hendricks a jeho algoritmus pro střední kompresi jsou samozřejmě falešní, ale po důkladném googlení jsem zjistil, že takový génius kompresního algoritmu existuje i v reálném životě.
Yann Collet vynalezl kompresní algoritmus LZ4 v roce 2011. Samozřejmě, algoritmus LZ4 není tak úžasný jako middle out, ale je známý svou neporazitelnou rychlostí komprese a rychlejší dekompresí, pokud je zaručena určitá rychlost komprese.
Nebudu zde podrobně rozebírat hodnocení rychlosti komprese, pokud vás to zajímá, můžete si přečíst tento srovnávací článek:Přihlášení k hypertextovému odkazu je viditelné.
Přiložena je také github adresa LZ4:Přihlášení k hypertextovému odkazu je viditelné.
Tento článek se zaměřuje na vysvětlení principu kompresního algoritmu LZ4. Velký bůh napsal vysvětlení algoritmu LZ4 dříve:Přihlášení k hypertextovému odkazu je viditelné.Ale když jsem se dříve učil, měl jsem pocit, že tento článek není příliš přátelský pro začátečníky, a tak jsem začal psát další článek pro začátečníky jako jsem já.
Pokud to shrnete do jedné věty, LZ4 je LZ77, který uchovává slovník s hashovací tabulkou o velikosti 16k a zjednodušuje vyhledávání.
LZ4 je bezztrátový kompresní algoritmus, který nabízí rychlost komprese > 500 MB/s na jádro, což lze škálovat pomocí vícejádrových CPU. Má extrémně rychlé dekodéry s rychlostí několika GB/s na jádro, často dosahující limitů RAM u vícejádrových systémů.
Rychlost lze dynamicky upravovat, přičemž se vybírá faktor "akcelerace", který vyměňuje kompresní poměr za vyšší rychlost. Na druhou stranu je také k dispozici vysoce kompresní derivační LZ4_HC pro zvýšení komprese na úkor času CPU. Všechny verze mají stejnou rychlost dekomprese.
Co je tedy LZ77?
Komprese a princip LZ77
LZ77 je algoritmus, který používá slovník pro kompresi. Laicky řečeno, jde o to, aby program sledoval (podíval se do slovníku), zda jsou aktuálně viděná data duplikována s předchozími, a pokud ano, uložíme vzdálenost (offset) a délku duplicitních polí, abychom nahradili duplicitní pole a data zkomprimovali.
odkazPřihlášení k hypertextovému odkazu je viditelné.
Pro řetězec písmen A A B C B B A B C, když je přečteno druhé A, program uloží (1,1) (1 číslici z předchozí, délka 1), a podobně při přečtení druhého B program uloží (2,1) (vzdálenost 2, délka 1).
Pokud je však řetězec delší a program data neustále zapisuje do slovníku, hledání duplicitních polí se stává extrémně časově náročným, protože v nejhorším případě program projde celý slovník s každým novým přečteným písmenem. LZ77 používá k řešení tohoto problému metodu posuvného okna.
Podobně jako výchozí bod TCP s posuvným oknem může posuvné okno zmenšit oblast cache, aby se zabránilo současnému zpracování příliš velkého množství cacheovaných dat. V LZ77 se slovník nezvyšuje neustále, ale vyřazuje první znaky přidané do slovníku, pokud překročí maximální velikost stanovenou slovníkem, aby byla velikost slovníku vždy zachována na stanovené maximální velikosti.
Předpokládejme, že délka slovníku 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 částí posuvného okna je cache, kterou je třeba prohledat (buffer look ahead nemá oficiální překlad). Cache, která se má prohledávat, je nekomprimovaná část délky nejblíže slovníku. Algoritmus LZ77 přiřadí nejdelší řetězec v této části znaku, který je stejný jako ve slovníku. Předchozí příklad lze považovat za buffer pro pohled dopředu o hodnotě 1.
Předpokládejme, že délka slovníku je 5 a velikost cache, kterou chceme prohledávat, je 3
| Slovník | Vypadat dopředu buffer |
A | A B C B B | A B C |
Výstup(5,3)
Nejdelší řetězec, který odpovídá, je ABC
Kompletní proces komprese:
Předpokládejme, že délka slovníku je 5 a velikost cache, kterou chceme prohledávat, je 3
| Slovník | Vypadat dopředu 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 | 。。。 |
Není třeba ukládat slovník do výstupního souboru kompresoru, protože dekompresní program slovník obnoví porovnáním výstupních jednotek.
Proces dekomprese
Jednou z velkých výhod algoritmu LZ77 je, že se velmi rychle dekomprimuje.
Pokud je první jednotka shody (0,0,A), pak výstup je A.
Druhá jednotka pro shodu je (1,1), která kopíruje předchozí bit ve výstupním řetězci a vydává A, pokud je délka kopie 1.
。。。
Pokud je poslední shodná jednotka (5,3), podívejte se zpět na 5 bitů v výstupním řetězci kopírování, a pokud je délka kopie 3, pak výstup A, B, C.
Nejčasovější částí komprese algoritmu LZ77 je nalezení nejdelšího shodného znaku v cache, který se hledá ve slovníku. Pokud je slovník a cache k vyhledávání příliš krátké, šance najít shodu jsou malé. Proto LZ4 změnil algoritmus párování pro LZ77.
Za prvé, slovník algoritmu LZ4 je hashovací tabulka. Klíč ve slovníku je 4bajtový řetězec, každý klíč odpovídá pouze jednomu slotu a hodnota ve slotu je pozice tohoto řetězce.
Místo vyhledávání v cache LZ4 čte vždy čtyři bajty ze vstupního souboru a poté hledá slot odpovídající řetězci v hashovací tabulce, který je dále označován jako současný řetězec.
Pokud jste se dostali na posledních 12 znaků, vložte je přímo do výstupního souboru.
Pokud ve slotu není přiřazena žádná hodnota, znamená to, že se čtyři bajty objeví poprvé, přičte tyto čtyři bajty a pozice do hashovací tabulky a pokračujte v hledání.
Pokud je ve slotu přiřazeno, znamená to, že jsme našli shodnou hodnotu.
Pokud hodnota ve slotu plus velikost okna posuvníku < pozice aktuálního znaku, pak pozice shody překračuje velikost bloku a program aktualizuje hodnotu v hashovacím slotu na pozici aktuálního řetězce.
LZ4 zkontroluje, zda došlo ke konfliktu hashů. Pokud 4 bajty ve slotu nejsou totožné s aktuálním řetězcem, musí dojít ke konfliktu hashů. Autorův vlastní xxhash je také známý svou efektivitou, ale konflikty jsou nevyhnutelné. V případě konfliktu program také aktualizuje hodnotu v hashovacím slotu na aktuální pozici řetězce
Nakonec můžeme potvrdit, že shoda je platná, a program bude dál sledovat, zda jsou následující znaky v odpovídajícím řetězci stejné. Nakonec zkopírujte všechny znaky z konce předchozí platné shody na začátek této platné shody do komprimovaného souboru a přidejte odpovídající sekvenci této platné shody.
Collet volá odpovídající jednotky výstupu sekvencí LZ4 a tvoří komprimovaný soubor LZ4. Podrobnosti jsou následující:
Token je dlouhý 1 bajt, přičemž první 4 slova představují délku slova a poslední 4 slova délku shody. Jak již bylo zmíněno, všechny znaky od konce předchozí platné shody až po začátek této platné shody budou zkopírovány do komprimovaného souboru, tyto nekomprimované soubory jsou doslovné a jejich délka je doslovná.
Doslova následovaná odchylkou. Stejně jako v LZ77 označují odchylka a délka shody délku aktuálního řetězce od jeho shody a délka shody označuje délku délky shody současného řetězce se stejným řetězcem ve slovníku. V dekompresi je třeba projít jimi, abyste našli řetězec k zkopírování a délku k kopírování. Velikost odchylky je pevně stanovená.
Na obrázku jsou literal length+ a match length+ (délka shody) – pokud literál nebo délka shody (4 slova) v tokenu nestačí, budou se dále zvyšovat na odpovídajících pozicích. 4 slova mohou představovat 0–15, a pokud jich je více, přidejte jeden bajt, tedy 255 k velikosti, dokud bajt nebude menší než 255. V odpovídající délce 0 představuje 4 bajty.
Posledních 12 bajtů končí doslova proto, že byl přímo zkopírován.
Podívejme se na kód (python je abstraktnější)
Shrnutí I když jsem to všechno řekl, stále jsem neshrnoval, proč je LZ4 tak rychlý. Nejprve porovnejme slovníkové vyhledávání mezi LZ77 a LZ4. Nativní LZ77 vyhledává slovníky podle největší shody v cache, kterou má být vyhledána, a ve slovníku. Jde o problém nalezení největšího stejného řetězce ve dvou řetězcích. Pokud nepoužijeme dynamické programování, pak v nejhorším případě musíme zvážit všechny podřetězce jednoho řetězce a pak je porovnat s jiným řetězcem. Pokud ×použijeme dynamické programování, použijeme tabulku, která uchová nejdelší shodu v dynamice, což nám umožní dokončit shodu pouze v případě O(m*n). A to jen pro dvojici vyhledávacích cache a slovníků. V nejhorším případě, pokud neexistují shody, bude muset LZ77 počítat (délku celého souboru – délku cache, kterou máme prohledávat) jako mnoho takových problémů s párováním. LZ4 ve skutečnosti používá vyšší úroveň dynamického programování: ukládá 4 bajty a jejich pozice do hashovací tabulky a pokaždé porovnává nové 4 bajty dat, aby ověřil, zda jsou hodnoty v hashovací tabulce platné. Po nalezení platné hodnoty shody, pokud se podíváte na následná data obou sad shodných hodnot, můžete také najít její nejdelší shodu. Protože každý klíč v LZ4 hashovací tabulce odpovídá pouze jednomu slotu, práce na hledání, přidávání a úpravě hashovací tabulky vyžaduje pouze O(1). Pokud se po párování najdou další shody, je potřeba více skupinových porovnání, ale v celkovém čase tato porovnání nahradí více času na vyhledání hashovací tabulky, takže celkový čas algoritmu LZ4 je pouze O(n). Musím obdivovat krásu Colletova algoritmu! Aby byl algoritmus ještě rychlejší, Collet nastaví výchozí velikost hashovací tabulky na 16k, což se doporučuje nepřesáhnout 32k, aby mohla být uložena do L1 cache téměř všech CPU (Intel). Všichni vědí, že poměr rychlosti a paměťové hodnoty CPU L1 cache je velmi odlišný, takže není překvapením, že LZ4 letí rychle, nemluvě o tom, že hashovací rovnice použitá v hashovací tabulce LZ4 je stále nejrychlejší xxhash. Samozřejmě, takový design má své nevýhody. Čím menší je hashovací tabulka, tím méně klíčů má. To znamená, že dojde k dalším konfliktům hashů, což je nevyhnutelné. A více kolizí hash znamená méně shod. A menší hashovací tabulka znamená také menší posuvné okno, což znamená, že více shod bude vyřazeno, protože jsou příliš daleko. Méně zápalek znamená menší kompresní poměr, což je důvod, proč má LZ4 méně výrazný kompresní poměr. Looking Ahead LZ4 nabízí širokou škálu scénářů použití. Stejně jako byl ve VR v Silicon Valley použit middleout, LZ4 může zvýšit využití šířky pásma tím, že přinese méně IO za cenu velmi nízké latence díky velmi rychlé kompresi. Existuje také malá spekulace, pokud je CPU s větší cache na úrovni 1, může LZ4 zvýšit kompresní poměr bez kompromisu na rychlosti?
Původní:Přihlášení k hypertextovému odkazu je viditelné. |
Zveřejněno 03.01.2022 13:54:23
|
|
|
|
