 _____                        _____
|  __ \                      / ____|
| |  | | ___ _ __ ___   ___ | |     ___  _ __ ___  _ __  _ __ ___  ___ ___
| |  | |/ _ \ '_ ` _ \ / _ \| |    / _ \| '_ ` _ \| '_ \| '__/ _ \/ __/ __|
| |__| |  __/ | | | | | (_) | |___| (_) | | | | | | |_) | | |  __/\__ \__ \
|_____/ \___|_| |_| |_|\___/ \_____\___/|_| |_| |_| .__/|_|  \___||___/___/
                                                  | |
                                                  |_|
                                                                       v1.1

Kontakt: lenka.smejkalova@gmail.com

# Changelog:
#
# v1.1 (05.09.2008)
# Zmeneno nacitani prikazu
# Pouziti modulu Term::ReadLine::Gnu
# opravena chyba pri dekodovani LZW
# odstranen parametr u LZSS, zda se ma jednoznakova shoda kodovat jako novy znak
# pridano pocitani bitu na zakodovanou zpravu
#
# v1.0 (08.06.2008)
# Initial version


Obsah:

0. Úvod
1. Používání programu
	1.1. Popis příkazů
	1.2. Popis masky
	1.3. Přehled implementovaných metod
2. Přidání nové metody
	2.1. Vytvoření nového modulu
	2.2. Úprava main.pl 
3. Příklad
4. Závěr


0. Úvod

Program DemoCompress názorným způsobem ukazuje, jak fungují některé vybrané kompresní metody. Momentálně je implementováno 6 slovníkových metod, v budoucnosti je možné metody dále přidávat.
Projekt je napsán v Perlu a nemá žádné speciální nároky. Jediným malým problémem by mohla být potřeba modulu Term::ReadKey a Term::ReadLine::Gnu, který nemusí být nainstalován v každé distribuci. Perlivé moduly jsou volně dostupné zde:
http://search.cpan.org/
Konkrétní potřebné moduly pro tento projekt jsou připojeny v balíčku a nebo je naleznete např. zde:
http://search.cpan.org/~hayashi/Term-ReadLine-Gnu-1.17a/Gnu.pm
http://search.cpan.org/~jstowe/TermReadKey-2.30/ReadKey.pm

Dalším možným problémem by mohlo být nesprávné zobrazování diakritiky a proto jsou v balíčku celkem tři verze - iso8859-2, CP1250 a UTF8. Problémy se zobrazováním českých znaků se týkají pouze textů ve zdrojovém kódu (např. se bude nesprávně zobrazovat nápověda, chybové hlášky atd.), zadávání vstupu a jeho následné zobrazování by mělo být bez problémů.


1. Uživatelská dokumentace

Program se spustí souborem main.pl např. 'perl main.pl'. Nepřijímá žádné parametry a po spuštění se chová jako jednoduchá konzole - funguje doplňování příkazů, jejich historie (šipka nahoru), automatické doplňování příkazů (klávesa tab) i možnost pohybu po řádce pomocí šipek . Program nejprve vytiskne dostupné metody, info, jak zobrazit nápovědu a nakonec prompt (">"), což znamená, že očekává příkaz od uživatele. Seznam všech příkazů i se stručným popisem je obsažen v nápovědě a pro úplnost je uveden i zde s případnými dalšími popisky:

1.1. Popis příkazů

? .. zobrazí seznam příkazů se stručným popisem

describe .. s parametrem (id metody nebo její název se zadává jako parametr) vypíše info o metodě (popis algoritmu, popř. poznámky o konkrétní implementaci)
            bez parametru se chová jako 'methods'

exec .. spustí metodu (id nebo název je uveden jako parametr), pokud dosud nebyl zadán řetězec, který se má zakódovat, vyzve nejprve uživatele k jeho zadání. Tento text je poté uložen po celou dobu běhu programu, popř. lze změnit (viz níže).
Nejprve se provede kódovací část, vytiskne se počet bitů, kolik je potřeba na původní a kolik na kódovanou zprávu, poté je uživateli položen dotaz, zda si přeje provést i dekódovací část. Průběh těchto částí ovlivňují parametry encode_mode a decode_mode, které budou popsány samostatně.

exit .. ukončí program

help .. zobrazí seznam příkazů se stručným popisem

input <text> .. zadání nebo změna vstupního řetězce
Je možné zadat s parametrem (text) i bez parametru
Na začátku textu nemohou být bílé znaky, délka není omezena. Text bude rozdělen na části (znaky nebo slova) podle použité metody.

methods .. vypíše všechny dostupné metody jako číslovaný seznam, při odkazu na metodu je možno použít její název (case-insensitive) nebo číslo, pod kterým je uvedena v tomto seznamu

print_input .. vystikne zadaný vstupní řetězec nebo info, že ještě nebyl zadán

print_params .. vypíše aktuální hodnoty parametrů

print_mask_info .. vypíše informace o tom, z čeho se skládá maska a jak ji vytvořit (použita u parametrů encode_mode a decode_mode)

quit .. ukončí program

set_mode_dec <mask> .. nastaví masku, která ovlivňuje průběh dekódování.
Maska se zadává jako přirozené číslo. Jak toto číslo vytvořit viz níže.
Pokud je mask 'default', použije se přednastavená hodnota.

set_mode_enc <mask> .. nastaví masku, která ovlivňuje průběh kódování.
Maska se zadává jako přirozené číslo. Jak toto číslo vytvořit viz níže.
Pokud je mask 'default', použije se přednastavená hodnota.

set_params .. spustí proceduru pro změnu nastavitelných parametrů
Uživatel bude postupně dotazován, který parametr chce změnit. Jednotlivé parametry je možné měnit i samostatně.

set_window <param> .. nastaví výchozí velikost okénka (pro metody LZ77 a LZSS)
	pokud je parametr 'default', použije se přednastavená hodnota
	jinak je třeba zadat parametr ve tvaru <P> <B> (P - processed, B - buffer)

version .. zobrazí verzi programu


1.2. Popis masky

Maska slouží k nastavení parametrů, které nabývají pouze pouze hodnot TRUE / FALSE do jednoho parametru.
Každému parametru je v binární reprezentaci přiřazen jeden bit, výsledná maska je dána součtem (or) hodnot parametrů.
Díky tomu je možné předávat několik parametrů jako jeden.
Zde maska sdružuje tyto parametry:
0 .. waiting_mode/no_waiting_mode
1 .. no_silent_mode/silent_mode
2 .. tree_view/no_tree_view
3 .. list_view/no_list_view
Při nastavení waiting_mode se do masky připočítá hodnota 1 (2^0). Kódovací resp. dekódovací proces se bude chovat tak, že po provedení jednoho kroku bude čekat na stisk libovolné klávesy, aby mohl pokračovat dále. Ale pouze v případě, že bude nastavený no_silent_mode (2 = 2^1). Silent_mode znamená, že se nemá nic vypisovat - pak se tedy ignoruje hodnota waiting_mode.
Další dva parametry se uplatňují jen u metod LZ78 a LZW. Pokud je nastaven no_silent_mode, tak po každém kroku algoritmu vypíší slovník jako strom (tree_view) nebo seznam (list_view). Pokud jsou nastaveny oba na kladnou hodnotu, vypíše se strom i seznam.
Pokud je nastaven waiting_mode, tak u těchto metod (LZ78, LZW) se dá vyvolat vypsání slovníku explicitně:
písmeno t pro vypsání slovníku ve stromovém formátu
písmeno l pro vypsání slovníku jako indexovaného seznamu
a písmeno b pro obojí (nejdříve strom, pak seznam)


1.3. Přehled implementovaných metod:

1) LZ77
2) LZSS
3) LZ78
4) LZW
5) BSTW
6) Intervalové kódování



2. Programátorská dokumentace

2.1 Popis funkčnosti programu

Celý projekt je rozdělen na hlavní program 'main.pl' a několik modulů, které odpovídají jednotlivým metodám. Výjimkou je modul Common.pm, který obsahuje užitečné funkce využívané jak v modulech, tak v hlavním programu. Každý modul musí obsahovat čtyři základní funkce - pro kódování a dekódování, výpočet potřebných bitů na zakódovanou zprávu a funkci, která zobrazí nápovědu. Dále může obsahovat libovolné množství pomocných funkcí, které nejsou viditelné mimo modul (neexportují se).

Moduly jsou do hlavního programu zapojeny pomocí struktury %methods, klíč je název metody a hodnotou je další asociativní pole s těmito položkami:
		id .. přidělujeme inkrementálně
		f_encode .. ukazatel na kódovací funkci
		f_decode .. ukazatel na dekódovací funkci
		params .. seznam parametrů
		f_info .. ukazatel na funkci, která vytiskne popis metody
		f_count_bits .. ukazatel na funkci, která zjistí, kolik bitů je potřeba na zakódovanou zprávu

Parametry se medodám předávají právě díky této struktuře, takže v momentě volání de/kódovací funkce je nutné, aby parametry byli již inicializované.

Podporované příkazy jsou obsaženy ve struktuře %commands. Klíčem je název příkazu, hodnotou je asociativní pole s dvěmi položkami:
		func .. ukazatel na funkci, která se má volat při zadání příkazu
		doc .. stručný popis příkazu, který se zobrazuje v nápovědě

Program je tvořen jedním cyklem, ve kterém se vykonávají příkazy, dokud je zadáván nějaký vstup od uživatele. Vstupní řádka je rozdělena na název příkazu a argument, následně se zavolá daná funkce s tímto argumentem. Argument je pouze jeden, v případě potřeby lze parsovat ve volané funkci. Z tohoto důvodu je důležité, aby každý příkaz byl jednoslovný - bez mezer. Pokud funkce příkazu vrátí nenulovou hodnotu, hlavní cyklus bude ukončen.



2.2. Přidání nové metody

Přidání nové metody se skládá ze dvou částí:
1) Vytvořit nový Perlivý modul (každá metoda je v samostatném modulu)
2) Upravit main.pl


2.2.1. Vytvoření nového modulu

Vytvoření nového modulu v Perlu není nijak složité. Lze použít strukturu, která je u ostatních modulů v tomto projektu. V modulu může být libovolné množství pomocných funkcí, důležité je, aby obsahoval tyto čtyři funkce, které budou viditelné i mimo modul:
	print_help_metoda() - pouze vypsání informací o metodě - jak funguje, popř. jak je implementována
	metoda_encode() - kódování
	metoda_decode() - dekódování
	metoda_count_bits - výpočet bitů, kolik je potřeba na zakódovanou zprávu
Viditelnost se zajistí pomocí:
	@EXPORT = qw(&metoda_encode &metoda_decode &print_help_metoda, metoda_count_bits);
Je možné zde používat pomocné funkce z modulu Common.pm pomocí volání "use Common;". Je možné i přidávat další funkce do tohoto modulu. 
Dále by bylo vhodné, aby funkce pro de-/kódování spolupracovaly s de/en-code_mode.


2.2.2. Úprava main.pl 

Po vytvoření Perlivého modulu je zapotřebí ho integrovat do zbytku projektu. Projdeme soubor main.pl od začátku a řekneme, kde všude je třeba co přidat (předpokládáme, že jsme vytvořili nový modul pro metodu LZJ a nazvali ho LZJ.pm):

1) přidat řádek pro includování modulu 
	use LZJ;

2) (optional) Pokud přidávaná metoda vyžaduje nějaký parametr, přidáme jeho inicializaci do části "inicializace parametru"

3) upravit strukturu %methods (hash pole)
	např.:
		'LZJ' => {
			id => 7,
			f_encode => \&lzj_encode,
			f_decode => \&lzj_decode,
			params => [],
			f_info => \&print_help_lzj,
			f_count_bits => \&lzj_count_bits
		},


4) (optional) Pokud jsme přidali nový parametr, bylo by vhodné přidat příkaz, kterým je možné hodnotu parametru upravit (nezapomeňte tento příkaz přidat do struktury %commands), dále by bylo vhodné upravit fce print_params() a set_params().


A pokud jste všechno udělali správně, tak by to mělo fungovat.


3. Příklad

> methods # vypíše seznam metod
Momentálně jsou k dispozici tyto metody:
1 : LZ77
2 : LZSS
3 : LZ78
4 : LZW
5 : BSTW
6 : Interval

> describe lz77 # vypíše info o metodě 

LZ77

Metoda LZ77 (angl. sliding window) využívá okénka o velikosti P+B. První část
o velikosti P obsahuje již zpracovaný text (nazveme ji processed). Po inicializaci
je prázdná. Druhá část (buffer) obsahuje text, který se bude právě zpracovávat.
Na začátku obsahuje začátek vstupu. Jeden krok algoritmu vypadá tak, že se v poli
processed hledá poslední výskyt nejdelšího podřetězce začínajícího na začátku
bufferu. Je povoleno, aby konec tohoto podřetězce zasahoval do bufferu.
Po nalezení se na výstup posílá trojice (posun, počet, znak), kde 'posun' znamená
o kolik znaků se posouváme zpět, 'počet' - kolik znaků se má od této pozice
kopírovat a 'znak' - jaké je další písmeno, které již nebylo obsaženo v podřetězci.
Poté se okénko posune tak, aby 'znak' byl na poslední pozici v poli processed.

Typické hodnoty parametrů jsou P <= 8192, B 10-20, pro demonstraci doporučuji
použít parametry P = 7, B = 3.

> set_window 15 3 # nastaví velikost okénka
new window_size: 15 3

> input prší, prší, jen se leje... # zadání vstupu

> print input # kontrolní vytištění vstupu
Input: prší, prší, jen se leje...

> print_mask_info # vypíše informace o tom, jak vytvořit masku
Maska se zadává jako součet voleb:
    waiting_mode    :  1 (při (de)kódování se bude čekat na stisk klávesy v každém kroku)
    no_waiting_mode :  0
    silent_mode     :  0 (v jednotlivých krocích se nebude nic vypisovat)
    no_silent_mode  :  2
    tree_view       :  4 (pouze u lz78 a lzw - vypsat slovník jako strom po každém kroku)
    no_tree_view    :  0
    list_view       :  8 (pouze u lz78 a lzw - vypsat slovník jako seznam po každém kroku)
    no_list_view    :  0

> set_mode_enc 3 # nastavení masky pro kódování (waiting + no_silent)
new encoding mode: (3) waiting no_silent

> set_mode_dec 3 # nastavení masky pro dekódování (waiting + no_silent)
new decoding mode: (3) waiting no_silent

> exec lz77 # spuštění metody
...

> set_window default # nastaví původní velikost okénka
new window_size: 7 3



4. Závěr

Doufám, že tento jednoduchý prográmek poslouží k lepšímu pochopení implementovaných metod.
V případě, že máte nějaký dotaz, připomínku nebo naleznete chybu, neváhejte napsat na moji e-mailovou adresu: lenka.smejkalova@gmail.com .
