LZW

Az LZW (Lempel-Ziv-Welch) egy veszteségmentes tömörítési algoritmus. Az informatikában széles körben használt eljárást Terry Welch publikálta 1984-ben az Abraham Lempel és Jacob Ziv által 1978-ban közzétett LZ78 algoritmus továbbfejlesztéseként.Terry Welch, "A Technique for High-Performance Data Compression", IEEE Computer, June 1984, p. 8–19.

Az algoritmus A tömörítés alapja, hogy a kódoló csak egy szótárbeli indexet küld át. A szótár dinamikusan bővül, kiinduló állapotban az összes egybetűs szimbólumot tartalmazza. A kódolás elve igen egyszerű: az aktuális pozíciótól kezdve addig kell a szimbólumokat kiolvasni, amíg a sorozat szerepel a szótárban. Ezután elküldjük ezen sorozat indexét, a szótárba felvesszük kiegészítve a következő szimbólummal, és az algoritmust ettől a szimbólumtól folytatjuk.

A Welch 1984-es dolgozatában leírt eset 8 bites adatok sorozatát kódolja fix 12 bites kóddá. A 0 és 255 közti kódok az illeszkedő 8 bites karaktert írják le, míg a 256-4095 kódok az adatok a kódolás közben fellelt sorozatok szótárát hozzák létre. A kódolás minden állomásánál az input bájtokat egy sorozatba gyűjtik, egészen addig, ameddig a következő karakter olyan kódot érne el, mely nincs a szótárban. A sorozat kódját (a karakter nélkül) elküldik és a szótárba egy új kódot adnak (a karakterrel).

Az ötletet hamar felhasználták más helyzetekben. Például egy színtáblázat alapú képnél a természetes karakterábécé beállítható a színindexeknek, mivel az 1980-as években gyakran kevés (16) színt használtak. Egy ilyen csekély ábécére a teljes 12 bites kódok alacsony tömörítési rátát értek volna el, ha a kép nem volt nagy, tehát bevezették a változó bitszélességű kódokat: a kódok alapból 1 bittel hosszabbak a kódolt szimbólumoknál és amint egy kódméretet felhasználnak, ez tovább nő egy meghatározott maximumig (általában 12 bit).

A későbbi finomítások tartalmaznak egy kódot arra, ha a kódtábla "felszabadítandó" ("törlőkód", ez a jel általában az ábécé értékei után az első jel) és egy kódvéget jelölő jelet ("stop kód", ez általában az előző jelnél eggyel nagyobb). A törlőkód lehetővé teszi a táblázatnak az újrainicializálódását, amikor megtelik, amely lehetővé teszi a kódolásnak az adatban levő változó mintázatokhoz való alkalmazódást. Az intelligens kódolók figyelhetik a tömörítési hatékonyságot és törölhetik a táblázatot vagy egy részét,Lempel-Ziv-Welch (LZW) Algorithm ha a meglevő nem illeszkedik jól a bemenethez.

Mivel a kódokat az adat által meghatározott módon adják hozzá, a dekódoló utánozza a táblázat felépítését, mivel látja az eredményképp kijövő kódokat. Létfontosságú, hogy a kódoló és a dekódoló megegyezzen az LZW használati módjában: az ábécé mérete, a kód maximális szélessége, változó vagy fix bitszélességű-e a kódolás, az eredeti kódméret, a törlőkódok használata vagy kihagyása (és ha vannak, akkor az értékük). A legtöbb LZW-t használó formátum mindezen adatokat beleépíti a formátumspecifikációba vagy pedig a tömörítés fejrészében külön helyet hagy neki.

Kódolás A kódolási algoritmus egy magas szintű megközelítése A szótárt inicializáljuk az összes 1 hosszú sztringgel Kikeressük a szótárból a leghosszabb, jelenlegi inputtal összeillő W sztringet W szótárindexét kiadjuk, és W-t eltávolítjuk az inputról A W szó és az input következő szimbólumának konkatenációját felvesszük a szótárba A 2. lépéstől ismételjük

A szótár inicializálása úgy történik meg, hogy tartalmazzon minden lehetséges bemeneti karaktert (és semmi mást, csak legfeljebb a törlő és a stop kódokat, amennyiben használatban vannak). Az algoritmus működése a bemeneti sztring keresése hosszabb rész-sztringekkel míg nem talál egy könyvtárban nem találhatót. Amikor egy ilyen sztringet talál az algoritmus, az utolsó karakter nélküli sztring indexét (magyarán a szótárban levő leghosszabb sztring) kinyerik a szótárból és elküldik a kimenetre, az új sztringet (az utolsó karakterrel) hozzáadják a szótárhoz, a következő kulccsal. Az utolsó bemeneti karaktert használják tovább a rész-sztring keresés kezdőpontjaként.

Ilyen módon egyre hosszabb sztringeket adnak hozzá a szótárhoz és tesznek lehetővé egy kimeneti értékként való kódolásra. Az algoritmus legjobban az ismétlődő mintákkal rendelkező kódolásra működik, így tehát az üzenet kezdeti részei alacsony tömörítési rátával rendelkeznek. Az adatmennyiség növekedésével azonban a tömörítési ráta aszimptotikusan tendál a maximumhoz.Jacob Ziv and Abraham Lempel; Compression of Individual Sequences Via Variable-Rate Coding , IEEE Transactions on Information Theory, September 1978.

Dekódolás A dekódolási algoritmus működése a kódolt inputból egy érték beolvasása és az inicializált szótárból az érték kikeresése. Egyazon időben a következő értéket is kikeresi az inputból és a szótárhoz adja a csak kimeneti sztring és a kinyert sztring utáni következő rész-sztring dekódoltjának első karakterének összefűzését. A dekódoló ezután a következő inputértéket nyeri ki (melyet már előzőleg beolvasott, mint "következő érték") és megismétli a folyamatot egész addig, míg még van további input, majd amikor nincs, a végső értéket dekódolja a szótárhoz való további sztringek adása nélkül.

Ezen módon a dekódoló a kódoló által használttal megegyező szótárat hoz létre és használ a következő inputértékek dekódolásához. Emiatt a teljes szótárat nem szükséges elküldeni; elegendő kizárólagosan az eredeti, egykarakteres kódmegfeleltetéseket elküldeni (és ezt általánosságban a kódoló és a dekódoló már korábban definiálja, így ezt sem kell elküldeni.)

Változó bitszélességű kódok A változó bitszélességű kódok használata esetén a kódolónak és a dekódolónak egyazon pillanatban kell a kódolt adatban a bitszélességet váltani, különben a folyamban található kódhatárokban egyet nem értés lesz köztük. A standard változatban a bitszélességet a kódoló abban az esetben növeli meg, ha egy olyan üzenettel találkozik, mely nincs benne a kódtáblázatban, ám már nincs szabad adott p szélességű kód. A kódoló ekkor kiadja az eredeti p bitszélességűvel még az utolsót, ám innentől kezdve megnöveli a bitszélességet eggyel és a következőként kiadott kódok már p+1 szélesek lesznek.

A dekódoló mindig eggyel van a kódoló mögött, így tehát amikor látja azt, ahol már határátlépés van a kódolóban, akkor egy 2p − 1 értékű kódot tárol el. Mivel ez az a pont, ahol a kódoló bitszélességet vált, itt kell a dekódolónak is, amikor a legnagyobb még p bites kódot létrehozza.

Sajnálatosan némely korai implementáció azonban először megnöveli a kódszélességet és csak azt követően adja ki a sztringet, az új bitszélességgel, nem pedig még a régivel, tehát a dekódoló számára úgy tűnik, hogy a kód bitszélesség váltása túl korán következik be. Ez az úgynevezett „korai váltás” („Early Change”); amely annyi zavart okozott, hogy mára az Adobe engedélyezi mindkét változatot, ám egy külön headert tart fenn annak a részére, hogy az LZW-vel kódolt stream használja-e a korai váltást. A legtöbb grafikus formátum nem használja a korai váltást.

Amikor a tábla üressé válik a törlőkód hatására, mind a kódoló és a dekódoló kódszélességet váltanak, vissza az eredeti bitszélességre.

Bitsorrend Mivel a kiadott kódok tipikusan nem függnek a bájthatároktól, a kódoló- és a dekódolónak meg kell egyeznie a bájtok csomagolásán. A két gyakori metódus az LSB-First ("Least Significant Bit First", "legkevésbé fontos bit elsőnek") és az MSB-First ("Most Significant Bit First", "legfontosabb bit elsőnek"). Az LSB-First esetben a kód úgy rendeződik el, hogy a legkevésbé fontos bit a kódban a bájt-stream legkevésbé fontosabb bitjére kerül és ha a kód több, mint 8 bites, abban az esetben a megmaradó bitek a következő bájt legkevésbé fontos helyeire kerülnek; míg a további kódoknál a legkevésbé fontos bit kerül a megmaradó legkevésbé fontos bit helyére, stb., szükség esetén további bájtokon. az MB-firstben pedig az MSB esik a kód legfontosabb helyére, a túlcsordulás pedig a következő kód MSB-jére kerül; a további kódoknál pedig a legszignifikánsabb bájt kerül a legszignifikánsabb üres helyre.

A GIF fájlok LSB-First sorrendet, míg a TIFF és a PDF fájlok MSB-First sorrendet használnak.

Példa A következő példa az LZW kódolást mutatja be, a kimenet státuszát és minden állapotnál a szótárat, mind a kódolás, mind a dekódolás részénél. Ez a példa úgy lett létrehozva, hogy jó tömörítési rátát adjon viszonylagosan rövid szövegre is. A valódi szöveges adatnál az ismétlődés jóval ritkábban jön létre, tehát általánosságban hosszabb bemeneti folyamok szükségeltetnek a jó tömörítési ráta eléréséhez.

A kódolandó szöveg (az ábécéből csak nagybetűkkel):

TOBEORNOTTOBEORTOBEORNOT#

A # az üzenet végének jelzésére használatos. Ebből következően tehát 26 jel van az ábécében (a 26 nagybetű A és Z közt), továbbá a # stop kód. Önkényesen a betűknek az 1-26 számokat adjuk, míg a stop kódnak a 0-t. (Az LZW legtöbb felhasználásában a stop kód az ábécé után van, de az alap algoritmusban mindezt semmi nem követeli meg. Mindössze annyi kell, hogy a kódoló és a dekódoló megegyezzen az értékeikben.)

A számítógép ezeket bitsztringekként fogja renderelni. 5 bites kódok kellenek a 27 érték megfelelő eltárolásához. TA szótár kezdeti értéke eme 27 értékkel töltődik fel. Amint a szótár növekszik, a kódok méretének is növekednie kell az eltároláshoz. Egy 5 bites kód 25 = 32 lehetséges bitkombinációt biztosít, így a 33. szó létrehozásával az algoritmusnak 5 bitesről 6 bites sztringekké kell váltania a kódokat (minden kódértéket, beleértve a már létrehozottakat is). Megjegyzendő, hogy mivel a csupa nullából álló 0-jelű 00000-t is használjuk, a 33. szótárbejegyzés a 32-es számmal jelölt lesz. (A korábban generált kódkimenetet nem változtatja meg a kódszélesség-változás, de amint egy 6 bites érték generálódik, elképzelhető, mint a következő kimeneti érték, így tehát mindennek 6 bitesre kell váltania.)

A kezdeti szótár értékei:

Jel Bináris Decimális # 00000 0 A 00001 1 B 00010 2 C 00011 3 D 00100 4 E 00101 5 F 00110 6 G 00111 7 H 01000 8 I 01001 9 J 01010 10 K 01011 11 L 01100 12 M 01101 13 N 01110 14 O 01111 15 P 10000 16 Q 10001 17 R 10010 18 S 10011 19 T 10100 20 U 10101 21 V 10110 22 W 10111 23 X 11000 24 Y 11001 25 Z 11010 26

Kódolás Az input karakterek pufferelése egy ω sztringgé, amíg a ω + következő karakter a szótárban van. Amikor már nincs, a ω kódjának kibocsátása és ω + next következő karakter szótárba vétele történik meg. A pufferelés újrakezdődik a következő karakterrel.

Jelenlegi sorozat Következő karakter Kimenet Bővített szótár Megjegyzések Kód Bitek NULL T T O 20 10100 27: TO 27 = az első elérhető kód a 0-26 után O B 15 01111 28: OB B E 2 00010 29: BE E O 5 00101 30: EO O R 15 01111 31: OR R N 18 10010 32: RN a 32 6 bitet igényel, így a következő kimenet 6 bites N O 14 001110 33: NO O T 15 001111 34: OT T T 20 010100 35: TT TO B 27 011011 36: TOB BE O 29 011101 37: BEO OR T 31 011111 38: ORT TOB E 36 100100 39: TOBE EO R 30 011110 40: EOR RN O 32 100000 41: RNO OT # 34 100010 a # befejezi az algoritmust és elküldi a jelenlegi sorozatot 0 000000 és a stop kódot

Kódolatlan hossz = 25 jel × 5 bit/jel = 125 bit Kódolt hossz = (6 kód × 5 bit/kód) + (11 kód × 6 bit/kód) = 96 bit.

Az LZW használatával 29 bitet megtakarítottunk a 125-ből, ezáltal az üzenet méretét 22%-kal csökkentettük. Amennyiben az üzenet hosszabb lett volna, a szótárértékek egyre hosszabb és hosszabb üzenetet tudnak továbbítani.

Dekódolás Egy LZW-vel kódolt adat dekódolásához szükségeltetik a kezdeti szótár megismerése, ám a további bejegyzések könnyen rekonstruálhatók, mivel a meglevő bejegyzések összefűzései.