Miután megnéztem az HBO "Silicon Valley" című drámáját, mindig is érdekelt a tömörítési algoritmusok. Richard Hendricks és a középső kizáró tömörítési algoritmusa természetesen hamis, de miután rákerestem a Google-re, rájöttem, hogy létezik ilyen tömörítési algoritmus zseniális a valóságban.
Yann Collet 2011-ben találta fel az LZ4 tömörítési algoritmust. Természetesen az LZ4 algoritmus nem olyan fantasztikus a középső ki, de ismert a legyőzhetetlen tömörítési sebességéről és gyorsabb dekompressziós sebességéről, amikor bizonyos tömörítési ráta garantált.
Nem részletezem a tömörítési sebesség értékelését, ha érdekel, elolvashatod ezt az összehasonlító cikket:A hiperlink bejelentkezés látható.
Csatolva van továbbá az LZ4 github címe:A hiperlink bejelentkezés látható.
Ez a cikk az LZ4 tömörítési algoritmus elvének magyarázatára fókuszál. Egy nagy isten korábban írt magyarázatot az LZ4 algoritmusról:A hiperlink bejelentkezés látható.De amikor korábban tanultam, úgy éreztem, hogy ez a cikk nem túl barátságos a kezdőknek, ezért indítottam egy új cikket az olyan kezdőknek, mint én.
Ha egy mondatban összefoglaljuk, az LZ4 egy LZ77, amely egy szótárt tárol egy 16k méretű hash táblával, és leegyszerűsíti a lekérést.
Az LZ4 egy veszteségmentes tömörítési algoritmus, amely magonként > 500 MB/s tömörítési sebességet kínál, amelyet többmagos CPU-kkal is skálázható. Rendkívül gyors dekóderekkel rendelkezik, amelyek több GB/s sebességgel magonként, gyakran elérik a RAM sebességhatárokat többmagos rendszereken.
A sebesség dinamikusan állítható, kiválasztva egy "gyorsulási" tényezőt, amely a kompressziói arányt cseréli a nagyobb sebességre. Másrészt egy magas kompressziós derivált LZ4_HC is elérhető, amely növeli a tömörítést a CPU idő rovására. Minden verziónak ugyanaz a dekompressziós sebessége van.
Szóval mi az az LZ77?
LZ77 tömörítés és elv
Az LZ77 egy olyan algoritmus, amely tömörítésre szótárt alkalmaz. Egyszerű kifejezéssel szólva, hogy a program megfigyelje (nézze meg a szótárt), hogy a jelenleg látható adatok duplikálódnak-e az előzővel, és ha igen, akkor elmentjük a távolságot (eltolódást) és a duplikált mezők hosszát, hogy lecseréljük a duplikált mezőket és tömörítsük az adatokat.
utalásA hiperlink bejelentkezés látható.
Egy betűsorozat esetén, ahol A B C C B B B A B C, amikor a második A betűt olvassuk, a program elmenti (1,1) (1 számjegyet az előzőből, hossz 1), és hasonlóképpen, amikor a második B-t olvassuk, a program (2,1) (távolság 2, hossz 1) ment.
De ha a sorozat hosszabb, és a program folyamatosan rögzíti az adatokat a szótárba, akkor a duplikált mezők keresése rendkívül időigényessé válik, mert a legrosszabb esetben a program minden új betű olvasásával végigfutja az egész szótárt. Az LZ77 csúszóablak módszerrel működik ennek a problémának a megoldására.
Hasonlóan a TCP kiindulópontjához, a csúszóablak is csökkentheti a gyorsítótár területét, hogy elkerülje a túlzott gyorsítótár adatfeldolgozását egyszerre. Az LZ77-ben a szótár nem folyamatosan nő, hanem akkor kidobja az első karaktereket, amelyeket a szótár megjelölt, ha az meghaladja a szótár által megadott maximális méretet, hogy a szótár mérete mindig a megadott maximális méreten maradjon.
Tegyük fel, hogy a szótár hossza 3
| szótár |
| A | A B C B B A B C
Kimenet (0,0,A)
| A A | B C B B A B C
Kimenet(1,1)
| A A B | C B B A B C
Kimenet (0,0,B)
A | A B C | B B A B C
Kimenet (0,0,C)
A A | B C B | B A B C
Kimenet(2,1)
A csúszóablak másik része a keresendő gyorsítótár (a look ahead puffernek nincs hivatalos fordítása). A keresendő gyorsítótár a szótárhoz legközelebbi tömörítetlen hossz része. Az LZ77 algoritmus egyezik a karakter ezen részének leghosszabb stringjével, amely megegyezik a szótárral. Az előző példa tekinthető előretekintő pufferként 1-re.
Tegyük fel, hogy a szótár hossza 5, és a keresendő cache mérete 3
| szótár | Nézz előre buffer |
A | A B C B B B | A B C |
Kimenet(5,3)
A leghosszabb vonós, ami egyezik, az ABC
Teljes tömörítési folyamat:
Tegyük fel, hogy a szótár hossza 5, és a keresendő cache mérete 3
| szótár | Nézz előre buffer |
| A A B | C B B A B C
Kimenet (0,0,A)
| A | A B C | B B A B C
Kimenet(1,1)
| A A | B C B | B A B C
Kimenet (0,0,B)
| A A B | C B B | A B C
Kimenet (0,0,C)
| A A B C | B B A | B C
Kimenet(2,1)
| A A B C B | B A B | C
Kimenet(1,1)
A | A B C B B B | A B C |
Kimenet(5,3)
A A B C | B B A B C | 。。。 |
Nem szükséges a szótárt a kompresszor kimeneti fájljába menteni, mert a dekompresszió program a kimeneti egységek egyeztetésével állítja vissza a szótárt.
Dekompressziós folyamat
Az LZ77 algoritmus egyik nagy előnye, hogy nagyon gyorsan lekompressziós.
Ha az első párosító egység (0,0,A), akkor A kimenet.
A második párosító egység a (1,1), amely lemásolja a kimeneti lánc előző bitjét, és A kiad, ha a másolás hossza 1.
。。。
Ha az utolsó egyező egység (5,3), akkor nézz vissza 5 bitet a másolási kimeneti láncon, és ha a másolás hossza 3, akkor A, B, C kimenetel.
Az LZ77 algoritmus tömörítésének legidőigényesebb része az, hogy megtaláljuk a gyorsítótárban a leghosszabb egyező karaktert, amit a szótárban kell keresni. Ha a szótár és a keresett gyorsítótár túl rövid, az esélye a találatot kicsi. Ezért az LZ4 megváltoztatta az LZ77 párosítási algoritmusát.
Először is, az LZ4 algoritmus szótára egy hash tábla. A szótárban a kulcs egy 4 bájtos string, minden kulcs csak egy slotnak felel meg, és a slotban lévő érték ennek a sornak a pozícióját mutatja.
Ahelyett, hogy a gyorsítótárban keresnénk, az LZ4 egyszerre négy bájtot olvas a bemeneti fájlból, majd keresi a hash táblában a stringhez tartozó helyet, amelyet ezutáni jelenlegi stringként említenek.
Ha elérted az utolsó 12 karaktert, tedd őket közvetlenül a kimeneti fájlba.
Ha nincs érték a slotban, az azt jelenti, hogy a négy bájt először jelenik meg, hozzáadja ezeket a négy bájtot és pozíciót a hash táblához, majd folytatja a keresést.
Ha van egy kiosztás a slotban, az azt jelenti, hogy találtunk egy egyező értéket.
Ha a slot értéke plusz a csúszka ablak mérete < a jelenlegi karakter pozíciója, akkor a párosítás pozíciója meghaladja a blokk méretét, és a program frissíti a hash slot értékét az aktuális string pozíciójára.
Az LZ4 ellenőrzi, hogy volt-e hash ütközés. Ha a slot 4 bájtja nem egyezik meg a jelenlegi stringmel, akkor hash ütközés kell, hogy legyen. A szerző saját xxhashje is híres hatékonyságáról, de a konfliktusok elkerülhetetlenek. Ellentmondás esetén a program frissíti a hash slot értékét a lánc aktuális pozíciójára
Végül megerősíthetjük, hogy az egyezés érvényes, és a program továbbra is ellenőrizni fogja, hogy a következő karakterek ugyanazok-e a megfelelő láncsorban. Végül másoljuk le az előző érvényes egyezés végéről az érvényes egyezés elejéig az összes karaktert a tömörített fájlba, és hozzáadjuk ennek az érvényes egyezésnek a párosítási sorozatát.
Collet az LZ4 által kiadott párosítási egységeket szekvenciáknak nevezi, és ezek alkotják az LZ4 tömörített fájlt. A részletek a következők:
A token 1 bájt hosszú, az első 4 szó a szó szerinti hosszúság, az utolsó 4 szó pedig a párosítás hossza. Ahogy korábban említettük, az előző érvényes egyezés végétől az érvényes egyezés kezdetéig terjedő összes karaktert egy tömörített fájlba másolnak, ezek a tömörítetlen fájlok literálisak, és hosszuk literális hosszúság.
Szó szerint ezt követi eltérés. Ahogy az LZ77-ben, a deviáció és a párosítás hossza a jelenlegi lánc egyezéséből való hosszát jelöli, míg a egyezési hossz a jelenlegi húr egyezési hosszának hosszát jelenti ugyanahhoz a lánchoz a szótárban. A dekompresszióban átmenni rajta, hogy megtaláld a másolandó húrt és a másolandó hosszúságot. A deviáció nagysága fix.
Az ábrán a literális hosszúság+ és a match length+ így szerepel, ha a jel literális vagy egyezési hossza 4 szó nem elegendő, akkor a megfelelő pozíciókban tovább nőnek. 4 szó képviselheti a 0-15 közötti különbségeket, és ha több van bíró, adj hozzá egy bájtot, vagyis adjunk hozzá 255-öt, amíg a bájt kevesebb nem lesz, mint 255. A párosítási hosszban 0 4 bájtot jelent.
Az utolsó 12 bájt szó szerint azért ér véget, mert közvetlenül lemásolták.
Nézzük meg a kódot (a python absztraktabb)
Összefoglaló Mindezek ellenére még mindig nem tudtam összefoglalni, miért olyan gyors az LZ4. Először hasonlítsuk össze a szótárkeresést az LZ77 és az LZ4 között. A natív LZ77 szótárokat keres, ha a legnagyobb egyezést keresi a gyorsítótárban és a szótárban. Ez a legnagyobb azonos húr megtalálásának problémája két húrban. Ha nem használunk dinamikus programozást, akkor legrosszabb esetben az egyik string összes alhúrját figyelembe kell vennünk, majd egy másik stringben kell összeilleszteni őket. Ha ×dinamikus programozást használunk, akkor egy táblázatot használunk a dinamika leghosszabb egyeztetésére, ami csak O(m*n) esetén teszi lehetővé az egyeztetés befejezését. És ez csak egy pár kereső cache-re és szótárra vonatkozik. Legrosszabb esetben, ha nincs egyezés, akkor az LZ77-nek (az egész fájl hosszát – a keresendő gyorsítótár hosszát) kell számosítania az ilyen párosítási problémáknak. Az LZ4 valójában nagyobb szintű dinamikus programozást használ: 4 bájtot és azok pozícióit tárol egy hash táblában, majd minden alkalommal egy új 4 bájtos adatot párosít, hogy megnézze, érvényesek-e a hash tábla értékei. Miután megtaláljuk az érvényes egyezési értéket, ha megnézzük a két egyezési értékkészlet követő adatait, megtalálhatjuk a leghosszabb egyezést is. Mivel az LZ4 hash tábla minden kulcsa csak 1 slotnak felel meg, a hash tábla megtalálása, hozzáadása és módosítása csak O(1) szükséges. Ha több egyezést találnak a párosítás után, több csoportos összehasonlításra van szükség, de az összesített idő alatt ezek az összehasonlítások több időt váltanak fel a hash tábla keresésére, így az LZ4 algoritmus teljes ideje csak O(n). Csodálnom kell Collet algoritmusának szépségét! Az algoritmus még gyorsabb javítása érdekében a Collet az alapértelmezett hash tábla méretét 16k-ra állítja, amelyet nem ajánlanak meghaladni 32k-t, hogy szinte minden CPU (Intel) L1 gyorsítótárába be lehessen helyezni. Mindenki tudja, hogy a CPU L1 gyorsítótár sebessége és memóriaaránya nagyon eltérő, így nem meglepő, hogy az LZ4 gyorsan halad, nem beszélve arról, hogy az LZ4 hash táblázatában használt hash egyenlet még mindig a leggyorsabb xxhash. Természetesen egy ilyen dizájntának megvannak a hátrányai. Minél kisebb a hash table, annál kevesebb kulcsa van. Ez azt jelenti, hogy több hash konfliktus fog kialakulni, ami elkerülhetetlen. És több hash ütközés kevesebb egyezést jelent. És egy kisebb hash tábla kisebb csúszóablakot is jelent, ami azt jelenti, hogy több egyezést dobnak el, mert túl messze vannak. Kevesebb egyezés kisebb tömörítési arányt jelent, ezért az LZ4 kevésbé feltűnő a kompressziós arány. Előre nézve az LZ4 széles körű alkalmazási helyzeteket kínál. Ahogyan a Szilícium-völgyben a VR-ben is a middle out funkciót használták, az LZ4 is növelheti a sávszélesség-használatot azáltal, hogy kevesebb IO-t hoz, ami nagyon alacsony késleltetés árán a nagyon gyors tömörítési sebessége miatt. Van egy kis feltételezés is: ha van egy CPU nagyobb gyorsítótárral 1. szinten, akkor az LZ4 növelheti-e a tömörítési arányt anélkül, hogy a sebességet rombolná?
Eredeti:A hiperlink bejelentkezés látható. |
Közzétéve 2022. 01. 03. 13:54:23
|
|
|
|
