kompresija algoritmi in programski jeziki uvod v tej seminarski nalogi vam bom predstavil kompresijo ter njuno uporabo v vsakdanjem zivljenju vse od najbolj primitivnih kompresij run length encoding skozi pretvornike move to front pa do bolj kompleksnejsih algoritmov za transformiranje podatkov v drugacne oblike burrows and wheeler transform ki naj bi bile bolj primerne za aritmeticne kompresorje seveda bom predstavil tudi order aritmeticno kompresijo dokumentu bo prilozena izvorna koda vsakega opisanega dela stopnje kompresije ter skupna verzija ki bo konkurencna kaksnemu komercialnemu programu za kompresijo kot arj ali pkzip introduction in this paper i will introduce compression and its uses in everyday life everything from the most primitive compression algorithms run length encoding trough transformation algorithms move to front to more complex algorithms for data transformation burrows and wheeler transform witch are more suitable for arithmetic compressors i will briefly introduce the order arithmetic compression algorithm attached to this paper will be the source code of every described part of compression and a joined version witch will be competitive with commertial programs for compression pkzip arj zgodovina odkar poznamo racunalnike obstajajo metode za kompresijo vse od leta so se pojavljali bolj napredni algoritmi za kompresijo in kot prvi je dobil patent rle run length encoding rle spada v poglavje nadomestitvenih kompresorjev se pravi kompresorji ponovitev tukaj obstajata dve varijaciji imenovani po jakobu zivu ter abrahamu lempelu ki sta jih prvic predstavila v letu ter in od takrat to druzino kompresorjev oznacujemo z oznako lz lempel ziv lz druzina kompresorjev lz kompresor sledi podatkom zadnjih n zlogov ter ko najde frazo ki je bila ze uporabljena zapise dve vrednosti pozicijo fraze v predhodni tabeli ter dolzino fraze rle algoritem temelji na lz varijanti ter ima patent izdan leta in ponovno prvi patent pokriva rle v najbolj primitivni varijanti stevilo ponovitev ki ji sledi zlog ki naj bi ga ponovili druga verzija je omejitev ponovitev na se pravi uporaba ih bitov za stevilo ponovitev rle run length encoding verzija rle ki ima patent izdan v letu je danes uporabljena pri pcx tga formatu ter kot podloga glavni kompresiji bolj znanih komercialnih programov arj rar pkzip ter nekomercialnih kot naprimer bzip ki je ucinkovit primer uporabljanje transformacijske metode ki jo bom kasneje tudi opisal bwt burrows and wheeler transform rle je kompresija ki belezi ponovitve naprimer stavek haaaaaaaaaaaaloooooooooooo bi lahko zapisali kot ha lo tukaj lahko prihranimo zloga ce zapisemo stevilki z enim zlogom ampak ta algoritem je neprimeren za kompresijo datotek ker se v datoteki lahko ponovijo vse mozne kombinacije stevilk crk ter zlogi vseh moznih vrednosti kako naj vemo da imamo ponovitev v datoteki pri metodi iz pcxa uporabimo neke vrste stevec ponovitev ampak sam algoritem je preprosto prevec ne izpopolnjen saj omogoca najvec ponovitev mi bomo uporabili bolj napredno verzijo algoritma da nam bo omogocila boljso kompresijo kot pcx format preprosto dolocimo da ponovitev dveh znakov v datoteki pomeni ponovitev zato najprej preberemo en zlog iz datoteke ga izpisemo v novo datoteko ter ga primerjamo z predhodno vrednostjo ki je za prvi byte enaka ce je vrednost enaka predhodni zacnemo beleziti stevilo ponovitev ki so omejena na ce je nadaljnih ponovitev vec kot potem ponovno izpisemo znak ter spet stevilo ponovitev dokler ne naletimo na drug znak v datoteki povzetek v podatkovnem toku dva enaka znaka predstavljata ponovitev byte ki jima sledi je byte ki zaznamuje stevilo dodatnih ponovitev znaka preprost primer bi bil naprimer ponovitev crke a ter ponovitev crke b ki bi po poteku rle algoritma za naso uporabo postal naslednji niz aa ff a bb ff b d se pravi ponovitev crke a ter z nasim pametnim algoritmom ne izgubimo niti enega zloga pri datotekah v katerih nimamo ponovitev preprost niz internationaly bi po poteku ostal enak ker ne vsebuje ponovitev med tem ko pri ponovitvi samo dveh znakov pridobimo en byte na dolzini datoteke se pravi internacionally bi pretvorili v internationall y iz tega lahko ze sklepamo pri katerih datotekah se rle odnese najbolje mtf move to front kot lahko ze sklepate iz naslova je mtf algoritem za transformiranje s tem da naredi nekatere zloge bolj pogoste ter s tem omogoca boljse kompresiranje transformiranih podatkov v teoriji je vsak princip lahek in tako tudi ta ni izjema imamo tabelo z razlicnimi indeksi inicializiran tako da ima vsak zlog svoj indeks za tabelo vsakic ko preberemo zlog ga mtf izpise kot pozicijo v tabeli ne pa kot njegovo pravo vrednost takoj za tem postavimo zlog na prvi indeks tabele table ampak najprej premaknemo ostale vrednosti do indexsa ki je prej vseboval zlog za en zlog v desno table table table table s tem dosezemo da imamo vedno vsak mozni zlog v tabeli in ne moremo narediti napake pri transformaciji ta transformacija naredi to da pogosto ponovljenim znakom dodeli nizke vrednosti cim vec ponovitev imajo kar je pogosto uporabno pri bit stream kompresorjih ki delujejo na verjetnosti kot naprimer huffman ki postavi kodo za verjetnost znaka namesto znaka tako da vecja verjetnost manj bitov kar potem pomeni hkrati vecjo kompresijo tukaj lahko vidimo ze par prednosti mtfja po transformaciji so podatki bolj stisljivi za kompresorje ki temeljijo na verjetnostih ponovitve implementacija je lahka in hitra edine dve slabi stvari na mtfju sta to da se ne obnese dobro pri uporabi lz kompresorjev ter dejstvo da sam ne stisne podatkov no ko sem enkrat naredil encoder je bil decoder se lazji kot v encoderju imamo tabelo ki je na zacetku inicializirana tako da velja indeks tabela preberemo znak iz tabele ki ima indeks znaka iz transformirane datoteke sedaj spet premaknemo del tabele kot v encoderju ter postavimo prebrani znak iz tabele na zacetek tabele ter v novo datoteko ter tako ponavljamo dokler ne pridemo do konca transformirane datoteke aritmeticno kodiranje aritmeticen koder je sirno uporabljan koder katerega edini problem je njegova hitrost ampak kompresija je boljsa od tiste ki jo doseze huffman ta del seminarske predstavlja osnovno aritmeticno kodiranje ce niste se nikoli implementirali aritmeticnega kompresorja potem lahko kar berete naprej ce pa ste ze potem poglejte drugam za boljse implementacije ideja za aritmeticnem kodiranjem je to da imamo linijo moznosti od do ter za vsak simbol dolocimo del te linije 'obseg' ki temeblji na verjetnosti simbola vecja verjetnost tem vecji bo obseg ki ga bo simbol dobil na tej liniji ter podobno simbol ki bo imel manjso verjetnost bo dobil tudi manjsi delcek obsega ko smo enkrat dolocili obsege po liniji verjetnosti potem lahko zacnemo kodirati simbole vsak simbol definira mesto kam pristane izhodno stevilo simbol a b c verjetnost obseg opazite matematicne izraze ' ' pomeni da je naslednja cifra v intervalu ' ' pa pomeni da je predhodna cifra ze v drugem intervalu se pravi simbol 'a' lahko zavzame vrednosti vse od do ko imamo enkrat te obsege na crti verjetnosti lahko zacnemo z kodiranjem simbolov in racunanjem izhodne vrednosti psevdo koda low high zanka skozi vse simbole range high low high low range high range simbola ki ga kodiramo low low range low range simbola ki ga kodiramo tukaj nam range pove kje bo naslednji obseg ter high ther low dolocata izhodno stevilo tukaj je en primer simbol obseg spodnja vrednost zgornja vrednost b a c a izpisano stevilo bo enako nacin dekodiranja je da najprej vidimo kje stevilo pristane izpisemo pripadajoci simbol ter potem izracunamo obseg simbola iz stevila algoritem za to je zanka skozi vse simbole range high range simbola low range simbola number number low range simbola number number range in tako poteka dekodiranje simbol obseg cifra b a c a priporocljivo je da rezervirate majhen range za eof simbol ceprav lahko podate kar dolzino datoteke kompresorju tako da ve kdaj naj bi koncal z komprecijo implementacija kot lahko vidite iz primerov je obvezno podati dekompresorju realno stevilo ni treba zaokrozevati ampak z danasnjimi fpu floating point unit je najvecja mozna natancnost okoli bitov tako da ne moremo delati z celimi stevili morali bomo redebinirati nase obsege namesto do bomo imeli h to ffffh kar bo za nas primer enako zmanjsali bomo tudi verjetnosti da ne bomo potrebovali celega dela ampak samo bitov ali ne verjamete da je isto pa poglejmo par stevil h h h c h ffffh ce vzamemo ta stevila in jih delimo z maksimumom bomo jasno videli h h h c h ffffh prilagodili bomo tudi verjetnosti tako da bodo biti potrebovani za operacije s stevilom zasedli najvec bitov in sedaj ko smo definirali interval in smo prepricani da lahko delamo samo z biti lahko zacnemo pisati program nacin z katerim onemogocimo ukvarjanje z neskoncnim stevilom je da imamo samo prvih bitov prebranih in ko potrebujemo lahko dodajamo nove bite delamo samo z temi biti ter ko potrebujemo nove bite uporabimo shift algoritem aritmeticnega kodiranja pomeni ce je kadarkoli msb od high in low enak potem se nikoli ne spremeni to je nacin kako lahko izpisemo visoke bite iz neskoncnega stevila ter nadaljujemo delo z samo biti nazalost to ne velja vedno preliv na napacni strani underflow preliv na napacni strani se pojavi ko se obe vrednosti high and low blizata neki vrednosti ampak se njun najbolj pomemben bit ne ujema kot na primeru high in low ce imamo kdaj taka stevila in se nadaljujejo blizati drug drugemu ne bomo mogli izpisati najbolj pomembnega bita in potem v par iteracijah bitov ne bo dovolj kar moramo storiti v tej situaciji je premakniti moramo drugo stevilo v nasi implementaciji bit in ko sta koncno bita msb enaka tudi izpisemo zanemarjena stevila zbiranje verjetnosti za nase potrebe bomo uporabili staticni order model imamo tabelo inicializirano na vrednost in stejemo kolikokrat se posamezen zlog ponovi in ko jih imamo jih moramo samo se prilagoditi tako da ne rabimo vec kot bitov pri racunanju ce zelimo to doseci mora biti vsota vseh verjetnosti pod za prilagoditev lahko delimo verjetnosti dokler ne pristanejo na bitov dolzine ampak obstaja lazja in hitrejsa pot do istega rezultata dobimo najvecjo moznost in jo delimo z to je faktor ki ga bomo uporabljali za verjetnosti tudi ko delimo ce je rezultat ali pod potem dolocimo vrednost tako da ima simbol nek obseg nasljednja prilagoditev obravnava maximum od sestejemo vse verjetnosti simbola in potem preverimo ce je sestevek nad ce je potem delimo z faktorjem ali in naslednje domneve bodo pravilne vse verjetnosti bodo v obsegu to nam pomaga prihraniti header z verjetnostmi sestevek vseh verjetnosti ne pride nad in tako potrebujemo samo bitov za racunanje shranjevanje verjetnosti nase verjetnosti so dolzine enega zloga tako lahko shranimo celo tabelo ki bo dolga najvec zlogov ter bo zapisana samo enkrat tako da to kompresiji ne skoduje veliko ce pricakujemo da se neki simboli ne bodo pojavili lahko rle zakodiramo verjetnosti dolocanje obsega za vsak simbol moramo definirati high in low vrednost te vrednosti definirajo obseg narediti to je preprosto uporabimo njegovo verjetnost za obseg kar bomo uporabili je high in low in ko bomo racunali stevilo bomo izvedli deljenje da jih stlacimo med vrednosti in v vsakem primeru ce pogledamo na high in low vrednosti boste opazili da je low vrednost trenutnega simbola enaka high vrednosti predhodnega simbola to znacilnost lahko uporabimo da razpolovimo uporabljenost pomnilnika moramo biti samo pozorni na simbol z high vrednostjo simbol verjetnost high a b c in tako ko prebiramo high vrednost simbola ga preberemo v svojo pozicijo in za low vrednost preberemo prednodno vrednost high za trenutni primer ko beremo simbol b preberemo njegovo vrednost na trenutni poziciji simbola v tabeli in za low vrednost predhodna ker nase verjetnosti zasedejo samo en byte bo cela tabela zavzela le byteov bwt burrows and wheeler transform bwt je algoritem za transformacijo ne pa za kompresijo kar lahko zvemo ze iz naslova ampak njegova znacilnost transformiranja neredundantnih podatkov v redundantne nam daje veliko prednost pred programi za kompresijo ki ga nimajo implementiranega tehnologija bwt se uporablja v nekomercialnem programu bzip ki je vrh trenutne lestvice kompressorjev in res predstavlja tehnologijo v svoji podobi algoritem je zelo zanimiv ter se ga z lahkoto implementira originalen dokument od gospodov burrows in wheeler je naslovljen a block sorting lossless data compression algorithm ta naslov kar dobro opise kaj se dogaja v tem algoritmu vzamemo blok podatkov in ga sortiramo na poseben nacin naj imamo niz seminarska vzamemo ta niz in naredimo n kopij n je dolzina niza ter v vsako kopijo postavimo niz zarotiran za n znakov v levo po tem imamo n niz seminarska eminarskas minarskase inarskasem narskasemi arskasemin rskasemina skaseminar kaseminars aseminarsk sedaj sortiramo teh n nizov n niz original n a rskasemi n a seminars k e minarska s i narskase m k aseminar s m inarskas e n arskasem i r skasemin a s eminarsk a s kasemina r verjetno ste opazili da sem omenil vrednost rotacije nizov index hitro bom obrazlozil kaj naredimo z njim razdelil sem tudi prve in zadnje znake v posebne stolpce ter jih odstranil od ostalega dela ta dva niza bom imenoval kot f and l od katerih je i index stevilo niza ta dva niza imata kljucno pozicijo v bwt algoritmu tabelo f sestavljajo sortirani znaki vhodne datoteke aaeikmnrss v tem primeru tabela l nima nobenege posebne razporeditve vsaj na prvi pogled ravnotako pa tudi vsebuje vse znake ki jih podamo z nizom z to lastnostjo lahko rekonstruiramo f iz l s tem da sortiramo niz l to je zelo pomembno za bwt izpis bwt algoritma pri kodiranju je l ter t i primarni index ki je index prvotnega prvega znaka v l to je vedno stevilo katerega originalni index je enak se pravi v nasem primeru stevilo problem sedaj imamo naso transformacijo ampak imamo tudi problem kako lahko naredimo inverzno transformacijo to se nam ne zdi mozno vsaj ne z podatki ki so nam na voljo stvar ki jo potrebujemo je t i transformacijski vektor transformacijski vektor transformacijski vektor nam bo dal moznost vzpostavitve prvotnih podatkov imenoval ga bom t transformacijski index bo spet organiziran po vrsticah nizov povedal nam bo kako od sortiramo f da dobimo prvotne podatke definira v kateri vrsti je predhodna crka to pomeni znak v originalnem nizu ne pa v sortiranem nizu to je tezji del za obrazlozitev dal vam bom primer na vrsti sortiranih nizov lahko najdemo originalni niz seminarska t bi bil stevilo vrste v katerem se nahaja eminarskas se pravi zarotiran niz bi bil minarskase se pravi bi bil t ter tako naprej n niz original n f l zarotiran niz t arskasemin a n rskasemina aseminarsk a k seminarska eminarskas e s minarskase inarskasem i m narskasemi kaseminars k s aseminarsk minarskase m e inarskasem narskasemi n i arskasemin rskasemina r a skaseminar seminarska s a eminarskas skaseminar s r kaseminars tukaj jasno vidimo da je t niz indeksov na prvotno sortirane nize dekodiranje niza potem poteka nekako takole int t char l nksmseiaar int primary ind int main int ind primary ind for int i i i cout l ind t cout endl return seveda ta program izpise seminarska tako da se razumemo tako zdaj imamo transformacijski vektor samo ga imamo dostavljenega z problemom nujno ga rabimo za dekodiranje transformacije ampak ga ne smemo zapisati v datoteko saj bi to prevec povecalo podatke tako imamo samo eno mozno resitev moramo ga generirati iz podatkov ki so nam na voljo l ter nas osnovni indeks v bistvu rabimo samo l za zgraditev nasega transformacijskega vektorja za kreacijo transformacijskega vektorja rabimo kopijo f in l ampak kot sem ze prej navedel lahko dobimo f zastonj z sortiranjem l sedaj moram spet povedati nekaj o kreiranju transformacijskega vektorja kajti spet imamo problem imamo samo prvo in zadnjo vrsto zarotiranih nizov ne pa ostalega vsaj ne v nekem zaporedju kaj lahko zdaj naredimo sheme ki sem jo uporabil za racunanje transformacijskega vektorja v prejsnjem delu tukaj ne moremo uporabiti ker ne dela ampak poglejte zadnjo tabelo se enkrat opazili boste da lahko transformacijski vektor zgradimo na preprostejsi nacin mislite nanj kot naslednje ko zarotiramo niz v levo za en znak kaj vsebuje nas f l znak tako je vse kar moramo storiti iskanje indeksa znaka v l kjer lahko najdemo nas f znak ce to naredimo potem vidimo da so stevila ki jih dobivamo nas transformacijski vektor ampak tukaj imamo spet en problem v nasem nizu ki ga imamo za primer so nekateri znaki podvojeni tako se uprasamo katere znake v l naj uporabimo odgovor je preprost enega za drugim f in ostali nizi so sortirani in l je samo funkcija f oziroma si lahko to zamisljamo za poenostavitev tako so vpisi v l enega danega znaka v enakem zaporedju kot v f tako prvi a v f odgovarja prvemu a v l z to dodatno informacijo lahko zgradimo transformacijski vektor tudi od zadaj naprej iz l nas l je nksmseiaar po sortiranju dobimo f ki je aaeikmnrss ce vzamemo prvi znak v l n iscemo prvi prikaz crke v f dobimo indeks temu potem odgovarja t ko preverimo v nasih predhodnih podatkih je ta trditev pravilna potem vzamemo drug znak iz l k iscemo prikaz crke v f dobimo indeks ko preverimo zgoraj vidimo da je t res to lahko naredimo za vse znake v l da dobimo nas transformacijski vektor in s tem imamo ze napisano transformacijo v obe smeri sedaj ostane samo se tisto vprasanje zakaj bwt deluje tako dobro bwt sortira nize na poseben nacin in rezultat je bolj stisljiv za kompresorje kot so aritmeticni ter mogoce llp druzina slabo se pa obnese na lz ter podobnih variacijah zaradi tega ker bwt odstrani stisljive dele ki jih isce ta druzina kompresorjev approach txt b approach mc b datoteka komprimirana z zgornjimi algoritmi approach bzip b bzip file approach tgz b tar gzipped file approach zip b zipped file tukaj je je najbolje izkazal bzip ki je boljsa implementacija mc bwt algoritma oziroma moje implementacije razlog zakaj sta se zip in tgz izkazala bolje kot moja implementacija je to da sta oba algoritma variante lz kompresorskih algoritmov ter tako eliminirajo stevilne ponovitve besed katerih je v kb knjigi lahko zelo veliko flowa tga nekompresiran tga bitna slika b tga original b tgz gzipped tarball b zip pkzip b mc mcompress nasa implementacija b bzip bzip napreden bwt algo kompresija tukaj je nas kompressor prekasal zip in tar gzip kompresijo saj slika ni vsebovala veliko ponovitev ter tudi ce bi jih so ponovitve bitne kar pomeni da bi lz druzina odkrila samo vsako tretjo ponovitev ker delujejo na bitni osnovi in ne na bitni pgpkey txt pgp kljuc v txt datoteki visoka stopnja kompresije b original b zip b tgz b mc mcompress b bzip razlog za tako revno kompresijo na mc je tukaj ociten in se ukvarja z ocitno teorijo o kompresiji ni ga podatka ki bi se dal stisniti v neskoncnost vseeno mi je uspelo spraviti velikost mc verzije na b z odstranitvijo stopnje rle kompresije ker rle slabo kompresira majhne datoteke in tudi ce jih ze je to prevec potratno za druge stopnje