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

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

[es] :: Art of Programming :: Ideja za novi tip kompresije? Jel neko cuo za ista slicno ...?

[ Pregleda: 2949 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

Autor

Pretraga teme: Traži
Markiranje Štampanje RSS

vlaiv
Vladimir Vlaisavljevic
Novi Sad

Član broj: 15993
Poruke: 352
*.neobee.net.



+1 Profil

icon Ideja za novi tip kompresije? Jel neko cuo za ista slicno ...?05.02.2005. u 14:38 - pre 204 meseci
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?
 
Odgovor na temu

jablan

Član broj: 8286
Poruke: 4541



+709 Profil

icon Re: Ideja za novi tip kompresije? Jel neko cuo za ista slicno ...?05.02.2005. u 23:49 - pre 204 meseci
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.
 
Odgovor na temu

[es] :: Art of Programming :: Ideja za novi tip kompresije? Jel neko cuo za ista slicno ...?

[ Pregleda: 2949 | Odgovora: 1 ] > FB > Twit

Postavi temu Odgovori

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