Run-length koodaus

RLE - pakkaus tai Run-length-koodaus on hyvin yksinkertainen tietojen pakkausmuoto , jossa peräkkäiset datasekvenssit, joilla on sama arvo, tallennetaan yhtenä arvona plus sen lukumäärä. Tämä on hyödyllisin tiedoissa, jotka sisältävät monia tällaisia ​​"sekvenssejä"; esimerkiksi yksinkertaista grafiikkaa tasaisilla värialueilla, kuten kuvakkeita ja logoja .

Harkitse esimerkiksi näyttöä, jossa on mustaa tekstiä valkoisella taustalla. Tällaisia ​​sekvenssejä, joissa on valkoisia pikseleitä tyhjissä marginaaleissa, ja muita mustia pikseleitä tekstialueella olisi monia. Oletetaan, että yksi viiva (tai skannausviiva ), jossa N edustaa mustia alueita ja B valkoisia:

BBBBBBBBBBBBBBBBBBBBBBBBBBNNNBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBBB

Jos käytämme run-length-koodausta tälle riville, saamme seuraavan:

12B1N12B3N24B1N14B

Tulkitaan tämä 12 B-kirjaimeksi, 1 N-kirjaimeksi, 12 B-kirjaimeksi, 3 N-kirjaimeksi jne. Run-length- koodi tuottaa alkuperäiset 67 merkkiä vain 18:ssa. Tämä tarkoittaa, että alkuperäinen rivi on 67 tavua ja koodattu merkkijono vain 18 tavua. Tätä binäärikoodausta , jonka periaate on sama, käytetään kuvien tallentamiseen. Jopa binääridatatiedostot voidaan pakata tällä menetelmällä. Ensimmäinen tavu sisältää luvun, joka edustaa merkin toistojen määrää. Toinen tavu sisältää itse merkin. Muissa tapauksissa ne on koodattu yhteen tavuun: 1 bitti (0 tai 1) ja 7 bittiä peräkkäisten merkkien määrän määrittämiseksi.

Nykyaikaisemmat pakkausjärjestelmät käyttävät kuitenkin usein deflaatioalgoritmia tai muita LZ77 -pohjaisia ​​algoritmeja , joiden etuna on merkkijonosekvenssien käyttö .

Joitakin tätä koodausta käyttäviä muotoja ovat Packbits , PCX ja ILBM .

Run-length-koodaus suorittaa häviöttömän tietojen pakkaamisen , ja sitä käytetään laajalti indeksoiduissa 8-bittisissä kuvissa (se käytettiin alun perin mustavalkoisiin kuviin). Se ei toimi yhtä hyvin jatkuvasti vaihtelevissa pikselivärikuvissa kuin valokuvissa, vaikka JPEG käyttää sitä tehokkaasti kertoimiin, jotka jäävät jäljelle kuvalohkojen muuntamisen ja kvantisoinnin jälkeen. Se on sittemmin muodostanut perustan muille pakkausjärjestelmille, kuten CCITT Group 3 – 1D