Coding_and_Decoding_Lempel-Ziv-Welch_in_Python.py

import typing

## Encodage de Lempel-Ziv-Welch

def encodage_LZW(mot: str) -> typing.List[int]:
    codes_ecrits = []
    dictionnaire = { chr(i): i for i in range(255) }
    prochain_code = 257
    mot_actuel = ""
    n = len(mot)
    i = 0
    while i < n:
        lettre = mot[i]
        mot_actuel = mot_actuel + lettre
        print("Lecture de lettre = {}, mot actuel = {}".format(
            lettre, mot_actuel))
        if mot_actuel in dictionnaire:
            i += 1
        else:
            print("Ajout de '{}' au dictionnaire, de code = {}".format(
                  mot_actuel, prochain_code))
            dictionnaire[mot_actuel] = prochain_code
            prochain_code += 1
            code_actuel = dictionnaire[mot_actuel[:-1]]
            codes_ecrits.append(code_actuel)
            print("On écrit {} dans le code de sortie...".format(code_actuel))
            mot_actuel = mot_actuel[-1]
            i += 1
    if mot_actuel in dictionnaire:
        # on écrit le dernier mot
        code_actuel = dictionnaire[mot_actuel]
        codes_ecrits.append(code_actuel)
        print("On écrit {} dans le code de sortie...".format(code_actuel))
    return codes_ecrits

assert encodage_LZW("barbapapa") == [98, 97, 114, 257, 112, 97, 261]


## Décodage de Lempel-Ziv-Welch

def decodage_LZW(code_lu: typing.List[int]) -> str:
    mot_lu = ""
    dictionnaire = { i: chr(i) for i in range(255) }
    prochain_code = 257
    mot_actuel = ""
    
    m = len(code_lu)
    if m == 0: return ""
    
    code_actuel = code_lu[0]
    mot_actuel = dictionnaire[code_actuel]
    mot_lu += mot_actuel
    w = mot_actuel

    i = 1
    while i < m:
        code_actuel = code_lu[i]
        if code_actuel in dictionnaire:
            mot_actuel = dictionnaire[code_actuel]
            print("Code lu = {}, mot correspondant = {}.".format(
                code_actuel, mot_actuel))
        elif code_actuel == prochain_code:
            mot_actuel = w + w[0]
            print("Code lu = {}, mot correspondant = {}.".format(
                code_actuel, mot_actuel))
        else:
            raise ValueError("Mauvaise compression code_actuel = {}".format(code_actuel))
        mot_lu += mot_actuel
        print("Ajout de {} au dictionnaire, de valeur = '{}'".format(
            prochain_code, mot_actuel))
        dictionnaire[prochain_code] = w + mot_actuel[0]
        prochain_code += 1
        i += 1
        w = mot_actuel
    return mot_lu


assert decodage_LZW([98, 97, 114, 257, 112, 97, 261]) == "barbapapa"