========================================= Kompresni metoda LZW - navrh implementace ========================================= Autor: Jan Outrata, student UP OL, obor Informatika email: outrataj@phoenix.inf.upol.cz Datum: 1. 2. 1999 --------------------------------------------------- LZW je slovnikova kompresni metoda, kterou vymysleli panove Lempel, Ziv a Welch v roce 1978, a je to asi nejznamejsi implementace metody LZ78. Algoritmus teto metody je takovy, ze se nahrazuji jiz vyskytnute retezce znaku ze souboru urcitymi kody. Kompresni pomer teto metody neni nejlepsi (asi o 30% horsi nez u nejlepsich komprimacnich programu, v nejhorsim pripade je vystupni soubor o 25% vetsi nez vstupni), ale jeho obrovskou vyhodou je to, ze jeji implementace je velmi rychla a snadno resitelna! Timto je tato metoda urcena hlavne pro kompresi a dekompresi v realnem case, proto jeji nejvetsi vyuziti je u formatu prenosu dat v sitich (pr. formaty u modemu), ale je pouzita tez v obrazovych formatech GIF a TIFF nebo u postscriptu. "Rodicovska" metoda LZ78 je pouzita u kompresnich programu PKARC, PAK a PKZIP (starsi verze). Implementace ============ Inicializace slovniku komprese a dekomprese: -------------------------------------------- Index frazi ve slovniku od nuly. Na zacatku (novy slovnik) jen fraze = vsechny znaky (jejich pocet = velikost abecedy, pr. 256). Pr. 4 znaky a,b,c,d -> slovnik: fraze index a 0 b 1 c 2 d 3 Komprese: --------- 1. Najit nejdelsi frazi ve slovniku shodnou se vstupem. Jeji index na vystup. Odebrat frazi ze vstupu. 2. Nova fraze - (nalezena fraze + znak na vstupu). Pr. abacdacacadaad krok text vstupu nalezena fraze vystup nova fraze index 1 abacdacacadaad a 0 ab 4 2 bacdacacadaad b 1 ba 5 3 acdacacadaad a 0 ac 6 4 cdacacadaad c 2 cd 7 5 dacacadaad d 3 da 8 6 acacadaad ac 6 aca 9 7 acadaad aca 9 acad 10 8 daad da 8 daa 11 9 ad a 0 ad 12 10 d d 3 Dekomprese: ----------- 1. Ze vstupu cislo, odpovidajici fraze na vystup. 2. Nova fraze - (odpovidajici fraze minuleho kroku + 1. znak odpovidajici fraze tohoto kroku). Jestli cislo fraze ze vstupu = (max (maximalni pouzity index ve slovniku) + 1) -> vystup = (minula odpovidajici fraze + jeji prvni znak) = nova fraze. Pr. 0102369803 krok vtup vystup nova fraze index 1 0 a 2 1 b ab 4 3 0 a ba 5 4 2 c ac 6 5 3 d cd 7 6 6 ac da 8 7 9 aca aca 9 8 8 da acad 10 9 0 a daa 11 10 3 d ad 12 Ulozeni slovniku komprese: -------------------------- Model: Strom - z korene [velikost abecedy] znaku. Z kazdeho znaku 2 vetve - prvni nasledovnik znaku ve frazi (nasledovnik) a dalsi znak vychazejici z tehoz rodicovskeho znaku (soused). Pr. koren ----------------- | | | | a0 b1 c2 d3 | | | | b4-c6-d12 a5 d7 a8 | | a9 a11 | d10 Implementace: Tabulka - index radku = index fraze. 1. sloupec - znaky v ohodnocenich uzlu ve stromu 2. sloupec - index nasledovnika 3. sloupec - index souseda Pr. index znak nasledovnik soused 0 a 4 1 b 5 2 c 7 3 d 8 4 b 6 5 a 6 c 9 12 7 d 8 a 11 9 a 10 10 d 11 a 12 d Vyhledavani v kompresi: ----------------------- Znak ze vstupu = znak z korene, index nasledovnika ve 2. sloupci -> jdu tam, znak na tomto radku - jestlize to neni dalsi znak ze vstupu, jdu na radek = index souseda ze 3. sloupce. Opakuji, dokud neni nasledovnik ani soused. Navstivene znaky = fraze. Pr. acab.... vstup nalezena fraze a c a b aca Vytvareni slovniku komprese: ---------------------------- Index nalezene fraze, nasledovnik ve 2. sloupci - neni tam -> dam tam index nove fraze, je tam -> jdu tam, soused ve 3. sloupci - neni tam -> dam tam index nove fraze, je tam -> jdu tam a znova (soused). Na radek = index nove fraze dam do 1. sloupce znak ze vstupu, do 2. a 3. sloupce nic. Ulozeni slovniku dekomprese: ---------------------------- Tabulka - index radku = index fraze. 1. sloupec - znaky jako v tabulce komprese 2. sloupec - index predchudce Pr. index znak predchudce 0 a 1 b 2 c 3 d 4 b 0 5 a 1 6 c 0 7 d 2 8 a 3 9 a 6 10 d 9 11 a 8 12 d 0 Vyhledavani v dekompresi: ------------------------- Cislo ze vstupu = index fraze, pokud (index fraze < velikost abecedy) konec, jinak jdu na predchudce. Opakuji, dokud neni predchudce (tj. index < velikost abecedy). Navstivene znaky = fraze v opacnem poradi, ulozit na zasobnik. Ze zasobniku - vystup. Pr. 10 vstup nalezena fraze v opacnem poradi nalezena fraze 10 daca acad Vytvareni slovniku dekomprese: ------------------------------ Na radek = index nove fraze do 1. sloupce dam 1. znak odpovidajici fraze tohoto kroku nebo 1. znak odpovidajici fraze minuleho kroku (viz. bod Dekomprese) a do 2. sloupce dam index odpovidajici fraze minuleho kroku. Preteceni slovniku: ------------------- 1. Dal ho nezvetsuju a necham ho byt (tj. od ted je staticky) -> od ted mala komprese. 2. Jedu zase s novym a na vystup informace o novem slovniku (znak [velikost abecedy], pr. 256), dekompresor ji nacte a zrusi svuj slovnik taky -> mnohem lepsi komprese nez 1., rychlost nezmenena (inicializace slovniku??! - to nic netrva!). 3. Vyradim nejdele nepouzite fraze. Musim vest informace o frazich ve slovnicich (pr. kolikrat byly pouzity) -> lepsi komprese nez 2., ale znatelne zpomaleni (zjistovani, ktere fraze vyradit). - ja jsem pouzil ve sve implementaci 2. Konec komprese souboru: ----------------------- Informace pro dekompresor (znak [velikost abecedy + 1], pr. 257), nacte ji a konci. Ulozeni indexu fraze: --------------------- 1. [Cela cast logaritmu o zakladu 2 z [Max. index ve slovniku] + 1] = pocet bitu pro ulozeni indexu. 2. Na zacatku (novy slovnik) staci pro ulozeni indexu 9 bitu. Jakmile index > 511 -> 10 bitu atd. Informace o zmene bitove delky pro dekompresor (znak [velikost abecedy + 2], pr. 258), nacte ji a zmeni bitovou delku na vstupu. - ja jsem pouzil ve sve implementaci 2. A to je vse! Dotazy a pripominky: adresa (email) - outrataj@phoenix.inf.upol.cz