Run-length encoding

A run-length encoding (RLE, futáshossz-kódolás) egy nagyon egyszerű tömörítési eljárás, melyben az adatban található, hosszasan ismétlődő karaktereket egyetlen értékként és számként tárolják, az eredeti teljes karaktersorozat helyett. Ez leginkább sok ilyen hosszú karaktersorozattal rendelkező adatra hasznos: például egyszerű grafikus képek, mint ikonok, vonalrajzok és animációk. Nem hasznos azonban olyan adatokra, amelyeknél nincs sok ilyen karaktersorozat, hiszen jelentősen megnövelheti a fájlméretet.

Az RLE kifejezés utalhat egy korai, CompuServe által támogatott, fekete-fehér képeket tömörítő képformátumra is, amelyet később azonban az ő általuk létrehozott GIF formátum kiszorított. Az RLE továbbá jelöli a Windows 3.x-ben létező, kevéssé használt, rle kiterjesztésű képformátumot is, amely egy run-length encodinggal tömörített bitmap kép, amelyet például a Windows 3.x indítóképernyőjének tömörítéséhez használtak.

Példa

Például vegyünk egy rövid szöveget, amely egy teljesen fehér háttéren található. Ebben az esetben hosszú, kizárólagosan fehér pixelekből álló sorozatok lesznek az üres helyen, továbbá számos rövid fekete karaktersorozat. Vegyünk ebből egy egyszerű keresztmetszetet, ahol a B (black) a fekete és W (white) a fehér pixel. Ez például így nézhet ki:

WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW

Ha most ezen a run-length encoding (RLE) adattömörítő algoritmust alkalmazzuk, akkor kapjuk a következőt:

12W1B12W3B24W1B14W

Ennek az értelmezése: 12 W, 1 B, 12 W, 3B stb.

Így tehát a run-length encodinggal kódolt szöveg az eredeti 67 karaktert 18-cal írja le. Természetesen a képek tárolására szolgáló formátum általánosságban bináris, nem pedig az itt látható ASCII, azonban az alapelv megmarad. Még a bináris fájlok is tömöríthetők ezen eljárással; a fájlformátum-specifikációk gyakorta ismétlődő bájtokat hoznak létre. Mindazonáltal az újabb tömörítő eljárások, mint a DEFLATE gyakran használnak LZ77-alapú algoritmusokat, amelyek a run-length encoding általánosításai és nem csak egy karakter, hanem teljes sztringek ismétléseinél hasznosak lehetnek (mint például a BWWBWWBWWBWW).

Felhasználások

A run-length encoding veszteségmentes tömörítést ér el és jól használható a színskála-alapú ikonképekhez. Ellenben nem működik jól folytatólagos színváltásokkal rendelkező képekhez, mint például a fényképek, habár a JPEG eléggé hatékonyan használja a képblokkok átalakítása után.

A run-length encoding-ot használó adatformátumok többek között a Truevision TGA, a PackBits, a PCX és az ILBM.

A run-length encoding-ot használják továbbá a faxgépekben is (egyéb technikákkal kombinálva, mint a módosított Huffman-kódolás). Relatíve hatékony eljárás, mivel a legtöbb faxolt dokumentum leginkább fehér, néhány helyen megszakítva feketével.

Fordítás

• Ez a szócikk részben vagy egészben a Run-length encoding című angol Wikipédia-szócikk fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Források

• fileformat.info: Run-Length Encoding (RLE)

Lásd még

• Huffman-kódolás
• Burrows-Wheeler transzformáció

Források

• A run-length encoding implementációja számos programnyelvben (a Rosetta Code-on)
• Run-length encoding variációk Daniel Lemire által