¢ Run Length Encoding¢ -* *-¢¢¢ aaaaaabbbbbbbcccccccdddddd=??????¢¢¢ W poprzednich artyku ach omwi em¢ kompresj❎ s ownikow⇧ i probabilisty-¢ czn⇧.¢¢ (Si❎gamy do wcze③niejszych wyda maga-¢ zynu SERIOUS - Zenon)¢¢ Metody te pomimo wielu zalet nie zaw-¢ sze jednak umoəliwiaj⇧ optymaln⇧ kom-¢ presj❎. Jeəeli w danych, ktre chcemy¢ skompresowa⇨ jest ci⇧g identycznych¢ bajtw, powyəsze metody nie sprawdzaj⇧¢ si❎ najlepiej.¢ W przypadku metody s ownikowej taki¢ sam ci⇧g powinien wyst⇧pi⇨ wcze③niej,¢ əeby mg by⇨ skrcony (chociaə da si❎¢ to omin⇧⇨).¢ Cz❎sto metoda s ownikowa operuje na¢ krtkich frazach, co moəe powodowa⇨,¢ əe jeden ci⇧g b❎dzie podzielony na¢ kilka cz❎③ci, pomimo, əe moəna by to¢ zrobi⇨ optymalniej. Takəe metoda pro-¢ babilistyczna jest ma o uəyteczna w¢ przypadku takich danych. Na przyk ad¢ ci⇧g 64 identycznych bajtw moəna za¢ jej pomoc⇧ spakowa⇨ maksymalnie do 8¢ bajtw (co i tak jest ma o realne),¢ natomiast sama struktura tych danych¢ sugeruje, əe moəna by tutaj zastosowa⇨¢ metod❎, ktra skrci te dane do dwch,¢ moəe trzech bajtw.¢¢ Metoda, ktra najlepiej nadaje si❎ do¢ kompresji powtarzaj⇧cych si❎ danych,¢ zwana metod⇧ powtarzaj⇧cych si❎ ele-¢ mentw lub RLE (Run Length Encoding),¢ stosuje licznik informuj⇧cy ile razy¢ powtarza si❎ dany bajt, po czym nast❎-¢ puje bajt, ktry naleəy powieli⇨. Tu-¢ taj jednak pojawia si❎ problem odrə-¢ nienia licznika od pozosta ych danych.¢ I tu moəna zastosowa⇨ dwa podej③cia.¢¢ Pierwszym sposobem jest wybranie naj-¢ rzadziej wyst❎puj⇧cego bajtu i trakto-¢ wanie go jak znacznik dla sekwencji.¢ Dane nie stanowi⇧ce sekwencji b❎d⇧¢ przepisywane bez zmian.¢¢ Przyk ad.¢¢ Ci⇧g wej③ciowy:¢ 0000011112000087654...000000¢¢ Kaədy z bajtw zawiera si❎ w powyəszym¢ przyk adzie na jednej pozycji.¢ "..." - oznacza, əe jest tu duəo rə-¢ nych dziwnych danych, ktre akurat, w¢ tym przyk adzie, ma o nas interesuj⇧¢ ;-)¢¢ Interesuje nas jedynie to, əe najrza-¢ dziej wyst❎puj⇧cym symbolem okaza si❎¢ bajt "2". Moəemy zakodowa⇨ nasz ci⇧g¢ wej③ciowy jako:¢¢ 2 250 241 212 240 87654 ... 260¢ Spacje zosta y uəyte tylko w celu¢ u atwienia ogl⇧dania (nie tworz⇧ da-¢ nych wynikowych) ;-)¢ Ci⇧g wej③ciowy mia d ugo③⇨ 25+? baj-¢ tw, wyj③ciowy natomiast ma 21+?.¢¢ Przeanalizujmy:¢ Pierwszy bajt informuje, co jest zna-¢ cznikiem ("2").¢¢ "250": "2"- znacznik czyli mamy do¢ czynienia z sekwencj⇧, kolejne dwa¢ bajty okre③laj⇧ szczeg y.¢¢ "5" - kolejny bajt powielamy pi❎cio-¢ krotnie.¢¢ "0" - bajt, ktry naleəy powieli⇨.¢¢ Czyli dostajemy "00000".¢¢ "241": "2" - sekwencja, "41"-->"1111"¢¢ Dekodujemy pozosta e grupy. Po zdeko-¢ dowaniu grupy "240" natrafiamy na "8".¢¢¢ Poniewaə nie jest to znacznik sekwen-¢ cji, wi❎c przepisujemy bez zmian. Tak¢ samo z pozosta ymi bajtami, aə do ko-¢ lejnej "2".¢¢¢ Podczas kompresji moəe wyst⇧pi⇨ do③⇨¢ specyficzna sytuacja o ktrej naleəy¢ tu wspomnie⇨.¢ Je③li bajtem do kompresji okaəe si❎¢ bajt, ktry wyznaczony zosta na zna-¢ cznik sekwencji, to nie moəe on by⇨¢ w prosty sposb przepisany jak inne¢ bajty, ktre nie tworz⇧ sekwencji (np.¢ "87654").¢ W naszym przyk adzie takim bajtem jest¢ ten z pozycji dziesi⇧tej ("2").¢ Przepisanie go bez zmian spowodowa oby¢ əe przy dekompresji bajt ten zosta by¢ potraktowany jak znacznik, niszcz⇧c¢ ca ⇧ struktur❎ danych. W celu omini❎-¢ cia takiej sytuacji stosuje si❎ zabieg¢ tworzenia sekwencji o d ugo③ci 1.¢¢ W naszym przyk adzie "2" zosta o zako-¢ dowane jako¢¢ "212", czyli:¢ 2 - znacznik wyst⇧pienia sekwencji¢ 1 - ile razy powieli⇨.¢ 2 - bajt, ktry naleəy powieli⇨.¢¢ Powoduje to wyd uəenie danych wyniko-¢ wych, ale ten sposb kompresji nadaje¢ si❎ tylko do specyficznych danych, a w¢ takich danych cz❎sto si❎ zdarza, əe¢ jaki③ bajt nie wyst❎puje ani razu.¢ Przy niewielkiej liczbie wyst⇧pie¢ bajtu-znacznika kompresja teə moəe¢ okaza⇨ si❎ op acalna. Jak zawsze sens¢ stosowania metody zaleəy od struktury¢ kompresowanych danych. Jednak moəe si❎¢ tak zdarzy⇨, əe sporo bajtw u oəo-¢ nych jest w grupy, a pomimo to kompre-¢ sja okazuje si❎ nieop acalna. Powodem¢ tego jest zbliəona cz❎stotliwo③⇨ wy-¢ st❎powania poszczeglnych bajtw. Nie¢ sposb wwczas wybra⇨ bajt, ktry s u-¢¢ əy by za znacznik, gdyə kaəde jego wy-¢ st⇧pienie w danych wej③ciowych wyd uəa¢ dane wyj③ciowe, cz❎sto do tego sto-¢ pnia, əe kompresja traci sens.¢¢ W takiej sytuacji moəna zastosowa⇨¢ drug⇧ metod❎. Charakteryzuje si❎ ona¢ tym, əe wyst❎puj⇧ tutaj dwa znaczniki.¢ Jeden dla sekwencji i drugi dla pozo-¢ sta ych danych. Juə z jednym znaczni-¢ kiem by problem, a z dwoma ma by⇨¢ pro③ciej?¢ Tak, poniewaə nie jest on teraz bajtem¢ ale bitem. W zwi⇧zku z tym bajt moəna¢ podzieli⇨ na dwie cz❎③ci:¢¢ ZXXXXXXX.¢¢ "Z" - oznacza znacznik.¢¢ Przyjmijmy əe: 1 - sekwencja¢ 0 - dowolne dane¢¢ XXXXXXX - jest licznikiem.¢¢ W przypadku sekwencji licznik informu-¢ je ile razy skopiowa⇨ bajt, ktry po-¢ jawi si❎ jako nast❎pny. Poniewaə nie¢ ma sensu kodowa⇨ sekwencji jedno i¢ dwuelementowych, wi❎c warto③⇨ zero li-¢ cznika moəe oznacza⇨ trjelementowe¢ sekwencje. I tak analogicznie maksyma-¢ lna warto③⇨ licznika (127) oznacza se-¢ kwencje 130-elementowe. Sekwencje je-¢ dno i dwuelementowe moəna traktowa⇨¢ jak dane nie stanowi⇧ce sekwencji.¢¢ W przypadku gdy Z=0, licznik informuje¢ ile kolejnych danych naleəy przepisa⇨¢ bez jakichkolwiek zmian. Poniewaə zero¢ jest warto③ci⇧ ma o sensown⇧, wi❎c¢ ilo③⇨ danych do przepisania b❎dzie¢ warto③ci⇧ licznika zwi❎kszon⇧ o jeden.¢ Z danych w naszym przyk adzie mamy:¢¢ $82$00 $81$01 $00$02 $81$00¢ $04$08$07$06$05$04 ... $83$00¢¢ Czyli otrzymali③my 16+? bajtw. (HEX)¢¢ Dla rozwiania w⇧tpliwo③ci zdekodujmy:¢¢ $82=%10000010 czyli:¢ znacznik=1 i licznik=2,¢ a wi❎c sekwencja, czyli ilo③⇨ elemen-¢ tw wynosi (licznik+3). Dla sekwencji¢ pobieramy kolejny bajt ($00). Po zde-¢ kodowaniu otrzymujemy 00000.¢¢ $81=%10000001: Z=1, L=1, wi❎c sekwe-¢ ncja, pobieramy kolejny bajt ($01) i¢ przepisujemy go (L+3) razy: 1111¢¢ $00=%10000000: Z=0, L=0, dane niepo-¢ wtarzalne. Ich ilo③⇨ wynosi (L+1),¢ wi❎c przepisujemy (L+1) kolejnych¢ bajtw (czyli w naszym przypadku 1).¢ Na wyj③cie trafi wi❎c bajt 2.¢¢ Kolejna grupa $81$00 -> 0000¢¢ Nast❎pny bajt $04. Z=0, L=4.¢ Dane niepowtarzalne o ilo③ci (L+1),¢ czyli przepisujemy 5 sztuk: 87654.¢¢¢ Trudno jest okre③li⇨, ktra z powy-¢ əszych metod jest lepsza. Jak zawsze¢ wszystko zaleəy od danych wej③ciowych.¢ Waəne jest to, iə metoda ta zak ada¢ wyst❎powanie do③⇨ specyficznego uk adu¢ danych i tylko wwczas jest sens jej¢ stosowania. Jednak je③li ten specyfi-¢ czny uk ad danych wyst⇧pi, a metoda ta¢ nie zostanie zastosowana, wyniki kom-¢ presji b❎d⇧ znacz⇧co gorsze, nawet¢ przy stosowaniu do③⇨ z oəonych algory-¢ tmw jakimi s⇧ metody s ownikowe i¢ probabilistyczne.¢¢¢ Glonisz/Quasimodos¢¢
