LZ77 - Sliding Window

V tomto algoritme sa ako slovník používa časť vstupného textu, ktorá bola nedávno zakódovaná. Text, ktorý sa kóduje sa porovnáva so symbolmi v slovníku. Najdlhšia nájdená zhoda v slovníku je charakterizovaná pointrom, ktorý pozostáva z trojice dát.

Algoritmus v LZ77 sa nazýva algoritmus posúvania okien. Okno pozostáva z dvoch častí: search bufer(SB) a look-ahead bufer (LAB). V SB je časť textu, ktorá už bola nedávno zakódovaná (bolo povedané, to je náš slovník), LAB obsahuje text, ktorý ideme v nasledujúcom kroku komprimovať. Tieto dva bufre (okná) sa počas procesu komprimácie posúvajú.

Kompresia a dekompresia

Pozrime sa najprv na jeden príklad, ktorý je znázornený na obrázku 3.8. Vstupný text je ikaccbadaccbaccbaccgikmcaib. Na obrázku má SB veľkosť 9 symbolov, LAB 6 symbolov. Pokúsime sa zakódovať symboly, ktoré sa nachádzajú v LAB. Proces začína hľadaním prvého znaku v LAB, teda b v SB odzadu. Prvú zhodu nájdeme na šiestom políčku odzadu. Ďalej zistíme, že najdlhšia zhoda, aká existuje, je dĺžky 2 (ba). Ukazovateľ je potom reprezentovaný trojicou , kde je vzdialenosť prvého symbolu od LAB (táto vzdialenosť sa tiež nazýva ofset), čo je v našom prípade 6. Druhá položka, teda , určuje dĺžku reťazca, ktorý sa zhoduje, teda 2. Tretí symbol je znak, ktorý v LAB nasleduje hneď za zhodujúcim sa reťazcom, teda , kde C je funkcia mapujúca zdrojové symboly na kódové slová. Takže náš triplet po prvom kroku je (obrázok 3.8a).

Dôvod, prečo sa pridáva , je pomerne jednoduchý. V prípade, že sa v SB nenájde žiadna zhoda, potom obe , budú nulové. Tretia položka v tomto prípade ukazuje na prvý symbol v LAB. Keď dekóder dostane trojicu vie, že nebola nájdená žiadna zhoda a dekóduje iba symbol . Tento prípad je znázornený na obrázku 3.8c.

Druhý krok začína tým, že sa obe okná posunú o tri symboly doprava, teda o jeden symbol viac, ako bola v predchádzajúcom kroku nájdená najdlhšia zhoda. Pri hľadaní zhodného podreťazca v SB, nájde prvú zhodu na ofsete 1 s dĺžkou 1. Ďalšia zhoda je na ofsete 4 s dĺžkou 5. Je zaujímavé, že maximálna zhoda môže presiahnuť hranice SB a tým zasiahnuť aj LAB. Prečo môže byť táto situácia akceptovateľná, si vysvetlíme pri dekompresii. Teda dĺžka tejto zhody je 5. Poslednú zhodu nájdeme na offsete 5 s dĺžkou 1. Keďže sa tu používa GREEDY algoritmus, je vybraná druhá zhoda s dĺžkou 5 a jej prislúchajúci triplet (obrázok 3.8a).

V ďalšom kroku sa obe okná posunú o 6 miest doprava. Tento prípad je znázornený na obrázku 3.8c. Tu nie je nájdená žiadna zhoda pre symbol , takže výsledný triplet je .

Komprimačný proces potom pokračuje podobne ďalej. Všetky možné situácie sú popísané v predchádzajúcich troch krokoch. Proces dekompresie je oveľa jednoduchší, pretože tu už netreba hľadať žiadne zhody ani porovnávať dĺžky. Je znázornený na obrázku 3.9.

Obrázok 3.8: LZ77 - kompresia

V časti (a) obrázku 3.9 je SB rovnaký ako v prvej časti dekódovania (3.8 (a)). Je v ňom uložený reťazec , ktorý sme práve dekódovali.

Keď dostaneme na vstup triplet , dekóder sa posunie o 6 znakov doľava. Potom bude ukazovať na , skopíruje dva znaky začínajúc znakom , teda , do LAB. Symbol skopíruje napravo od $ba$. Je to znázornené na obrázku 3.9b. Okná sa potom posunú o tri pozície doprava (3.9c).

Pri sa dekóder posunie o 4 pozície doľava (bude ukazovať na ) a skopíruje 5 znakov. Ako vidíme, na začiatku kopírovania máme k dispozícii iba 4 znaky. Piaty znak dostaneme až počas kopírovania. Všetky znaky, ktoré počas kopírovania vytvoríme, môžu ďalej slúžiť ako symboly na ďalšie kopírovanie. Nakoniec sa skopíruje ešte znak (obrázok (3.9d), a posunie sa o 6 znakov doprava (obrázok (3.9e).

Triplet hovorí, že nebola nájdená žiadna zhoda a iba samotné je dekomprimované (obrázok 3.9f).

Dekompresiou týchto troch tripletov sme dostali , čo je presne ten istý reťazec, ktorý bol pomocou nich v predchádzajúcej časti zakódovaný.

Obrázok 3.9: LZ77 - dekompresia

Záverečné poznámky

Označme si, tak ako už bolo predtým používané, search bufer ako SB, look-ahead bufer ako LAB, a veľkosť zdrojovej abecedy A. Tiež predpokladajme, že používame binárne kódovanie. Prístup LZ77 algoritmu je kódovať postupnosti s rôznou dĺžkou do kódových slov s fixnou dĺžkou. Na ofset použitých bitov, na LAB a na zdrojový symbol .

Pokiaľ sú rozostupy medzi opakujúcimi sa postupnosťami textu príliš veľké, väčšie ako veľkosť oboch bufrov, potom tento algoritmus nie je schopný komprimovať text.

Bolo vymyslených veľa modifikácií tohto algortimu, ktoré ho mali zefektívniť. Jednou z nich je LZSS [4].