Projekty a zdrojové kódy - Jihočeská univerzita
Řešení v prologu
Nebudu zde rozebírat celý program a každý predikát co znamená. Myslím, že jsem predikáty dosti okomentoval v samotném zdrojovém kódu a proto se zaměřím hlavně na 3 hlavní predikáty a to:
× loadFile(NameOfFile).
× makeCompression(String).
× engine(Chars,I).
Algoritmus LZW kompresní metody je právě obsažen v predikátech makeCompression/1 a engine/2.
Popis predikátu loadFile(NameOfFile).
loadFile(NameOfFile):-
see(NameOfFile),
repeat,
get0(ASCIIChar),
not helpPrint(ASCIIChar),
ASCIIChar = (-1),
!,
seen.
Predikát loadFile/1 má jeden parametr a to NameOfFile. NameOfFile je jméno souboru s textem, který si přejeme komprimovat. Abychom mohli číst ze souboru, musíme použít predikát see/1. Ten nám přepdne vstupní zařízení z klávesnice na soubor (stream).
Následuje smyčka repeat, která se vykonává, dokud jsou všechny podmínky splněny a když jsou podmínky splněny, tak dojdeme ažk řezu !. Po smyčce přepneme vstupní zařízení zpět na klávesnici.
Smyčka tedy načte každý znak ze streamu pmocí predikátu get0/1. Znak má ale podobu ASCII kódu a tak když ho chceme vypsat na obrazovku, musíme znak převést z ASCII kódu na klasický znak. O to se stará predikát helpPrint/1. Je negován kvůli smyčce, aby byl vždy úspěsný. Smyčku zastavíme až když se ASCII znak rovná mínus jedné (-1). Tedy hodnotě, která reprezentuje konec streamu.
Popis predikátu makeCompression(String).
makeCompression(String):-
stringToASCIIChars(String,Chars),
makeDictionary,
nl,
write('LZW code for input string: '),
nl,
engine(Chars,128),
!.
makeCompression(String):-
retractall(replace(_,_)).
stringToASCIIChars(String,Chars):-
atom_chars(String,ASCIIChars),
aSCIICharsToChars(ASCIIChars,Chars).
aSCIICharsToChars([],[]):-!.
aSCIICharsToChars([H|T],[H1|T1]):-
atom_chars(H1,[H]),
aSCIICharsToChars(T,T1).
Predikát makeCompression/1 má jeden parametr String. String je řetezec znaků, tedy text, který budeme komprimovat. Abychom mohli text komprimovat, musíme ho rozsekat na jednotlivé znaky.
K tomu použijeme predikát stringToASCIIChars/2. Vestavěný predikát atom_chars/2 převede celistvý text na seznam jednotlivých znaků, ale znaky jsou v seznamu v ASCII podobě a tak si je ještě převedeme na klasické znaky. K tomu nám dopomůže predikát aSCIICharsToChars/2.
aSCIICharsToChars/2 již využívá rekurze, aby se poršel celý seznam znaků. Pokud převádíme prázdný seznam ASCII znaků, tak vznikne prázdný seznam klasických znaků a proto je to také zastavovací podmínka rekurze. Řez říká, že již nemá cenu pokračovat. Pokud ovšem seznam ASCII znaků není prázdný, tak vždy vezmeme první ASCII znak ze seznamu a převedeme ho na klasický znak. Pak rekurzivně zalováme predikát aSCIICharsToChars/2 na zbytek zeznamu.
Po těchto převodech se vrátíme do predikátu makeCompression/1 a vytvoříme základní slovník znaků - makeDictionary. Vypíšeme na obrazovku, že již příjde výsupní kód. O to se již postará predikát engine/2. Viz dále.
Pokud budou podmínky predikátu makeCompression/1 neúspěšné, tak se volá její bratříček makeCompression/1, který pomocí vestavěného predikátu retractall/1 smaže všechny položky slovníku. Podmínky jsou neuspěšné právě když je engine/2 neúspěšný, což značí konec komprese.
Popis predikátu engine(Chars,I).
engine([],I):-!.
engine(Chars,I):-
findall(Number,sublist(Chars,Number),List),
maximum(Code,List),
write(Code),
write('-'),
replace(Code,Value),
concatenation(Value,NewChars,Chars),
addCodeValue(Value,Chars,Result),
assertz(replace(I,Result)),
I1 is I + 1,
engine(NewChars,I1).
Predikát engine/2 je opět rekurzí. Pokud je seznam znaků prázdný, nemáme z čeho stavět slovník ani co komprimovat a tak i řezem rekurzi zastavíme.
Pokud ovšem existuje seznam znaků, můžeme konečně začít s LZW kompresí. Pro lepší přehlednost si kompresi rozdělíme do několika kroků:
1) Najít podseznamy (reprezentované čísly) pro první znaky celého řetězce.
Tyto podseznamy nám vyhledá predikát sublist/2 a také jim přiřadí čísla podle slovníku. Abychom si pomatovali vsechny číslo podseznamů, použijeme vestavěný predikát findall/3.
2) Najít největší číslo ze seznamu čísel
Z minulého kroku tedy máme seznam čísel reprezentující jednotlivé podseznamy. Také víme, že čím větší číslo, tím novější podseznam (položka) ve slovníku. Neplatí to pro podseznam složený pouze z jednoho znaku. Ale tuto skutečnost můžemem pominout. A tak začneme hledat největší číslo v seznamu a to pomocí predikátu maximum/2 (bubbleSort/2).
3) Vypíšeme kód
Vestavěný predikát write/1 vypíše právě kód podseznamu s největším číslem (klíčem). Můžeme tedy konstatovat, že naše číslo = klíč v seznamu = kód pro podseznam.
4) Ke klíči si zpětně najdeme podseznam
Víme tedy klíč k hodnotě, co již byla komprimována. Predikátem replace/2 si ke klíči zpětně zjistíme hodnotu pro klíč ze seznamu, tedy podseznam.
5) Smažeme podseznam
Podseznam je začátek celého řetezce znaků a tak ho můžeme (musíme) odstranit, jelikož už byl zkomprimován a tak dostaneme nový seznam znaků. Teď tedy bude kratší o smazaný podseznam. K mazání jsem použil predikát pro rozdělování či spojování seznamů - concatenation/3.
6) Vytvoření nové položky slovníku
O to se postará predikát addCodeValue/3. Ten vezme náš podseznam a zjistí následující znak z celkového řetězce. Tento znak dá nakonec podseznamu, címž se vytvoří nový seznam složený právě z podseznamu a daného znaku. Tento celek pak bude nová položka ve slovníku.
7) Přidání položky do slovníku
Do slovníku pomocí vestavěného predikátu assertz/1 vložíme položku na konec slovníku. Tu jsme si zjistili v minulém bodě. Zde se také dostáváme k tajemnému I. I je pomocná proměnná typu integer, která se inkrementuje každým průchodem rekurzí. I je na začátku instanciováno na číslo 128, tedy první volné číslo v ASCII tabulce. Slouží nám jako kód (klíč) pro hodnotu ukládanou do slovníku.
7) Rekurze
Zavoláme opět predikát engine/2, ale tentokrát s novým seznamem znaků. Samozřejmě s tím kratším, co nám zbyl po odmazání v kroku 5). Takto se postupně dostaneme ke konci, kdy už nebude v seznamu znaků žádný znak a komprese tak bude dokončena.