Le tudnä valaki írni egy aránylag hatékony tömörítő algoritmust az alábbi adatstruktúrára?
A bemenetre jellemző adatstruktúrák egyikére példát tudok mutatni:
{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 6, 42, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 20, 0, 0, 1, 63, 63, 61, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 62, 0, 0, 3, 63, 63, 63, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 61, 0, 0, 11, 63, 63, 63, 48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 60, 0, 0, 15, 61, 1, 47, 56, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 60, 0, 0, 47, 52, 0, 11, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 11, 52, 0, 0, 63, 32, 0, 3, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 48, 0, 0, 63, 0, 0, 3, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 48, 0, 0, 63, 0, 0, 3, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 48, 0, 1, 63, 0, 0, 3, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 48, 0, 3, 62, 0, 0, 11, 52, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 48, 0, 3, 60, 0, 0, 15, 48, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 56, 0, 3, 60, 0, 0, 47, 16, 0, 0, 0, 0, 0, 0, 0, 0, 0, 15, 61, 0, 3, 60, 0, 2, 61, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 7, 63, 16, 3, 60, 0, 11, 52, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 63, 62, 43, 62, 42, 63, 37, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 63, 63, 63, 63, 63, 63, 63, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 27, 63, 63, 63, 63, 63, 63, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 26, 63, 63, 63, 63, 63, 60, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 20, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, }
A tömbben egy adat max. 64 féle lehet (0-63).
A tömb elejének és végének környékén jellemzően több 0-a van, illetve ami még látható, hogy csoportonként szigetelődnek el nem 0-ás számadatok kisebb 0-ás csoportok között.
Egy ehhez hasonló adattömbre alkalmazható egyértelmű tömörítési algoritmust kéne találni, aminek kimenetele egy szintén max. 6 bites (0-63 közötti értéket felvevő) számokat tartalmazó, DE KISEBB elemszámú tömb kéne hogy legyen.
Az algoritmusnak értelemszerűen egyaránt szükséges egy be- ill. kitömörítő része.
Van erre valakinek valamilyen ötlete?
Max. vasárnap délig esedékes.
Azt a fontos megkötést kifelejtettem, hogy max. 1 dimenziós tömbök alkalmazhatóak mind a betömörítő, mind a kitömörítő algoritmusnál, ill. egyiknél sem használhatók közvetlen biteltolások.
Ezek a megkötések amiatt vannak, mert ahol implementálnom kéne a tömörítést, ezekre nincs módom.
válasza:Ha sok az ismétlődés, akkor lehet játszadozni a darabszámokkal.
Például letárolod, hogy hány darab és miből, majd megint hány darab és miből.
Ha sok az ismétlődés, akkor ezzel sokat lehet nyerni, bár a 0-63 közötti itt egy elég nagy megkötés lehet.
válasza:Én valami olyasmit csinálnék, hogy egy N db nullából csoportot lecserélnék { 0, N } -re. Persze ezt csak N<=63-nál lehet megtenni.
Kitömörítéskor pedig, ha 0-t találok, akkor tudom, hogy az utána következő szám az N, ami megmondja, hogy hány 0 van a csoportban. A többi szám meg marad ugyanúgy.
Pl.
0,0,0,0,1,2,0,3,4,0,0,0
->
0,4,1,2,0,1,3,4,0,3
Persze ez kis nullás csoportokra nem mindig eredményez rövidet, de sok nullás csoportok ellensúlyoz(hat)ják.
Igazából ez már nekem is halványan megfordult a fejemben, de akkor arra gondoltam, hogy ennél az adatnál még mindig nem akkora a 0-ás csoportok aránya és hossza, hogy az egyedüli 0-ásokat ellensúlyozza, amiknél így értelemszerűen mindig 1-1 extra elem adódna a kimeneti tömbhöz.
Viszont most, ahogy látom, talán a legtöbb esetben tudna működni ez a kőbaltás módszer valódi tömörítéssel... igaz, eléggé kicsi hatékonysággal. Ezért reméltem hogy létezik egy köztes megoldás, aminek nagyobb a hatásfoka ennél a megoldásnál, de még mindig tudnám Scratch-ben összepakolgatni/implementálni.
válasza:64 féle érték tárolható 6 biten, jelenleg legalább 8 bit (karakter) van rá használva. Ez már legalább két bit számonként. Aztán az ismétlődéseket ki lehet használni, ha jellemző, hogy ilyen mennyiségű 0 van, akkor a 0-kat max 64 hosszúságú blokkonként össze lehet vonni (lejegyzel egy 0-t, és aztán még egy számot, ami a 0-k darabszáma - 1-t jelenti (egy mindig van ugye)).
Ezen túl általános megoldásként az LZW-t tudom javasolni (wiki a barátod).
válasza: válasza: válasza: válasza:Csinálhatod azt, hogy egyrészt nem csak a 0-k sorozatát kódolod, hanem bármelyikét, másrészt azokat a sorozatokat nem, amelyek 3-nál kevesebb elemből állnak.
Ha a sebesség nem számít, akkor az eltolást csinálhatod kettővel/néggyel/stb. való szorzással/osztással is, akkor viszont huffman tömörítést vagy lzw-t használhatsz.
válasza:Ha ezek a megkötések (nem használhatsz biteltolás) és ez a tipikus bemenet (rengeteg 0 egy csomóban, a többi szám meg viszonylag ritka), akkor az az értelmes megoldás, hogy minden 0 csoportot (az egy elemű csoportot is csoportnak tekintve) két elemmel helyettesítesz: egy 0-val és az előfordulások számával. Ha 63-nál több nulla van, akkor azt több csoportnak veszed. Pl. az első 84 db nullát tartalmazó csoport kódolása: 0 63 0 21. A dekódolás még ennél is egyszerűbb: ha nullát találsz, beolvasod a következő számot és annyi nullával helyettesíted.
Annyit tudsz még a kódoláson minimálisan finomítani, hogy a 0 után az "előfordulások száma mínusz egyet" kódolsz, amit nyugodtan megtehetsz, mert nulla hosszúságú csoport nem lesz. A nyereség ott van ennél a módszernél, hogy a 64 elemű 0-s csoportot nem 0 63 0 1 -re kódolod, hanem 0 63-ra. A dekódolást természetesen ehhez kell igazítani.
Kapcsolódó kérdések:
Minden jog fenntartva © 2024, www.gyakorikerdesek.hu
GYIK | Szabályzat | Jogi nyilatkozat | Adatvédelem | Cookie beállítások | WebMinute Kft. | Facebook | Kapcsolat: info(kukac)gyakorikerdesek.hu
Ha kifogással szeretne élni valamely tartalommal kapcsolatban, kérjük jelezze e-mailes elérhetőségünkön!