Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.

Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?

[es] :: Python :: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?

[ Pregleda: 4132 | Odgovora: 10 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

MixMaster

Član broj: 10076
Poruke: 323
147.91.169.*



+32 Profil

icon Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?29.12.2005. u 15:18 - pre 222 meseci
Posto nisu uspjeli na forumu C/C++ (a na forumu Seminarski radovi niko nije ni pokusao  ) da mi pomognu ni malo sa mojim problemom odlucio sam da potrazim programski jezik koji dobro i prije svega lako barata sa stringovima i slogovima. Naisao sam na Python i odmah mi se dopao. Imam, naravno, jos nekih problema, ali se nadam da ce te mi vi brze odgovoriti na njih.
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):
Code:

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!
Vidi bako, DžEDAJ!
 
Odgovor na temu

vpetrovic
Vladimir Petrovic

Član broj: 57552
Poruke: 8
*.128.



Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?29.12.2005. u 15:39 - pre 222 meseci
Citat:
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!!


Nije mi bas jasno sta tacno pitas. Vrlo je jednostavno dadati nesto na pocetak liste, npr:
Code:
rjecnik = ['null', ] + rjecnik


Problem u tvom kodu je sledeci:
Code:
if rijec not in rjecnik


Naime, python ce tu linearno proci kroz celu listu trazeci rec, sto je neefikasno. U slucaju
da ces imati do nekoliko hiljada razlicitih reci, treba koristiti i jedan "dictionary" za upit (on interno koristi hash tabelu), npr ovako:

Code:

rjecnik = []
rijec = ''
rdict = {}

for karakter in sekvenca:
     rijec += karakter
     if not rdict.get (rijec, None):
         rjecnik.append(rijec)
         rdict [rijec] = 1
         rijec = ''


Umesto da dodeljujes 1, mozes npr. da dodelis poziciju reci. Ako ces imati vise od par hiljada razlicitih reci, hash tabela vise nije efikasna i treba koristiti neku vrstu drveta za cuvanje reci. Koliko se secam, toga nema u standardnoj python biblioteci, ali sigurno moze negde da se nadje.
 
Odgovor na temu

MixMaster

Član broj: 10076
Poruke: 323
147.91.169.*



+32 Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?29.12.2005. u 16:04 - pre 222 meseci
Ne, nece imati vise hiljada rijeci. Trebam samo da kodiram (a poslije i da dekodiram...ali kasnije o tome) string koji ce biti sastavljen od nula i jedinica, nista vise. Mislim da nije potreban dictionary koji si ti koristio. Kod koji sam postovao radi stvar (probaj da ga pokrenes sa lz('10110010'), vidjeces o cemu govorim). Znaci, meni na prvom mjestu u izlazu treba da bude rijec 'null', a od indexa 1 da pocinje kod koji ces ti dobiti pokretanjem na gore navedeni nacin.

Podrav i hvala jos jednom.
Vidi bako, DžEDAJ!
 
Odgovor na temu

MixMaster

Član broj: 10076
Poruke: 323
147.91.169.*



+32 Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?29.12.2005. u 19:07 - pre 222 meseci
Rijesili smo pomenuti problem

Dakle, unijeli smo
LZkodiranje('101100',)

Dobijamo
rjecnik = ['1', '0', '11', '00']

Znaci, dobili smo rjecnik...sada treba procitati u mom prvom postu sta se radi dalje nakon ovoga, da ne dupliram.

p.s. Podrzava li Pythonn visedimenzionalne nizove? Pitam, jer u koliko kao uslov unesemo da mi se rjecnik resetuje (opet krene od indexa 0) zelim da nove slogove upisujem u sledeci red!?
Vidi bako, DžEDAJ!
 
Odgovor na temu

vpetrovic
Vladimir Petrovic

Član broj: 57552
Poruke: 8
*.com
Via: [es] mailing liste



Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?31.12.2005. u 09:38 - pre 222 meseci
Dakle, vrlo je jednostavno dodati nesto na pocetak liste npr. sa:
Code:
 lista  = ['nesto',] + list 


Visedimenzionalni niz bi se u pythonu predstavio kao lista listi, npr:
Code:

l = [[], []]
l [0].append (1)
l.append ([1, 2, 3])
print l [0] [0]
print l [2][2]

ovo ce stampati 1 i 3. Koristeci prethodni primer mozes lako dodati listu na
pocetak liste.
 
Odgovor na temu

boskom
srb

Član broj: 31456
Poruke: 17
*.net
Via: [es] mailing liste



+1 Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?31.12.2005. u 11:29 - pre 222 meseci
Metod (atribut) kojim se objekat ubacuje u listu je insert
Code:

lista.insert(pozicija,objekat)
#umetanje na pocetak
lista.insert(0,objekat)

To je ono sto hoces da uradis.
Ako bi zeleo da trecu listu dobijes nadovezivanjem dve onda
bi pisao npr.:
Code:
 lista3  = lista1 + lista2 

Ovaj pristup je vise od deset puta sporiji od insert kada se
koristi za ubacivanje elementa na pocetak liste, i sto su liste
vece sve je sporiji.
 
Odgovor na temu

MixMaster

Član broj: 10076
Poruke: 323
147.91.169.*



+32 Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?01.01.2006. u 18:02 - pre 222 meseci
OK, hvala na predlozima. Isprobacu ovo sto ste predlozili pa cu vam javiti u naredna dva dana.

Pozdrav.
Vidi bako, DžEDAJ!
 
Odgovor na temu

MixMaster

Član broj: 10076
Poruke: 323
147.91.169.*



+32 Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?07.01.2006. u 21:43 - pre 221 meseci
Shvatio sam visedimenzionalne nizove. Hvala na objasnjenjima.
Sledeci problem...
Izlaz programa koji sam ja napisao je
Code:

indeks = [0, 1, 2, 3]
rjecnik = ['0', '1', '01', '10']

dakle, svaki clan rjecnika ima svoj indeks.
Problem je sto sada treba da napravim petlju koja uzima samo poslednju cifru clana rjecnika i gledamo sta se nalazi ispred njega. Na kraju treba da ispadne (ako nam je sekvenca koju rastavljamo '010110')...
Code:

0, 0 (sa desne strane zareza je nula tj nas prvi clan niza...prije njega nemamo nista)
0, 1 (...)
0, 1 
1, 0 (poslednji clan je '10', uzimamo nulu...ispred nje je 1...indeks...JEDINICA U RJECNIKU JE NA POZICIJI 1 CIJI JE INDEKS 1, koji pisemo sa lijeve strane zareza)

Prosto je...ali je moguce da sam ja zakomplikovao malo stvar svojim objasnjenjem.

Zahvaljujem i pozdravljam.
Vidi bako, DžEDAJ!
 
Odgovor na temu

boskom
srb

Član broj: 31456
Poruke: 17
*.net
Via: [es] mailing liste



+1 Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?08.01.2006. u 00:29 - pre 221 meseci
Nisi jasno rekao koji algoritam treba da implementiras
Lempel Ziv 78 ili Lempel Ziv Welch. To sto si dosada
objasnjavao verovatno je LZ78 (dakle jednostavnija verzija).
Dekodiranje je jednostavnije od kodiranja. Iz kodera
dobijamo parove (kod,znak). Ovde treba reci da ne saljemo
recnik vec ga prilikom dekodiranja formiramo i on ce biti
identican onom na strani kodera. U paru (kod,znak) kod je
redni broj elementa iz 'recnika' ('recnik' nije tipa
dictionary vec je to lista).
Jos jedna glupava stvar u tvom primeru koja buni je sto su
kod tebe kod i znak iz istog skupa {'0','1'}. Preglednije je
iako saljes binarnu sekvencu da je oznacis kao 'ABABBA'

Izlaz tvog kodera je:
Code:

indeks = [0, 1, 2, 3]
rjecnik = ['0', '1', '01', '10']


U Python-u je suvisno vuci pored liste i listu njenih
indexa. Ako kroz listu iteriras a trebaju ti i indeksi to
moze ovako da se napise:
Code:

for i,x in enumerate(l):
    print i,x
    # x = l[i]

Tvoj rjecnik u koderu bi trebao ovako da izgleda:
Code:

rjecnik = ['','A','B','AB','BA']

I sam si u nekom od prethodnih postova napisao da u recnik
pocinjes da upisujes od pozicije 1, a ne 0.

Izlaz iz tvog kodera bi trebao da bude ovakav:
(0,'A')
(0,'B')
(1,'B')
(2,'A')

dekoderu saljemo sledecu listu:
[(0,'A'), (0,'B'), (1,'B'),(2,'A')]

Ovde se koristi tip podataka 'tuple' koji se oznacava oblim
zagradama ( ) i predstavlja listu ciji se sadrzaj ne moze
menjati, ako te to trenutno buni mozes bez problema
koristiti i liste tj [ [1,'A'], ... ].

Code:

def lz78_dekoder( ulazna_sekvenca ):
    recnik = ['']
    for kod,znak in ulazna_sekvenca:
        rec = recnik[kod] + znak
        recnik.append( rec )
    #sada od liste reci pravimo izlazni string
    # ''.join( ['a','b','c'] ) -> 'abc'
    return ''.join( recnik )


Dekodirana sekvenca je :'ABABBA'


[Ovu poruku je menjao boskom dana 08.01.2006. u 13:26 GMT+1]
 
Odgovor na temu

boskom
srb

Član broj: 31456
Poruke: 17
*.net
Via: [es] mailing liste



+1 Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?08.01.2006. u 12:19 - pre 221 meseci
Tu su i koder i dekoder. Nadam se da je to ono sto si
mislio.
Code:

def lz78_koder( ulaz ):
    '''Koduje niz karaktera pomocu LZ78

    znak - Osnovni element ulaznog toka
    ulaz - lista znakova
    '''
    recnik = ['']
    prefiks = ''
    izlaz_kodera = []
    for znak in ulaz:
        if (prefiks + znak) in recnik:
            prefiks += znak
        else:
            recnik.append( prefiks + znak )
            kod_prefiksa = recnik.index( prefiks )
            izlaz_kodera.append( ( kod_prefiksa, znak ) )
            prefiks = ''
            
    if prefiks:
        kod_prefiksa = recnik.index( prefiks )
        izlaz_kodera.append( ( kod_prefiksa, '' ) )
    return izlaz_kodera
            
def lz78_dekoder( ulazna_sekvenca ):
    print ulazna_sekvenca
    recnik = ['']
    for kod,znak in ulazna_sekvenca:
        rec = recnik[kod] + znak
        recnik.append( rec )
    #sada od liste reci pravimo izlazni string
    # ''.join( ['a','b','c'] ) -> 'abc'
    return ''.join( recnik )

if __name__ == '__main__':
    test = [ list('ABBCBCABA'), 
             'Jedan Dva Jedan Jedan Jedan Dva'.split()
           ]
    for s in test:
        print s
        print lz78_dekoder( lz78_koder( s ) )

 
Odgovor na temu

MixMaster

Član broj: 10076
Poruke: 323
147.91.169.*



+32 Profil

icon Re: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?16.01.2006. u 23:44 - pre 221 meseci
Eh, steta sto nisam mogao da se zakacim na internet u zadnjih skoro 10 dana. Sada vidim da sam dosta propustio. Projekat smo kako-tako zavrsili, vec su bili rezultati...96%, sto je realna ocjena za to koliko smo stigli. Profesoru su neke nase ideje bile vrlo interesantne, a vrlo mu je zanimljivo bilo i to sto smo se odlucili za Python (svi ostali su radili u C/C++ ili Matlab, sa kojima smo do sada radili na faxu) cije osnove smo naucili za par dana.
Ipak, puno hvala, bili ste od velike pomoci, narocito boskom!

Hvala jos jednom i veliki pozdrav!
Vidi bako, DžEDAJ!
 
Odgovor na temu

[es] :: Python :: Lempel Ziv kompresija [zadatak]!? Trebalo bi da je lako u Python-u!?

[ Pregleda: 4132 | Odgovora: 10 ] > FB > Twit

Postavi temu Odgovori

Navigacija
Lista poslednjih: 16, 32, 64, 128 poruka.