Ideja za novi tip kompresije? Jel neko cuo za ista slicno ...?
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?
 |  |
 |
