Í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.
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.
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 == input_string:
count += 1
else:
encoded.append(f"{count}{input_string}")
count = 1
# Utolsó karakter hozzáadása
encoded.append(f"{count}{input_string}")
return "".join(encoded)
# Teszt
input_string = "AAABBBCCDAA"
print(run_length_encoding(input_string)) # Kimenet: 3A3B2C1D2A
#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 == input) {
++count;
} else {
encoded += to_string(count) + input;
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
Ha szeretnéd a visszafejtési (dekódolási) változatot is, csak jelezd! 😊