🧠 Kompresné algoritmy v Pythone

📦 Run Length Encoding (RLE)

Jednoduchý algoritmus: ukladá (počet, znak).

✅ Kódovanie

def rle_encode(data: str) -> str:
    if not data:
        return ""

    result = []
    count = 1

    for i in range(1, len(data)):
        if data[i] == data[i - 1]:
            count += 1
        else:
            result.append(f"{count}{data[i-1]}")
            count = 1

    result.append(f"{count}{data[-1]}")
    return "".join(result)

🔓 Dekódovanie

def rle_decode(data: str) -> str:
    result = ""
    count = ""

    for char in data:
        if char.isdigit():
            count += char
        else:
            result += char * int(count)
            count = ""

    return result

▶️ Príklad

text = "WWWWWWWWWWWWBWWWWWWWWWWWWBBBWWWWWWWWWWWWWWWWWWWWWWBWWWWWWWWWWWWWW"

encoded = rle_encode(text)
decoded = rle_decode(encoded)

print(encoded)  # 12W1B12W3B24W1B14W
print(decoded == text)  # True

📚 Lempel-Ziv 77 (LZ77)

Používa posunutie (offset), dĺžku, ďalší znak.

✅ Kódovanie (jednoduchá verzia)

def lz77_encode(data: str, window_size=20):
    i = 0
    output = []

    while i < len(data):
        match_length = 0
        match_distance = 0

        start = max(0, i - window_size)

        for j in range(start, i):
            length = 0
            while (i + length < len(data) and
                   data[j + length] == data[i + length]):
                length += 1
                if j + length >= i:
                    break

            if length > match_length:
                match_length = length
                match_distance = i - j

        next_char = data[i + match_length] if i + match_length < len(data) else ''
        output.append((match_distance, match_length, next_char))

        i += match_length + 1

    return output

🔓 Dekódovanie

def lz77_decode(encoded):
    result = ""

    for distance, length, char in encoded:
        if distance == 0:
            result += char
        else:
            start = len(result) - distance
            for i in range(length):
                result += result[start + i]
            result += char

    return result

▶️ Príklad

text = "ABABABA"

encoded = lz77_encode(text)
decoded = lz77_decode(encoded)

print(encoded)
print(decoded)

📖 Lempel-Ziv 78 (LZ78)

Používa slovník: (index, znak).

✅ Kódovanie

def lz78_encode(data: str):
    dictionary = {}
    result = []
    buffer = ""
    index = 1

    for char in data:
        if buffer + char in dictionary:
            buffer += char
        else:
            result.append((dictionary.get(buffer, 0), char))
            dictionary[buffer + char] = index
            index += 1
            buffer = ""

    if buffer:
        result.append((dictionary[buffer], ""))

    return result

🔓 Dekódovanie

def lz78_decode(encoded):
    dictionary = {0: ""}
    result = ""
    index = 1

    for idx, char in encoded:
        entry = dictionary[idx] + char
        result += entry
        dictionary[index] = entry
        index += 1

    return result

▶️ Príklad

text = "ABAABABAABAB"

encoded = lz78_encode(text)
decoded = lz78_decode(encoded)

print(encoded)
print(decoded)

🧪 (Bonus) LZW – praktickejšia verzia

Používa sa v GIF, PDF, ZIP.

✅ Kódovanie

def lzw_encode(data: str):
    dictionary = {chr(i): i for i in range(256)}
    current = ""
    result = []
    code = 256

    for char in data:
        combined = current + char
        if combined in dictionary:
            current = combined
        else:
            result.append(dictionary[current])
            dictionary[combined] = code
            code += 1
            current = char

    if current:
        result.append(dictionary[current])

    return result

🔓 Dekódovanie

def lzw_decode(data):
    dictionary = {i: chr(i) for i in range(256)}
    result = ""
    prev = chr(data[0])
    result += prev
    code = 256

    for curr_code in data[1:]:
        if curr_code in dictionary:
            entry = dictionary[curr_code]
        elif curr_code == code:
            entry = prev + prev[0]
        else:
            raise ValueError("Invalid LZW code")

        result += entry
        dictionary[code] = prev + entry[0]
        code += 1
        prev = entry

    return result

🧾 Zhrnutie

# RLE  → jednoduché opakovania (ASCII art)
# LZ77 → sliding window (gzip základ)
# LZ78 → slovník
# LZW  → optimalizovaná verzia (GIF, PDF)