futáshossz-kódolás

Kiejtés

  • IPA: [ ˈfutaːʃhoskoːdolaːʃ]

Főnév

futáshossz-kódolás

  1. (matematika)

Íme a futáshossz-kódolás (Run-Length Encoding, RLE) algoritmus leírása, valamint a pszeudokód, Python, és C++ implementációk.



1. Algoritmus leírása (pszeudo)

A futáshossz-kódolás egy tömörítési algoritmus, amely egymás után ismétlődő elemeket számlál.
Például: "AAABBBCCDAA"3A3B2C1D2A.

Pszeudokód:

1. Kezdj egy üres kimenettel.
2. Állítsd be az aktuális karaktert az első karakterre.
3. Számolj addig, amíg ugyanaz a karakter ismétlődik.
4. Add hozzá a számlálót és a karaktert a kimenethez.
5. Lépj a következő karakterre, ismételd a 3–4 lépéseket.
6. Végezd el a műveletet az összes karakterre.
7. Add vissza a tömörített kimenetet.

2. Python implementáció

def run_length_encoding(input_string):
    if not input_string:
        return ""
    
    encoded = []
    count = 1
    
    for i in range(1, len(input_string)):
        if input_string[i] == input_string[i-1]:
            count += 1
        else:
            encoded.append(f"{count}{input_string[i-1]}")
            count = 1
    
    # Utolsó karakter hozzáadása
    encoded.append(f"{count}{input_string[-1]}")
    
    return "".join(encoded)

# Teszt
input_string = "AAABBBCCDAA"
print(run_length_encoding(input_string))  # Kimenet: 3A3B2C1D2A

3. C++ implementáció

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

string runLengthEncoding(const string& input) {
    if (input.empty()) return "";

    string encoded = "";
    int count = 1;

    for (size_t i = 1; i < input.size(); ++i) {
        if (input[i] == input[i - 1]) {
            ++count;
        } else {
            encoded += to_string(count) + input[i - 1];
            count = 1;
        }
    }

    // Utolsó karakter hozzáadása
    encoded += to_string(count) + input.back();
    return encoded;
}

int main() {
    string input = "AAABBBCCDAA";
    cout << "Eredeti: " << input << endl;
    cout << "Tömörített: " << runLengthEncoding(input) << endl;
    return 0;
}

Kimenet:

Eredeti: AAABBBCCDAA  
Tömörített: 3A3B2C1D2A

Magyarázat:

  • A Python és C++ változat ugyanazon elvet követi:
    1. Végiglépked a bemeneti sztringen.
    1. Számolja az ismétlődő karaktereket.
    1. Amikor egy új karakterhez ér, az előző karaktert és a számlálót hozzáfűzi a kimenethez.
    1. Végül az utolsó karaktert is hozzáadja.

Ha szeretnéd a visszafejtési (dekódolási) változatot is, csak jelezd! 😊

Fordítások