28 - Slovníkové metody (LZ77, LZ78, práce se slovníkem, pohyblivé okno, prodlužování položek).
pondělí 21. května 2018
17:24
Slovníkové metody využívají pro kompresi slovník. Slovník udržuje řetězce symbolů a může být statický nebo dynamický:
Statické slovníky jsou stálé a přípouštějí přidávání řetězců, ale ne vymazávání. 
Dynamické slovníky udržují řetězce, dříve nalezené ve v vstupním a dovoluji přidávat i rušit řetězce při načítání nového vstupu.
Představme si slovník, obsahující řekněme půl miliónu slov (bez jejich definicí). Slovo (řetězec symbolů zakončený mezerou nebo interpunkčním znakem) se načítá ze vstupního toku a pak se prohledává slovník. Když se nalezne shoda, tak se ukazatel do slovníku zapíše do výstupního toku. Jinak se zapíše samotné nekomprimované slovo. (To je příklad logické komprese). Výsledkem je, že výstupní tok obsahuje indexy a prostá slova.
LZ77
Základní myšlenkou této metody (někdy označované LZ1) je použít části dříve načteného vstupního toku jako slovníku. Kodér udržuje nad vstupním tokem okno a nasouvá vstup do tohoto okna zprava doleva tak, jak se kódují řetězce symbolů. Metoda je tedy založena na pohyblivém oknu. Okno je rozděleno na dvě části:
Levá  část se nazývá vyhledávací buffer (search buffer, S). Je to aktuální slovník, který vždy obsahuje symboly, které vstoupily a byly zakódovány v poslední době. Je vyhledávací buffer dlouhý několik tisíc bytů.
Část vpravo je předvídací buffer (look-ahead buffer, L), který obsahuje text, který se bude teprve kódovat. Předvídací buffer je dlouhý pouze několik desítek bytů. 
Příklad:
Text:
←kódovaný text ... [sir sid eastman easily t|eases sea sick seals] ...← text, který se má číst
Kolmá čárka mezi t a e v textu výše reprezentuje okamžitou dělící čáru mezi dvěma buffery. Tedy předpokládáme, že text „sir sid eastman easily t|“ už byl zkomprimován, zatímco text „eases sea sick seals“ se teprve bude komprimovat.
Kodér prohlíží vyhledávací buffer zprava doleva (od konce, odzadu) a vyhledává shodu
s prvním symbolem e v předvídacím bufferu. Jednu najde u symbolu e ve slově easily. Toto e
je ve vzdálenosti (s offsetem) 8 od konce vyhledávacího bufferu. Kodér pak hledá shodu v co
nejvíce symbolech, následujících za těmito dvěma e. V tomto případě se shodují tři symboly
eas, takže délka shody je 3. Kodér pak pokračuje ve zpětném prohlížení a snaží se najít delší
shodu. V našem případě je zde ještě jedna shoda ve slově eastman, s offsetem 16, a má
stejnou délku. Kodér vybere nejdelší shodu, anebo když jsou všechny stejně dlouhé, pak tu
poslední nalezenou, a připraví značku (16, 3, „e“).
LZ77 využívá vnitřního implicitního předpokladu, že vzorky se ve vstupních datech vyskytují blízko u sebe. Datové toky, které tento předpoklad nesplňují, se komprimují špatně. Jinou nevýhodou LZ77 je omezená velikost L předvídacího bufferu. Velikost srovnávaných řetězců je omezená na L – 1, avšak L se musí udržovat malé, protože proces vyhledávání shody řetězců zahrnuje srovnávání jednotlivých symbolů. Velikost S vyhledávacího bufferu je rovněž omezená. Velký vyhledávací buffer umožňuje lepší kompresi, ale kodér se tím zpomaluje, protože vyhledávání trvá déle
LZ78
Metoda LZ78 (někdy se označuje LZ2) nepoužívá žádný vyhledávací buffer, předvídací buffer, ani pohyblivé okno. Místo toho má slovník dříve nalezených řetězců. Tento slovník začíná prázdný (nebo téměř prázdný), a jeho velikost je omezena pouze velikostí poskytnuté paměti. Kodér vysílá značky se dvěma poli (ukazatel do slovníku, kód symbolu).
Jak symboly vstupují a kódují se, řetězce se přidávají do slovníku na pozice 1, 2, a tak dále. Když se ze vstupního toku přečte další symbol x, vyhledává se ve slovníku položka s jednosymbolovým řetězcem x. Když se žádný nenalezne, tak se x přidá do první volné pozice slovníku, a na výstup se pošle značka (0, x). Tato značka indikuje řetězec „prázdný x“ (spojení prázdného řetězce a x). Pokud se položka s x najde, (řekněme na pozici 37), načte se následující symbol y, a ve slovníku se vyhledává dvousymbolový řetězec xy. Když se žádný nenajde, tak se řetězec xy přidá do
následující volné pozice ve slovníku a vyšle se značka (37, y). Tato značka indikuje řetězec
xy, protože 37 je poloha řetězce x ve slovníku. Proces pokračuje, až se dosáhne konce
vstupního toku.
Značky neobsahují délku řetězce, protože to vyplývá ze slovníku. Každá značka odpovídá řetězci vstupních symbolů, a poté, co se značka zapíše do komprimovaného toku, přidá se tento řetězec do slovníku. Doposud se ze slovníku nic nevymazalo, což je oproti LZ77 jednak výhoda (protože budoucí řetězce se mohou komprimovat i pomocí řetězců nalezených ve vzdálené minulosti), jednak nevýhoda (protože slovník má tendenci rychle růst a zaplnit celou určenou paměť).
Slovník nemusí být nutně prázdný, ale je možné jej předem inicializovat (například položkamis  jednotlivými symboly). Obvykle se pro uložení slovníku používá stromová strukura. 
Notes*
Kdo me primarne zkousel: Drábek
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Začal sem sám. Popsal statický a dynamický slovník (rozdíly, tokeny ...). Drábek řekl ať popíšu LZ77 a 78. První (77), okno (look ahead buffer x search buffer), jak vypadaji tokeny, princip komprese a rozdíl délek mezi oběma částmi okna. Občas sem se zasekl a na chvilku zapřemýšlel, abych to řekl dobře. Drábek přikyvoval. Druhá (78), rozdíl slovníku oproti první, princip komprese, že slovník je na začátku prázdný, atd. Chtěl vědět co je ve slovníku. Dál se zeptal jakou strukturu má slovník - strom. Poslední otázky sem čekal, neboť sem je viděl zde na fitušce. Ptal se, jestli musí být slovník na začátku prázdný. Odpověděl sem, že ho můžeme nainicializovat pro zlepšení počátečního vyhledávání symboly nějaké abecedy. Jaké? ASCII. Řekl že mu to stačí a konec (díky fituško). Celkově za A. 
From <[link]> 
Kdo me primarne zkousel: Balík Miroslav, Ing., Ph.D.
Co jsem k tomu rekl(a)/na co se ptali/co mne vytkli:
Trosku pre mna necakana otazka od neho, na papieriku som mal len slovnikove metody, nic viac. Vravim si, hm, ako sa len volali. Clovek sa to uci podla tych otazok a stane sa, ze zabudne si zapamatat ten nazov tych metod - cakal som ze budu napisane alebo dostanem ten papier s otazkami. Tak som zacal obecne, co je to kompresia, co chceme tym ziskat, co su to slovnikove metody - staticky/dynamicky slovnik. Aky je rozdiel, kedy sa z neho vymazava a pod. Ked uz ho to prestalo bavit pocuvat, tak mi vravi ze v otazkach mame LZ77 a LZ78 tak nieco o nich. Tak som zacal, potom sa ma spytal ci je to symetricka kompresia/dekompresia a co to znamena. Tak som vysvetlil a ze staci. 
From <[link]> 
Vysněná otázka, chtěl jsem bez přípravy začít mluvit, ale radši jsem si chvilku odpočnul (ta minuta najednou běžela strašně pomalu). Nemohl jsem se vymáčknout, jak začít, a tak jsem skočil hned k LZ77. Popsal jsem okno, napsal jsem příklad, jak vypadá záznam pro první písmeno a jak pro nějaký další. Drábek se ptal, jak velké to okno je. Řekl jsem, že jak si zvolíme. Chtěl víc - tak ne moc velké, aby se dlouho nevyhledávalo, ani malé, aby se něco našlo. Ještě jsem řekl, že asi ideálně 2^n. Zazvonil budík, a tak jsme ještě přešli na LZ78. Řekl jsem, že tam není okno a začíná se z prázným slovníkem. Prej ale podle verze a ne vždy, tak chtěl vědět, čím iniciačně naplníme slovník. Motal jsem se kolem toho co chtěli slyšet, vymejšlel jsem, že nejčastějšími dvojicemi a trojicemi v jazyku, ale chtěli slyšet, že 256 znaky z ASCII tabulky. Švéda většinu času poslouchal a na Drábka přikyvoval.
Nebyl to nejlepší výkon, ale měl jsem pocit, že jsem mu řekl skoro všechno. Když se na něco ptal, chtěl to (trošku nekompromisněji) slyšet. Jednou jsem se i snažil zamluvit jeho dotaz a s trošku zvýšeným hlasem chtěl, ať se vrátím k otázce.
Čas otázky: celkem 6 minut.
Zrovna tuhle otázku jsem věděl, dal bych si za výkon c, proto mě docela překvapilo E.
From <[link]> 