run-length encoding

Angol

Főnév

run-length encoding (tsz. run-length encodings)

(informatika) futáshossz-kódolás

Run-Length Encoding (RLE) egy egyszerű, de hatékony veszteségmentes tömörítési algoritmus, amelyet olyan adatoknál használnak, ahol ismétlődő értékek fordulnak elő egymás után, például képeknél, szöveges adatoknál vagy bináris fájloknál.

🧠 Alapötlet

A RLE nem az egyes karaktereket tárolja, hanem:

hány darab ugyanaz a karakter van egymás után (futam hossza),
milyen karakter ismétlődik.

Példa:

Eredeti szöveg:

AAAAABBBCCDAA

Tömörített forma (RLE):

5A3B2C1D2A

Ez azt jelenti:

5 darab A,
3 darab B,
2 darab C,
1 darab D,
2 darab A.

⚙️ Működés lépései

Bejárjuk a bemeneti adatokat sorban.
Számoljuk, hány ugyanolyan karakter van egymás után.
Az ismétlődő karaktereket egy számmal és egy jellel helyettesítjük.
Megismételjük ezt a végéig.

🧪 Egyszerű C++ példa

#include <iostream>
#include <string>
using namespace std;

string runLengthEncode(const string& input) {
    string encoded = "";
    int n = input.length();

    for (int i = 0; i < n; i++) {
        int count = 1;
        while (i + 1 < n && input[i] == input[i + 1]) {
            count++;
            i++;
        }
        encoded += to_string(count) + input[i];
    }

    return encoded;
}

int main() {
    string data = "AAABBBCCCCDA";
    cout << "Eredeti: " << data << endl;
    cout << "RLE: " << runLengthEncode(data) << endl;
    return 0;
}

🔄 Dekódolás (visszaalakítás)

A RLE tömörített adatokból visszaállítható az eredeti forma:

Számot beolvasunk → jelzi a futam hosszát.
Utána a karaktert → ismételjük n alkalommal.

📦 Alkalmazási területek

Fekete-fehér vagy kevés színt tartalmazó képek (pl. fax, BMP, TIFF)
Szöveg, ahol sok az ismétlődés (pl. space, tab)
Adatsorozatok, logikai értékek, bitmappák

⚖️ Előnyök és hátrányok

✅ Előnyök:

Nagyon gyors algoritmus
Egyszerű implementáció
Veszteségmentes tömörítés
Kis memóriaigény

❌ Hátrányok:

Nem hatékony ritka ismétlődésű adatoknál
Akár növelheti is a fájlméretet, ha sok különböző karakter van

🖼 Képi példa (bitmap)

Kép sor: 00000011110000

RLE formában: 6×0, 4×1, 4×0 → [6,0][4,1][4,0]

🧠 Összegzés

Téma	Leírás
Típus	Veszteségmentes
Lényege	Ismétlődések tömörítése
Hatékonyság	Magas ismétlődés esetén jó
Egyszerűsége	Nagyon könnyen implementálható
Korlátai	Alacsony hatékonyság szórt adatoknál

További információk

run-length encoding - Szótár.net (en-hu)
run-length encoding - Sztaki (en-hu)
run-length encoding - Merriam–Webster
run-length encoding - Cambridge
run-length encoding - WordNet
run-length encoding - Яндекс (en-ru)
run-length encoding - Google (en-hu)
run-length encoding - Wikidata
run-length encoding - Wikipédia (angol)