Futáshossz kódolás

A Programozás Wiki wikiből

A futási hossz kódolás az egyik legegyszerűbb veszteségmentes tömörítés. A módszer azon a felismerésen alapul, hogy az ember azt is mondhatja, hogy "van egy piros kanalam, mellette egy piros kanál, amellett egy piros kanál legvégül pedig egy kék", de akár azt is mondhatná, hogy van 3 piros és egy kék kanala. A módszerre sokan mint RLE-kódolás hivatkoznak(Run Lenght Encoding) ami a magyar név angol megfelelője. A módszer nagyon egyszerű, mégis még manapság is akad bőven felhasználási területe.

Hagyományos RLE[szerkesztés]

Tegyük fel, hogy van egy jelsorozatunk tetszőleges típusú adatból. Ez lehet egy szöveg, egy adatfájl, de lehet akár egy kép is sorfolytonos tárolással vagy egyéb dolog. A Példák kedvéért tegyük fel, hogy az alap adattípus valami számszerű dolog, például egész típusú elem, egyébként is ez a jellemző. Ekkor egy ciklusban olvassuk a bemeneti fájl elemeit, miközben egy számlálóval nyilvántartjuk hány darab azonos elemet olvastunk már. Ezt csináljuk egészen addig, míg egy másik értéket nem fedezünk fel, ekkor ugyanis kiírunk az outputra egy X,Y kettőst, ahol az X azt jelzi hány darab azonos szám fog következni, Y pedig magát a számot ami ismétlődik. Ezt mindaddig csináljuk, míg a teljes fájlon vagy tömörítendő adaton végig nem érünk. A kitömörítés értelemszerűen történik.

Példa(Hagyományos RLE)[szerkesztés]

  • Tömörítendő számsorozat(1):

0,0,1,1,1,1,1,1,3,4,10,100,123,32,42,42,42,42,42,43 (20 szám)

  • Kimenet(1):

2,0,6,1,1,3,1,4,1,10,1,100,1,123,1,32,5,42,1,43 (20 szám)

  • Tömörítendő számsorozat(2):

5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5,5 (20 szám)

  • Kimenet(2):

20,5 (2 szám)

  • Tömörítendő számsorozat(3):

1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2 (20 szám)

  • Kimenet(3):

1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2,1,1,1,2 (40 szám)

Gyakorlati megfontolások a hagyományos RLE-hez[szerkesztés]

  • A fent leírtak tökéletesen működnek elvi körülmények között, de a gyakorlati megvalósítás során törődnünk kell a számábrázolással is! Tegyük fel, hogy mind a tömítendő adatsor alaptípusa, mind az ismétlés számát leíró típusunk 4bites előjel nélküli egész szám. Ekkor a számértékek 0 és 15(ha úgy tetszik 0 és F) között szerepelnek majd és ha valamilyen jel 15-nél többször ismétlődik, problémákkal szembesülünk az ismétlési szám túlcsordulása miatt. A megoldás rendkívül egyszerű: amint túlcsordulnánk, írjuk ki a lehető legnagyobb számot mint ismétlődési szám, majd a számot. Ezek után úgy tekinthetünk a fájl maradék részére mint tömörítetlen adat és úgy folytatjuk, mintha egy másik számérték következett volna.
  • A (3)-as példában látszik, hogy változékony adatok esetén a módszer nem csak rosszul tömörít, hanem annyira rosszul, hogy a kimeneti fájl nagysága kétszerese lett az eredetinek. Ez tetszőleges olyan jelsorozatnál előfordul, mely ismétlődésmentes. A problémát az okozza, hogy amennyiben egy elem hosszúságú sorozatot kódolunk, az ismétlődésszám és maga az elem már nagyobb lesz, mint az eredeti egy darab adat. A gyakorlatban a fenti módszert kicsit megjavítják ennek a hatásnak a kiküszöbölése érdekében. Érdemes például játszani az ismétlődési számot leíró adattípussal, ha az input adat túl sokszínű, akkor folyamatosan kevesebbet vesztünk. Például a fenti (3)-as példában, ha a számok 16 bitesek, az ismétlődési szám pedig csak 8 bites, akkor a kimeneti fájl nem a kétszeresére, hanem csupán(?) másfélszeresére nő. Persze ilyenkor a csupa azonosból álló adat tömörítésénél vesztünk, mert gyakrabban csordul majd túl a számláló.
  • Egy másik lehetséges megoldás, hogy bevezetünk egy speciális számot(legyen például a nulla) és úgy gondolkozunk majd kitömörítéskor, hogy bármilyen szám jön az inputon azt kiírjuk, ha nullás jön, akkor pedig a következő szám megmutatja, hogy hányszor fog következni az azt következő szám a betömörítést pedig ennek megfelelően úgy végezzük, hogy az inputra írjuk az olvasott számot, kivéve ha az ismétlődik legalább háromszor. Ezt előreolvasási technika alkalmazásával, illetve pufferezéssel könnyű megoldani. Ezzel a megoldással a fenti (3)-as példa ugyanakkora marad tömörítve, mint "simán". Természetesen ha a kiválasztott speciális érték jön a tömörítendő inputban, akkor is ismétlődésként kell tömöríteni, ha csupán egyszer szerepel!
  • Képtömörítőknél szokás az előző vezérjeles trükköt úgy alkalmazni, hogy csak egy bitet használunk erre a célra: Alapvetően kitömörítéskor az input elemet csak másoljuk, amennyiben a legfelső bitje 0. Ha a legfelső bit egyes, akkor vezérjelnek tekintjük és ilyenkor a többi bit árulja el, hogy a következő elem hányszor fog ismétlődni. Ennek a megoldásnak előnye, hogy a vezérjel és az ismétlődési szám egy adatként tárolódik, illetve hogy a vezérjel csupán egy bitet foglal el. Hátrány a sima megoldáshoz képest, hogy így az összes olyan számértéket, melynek legfelső bitje egy, úgy kell tárolnunk, mintha ismétlődne.
  • Nagyon sok egyéb trükközést és módosítást alkalmaznak még az RLE tömörítés felhasználásakor, gyakran egyéb veszteséges vagy veszteségmentes tömörítésekkel is alkalmazzák elő vagy utófeldolgozásként. Például ha először egy a hasonló színű és egymáshoz közel lévő pixeleket egy köztes színűé alakító algoritmust alkalmazunk, majd az eredményt RLE-vel tömörítjük egy egyszerű veszteséges képtömörítőt kapunk. Képtömörítésnél szokás még a bejárás milyenségét is változtatni, sokszor a sorfolytonos bejárás helyett célszerűbb például kis négyzet alakú területeket bejárni, esetleg csigavonalban. Szokásos eljárás az is, hogy többféle RLE-variációt is alkalmaznak. Az inputfájlon ilyenkor lefuttatják az egyes variánsokat és a legjobb tömörítési arányt elérő változattal mentik az outputot a fejlécében az információval arról, hogy milyen megoldással kell kitömöríteni az adott állományt. Ehhez hasonlítható az a módszer is, ami kipróbál egy adott bináris fájlt több, különböző nagyságú szóhosszúsággal kódolni(4bit, 8bit, 16bit,...) és itt is a legjobbat használja, viszont az egybites szóhosszúságon működő bináris RLE kódolást külön ismertetjük lejjebb!

Bináris RLE[szerkesztés]

A hagyományos RLE kódolás nem igazán működik bináris szóhosszúsággal, viszont sokszor hasznos bináris számokat futásihossz kóddal kódolni. Például ha egy adatbázisban úgy tároljuk a táblát, hogy minden értékhez oszloponként nyilvántartjuk egy un. Bitmap index segítségével, hogy mely sorokban veszi fel az adott értéket, akkor valószínűleg egymás mellett sok nullát és csak időnként néhány egyest tartalmazó vektorokat kapunk értékenként. Az ilyen és ehhez hasonló problémák megoldására használt egybites szóhosszúságú speciális RLE kódolást nevezik bináris RLE variánsnak.

A tömörítés a következőképp zajlik: Olvassuk a bemeneti bitsorozatot amíg egyest nem érünk. Ha ez megvan, meghatározzuk, hogy hány bit szükséges az ismétlődési szám tárolásához. Ha ez megvan az outputra kiírunk eggyel kevesebb darab egyest, mint ahány bit az ismétlődési szám tárolásához szükséges lesz, majd egy nullást és az ismétlődési számot annyi biten, amennyi kellett a tároláshoz. A módszert addig ismételjük, amíg a fájl végére nem érünk. A kitömörítés itt is értelemszerűen történik. A csupa nullás bitsorozat kódolásához és dekódolásához felhasználjuk, hogy a bitsorozat hossza ismert!

Példa(Bináris RLE)[szerkesztés]

  • Input bitsorozat(1):

00000010100001 (14bit)

  • Output bitsorozat(1):

11011001110100 (14bit)

  • Ugyanis 6 darab nullás bitet számolunk és a 6-os érték 3 biten ábrázolható(110), ezért kiíródik az outputra 110110 a három bitet jelentő 110 és a 6-os ismétlődést jelző 110. Természetesen azt, hogy nullás bitek ismétlődnek nem tároljuk el! Hasonlóan lesz a 01 sorozatból 01 és a 00001 sorozatból 110100.
  • Input bitsorozat(2):

00000000000000000000000000000001 (32bit)

  • Output bitsorozat(2):

1111011111 (10bit)

  • Ugyanis 31-szer ismétlődik a nullás bit és így az ismétlődési szám(11111) 5 biten fér el.
  • Megjegyzés: Azt hogy az az ismétlődési szám hány biten fér el, a legfelső aktív bit helyével határozhatjuk meg, de hosszú ismétlődéseknél a gyakorlatban ajánlott inkább növelni a bitek számát, ha túlcsordulás jelentkezik.