A futáshosszúságú kódolás ( eng. r un- l ength e ncoding , RLE ) vagy ismétléses kódolás egy adattömörítési algoritmus , amely az ismétlődő karaktereket (sorozatokat) egy karakterre és annak ismétlődéseinek számára cseréli. A sorozat több azonos karakterből álló sorozat. Kódoláskor (csomagolás, tömörítés) a sorozatot alkotó azonos karakterekből álló sztringet egy magát az ismétlődő karaktert és annak ismétlődéseinek számát tartalmazó sztring helyettesíti.
Vegyünk egy olyan képet, amely fekete szöveget tartalmaz tömör fehér alapon. Egy ilyen kép pixeleinek soronkénti olvasásakor fehér (háttér) és fekete (betűk) pixelek sorozata lesz . A betű Begy fekete, a betű pedig W egy fehér pixelt jelöl. Vegyünk egy tetszőleges, 51 karakter hosszúságú képsort:
WWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWWSzámoljuk meg a karakterek számát:
Összesen 5 epizód található. Cseréljük le a sorozatot az ismétlések számával és magával az ismétlődő karakterrel:
9W3B24W1B14WAz eredmény egy 12 karakterből álló sorozat lett. Az eredeti sorozat 51 karakterből állt. Az adatokat 51/12≈4,25-szer tömörítettük.
Vegyünk egy karakterláncot, amely nagyszámú nem ismétlődő karakterből áll:
ABCABCABCDDDFFFFFFAz RLE módszerrel történő tömörítés után egy ilyen sor így fog kinézni:
1A1B1C1A1B1C1A1B1C3D6FAz eredeti karakterlánc 18 karakterből áll, a tömörített karakterlánc pedig 22 karakterből áll. Az adatméret 22/18≈1,22-szeresére nőtt.
Annak érdekében, hogy a tömörítés után az adatméret ne nőjön, az ábécét, amelyben a futások hosszát rögzítjük, két részre osztjuk (általában egyenlő). Például az egész számok ábécéje két részre osztható: pozitív és negatív számokra. A pozitív számok egy karakter ismétlődéseinek számának rögzítésére szolgálnak, a negatív számok pedig az egymást követő egyenlőtlen karakterek számának rögzítésére.
Számoljuk meg a karaktereket a fentiek figyelembevételével:
A tömörített karakterlánc a következőképpen lesz írva:
-9ABCABCABC3D6FAz eredeti karakterlánc 18 karakterből áll, a tömörített karakterlánc pedig 15 karakterből áll. Az adatméret 18/15=1,2-szeresére csökkent.
Tegyük fel, hogy az RLE metódus a sorozat hosszának rögzítésére (a karakterek számának megszámlálására) egy egész típusú változót használ „ ” jellel. Egy ilyen változóba -128 és 127 közötti számokat írhat be. Mi van, ha a sorozat hossza 128 karakter vagy több? Ebben az esetben a sorozatot részekre osztják úgy, hogy a rész hossza ne haladja meg a 127 karaktert. Például egy 256 "A" karakterből álló futás a következő karakterlánccal lenne kódolva (256=127+127+2): signed char
127A127A2AAz RLE algoritmus bizonyos programozási nyelveken történő megírása, figyelembe véve ezeket a korlátozásokat, nem triviális.
Természetesen a képek tárolására használt kódolás bináris adatokon működik, és nem ASCII-karaktereken , mint a tárgyalt példákban, de az elv ugyanaz marad.
Nyilvánvalóan az ilyen kódolás hatékony nagyszámú sorozatot tartalmazó adatok esetén, például egyszerű grafikus képek, például ikonok és grafikák esetében. Ez a kódolás azonban nem megfelelő sima tónusú képekhez, például fényképekhez.
Az RLE-vel való adatcsomagolás általános formátumai közé tartozik a PackBits , a PCX és az ILBM .
A tetszőleges bináris adatfájlok tömöríthetők futáshosszúságú kódolással , mivel a fájlformátum-specifikációk gyakran tartalmaznak ismétlődő bájtokat az adatigazítási területen. A modern tömörítési rendszerek (mint például a Deflate ) azonban gyakrabban használnak LZ77 - alapú algoritmusokat , amelyek a futáshosszúságú kódolási módszer általánosításai, és "BWWBWWBWWBWW" formájú karaktersorozatokon működnek.
A hosszú, egymást követő bájtfutású hangadatok (például gyenge minőségű hangminták ) RLE-vel tömöríthetők, miután Delta kódolást alkalmaztak rájuk .
| Tömörítési módszerek | |||||||
|---|---|---|---|---|---|---|---|
| Elmélet |
| ||||||
| Veszteségmentes |
| ||||||
| Hang |
| ||||||
| Képek |
| ||||||
| Videó |
| ||||||