Tesko.
Problem je sto ovde ulazni niz ima specijalnu osobinu - sadrzi "oznacene"
bajtove (recimo, nekim pomocnim nizom indeksa ili specijalnom vrednoscu) kojima
treba dodeliti proizvoljnu vrednost ([A,B]), ali tako da se niz dobijen jednom
takvom vrstom preprocesovanja maksimalno kompresuje algoritmom koriscenim za
kompresiju. Ovaj algoritam diktira pravila odabira vrednosti X-objekata, tj.
direktno utice na pripremu (prilagodjavanje) niza za kompresiju.
Tako se, na primer, ulazni X-objekat tezine 10 (`xxxxxxxxxx') moze zameniti
izlaznim nizom `3122248779' (7 objekata), samo sto ovakva interpretacija nema
mnogo smisla u slucaju zadate RLE kompresije gde treba teziti sto duzim
sekvencama istih objekata (tu bi X-ove trebalo "dodeljivati" iskljucivo
susedima). Interval [E,F] je neizbezan i posledica je koriscenja bajtova kao
brojaca uzastopnih pojavljivanja istih objekata.
S druge strane, pomenuto Huffman-ovo kodiranje maksimalno pojednostavljuje
resenje problema: prvo se pronadje "normalni" objekat sa najvecom frekvencijom
pojavljivanja da bi se zatim njegov tip jednostavno dodelio _svim_ X-objektima.
Steta samo sto iz nekih drugih razloga ovaj vid kompresije (ukljucujuci
varijacije i slozenije algoritme) nije opcija.
Zadatak je kombinatorne prirode, a neki kazu da podseca na klasicni bin-packing
problem (problem optimalnog izbora), samo sto ovde objekti (ulazni niz) nisu
"fiksni".
Par korisnih linkova (medju prvima na Google-u):
Run Length Encoding (RLE)
http://www.rasip.fer.hr/research/compress/algorithms/fund/rl/
Huffman Encoding
http://www.itee.uq.edu.au/~inf...ial%20Exercises/tutorial9.html
The Bin Packing Problem
http://eng.murdoch.edu.au/EngM...mo/Section01/Section0102c.html
/dux