Lempel-Ziva-Welch algoritmus

A Lempel -Ziv-Welch algoritmus ( Lempel -Ziv-Welch , LZW ) egy univerzális veszteségmentes adattömörítési algoritmus , amelyet Abraham Lempel , Jacob Ziv és Terry Welch készített . Welch adta ki 1984 -ben [1] a Lempel és Ziv által 1978 -ban közzétett LZ78 algoritmus továbbfejlesztett megvalósításaként [2] . Az algoritmust úgy tervezték, hogy szoftveresen és hardveresen is meglehetősen könnyen megvalósítható legyen [1] .

Az "LZW" betűszó az algoritmus feltalálóinak nevére utal: Lempel, Ziv és Welch, de sok[ ki? ] azzal érvelnek, hogy mivel a szabadalom a Ziv tulajdona, a módszert Ziv-Lempel-Welch algoritmusnak kell nevezni .

Leírás

Ez az algoritmus egy üzenet kódolásakor (tömörítésekor) dinamikusan létrehozza a kifejezések szótárát: bizonyos karaktersorozatokhoz (kifejezésekhez) fix hosszúságú bitcsoportokat (kódokat) rendelnek (például 12 bitesek, amint azt a Welch eredeti cikke [1] ). A szótár az összes 1 karakteres kifejezéssel inicializálva van (8 bites karakterek esetén ez 256 frázis). A kódolás során az algoritmus karakterenként balról jobbra szkenneli a szöveget. Amikor az algoritmus beolvassa a következő karaktert ebben a pozícióban, van egy W maximális hosszúságú karakterlánc, amely megfelel a szótár valamelyik kifejezésének. Ezután ennek a kifejezésnek a kódja elküldésre kerül a kimenetre, és a WK karakterlánc, ahol K a bemeneti üzenet W utáni karaktere, új kifejezésként bekerül a szótárba, és hozzárendelődik valamilyen kód (mivel a W-t választották mohón , a WK még nem szerepel a szótárban). A K karakter a következő kifejezés kezdete. Formálisabban ez az algoritmus a következő lépések sorozatával írható le:

A szótár inicializálása az összes lehetséges egykarakteres kifejezéssel. A W beviteli kifejezés inicializálása az üzenet első karakterével.
Ha END_MESSAGE, akkor adjon ki egy kódot W számára, és állítsa le az algoritmust.
Olvassa be a következő K karaktert a kódolt üzenetből.
Ha a WK kifejezés már szerepel a szótárban, állítsa a W beviteli kifejezést WK-ra, és folytassa a 2. lépéssel.
Ellenkező esetben adja ki a W kódot, adja hozzá a WK-t a szótárhoz, állítsa a W beviteli kifejezést K értékre, és folytassa a 2. lépéssel.

A dekódoló algoritmusnak csak a kódolt szövegre van szüksége bevitelként: a megfelelő kifejezésszótár könnyen létrehozható a kódoló algoritmus működésének utánzásával (de vannak finom árnyalatok, amelyeket az alábbi példában tárgyalunk ).

Megvalósítás

Az LZW algoritmus figyelemre méltó jellemzője a könnyű implementáció, ami még mindig nagyon népszerűvé teszi, annak ellenére, hogy az analógokhoz, például az LZ77 -hez képest gyakran rosszabb a tömörítési arány [3] . Az LZW-t általában egy szótárból származó kifejezéseket tartalmazó előtagfával valósítják meg : a W megtalálásához csak a lehető leghosszabb karakterláncot kell kiolvasni a fa gyökeréből, majd új kifejezés hozzáadásához hozzá kell adni a WK-t a talált csomóponthoz. az új fiút a K szimbólummal, és a W kifejezés kódja egy csomópont indexeként működhet az összes csomópontot tartalmazó tömbben.

Kifejezéskódolás

Rögzített hosszúságú kódok használata frázisokhoz (12 bit a Welch-leírásban [1] ) hátrányosan befolyásolhatja a tömörítési hatékonyságot, mivel először is a kezdeti kódolt karakterek esetében ez a megközelítés inkább felfújja az adatokat, nem pedig tömöríti (ha a karakter 8 bites ), másodszor pedig a szótár teljes mérete (2 12 =4096) nem olyan nagy. Az első problémát úgy oldjuk meg, hogy a kimeneti sorozatot Huffman algoritmussal (esetleg adaptív ) vagy aritmetikai kódolással kódoljuk . A második megoldására más megközelítéseket alkalmaznak.

Az első egyszerű lehetőség valamilyen optimális univerzális kód alkalmazása , például a Levenshtein kód vagy az Elias kód . Ebben az esetben elméletileg a szótár korlátlanul bővülhet.

Egy másik gyakoribb lehetőség a szótár maximális lehetséges méretének megváltoztatása a kifejezések számának növekedésével. [4] Kezdetben például a szótár maximális mérete 2 9 (2 8 kódot már foglaltak a 8 bites egykarakterek kódolására szolgáló frázisok), és 9 bit van lefoglalva a kifejezéskódhoz. Amikor a frázisok száma 2 9 lesz , a maximális méret 2 10 lesz, és 10 bit kerül lefoglalásra a kódokhoz. Stb. Így elméletileg egy szótár tetszőleges nagyságú lehet. Ezt a módszert az alábbi példa szemlélteti (általában azonban a szótár maximális mérete korlátozott; például az LZC-ben - az LZW népszerű módosításában, amelyet alább tárgyalunk - a kód hossza 9 bitről 16 bitre nő.).

Az utóbbi módszer legtöbb megvalósításában a fráziskódhoz lefoglalt bitek számát addig növelik, amíg egy új WK kifejezést nem adunk hozzá, ami túlcsordul a szótáron, de miután a W kódot a kimenetre írtuk, adja vissza a W kifejezéskódot, és adja hozzá az új WK kifejezés a szótárba; ha a WK kód egyenlő 2 p -vel (vagyis a WK túlcsordul a szótáron), akkor először a W p-bites kód kerül kiadásra, és csak ezután nő a p eggyel, így a következő kódok p + 1 bitet foglalnak el. Az LZW korai megvalósításai közé tartoznak azok, amelyek a W-kód kiadása előtt növelik a p értéket, azaz a WK szótárba való felvétele előtti W-kód kimenet már p+1 bitet foglal el (ami nem szükséges, mivel a W-kód kisebb, mint 2 p ). Ezt a viselkedést "korai változásnak" nevezik. Ez a megvalósítási zavar arra késztette az Adobe -t, hogy az LZW mindkét változatát támogassa PDF formátumban (hogy a "korai változtatások" használatban vannak-e, a tömörítendő adatok fejlécében egy speciális jelző jelzi). [5]

Szótár túlcsordulás

Mivel az LZW algoritmusban a kódok fix hosszúságúak, a szótár mérete korlátozott (nem fix hosszúságú kódok használatakor a szótár méretét a rendelkezésre álló memória mennyisége korlátozza). Felmerül a kérdés: mi a teendő szótár túlcsordulás esetén? Többféle stratégiát alkalmaznak.

A legkézenfekvőbb lehetőség az elkészített szótár egyszerű használata további módosítások nélkül. [1] Nyilvánvaló, hogy ez gyakran rossz stratégia.
Az egykor népszerű compress segédprogram szerzői egyszerűen felhasználják az összeállított szótárat, amíg a tömörítési arány elfogadható marad, majd megtisztítják, ha a tömörítés minősége romlik. Az LZW ezen módosítása az LZC (Lempel-Ziv-Compress, lásd alább). [6]
P. Tischer azt javasolta, mielőtt új kifejezést szúrna be a túlcsorduló szótárba, az algoritmus következő lépésében törölje ki a szótárból azt a kifejezést, amelyet a leghosszabb ideig nem használt (LRU, Least Recently Used). Ezt a módosítást néha LZT-nek is nevezik (Lempel-Ziv-Tischer, lásd alább). [7]

Példa

Ez a példa az LZW algoritmust mutatja be működés közben, megmutatva a kimenet és a szókincs állapotát az egyes szakaszokban, mind az üzenet kódolása, mind dekódolása közben. Az előadás egyszerűsítése érdekében egy egyszerű ábécére korlátozzuk magunkat - csak nagybetűkkel, írásjelek és szóközök nélkül. A tömörítendő üzenet így néz ki:

NEM VAGY NEM LESZNEM#

A # jelölő az üzenet végét jelöli. Így 27 karakter van az ábécénkben (26 nagybetű A-tól Z-ig és #). A számítógép ezt bitcsoportokként jeleníti meg, az ábécé minden karakterének megjelenítéséhez csak egy 5 bites csoportra van szükségünk karakterenként. A szókincs bővülésével a csoportok méretének is növekednie kell, hogy új elemeket tudjanak befogadni. Az 5 bites csoportok 2 5 = 32 lehetséges bitkombinációt adnak, így amikor a 33. szó megjelenik a szótárban, az algoritmusnak 6 bites csoportokra kell mennie. Vegye figyelembe, hogy mivel az összes nulla 00000 csoportját használjuk, a 33. csoport kódja 32 . A kezdeti szótár a következőket tartalmazza:

# = 00000 A=00001 B=00010 C=00011 . . . Z = 11010

Kódolás

Az LZW algoritmus használata nélkül az üzenet 25 karakter, egyenként 5 bites továbbításakor 125 bitre lesz szükség. Hasonlítsa össze ezt azzal, ami az LZW használatakor történik:

Szimbólum: Bitkód: Új szótári bejegyzés: (a kijáratnál) T20 = 10100 O 15 = 01111 27: TO B 2 = 00010 28: OB E 5 = 00101 29: BE O 15 = 01111 30: EO R 18 = 10010 31: VAGY <--- kezdje el a 6 bites csoportok használatát a következő karaktertől N 14 = 001110 32: RN O 15 = 001111 33: NEM T 20 = 010100 34: OT TO 27 = 011011 35: TT BE 29 = 011101 36: TOB VAGY 31 = 011111 37: BEO TOB 36 = 100100 38:ORT EO 30 = 011110 39: TOBE RN 32 = 100000 40: EOR OT 34 = 100010 41: RNO # 0 = 000000 42: OT# Teljes hossz = 6*5 + 11*6 = 96 bit.

Így az LZW használatával 29 bittel csökkentettük az üzenetet a 125-ből - ez majdnem 22%. Ahogy az üzenet hosszabb lesz, a szókincs egyre hosszabb részeit képviseli a szövegben, így az ismételt szavak nagyon tömörek lesznek.

Dekódolás

Most képzeljük el, hogy megkaptuk a fent látható kódolt üzenetet, és dekódolnunk kell. Mindenekelőtt ismernünk kell a kezdeti szótárat, és menet közben is rekonstruálhatjuk a következő szótárbejegyzéseket, mivel ezek egyszerűen az előző bejegyzések összefűzései.

Adatok: Kimenet: Új rekord: Teljes: Részleges: 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: VAGY 32: R? <---- kezdje el használni a 6 bites csoportokat 001110 = 14 N 32: RN 33: N? 001111 = 15 O 33: NO 34: O? 010100 = 20 T 34: OT 35: T? 011011 = 27 - 35: TT 36: TO? <---- 37 esetén csak az első elemet adja hozzá 011101 = 29 BE 36: TOB 37: BE? következő szótári szó 011111 = 31 VAGY 37: BEO 38: VAGY? 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 #

Az egyetlen kisebb nehézség akkor adódhat, ha az új szótári szót azonnal elküldi. A fenti dekódolási példában, amikor a dekódoló találkozik az első karakterrel, a T , tudja, hogy a 27. szó T betűvel kezdődik, de hol végződik? Illusztráljuk a problémát a következő példával. Dekódoljuk az ABABA üzenetet :

Adatok: Kimenet: Új rekord: Teljes: Részleges: . . . 011101 = 29 AB 46: (szó) 47: AB? 101111 = 47AB? <--- mit tegyünk ellene?

Első pillantásra ez egy megoldhatatlan helyzet a dekóder számára. Már előre tudjuk, hogy a 47-es szónak ABA -nak kell lennie , de honnan tud erről a dekódoló? Vegye figyelembe, hogy a 47-es szó a 29-es szóból és a következő karakterből áll. Így a 47. szó a következővel végződik: „a következő karakter”. De mivel ez a szó azonnal elküldésre kerül, a "következő karakterrel" kell kezdődnie, és így ugyanazzal a karakterrel végződik, mint ahogyan kezdődik, ebben az esetben A . Ez a trükk lehetővé teszi a dekódoló számára, hogy megállapítsa, hogy a 47-es szó ABA .

Általában ez a helyzet akkor fordul elő, ha egy cScSc formájú sorozatot kódolnak , ahol c egyetlen karakter, S pedig karakterlánc, és a cS szó már szerepel a szótárban.

A hatékonyság elméleti értékelése

A kötetlen szókincs LZW elméleti tulajdonságai általában megegyeznek az LZ78-éval, és a két tömörítési módszer elemzése hasonló. Ha korlátlan szótárt veszünk figyelembe, természetes az a feltételezés, hogy a kimeneti kifejezések változó hosszúságú kódokkal vannak kódolva, például valamilyen univerzális kóddal vagy fix kóddal, amelyek mérete a szótár maximális méretével nő (lásd a megvalósítási részt ).

Aszimptotikus optimalitás

A hatékonyság elméleti értékeléséhez ezt a tömörítési módszert összehasonlítják néhány referenciamutatóval. Sajnos az ideális referenciaadat-tömörítési metrika – Kolmogorov-komplexitás – még csak megközelítőleg sem számítható ki, ezért minden tömörítési algoritmus nyilvánvalóan veszít vele szemben. Lempel és Ziv a Kolmogorov-féle komplexitás gyengített változatát – véges automatákkal való tömörítést – javasolta [2] . Technikai okokból ez a mérőszám végtelen karakterláncokhoz van definiálva. Javítunk egy véges ábécét . Legyen egy végtelen karakterlánc . Jelölje a bitek számával az LZW kódolásban a karakterlánc korlátlan szótárával . Ezért van $\Sigma$ $x=x_{1}x_{2}\cdots$ $\Sigma$ $\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})$ ${\displaystyle x_{1}x_{2}\cdots x_{n))$

\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})\leq z\log _{2}z+O(z\log _{2}|\Sigma |),

ahol a kifejezések száma LZW kódolásban a következőhöz: . Ziv megmutatta [8] , hogy $z$ ${\displaystyle x_{1}x_{2}\cdots x_{n))$

\limsup \limits _{n\to \infty }{\frac {\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})}{n\log _{2}| \Sigma |}}\leq \mathrm {FS} (x),

ahol a tömörítési metrika véges automatákkal, az alábbiakban definiálva [2] . Így az LZW tömörítési arány ( a tömörítetlen karakterlánc által elfoglalt bitek számához viszonyított arány) aszimptotikusan korlátos , és ebben az értelemben az LZW optimális. Sőt, ha a szótár mérete korlátozott, és a túlcsordulási stratégia a legkevésbé használt kifejezések eltávolítása, az LZW aszimptotikusan is optimális a következő értelemben: [8] $\mathrm {FS} (x)$ $\mathrm {LZW} (x_{1}x_{2}\cdots x_{n})$ $n\log _{2}|\Sigma |$ $\mathrm {FS}$

\lim _{D\to \infty }\limsup \limits _{n\to \infty }{\frac {\mathrm {LZW} _{D}(x_{1}x_{2}\cdots x_ {n})}{n\log _{2}|\Sigma |}}\leq \mathrm {FS} (x),

ahol a bitek számát jelöli LZW kódolásban egy legfeljebb frázisokat tartalmazó szótárban, minden frázis hossza legfeljebb , és amikor a szótár túlcsordul, a legkevésbé használt kifejezés kidobásra kerül (ez az opció hasonló az LZT-hez; lásd a módosításokat ). Vegyük észre, hogy az LZ78 és LZ77 algoritmusok hasonló tulajdonságokkal rendelkeznek (beleértve a hasonló változatokat is, szótárral és korlátozott méretű csúszóablakkal) [8] . Most határozzuk meg . $\mathrm {LZW} _{D}(x_{1}x_{2}\cdots x_{n})$ $D$ $\log _{2}^{2}D$ $\mathrm {FS}$

A metrika sok tekintetben hasonlít a Kolmogorov-komplexitáshoz, de a definíciójában a teljes értékű Turing-gépek helyett véges memóriájú Turing-gépeket, azaz véges automatákat használnak. Adott szám esetén az összes olyan determinisztikus Mealy automata halmazát jelöljük , amelyek állapotai vannak, és az ábécé feletti karakterláncokat bináris sorozatokká kódolják át, így az automata kimenete vissza tudja állítani az eredeti karakterláncot; pontosabban bináris karakterláncok (esetleg üresek) vannak az automata éleire írva, így az ábécé feletti bármely véges karakterlánc esetén az automata valamilyen állapotba kerül, és a folyamat során egy bináris sorozatot állít elő , és ez egyedileg visszaállítható a sorozat és az állapot (hogy a zsugorodó automata élein üres sztringek legyenek, a sztringet nem csak a sorozat, hanem a végállapot is visszaállítja [9] ). Adott végtelen karakterlánchoz adja meg: [8] $\mathrm {FS} (x)$ $s$ ${\mathcal {A}}_{s}$ $A,$ $s$ $\Sigma$ $A$ $y$ $\Sigma$ $A$ $v$ $A(y)$ $A(y)$ $v$ $y$ $y$ $A(y)$ $v$ $x=x_{1}x_{2}\cdots$

\mathrm {FS} (x)=\lim _{s\to \infty }\limsup \limits _{n\to \infty }\min \limits _{A\in {\mathcal {A)) _{s}}{\frac {|A(x_{1}x_{2}\cdots x_{n})|}{n\log _{2}|\Sigma |}},

ahol a bitek számát jelöli . Így a lehető legkisebb tömörítési arány becslése, amely egy karakterlánc véges automatákkal történő tömörítésekor elérhető. Megjegyzendő, hogy a szótár korlátlansága miatt az LZW algoritmus nem modellezhető Mealy automatával, ellentétben a korlátozott szókincsű LZW algoritmussal, amely legfeljebb frázisokat tartalmazhat (egy ilyen Mealy automata mérete természetesen függ ). $|A(y)|$ $A(y)$ $\mathrm {FS} (x)$ $x$ $D$ $\log _{2}^{2}D$ $D$

Nem optimális számú kifejezés

A véges automaták tömörítési metrikája, bár természetes, nem olyan hatékony, mint amilyennek első pillantásra tűnik. Tehát aszimptotikusan optimális minden olyan tömörítési algoritmus, amely az adott karakterláncot különböző frázisokra bontja (vagyis mikor ) , majd [9] bitekkel kódolja . Nyilvánvaló, hogy egy ilyen gyenge kritériumot kielégítő algoritmusnak nem kell hatékonynak lennie a gyakorlatban. Ezenkívül az állapotgép-tömörítési metrika nem tükrözi számos tömörítési módszer azon képességét, hogy az adatokban a hosszú ismétlődő darabokat olyan helyre való hivatkozással helyettesítse, ahol az ilyen darab először előfordult (az állapotgépnek egyszerűen nincs elég memóriája a hosszú összehasonlításhoz darabok). Ez a mechanizmus gyakran az oka a nagy mennyiségű adat tömörítésének hatékonyságának a gyakorlatban, és amint az alább látható, az LZW (és az LZ78) a legrosszabb esetben is elég gyengén teljesít ebben a feladatban például az LZ77-hez képest. $\mathrm {FS}$ ${\displaystyle x=x_{1}x_{2}\cdots x_{n))$ ${\displaystyle f_{1}f_{2}\cdots f_{k))$ ${\displaystyle f_{i}\neq f_{j))$ $i<j<k$ $x$ $k\log _{2}k+O(k\log _{2}|\Sigma |)$

A korlátlan szótármérettel rendelkező LZW algoritmus a megadott végső karakterláncot frázisokra bontja úgy, hogy minden kifejezés egy karakter vagy egyenlő azzal , ahol néhány szám kisebb , mint és a kifejezés első karaktere . Léteznek egy karakterlánc alakjának más dekompozíciói is , és természetesen felmerül a kérdés: mennyire jó a mohó LZW algoritmus által felépített dekompozíció? ${\displaystyle x=x_{1}x_{2}\cdots x_{n))$ ${\displaystyle p_{1}p_{2}\cdots p_{z))$ $p_{k}$ $p_{h}a$ $h$ $k$ $a$ $p_{h+1}$ ${\displaystyle p_{1}p_{2}\cdots p_{z))$ $x$

Legyen jelölje a minimális számot úgy, hogy a karakterlánc olyan felbontásként ábrázolható, amelyben minden karakterlánc egy karakter vagy egyenlő azzal , ahol néhány szám kisebb , mint és a karakterlánc első karaktere . Sergio De Agostino és Ricardo Silvestri [10] bebizonyította, hogy ez a legrosszabb esetben is több lehet 1-nél , még akkor is, ha az ábécé csak két karaktert tartalmaz (ezt is kimutatták, hogy ez a becslés optimális). Más szóval, a mohó stratégia ebben az esetben olyan eredményeket ad, amelyek nagyon távol állnak az optimálistól. Az LZW megközelítés indoklása részben az, hogy az optimális frázisbontás megalkotása NP -teljes probléma , amint azt De Agostino és Storer [11] mutatja . ${\displaystyle z_{o))$ $x$ $p'_{1}p'_{2}\cdots p'_{z_{o))$ ${\displaystyle p'_{k))$ $p'_{h}a$ $h$ $k$ $a$ $p'_{h+1}$ $z$ ${\displaystyle z_{o))$ $\Omega (n^{1/4})$ $z\leq z_{o}\cdot O(n^{1/4}),$ ${\displaystyle z_{o))$

Egy másik természetes kérdés, hogy az LZW mennyire jó az LZ77 -hez képest ? Az LZ77-ről köztudott, hogy mohón bontja fel a karakterláncot frázisokra úgy, hogy minden egyes kifejezés a karakterlánc karaktere vagy részkarakterlánca . Hooke, Laurie, Re [12] és Charikar és munkatársai [13] kimutatták, hogy a legrosszabb esetben többszöröse is lehet, mint . Másrészt köztudott, hogy mindig nem kevesebb, mint , sőt több, mindig nem kevesebb, mint . [13] Más szóval, az LZW, és még az LZW "optimális" verziója is, amely kifejezéseket tartalmaz, nem lehet jobb, mint az LZ77 (legalábbis jelentősen - vegye figyelembe, hogy itt a kifejezések számáról van szó, nem a kódolásuk módjáról), és egyes kóros esetekben katasztrofálisan rosszabb is lehet. $x$ ${\displaystyle f_{1}f_{2}\cdots f_{w))$ $f_{h}$ ${\displaystyle f_{1}f_{2}\cdots f_{h-1))$ $z$ $\Omega ((n/\log n)^{1/2})$ $w$ $z$ $w$ ${\displaystyle z_{o))$ $w$ ${\displaystyle z_{o))$

Alkalmazás

Bevezetése idején az LZW algoritmus jobb tömörítési arányt adott a legtöbb alkalmazáshoz, mint bármely más korabeli jól ismert módszer. Ez lett az első számítógépeken széles körben használt adattömörítési módszer.

Az algoritmust (vagy inkább annak módosítását, az LZC-t, lásd alább) a compress programban valósították meg , amely 1986 körül többé-kevésbé szabványos segédprogram lett a Unix rendszereken. Számos más népszerű archiváló segédprogram is használja ezt a módszert, vagy a hozzá közel állók.

1987 -ben az algoritmus a GIF képformátum szabvány részévé vált . (opcionálisan) TIFF formátumban is használható . Ezenkívül az algoritmust a modem v.42bis kommunikációs protokollja és a PDF szabvány [14] használja (bár alapértelmezés szerint a PDF-ben található szöveges és vizuális adatok nagy része a Deflate algoritmussal van tömörítve ).

Szabadalmak

Az LZW algoritmusra és változataira számos szabadalmat adtak ki, mind az Egyesült Államokban, mind más országokban. Az LZ78-at a 4 464 650 számú US szabadalom a Sperry Corporation adta ki , amely később az Unisys Corporation része volt . Két amerikai szabadalmat adtak ki az LZW-re: a 4 814 746 számú amerikai egyesült államokbeli szabadalmat az IBM tulajdonában , és a Welch 4 558 302 számú amerikai egyesült államokbeli szabadalmat (kibocsátva 1983. június 20- án ), amelyet a Sperry Corporation birtokol, amelyet később az Unisys Corporation vette át. Mára minden szabadalom lejárt.

Unisys GIF-ek és PNG-k

A GIF formátum fejlesztése során a CompuServe nem tudott a 4 558 302 számú amerikai egyesült államokbeli szabadalom létezéséről . 1994 decemberében, amikor az Unisys tudomást szerzett arról, hogy az LZW-t széles körben használt grafikus formátumban használják, a vállalat nyilvánosságra hozta terveit, hogy jogdíjakat szedjen be olyan kereskedelmi programoktól, amelyek lehetővé teszik GIF-fájlok létrehozását. Ekkor már annyira elterjedt a formátum, hogy a legtöbb szoftvercégnek nem volt más választása, mint fizetni. Ez a helyzet volt az egyik oka a PNG grafikus formátum (nem hivatalos átirat: "PNG's Not GIF" [15] ) kifejlesztésének, amely a harmadik leggyakoribb lett. a WWW -en, GIF és JPEG után . 1999. augusztus végén a Unisys felmondta a jogdíjmentes licenceket az LZW számára az ingyenes és nem kereskedelmi szoftverekre [16] , valamint a licenc nélküli programok felhasználóira vonatkozóan, ami arra késztette a League for Programming Freedom -t, hogy elindítsa a "burn all GIFs" kampányt [17]. és tájékoztassa a nyilvánosságot a rendelkezésre álló alternatívákról. Számos szabadalmi jogi szakértő felhívta a figyelmet arra, hogy a szabadalom nem terjed ki azokra az eszközökre, amelyek csak az LZW-adatokat képesek kitömöríteni, de tömöríteni nem; Emiatt a népszerű gzip segédprogram képes olvasni a .Z fájlokat, de írni nem.

2003. június 20-án lejárt az eredeti amerikai szabadalom, ami azt jelenti, hogy a Unisys már nem gyűjthet rá jogdíjat. A hasonló szabadalmak Európában, Japánban és Kanadában 2004-ben lejártak.

Módosítások

Az LZC (1985, Thomas SW, McKie J., Davies S., Turkowski K., Woods JA és Orost JW) [6] az LZW egyik legismertebb gyakorlati megvalósítása, amelyet a tömörítő segédprogram (Lempel- Ziv-Compress). Az LZC 9-16 bitet használ fráziskódokhoz (a bitek száma a szótár méretével nő, lásd a megvalósítási részt ); amikor a szótár túlcsordul, az LZC egyszerűen folytatja a használatát további módosítások nélkül, de az algoritmus figyeli az adattömörítés mértékét, és ha az aktuális szótárral való tömörítés elfogadhatatlanul rossz lesz, az LZC törli a szótárt, és folytatja a munkát. Az LZC rosszabbul tömörít, mint az LZW, de a tömörítési sebesség nagyobb.
LZT (1985, Tischer P.) [7] az LZW másik ismert változata. Amikor a szótár túlcsordul, az LZT folytatja, de minden alkalommal, mielőtt új kifejezést illeszt be a szótárba, eltávolítja azt a kifejezést, amely a leghosszabb használaton kívüli levélnek felel meg az összes kifejezést tartalmazó előtagfában . Az LZT megvalósításban az összes levél egy linkelt listába kerül, és minden alkalommal, amikor a leveleket használja a tömörítés során, a levelek a lista elejére kerülnek; így a leghosszabb ideig nem használt levelek a lista végén vannak (a további részletek nyilvánvalóak).
LZMW (1985, Victor Miller és Mark Wegman ) [18] - megkeresi a bemeneti adatfolyamban a leghosszabb karakterláncot, amely már a szótárban van (jelöljük W), kiadja a W kódot, majd hozzáadja a szótárba a VW karakterláncot, ahol V a szótárból származó karakterlánc, amelynek kódját az előző lépésben visszaküldtük (kezdetben V egy üres karakterlánc). Így a szótárban lévő karakterláncok gyorsabban nőnek, mint az eredeti LZW-ben, és a gyakorlatban gyakran jobb tömörítési minőséget lehet elérni. Miller és Wegman azt is javasolta, hogy memóriahiány esetén a ritkán használt kifejezéseket távolítsák el a szótárból, akárcsak az LZT-ben.
Az LZAP (1988, James Storer) [19] az LZMW módosítása, amely abban különbözik, hogy minden lépésben nem csak a VW karakterlánc kerül a szótárba, hanem a VW 1 , VW 2 , …, VW |W karakterláncok is. |-1 , ahol W i egy W i hosszúságú előtag. (Az „AP” az „LZAP”-ban „minden előtagot”, azaz „minden előtagot” jelent.) Például, ha V = wiki és W = pedia - vagyis az előző lépésben az algoritmus megtalálta a karakterlánc wikit a szótárat , ezen pedig megtalálta a pedia -t - akkor az algoritmus hozzáadja a wikipedia karakterláncot a szótárhoz , ahogy az LZMW tenné, de hozzáadja a wikip , wikipe , wikiped , wikipedi karakterláncokat is . Az LZAP algoritmus könnyebben megvalósítható, mint az LZMW, ugyanakkor megőrzi az LZMW legtöbb előnyét, kivéve, hogy a szótári karakterlánckódok több helyet foglalnak el, mivel a szótár jobban fel van duzzadva.

Lásd még

Jegyzetek

↑ 1 2 3 4 5 Welch, 1984 .
↑ 1 2 3 Lempel, Ziv, 1978 .
↑ Arnold, Bell, 1997 .
↑ Bell, Witten, Cleary, 1989 , 3.4.6.
↑ PDF 1.7 specifikáció , 7.4.4.3. szakasz.
↑ 1 2 Bell, Witten, Cleary, 1989 , 3.4.8.
↑ 1 2 Bell, Witten, Cleary, 1989 , 3.4.9.
↑ 1 2 3 4 Ziv, 2015 .
↑ 12 Sheinwald , 1994 .
↑ De Agostino, Silvestri, 1997 .
↑ De Agostino, Tároló, 1996 .
↑ Hucke, Lohrey, Reh, 2016 .
↑ 12 Charikar et al., 2005 .
↑ PDF 1.7 specifikáció , 7.4.4.
↑ Webes áttekintés: A PNG NEM GIF! . Letöltve: 2018. október 18. Az eredetiből archiválva : 2022. március 30. (határozatlan)
↑ A Unisys LZW szabadalom és GIF fájlok . Letöltve: 2018. október 18. Az eredetiből archiválva : 2018. október 19. (határozatlan)
↑ Unisys GIF-szabadalmak érvényesítése - Slashdot . Letöltve: 2018. október 18. Az eredetiből archiválva : 2018. október 18.. (határozatlan)
↑ Miller, Wegman, 1985 .
↑ Tároló, 1988 .

Irodalom

Arnold R., Bell T. Korpusz veszteségmentes tömörítési algoritmusok kiértékeléséhez // IEEE Data Compression Conference. - 1997. - S. 201-210 . - doi : 10.1109/DCC.1997.582019 .
Bell T. , Witten IH , Cleary JG Modellezés szövegtömörítéshez // ACM Computing Surveys . - 1989. -T. 21,4. sz. –S. 557–591. doi:/76894.76896.
Charikar M., Lehman E., Lehman A., Liu D., Panigrahy R., Prabhakaran M., Sahai A., shelat a. A legkisebb nyelvtani probléma // IEEE Transactions on Information Theory . - 2005. - T. 51 , 7. sz . - S. 2554-2576 . - doi : 10.1109/TIT.2005.850116 .
De Agostino S., Silvestri R. Az LZ2 tömörítési algoritmus legrosszabb eset elemzése // Információ és számítás . - 1997. - T. 139 , 2. sz . – S. 258–268 . - doi : 10.1006/inco.1997.2668 .
De Agostino S., Storer JA On-line versus off-line számítás dinamikus szövegtömörítésben // Information Processing Letters . - 1996. - T. 59 , 3. sz . – S. 169–174 . - doi : 10.1016/0020-0190(96)00068-3 .
Hucke D., Lohrey M., Reh CP A legkisebb nyelvtani probléma újragondolva // String Processing and Information Retrieval (SPIRE). - 2016. - T. 9954 . — 35–49 . - doi : 10.1007/978-3-319-46049-9_4 .
Lempel A. , Ziv J. Egyedi szekvenciák tömörítése változó sebességű kódolással // IEEE Transactions on Information Theory . - 1978. - T. 24 , 5. sz . – S. 530–536 . - doi : 10.1109/TIT.1978.1055934 .
Miller V. S , Wegman MN Variációk egy témára, Ziv és Lempel // Kombinatorikus algoritmusok szavakon. - 1985. -T. 12. –S. 131–140. -doi:10.1007/978-3-642-82456-2_9.
Sheinwald D. A Ziv-Lempel bizonyítékról és a kapcsolódó témákról // Proceedings of the IEEE . - 1994. - T. 82 , 6. sz . – S. 866–871 . - doi : 10.1109/5.286190 .
Tároló JA Adattömörítés: Módszerek és elmélet. - New York, USA: Computer Science Press, 1988. - 413 p. - ISBN 0-7167-8156-5 .
Welch TA Nagy teljesítményű adattömörítési technika // Számítógép. - 1984. - V. 6 , 17. sz . — P. 8–19 . - doi : 10.1109/MC.1984.1659158 .
Ziv J. Az LZ78 korlátozott szótári változata aszimptotikusan eléri a véges állapotú tömöríthetőséget egy torzítás mértékével // IEEE Information Theory Workshop. - 2015. - S. 1–4 . - doi : 10.1109/ITW.2015.7133077 .
Adobe Systems Inc. Dokumentumkezelés – Hordozható dokumentumformátum – 1. rész: PDF 1.7 . PDF 1.7 specifikáció . Adobe (2008. július 1.). Hozzáférés időpontja: 2018. január 26.

Tömörítési módszerek

Elmélet

Információ	Saját Kölcsönös Entrópia Feltételes entrópia Bonyolultság Redundancia
Egységek	Bit Nat Rágcsál Hartley Hartley képlet

Veszteségmentes

Entrópia tömörítés	Aszimmetrikus számrendszerek Huffman algoritmus Adaptív Huffman algoritmus Shannon-Fano algoritmus Shannon algoritmusa Aritmetikai kódolás ( intervallum ) Golomb kódok Delta Univerzális kód Elias fibonacci
Szótári módszerek	RLE Kienged LZ ( LZ77/LZ78 LZSS LZW LZWL LZO LZMA LZX LZRW LZJB LZT LZ4 Brotli zstandard )
Egyéb	RLE CTW BWT MTF PPM DMC

Hang

Elmélet	Konvolúció PCM Aliasing Mintavétel Kotelnyikov tétele
Mód	LPC LAR LSP WLPC CELP ACELP Törvény μ-törvény ADPCM MDCT Fourier transzformáció Pszichoakusztikus modell
Egyéb	Audio kompresszor Beszédtömörítés Sáv kódolás

Képek

Feltételek	színtér Pixel Telítettségi részmintavétel Tömörítési műtermékek
Mód	RLE DPCM fraktál hullámocska EZW SPIHT LP PrEP PCL
Egyéb	Bitráta Szabványos tesztkép PSNR Kvantálás

Videó

Feltételek	Videó jellemzői Keret Keret típusok Videó minőség
Mód	Mozgáskompenzáció PrEP Kvantálás hullámocska
Egyéb	Videokodek Sebesség-torzítás elmélet CBR ABR VBR

Archív formátumok
Csak archiválás	ar cpio DAR shar kátrány LBR
Csak tömörítés	bzip2 tömörítés gzip LZMA LZW lzop rzip S.Q. XZ
Archiválás és tömörítés	7z ACB ÁSZ ÍV ALZip ARJ Szekrény cpt dd DGCA dmg GCA kgb LHA LZX PAQ PRS RAR qda sit SQX xar állatkert postai irányítószám
Szoftver csomagolás és forgalmazás	apk deb pkg drágakő FORDULAT MSI BEFŐTTES ÜVEG HÁBORÚ RAR (Java) FÜL