GLAVNI PROBLEM je bio Lempel-Ziv kodiranje (ne ne, nemojte odmah da bjezite, citajte dalje).
- Prosto OBJASNJENJE za LZ kodiranje bilo bi sledece (za one koji nisu upuceni):
LZ kodiranje je u stvari oblik kompresovanja, fajlova, teksta… cega god hocete.
- Sada jedan KRATAK PRIMJER:
Imamo jedan string, npr. '101100' koga zelimo da smanjimo (tj. kompresujemo)…
LZ kodiranje koristi rjecnik za to, evo kako:
Prva cifra u stringu odnosno cifra 1 se nije pojavljivala ranije u stringu, zato je stavljamo na poziciju 1 (ne na 0, vec na poziciju 1, objasnicu kasnije zasto) tj.
_|LZ kod
0|null
1|1
2|
3|
…
Sada uzimamo drugu cifru iz stringa tj. 0. Vidimo da se ni ona nije pojavljivala ranije (prije nje je bila samo jedinica). Dakle, nulu stavljamo na poziciju 2 u rjecniku tj.
_|LZ kod
0|null
1|1
2|0
3|
…
E SADA, uzimamo sa trece pozicije, cifru 1. Vidimo da se ona vec pojavljivala (imamo je vec na prvoj poziciji), pa ovoj (trecoj) jedinici dodajemo sledeci karakter stringa (posle trece jedinice imamo opet 1) i taj string stavljamo u rjecnik tj.
_|LZ kod
0|null
1|1
2|0
3|11
…
Ovako se radi do kraja stringa (naravno)
KRAJ PRIMJERA
- Trudio sam se, kao sto vidite, da sto jednostavnije obasnim LZ kodiranje.
Ja treba da napisem kod za KODIRANJE ali i za DEKODIRANJE takvih stringova.
Evo dokle sam ja stigao (kod za kodiranje):
def lz(sekvenca):
""" Vraca LZ KOD binarne sekvence koju unesemo. """
rjecnik = []
rijec = ''
for karakter in sekvenca:
rijec += karakter
if rijec not in rjecnik:
rjecnik.append(rijec)
rijec = ''
print rjecnik
print 'Velicina rjecnika je '
return len(rjecnik)
Evo neka prvo pitanje bude: Meni je potrebno da, ukoliko postoji tzv. ULAZNI RJECNIK, na prve dvije pozicije budu 0 i 1, a da kod pocinje da smjesta slogove u rjecnik od pozicije 2. U slucaju da nema ulaznog rjecnika na prvu poziciju treba da postavim rijec ‘null’. HUH!!
Unapijed se zahvaljujem!