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.[1]
Az algoritmus
[szerkesztés]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[1] 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,[2] 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
[szerkeszté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.[3]
Dekódolás
[szerkeszté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
[szerkesztés]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
[szerkesztés]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
[szerkesztés]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
[szerkeszté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
[szerkeszté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.
| Input | Kimeneti sorozat | Új szótárelem | Megjegyzés | ||||
|---|---|---|---|---|---|---|---|
| Bit | Kód | Teljes | Sejtés | ||||
| 10100 | 20 | T | 27: | T? | |||
| 01111 | 15 | O | 27: | TO | 28: | O? | |
| 00010 | 2 | B | 28: | OB | 29: | B? | |
| 00101 | 5 | E | 29: | BE | 30: | E? | |
| 01111 | 15 | O | 30: | EO | 31: | O? | |
| 10010 | 18 | R | 31: | OR | 32: | R? | a 31 kód létrehozása (utolsó 5 bitbe beleférő kód) |
| 001110 | 14 | N | 32: | RN | 33: | N? | az input beolvasása 6 bitnél |
| 001111 | 15 | O | 33: | NO | 34: | O? | |
| 010100 | 20 | T | 34: | OT | 35: | T? | |
| 011011 | 27 | TO | 35: | TT | 36: | TO? | |
| 011101 | 29 | BE | 36: | TOB | 37: | BE? | 36 = TO + az első jel (B) |
| 011111 | 31 | OR | 37: | BEO | 38: | OR? | a következő megérkező szekvenciából (BE) |
| 100100 | 36 | TOB | 38: | ORT | 39: | TOB? | |
| 011110 | 30 | EO | 39: | TOBE | 40: | EO? | |
| 100000 | 32 | RN | 40: | EOR | 41: | RN? | |
| 100010 | 34 | OT | 41: | RNO | 42: | OT? | |
| 000000 | 0 | # | |||||
Minden állomásnál a dekódoló megkapja az X kódot; megkeresi az X-et a táblázatban és kiadja az általa kódolt χ sorozatot és hozzáadja az χ + ?-et, melyet a kódoló épp hozzáadott – ugyanis a kódoló az X-et adta ki χ-re, hiszen χ + ? nem volt a táblázatban, így azt kell most hozzáadnia. De mi a hiányzó betű? Az első karaktere a dekódoló által megkapott következő Z kódnak. Tehát a dekóder megkeresi Z-t, dekódolja az ω sorozatba, kikeresi az első, z karakterét és χ-vel összefűzve szótárelemmé teszi.
Ez egészen addig működik, ameddig a Z a szótárban van, magyarán szekvenciába kódolható. Mi történik, ha a dekódoló egy szótárban nem levő Z-t kap? Mivel a dekódoló mindig eggyel van a kódoló mögött, a Z csak akkor lehet úgy a kódoló szótárában, hogy a dekódolóéban nincs, ha a kódoló éppen most generálta le azt, amikor kiadta az előző X kódot χ-re. Tehát Z valami olyan ω-t kódol, ami χ + ?, amikor pedig a dekódoló így állapíthatja meg az ismeretlen karaktert:
- A dekódoló látja X-et és Z-t.
- Tudja, hogy X a χ sorozatot kódolja és Z valami ω-t kódol.
- Tudja, hogy a Z-t a kódoló most adta hozzá, hogy kódoljon egy χ + ismeretlen karaktert,
- Tudja, hogy az ismeretlen karakter az első, z karakter ω-ból.
- De ω első karaktere (= χ + ?) mindenképpen χ első karaktere is.
- Így tehát ω alakja mindenképp χ + x, ahol is x az első karaktere χ-nek.
- Így hát a dekóder rájön arra, hogy mit is kódol Z, még ha nincs is a táblázatban,
- és Z megérkeztével a dekódoló dekódolja, mint χ + x, majd hozzáadja, mint χ + x a táblázathoz, Z értékkel.
Ez a szituáció akkor jön létre, ha az input formája cScSc, ahol c egy karakter, S egy sztring és cS már a szótárban van, de cSc még nincs. A kódoló kiadja a kódot, mely megfelel cS-nek, hozzáadja cSc-t a szótárhoz. Ezután látja cSc-t az inputban (a cScSc második c-jével kezdődve) és kiadja az újonnan beillesztett kódot. Ez bemutatja, hogy amennyiben a dekódoló egy, még a szótárban nem levő értéket kap, az a szituáció így kell, hogy kinézzen.
Habár a cScSc forma igencsak valószínűtlennek tűnik, ez könnyen előfordulhat, ha a bemeneti streamet jellemzi a magas ismétlődési arány. Egyes esetekben, amikor azonos karakterekből álló folyam tart hosszú ideig (amely gyakori az olyan képeknél, melyet az LZW-vel kódolnak) , huzamosan ilyen mintázat generálódhat.
További kódolás
[szerkesztés]A fent leírt egyszerű séma magát az LZW-t írta le. Számos alkalmazás további kódolást alkalmaz kimeneti szimbólumainál. Némelyek a kódolt folyamot binárisból szöveggé történő kódolással olvasható formába kódolják át; ez megnöveli a kódolt hosszt és csökkenti a tömörítési frekvenciát. Avagy megfordítva, nagyobb ráta érhető el az úgynevezett adaptív entrópiás kódolókkal. Egy ilyen kódoló kiszámítja a következő jel valószínűségi eloszlását az eddig megfigyelt frekvenciák alapján. Egy standard entrópiás kódoló a Huffman-kódolás vagy az aritmetikus kódolás, mely rövidebb kódot használ a magasabb valószínűségű jelekre.
Alkalmazása
[szerkesztés]A gyakorlatban fix szóhosszúságú szótárral használják, a szótár betelése után egyszerű fix szótáras tömörítést végeznek. Az LZW széles körben a Unix operációs rendszer compress segédprogramjának algoritmusaként terjedt el; ma leginkább a GIF képformátum részeként ismert. A GIF-hez használt implementációban a szótár maximális mérete 512, vagyis maximum 9 bit hosszú kódszavakat használ. Amikor a szótár betelik, 10 bites kódszavakra kell áttérni, vagyis a szótár mérete megduplázódik, és így tovább.
A TIFF képformátum és a PDF dokumentumformátum tömörítési eljárásai között is szerepel.[4]
Szabadalmak
[szerkesztés]Az Egyesült Államokban és más országokban is számos szabadalmat adtak be az LZW és hasonló algoritmus védelmére. Az LZ78-at a Lempel, Ziv, Cohn és Eastman által benyújtott 4464650-s szabadalom védte, a Sperry Corporation-höz, később pedig az Unisys Corporation-höz hozzárendelve, 1981. augusztus 10-én benyújtva. Az LZW-re az USA-ban 2 szabadalmat adtak be: 4814746-os szabadalom Victor S. Miller és Mark N. Wegman által, az IBM-hez rendelve, eredetileg benyújtva 1983. június 1-jén és 4558302-s szabadalom Welch által a Sperry Corporation-höz, később az Unisys Corporation-höz rendelve, benyújtva 1983. június 20-án. 2003. június 20-án az LZW ezen szabadalma lejárt.[5] Az LZW minden szabadalma a világon szintúgy lejárt, Európában és Japánban 2004-ben.[6]
A 4,558,302-as USA-beli szabadalom jelentékeny negatív sajtót kapott az LZW gif formátumban való használata után.[4]
Változatok
[szerkesztés]- LZMW (1985, V. Miller, M. Wegman)[7] – Az inputban a leghosszabb, már szótárban levő elemet keresi (a "jelenlegi" egyezés); ezután hozzáadja az ezen egyezést az előzővel összefűzött szöveget a szótárhoz. (Emiatt tehát a szótárbejegyzések gyorsabban nőnek; de ez a séma jóval komplikáltabban implementálható az előzőnél.) Miller és Wegman javasolták továbbá a feltöltődött szótárból az alacsony frekvenciájú elemek törlését.
- LZAP (1988, James Storer)[8] – az LZMW módosítása: az előző egyezés és a jelenlegi egyezés szótárba való sima hozzáadása helyett ez a variáns az előző egyezés a jelenlegivel való minden rész-sztringjét hozzáadja. (Az "AP" jelentése "all prefixes", azaz "minden prefixum".) Tehát például, ha az előző egyezés a "wiki" és a jelenlegi a "pedia", akkor az LZAP kódoló 5 új sorozatot ad a szótárhoz: "wikip", "wikipe", "wikiped", "wikipedi" és "wikipedia", míg az LZMW kódoló egyedül a "wikipedia" sorozatot adja hozzá. Ez kiiktatja az LZMW komplexitásának egy részét, ám több szótárbejegyzés hozzáadásának árán.
- Az LZWL az LZW szótagalapú variánsa.
Jegyzetek
[szerkesztés]- ↑ a b Terry Welch, "A Technique for High-Performance Data Compression", IEEE Computer, June 1984, p. 8–19.
- ↑ Lempel-Ziv-Welch (LZW) Algorithm
- ↑ Jacob Ziv and Abraham Lempel; Compression of Individual Sequences Via Variable-Rate Coding Archiválva 2012. április 12-i dátummal a Wayback Machine-ben, IEEE Transactions on Information Theory, September 1978.
- ↑ a b LZW compression
- ↑ Archivált másolat. [2009. június 2-i dátummal az eredetiből archiválva]. (Hozzáférés: 2009. június 2.)
- ↑ digitalpreservation.gov: LZW Compression Encoding
- ↑ David Salomon, Data Compression – The complete reference, 4th ed., page 209
- ↑ David Salomon, Data Compression – The complete reference, 4th ed., page 212
Fordítás
[szerkesztés]Ez a szócikk részben vagy egészben a Lempel-Ziv-Welch című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.
Források
[szerkesztés]- Welch, T.A., A Technique for High-Performance Data Compression, Computer, vol. 17, no. 6, pp. 8–19, June 1984.
alternatív link Archiválva 2019. május 30-i dátummal a Wayback Machine-ben. - 4558302 USA szabvány, Terry A. Welch, High speed data compression and decompression apparatus and method
- SharpLZW - C# nyílt forráskódú implementáció
