[es] - Ideja za novi tip kompresije? Jel neko cuo za ista slicno ...?

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Moderator
Član broj: 15993
Poruke: 281
*.neobee.net.

Profil

Ideja za novi tip kompresije? Jel neko cuo za ista slicno ...?

^{05.02.2005. u 14:38}

Listam forum i procitam post o "Konacnom resenju" ... :)

Pade mi na pamet jedna ideja koju sam ranije imao pa bi da prodiskutujem o
isplativosti i eventualnim dostignucima ...

Ideja je vrlo jednostavna, bazira se familiji algoritama iz druge oblasti (sortiranje) i u zavisnosti od izabranog algoritma naravno zavisi i implementacija kompresije ...

1. Ulazne podatke transformisati tako da pretstavljaju niz brojeva iz konacnog skupa (u klasicnom slucaju posmatrati niz bajtova ali se ne ogranicavati na grupe od 8bita ... moguca implementacija i za 1bit-ni niz ili recimo word-ove ili sta se vec u konkretnom slucaju pokaze kao (pseudo)optimalno resenje).

2. Izvrsiti jednostavno brojanje elemenata i zapisati neku vrstu tabele frekvencija kako bi se mogao iz nje generisati ulazni niz sortiran po rastucim vrednostima.

3. Za izabrani algoritam za sortiranje definisati skup kodova operacija:
primer:
1. zamena trenutnih mesta pokazivaca
2. Poredjenje trenutnih mesta pokazivaca
3. uvecavanje prvog pokazivaca za 1 i sl ...

Pustiti algoritam za sortiranje da radi i evidentirati kodove izlaza ...

Na kodove izlaza primeniti neku od standardnih metoda entropijskog kodiranja (huffman, aritmeticko ...)

Dekompresija:

uslov : Za odabrani algoritam za sortiranje i definisan skup kodova operacija postoji inverzni algoritam koji sortiran skup vraca u prvobitno stanje ...

1. Iz tabele frekvencija generisati sortiran niz ...
2. dekodirati niz kodova operacija
3. primeniti inverzan algoritam kako bi se sortiran niz vratio u prvobitno stanje ...

Jedina bojazan je naravno cinjenica da je broj operacija potrebnih za sortiranje niza daleko veci od broja elemenata niza ali ukoliko je broj operacija mali a cesto i neuniformno distribuiran nad skupom govori da entropija niza kodova operacija moze biti manja (u nekim slucajevima) od entropije ulaznog niza ...

Komentari?

^{05.02.2005. u 14:38}

jablan
Mladen Jablanović
Beograd

Član broj: 8286
Poruke: 2995
*.smin.sezampro.yu.

Sajt: blog.radioni.ca

Profil

Re: Ideja za novi tip kompresije? Jel neko cuo za ista slicno ...?

^{05.02.2005. u 23:49}

Onako na prvu loptu: svi algoritmi kompresije imaju složenost veću od n, dakle u proseku ćeš imati više podataka o toku sortiranja, nego početnih podataka. Pretpostavljam da postoji određeni broj sekvenci koje bi se dale kompresovati ovom metodom, ali da su u relativno retke.

Valjda će ti se javiti i neko kompetentniji od mene sa komentarom.

_{Probajte Ruby}

^{05.02.2005. u 23:49}