Run pituuskoodaus ( eng. r un- l ength e ncoding , RLE ) tai toistokoodaus on tietojen pakkausalgoritmi , joka korvaa toistuvat merkit (sarjan) yhdellä merkillä ja sen toistojen lukumäärällä. Sarja on sarja, joka koostuu useista identtisistä hahmoista. Koodauksessa (pakkauksessa, pakkaamisessa) sarjan muodostavien identtisten merkkien merkkijono korvataan merkkijonolla, joka sisältää itse toistuvan merkin ja sen toistojen lukumäärän.
Harkitse kuvaa, joka sisältää mustaa tekstiä tasaisella valkoisella taustalla. Kun luetaan tällaisen kuvan pikseleitä rivi riviltä, tulee sarja valkoisia (tausta) ja mustia (kirjaimet) pikseleitä . Kirjain Btarkoittaa mustaa pikseliä ja kirjain W valkoista pikseliä. Harkitse mielivaltaista kuvamerkkijonoa, jonka pituus on 51 merkkiä:
WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWLasketaan merkkien määrä:
Yhteensä löytyi 5 jaksoa. Korvataan sarja toistojen lukumäärällä ja itse toistuvalla symbolilla:
9W3B24W1B14WTuloksena oli 12 merkin pituinen sarja. Alkuperäinen sarja koostui 51 merkistä. Tiedot pakattiin 51/12≈4,25 kertaa.
Otetaan merkkijono, joka koostuu suuresta määrästä ei-toistuvia merkkejä:
ABCABCABCDDDFFFFFFRLE-menetelmällä tehdyn pakkaamisen jälkeen tällainen rivi näyttää tältä:
1A1B1C1A1B1C1A1B1C3D6FAlkuperäinen merkkijono koostuu 18 merkistä ja pakattu merkkijono 22. Tietokoko on kasvanut 22/18≈1,22 kertaa.
Jotta pakkaamisen jälkeen datan koko ei kasvaisi, aakkoset, joihin juoksujen pituudet tallennetaan, jaetaan kahteen osaan (yleensä yhtä suureen). Esimerkiksi kokonaislukujen aakkoset voidaan jakaa kahteen osaan: positiivisiin ja negatiivisiin lukuihin. Positiivisia numeroita käytetään kirjaamaan yhden merkin toistojen lukumäärä ja negatiivisia numeroita kirjaamaan toisiaan seuraavien eri merkkien lukumäärä.
Lasketaan merkit ottaen huomioon ylläoleva:
Pakattu merkkijono kirjoitetaan seuraavasti:
-9ABCABCABC3D6FAlkuperäinen merkkijono koostuu 18 merkistä ja pakattu merkkijono 15. Tietojen koko on pienentynyt 18/15=1,2 kertaa.
Oletetaan, että RLE-menetelmän toteutus sarjan pituuksien tallentamiseksi (merkkien määrän laskemiseksi) käyttää kokonaislukutyyppistä muuttujaa, jonka merkki on “ ”. Tällaiseen muuttujaan voit kirjoittaa numeroita -128 - 127 mukaan lukien. Entä jos sarjan pituus on 128 merkkiä tai enemmän? Tässä tapauksessa sarja jaetaan osiin siten, että osan pituus ei ylitä 127 merkkiä. Esimerkiksi 256 A-merkin sarja koodataan seuraavalla merkkijonolla (256=127+127+2): signed char
127A127A2ARLE-algoritmin kirjoittaminen jollain ohjelmointikielellä nämä rajoitukset huomioon ottaen ei ole triviaalia.
Tietenkin kuvien tallentamiseen käytetty koodaus toimii binääritiedolla eikä ASCII-merkeillä , kuten käsitellyissä esimerkeissä, mutta periaate pysyy samana.
Ilmeisesti tällainen koodaus on tehokas datalle, joka sisältää suuren määrän sarjoja, esimerkiksi yksinkertaisille graafisille kuville, kuten ikoneille ja grafiikalle. Tämä koodaus ei kuitenkaan sovellu hyvin tasaisille kuville, kuten valokuville.
Yleisiä datan pakkausmuotoja RLE:llä ovat PackBits , PCX ja ILBM .
Mielivaltaiset binaaridatatiedostot voidaan pakata run-length-koodauksella , koska tiedostomuotomääritykset sisältävät usein toistuvia tavuja tietojen kohdistusalueella. Nykyaikaiset pakkausjärjestelmät (kuten Deflate ) käyttävät kuitenkin useammin LZ77 - pohjaisia algoritmeja , jotka ovat yleistys run-length-koodausmenetelmästä ja toimivat "BWWBWWBWWWBWW"-muotoisilla merkkisarjoilla.
Audiodata , jolla on pitkiä peräkkäisiä tavuajoja (kuten huonolaatuiset ääninäytteet ), voidaan pakata RLE:llä sen jälkeen, kun siihen on käytetty Delta-koodausta .
| Puristusmenetelmät _ | |||||||
|---|---|---|---|---|---|---|---|
| Teoria |
| ||||||
| Häviötön |
| ||||||
| Audio |
| ||||||
| Kuvat |
| ||||||
| Video |
| ||||||