Slovníkové kódovanie

Úvod

Slovníkové kódovanie nie je založené, tak ako Huffman alebo aritmetické kódovanie, na štatistickom modeli. Tu je symbol alebo reťazec symbolov, ktoré vysiela zdroj, reprezentovaný indexom v slovníku. Tento slovník bol vytvorený na základe zdrojovej abecedy. Existuje veľa príkladov slovníkov, ktoré používame v dennom živote bez toho, aby sme si to uvedomili. Napríklad slovo September je reprezentované v slovníku mesiacov číslom , a iné.

Slovník pozostáva z dvoch prvkov definovaných ako , kde je konečná množina fráz generovaná zo zdrojových symbolov, je funkcia mapujúca na množinu kódových slov. Hovoríme, že množina je kompletná, ak akýkoľvek vstupný reťazec sa dá reprezentovať sériou fráz z množiny . Funkcia musí spĺňať podmienku prefixovosti. Pre dekompresiu ľubovoľného textu musí platiť, že množina fráz musí byť kompletná a funkcia spĺňať podmienku p refixovosti.

Najdôležitejšia pri tejto metóde je teda tvorba slovníka. Zle vytvorený slovník môže viesť k expanzii dát, čo je pri kompresii nevhodný jav.

Statický kódový slovník

V niektorých aplikáciách, kde je známa zdrojová abeceda, početnosť výskytov znakov zdrojovej abecedy, prípadne iné vedomosti o zdroji, je vhodné vytvoriť slovník ešte pred samotným procesom kompresie alebo dekompresie. Tento slovník sa potom používa pri oboch týchto procesoch a je verejne známy. Nevýhody spočívajú v nízkej efektivite kódovania a menšej flexibilite oproti dynamickým metódam. Menšia flexibilita znamená, že slovník je vytvorený pre špeciálnu aplikáciu a nie je vhodný na všeobecné použitie.

Dynamický kódový slovník

Druhý spôsob vytvárania slovníka je dynamický. Vtedy neexistuje kompletný slovník pred procesom kompresie alebo dekompresie, ale vytvára sa počas jeho behu. Na začiatku existuje iba základný slovník, ktorý sa počas behu modifikuje. Všetky algoritmy, založené na dynamickej (adaptívnej) tvorbe slovníka, sa dajú rozdeliť do práce dvoch ľudí: Liv a Zempel (1977, 1978)