Lempel-Ziv-Welch-algoritmus

Magyar

Kiejtés

IPA: [ ˈlɛmpɛlzivːɛlɦɒlɡoritmuʃ]

Főnév

(matematika) Az LZW-algoritmus (Lempel-Ziv-Welch) egy veszteségmentes adatkompressziós technika, amelyet Terry Welch dolgozott ki 1984-ben, az eredeti Lempel-Ziv algoritmusok továbbfejlesztéseként. Az LZW az ismétlődő mintázatok felismerésén és hatékony kódolásán alapul, és széles körben használják olyan formátumokban, mint a GIF, valamint tömörítési eszközökben.

Fő ötlet

Az LZW-algoritmus helyettesíti az ismétlődő szimbólumsorozatokat egyedi kódokkal egy dinamikusan bővülő szótár segítségével. Az algoritmus nem igényel előzetes ismereteket az adatokról, és a kódolás mellett visszafejtési képességgel is rendelkezik.

Elmélet

Alapok

Szótár:
- A kódolási folyamat egy előre inicializált szótárral indul, amely tartalmazza az összes lehetséges alapszimbólumot (pl. ASCII karakterek).
- A szótár dinamikusan bővül új szimbólumsorozatokkal, ahogy azokat az algoritmus találja.
Kódolási lépések:
- Olvasd az adatfolyamot karakterről karakterre.
- Ha egy ismert szimbólumsorozatot találsz, tartsd nyilván, és bővítsd a szótárt az új mintázattal.
- Helyettesítsd a sorozatot a szótár megfelelő kódjával.
Visszafejtés:
- A visszafejtés azonos módon használja a szótárat, hogy az adatfolyamot helyreállítsa.

Szótár bővítése:

Egy új sorozat hozzáadása: (W + K), ahol (W) az aktuális sorozat, (K) pedig az aktuális karakter.

Algoritmus lépései

Kódolás

Inicializáld a szótárat az alapszimbólumokkal.
Kezdd az első karakterrel ((W)).
Iterálj az adatfolyamon:
- Ha a következő karakterrel ((K)) bővített sorozat ((W + K)) szerepel a szótárban:
  - Állítsd be (W = W + K).
- Egyébként:
  - Kódold (W)-t a szótár megfelelő kódjával.
  - Adj hozzá a szótárhoz egy új bejegyzést ((W + K)).
  - Állítsd (W = K)-re.
Kódold (W)-t, amikor az adatfolyam véget ér.

Visszafejtés

Inicializáld a szótárat az alapszimbólumokkal.
Olvasd be az első kódot, és írd ki a hozzá tartozó szimbólumot.
Iterálj a kódokon:
- Ha a kód a szótárban van:
  - Írd ki a hozzá tartozó szimbólumot.
- Egyébként:
  - Kódolj egy új sorozatot az előző szimbólum alapján.
- Bővítsd a szótárat az új sorozattal.

Pszeudokód

Kódolás

LZW_Encode(input):
    Inicializáld a szótárat az összes alapszimbólummal
    W = ""
    output = []

    minden K karakter az inputban:
        ha W + K szerepel a szótárban:
            W = W + K
        különben:
            output.append(szótár[W])
            adj hozzá új bejegyzést a szótárhoz: W + K
            W = K

    ha W nem üres:
        output.append(szótár[W])

    térj vissza output

Visszafejtés

LZW_Decode(encoded):
    Inicializáld a szótárat az összes alapszimbólummal
    W = az első kód
    output = [szótár[W]]

    minden kód az encoded-ben a másodiktól:
        ha kód a szótárban van:
            entry = szótár[kód]
        különben:
            entry = szótár[W] + szótár[W][0]

        output.append(entry)
        adj hozzá új bejegyzést a szótárhoz: szótár[W] + entry[0]
        W = kód

    térj vissza output

Python implementáció

def lzw_encode(data):
    # Inicializáljuk a szótárat az összes ASCII karakterrel
    dictionary = {chr(i): i for i in range(256)}
    next_code = 256
    w = ""
    encoded = []

    for char in data:
        wc = w + char
        if wc in dictionary:
            w = wc
        else:
            encoded.append(dictionary[w])
            dictionary[wc] = next_code
            next_code += 1
            w = char

    if w:
        encoded.append(dictionary[w])

    return encoded

def lzw_decode(encoded):
    # Inicializáljuk a szótárat az összes ASCII karakterrel
    dictionary = {i: chr(i) for i in range(256)}
    next_code = 256

    w = chr(encoded.pop(0))
    decoded = [w]

    for k in encoded:
        if k in dictionary:
            entry = dictionary[k]
        elif k == next_code:
            entry = w + w[0]
        else:
            raise ValueError("Érvénytelen kód.")

        decoded.append(entry)

        dictionary[next_code] = w + entry[0]
        next_code += 1
        w = entry

    return "".join(decoded)

# Példa használat
data = "ABABABABABABABAB"
encoded = lzw_encode(data)
print("Kódolt:", encoded)
decoded = lzw_decode(encoded)
print("Visszafejtett:", decoded)

Kimenet:

Kódolt: [65, 66, 256, 258, 260, 262, 264]
Visszafejtett: ABABABABABABABAB

C++ implementáció

#include <iostream>
#include <vector>
#include <string>
#include <unordered_map>

using namespace std;

vector<int> lzw_encode(const string& data) {
    unordered_map<string, int> dictionary;
    for (int i = 0; i < 256; ++i) {
        dictionary[string(1, i)] = i;
    }

    string w;
    vector<int> encoded;
    int next_code = 256;

    for (char c : data) {
        string wc = w + c;
        if (dictionary.count(wc)) {
            w = wc;
        } else {
            encoded.push_back(dictionary[w]);
            dictionary[wc] = next_code++;
            w = string(1, c);
        }
    }

    if (!w.empty()) {
        encoded.push_back(dictionary[w]);
    }

    return encoded;
}

string lzw_decode(const vector<int>& encoded) {
    unordered_map<int, string> dictionary;
    for (int i = 0; i < 256; ++i) {
        dictionary[i] = string(1, i);
    }

    string w = dictionary[encoded[0]];
    string decoded = w;
    int next_code = 256;

    for (size_t i = 1; i < encoded.size(); ++i) {
        string entry;
        if (dictionary.count(encoded[i])) {
            entry = dictionary[encoded[i]];
        } else if (encoded[i] == next_code) {
            entry = w + w[0];
        } else {
            throw invalid_argument("Érvénytelen kód.");
        }

        decoded += entry;
        dictionary[next_code++] = w + entry[0];
        w = entry;
    }

    return decoded;
}

int main() {
    string data = "ABABABABABABABAB";
    vector<int> encoded = lzw_encode(data);
    cout << "Kódolt: ";
    for (int code : encoded) {
        cout << code << " ";
    }
    cout << endl;

    string decoded = lzw_decode(encoded);
    cout << "Visszafejtett: " << decoded << endl;

    return 0;
}

Kimenet:

Kódolt: 65 66 256 258 260 262 264 
Visszafejtett: ABABABABABABABAB

Összegzés

Előnyök:

Egyszerű és hatékony: Nincs szükség előzetes statisztikákra.
Gyors visszafejtés: Ugyanaz a szótárhasználat.

Hátrányok:

Szótár mérete: Nagy adatoknál a szótár gyorsan növekszik.
Nem hatékony kis ismétlődések esetén.

Az LZW-algoritmus egyszerűsége és hatékonysága miatt népszerű a veszteségmentes adatkompressziós alkalmazásokban.

További információk

Lempel-Ziv-Welch-algoritmus - Értelmező szótár (MEK)
Lempel-Ziv-Welch-algoritmus - Etimológiai szótár (UMIL)
Lempel-Ziv-Welch-algoritmus - Szótár.net (hu-hu)
Lempel-Ziv-Welch-algoritmus - DeepL (hu-de)
Lempel-Ziv-Welch-algoritmus - Яндекс (hu-ru)
Lempel-Ziv-Welch-algoritmus - Google (hu-en)
Lempel-Ziv-Welch-algoritmus - Helyesírási szótár (MTA)
Lempel-Ziv-Welch-algoritmus - Wikidata
Lempel-Ziv-Welch-algoritmus - Wikipédia (magyar)