#!/usr/bin/env python3 # -*- coding: utf-8 -*- """ Created on Fri Oct 28 21:16:56 2022 @author: adomps """ # https://www.lama.univ-savoie.fr/pagesmembres/hyvernat/Enseignement/1718/math202/tp2.html # http://igm.univ-mlv.fr/~nicaud/M1/LZ78.pdf # https://compression.fiches-horaires.net/la-compression-sans-perte/lz78-et-lzw-la-compression-par-dictionnaire/ # Livre Aubibert Oussalah # TP Laurent Schwald def LZ78(chaine) : ''' Je renvoie une liste, c'est plus pratique pour la décompression, car on distingue immédiatement les nombres et les chaines.''' resultat = [] mot_courant = '' dico = {'' : 0} for alpha in chaine : print('\n--- caractère examiné : ', alpha) if (mot_courant + alpha) not in dico : resultat.append(dico[mot_courant]) resultat.append(alpha) dico[mot_courant+alpha] = len(dico) mot_courant ='' else : print('on poursuit') mot_courant += alpha print('resultat', resultat) print('dico', dico) if mot_courant != '' : # le dernier caractère a donné un mot déjà répertorié racourci = mot_courant[:-1] resultat.append(dico[racourci]) resultat.append(mot_courant[-1]) # c'est la dernière lettre return resultat mot1 = 'abracadabra' mot2 = 'ABABABCABCDE' mot3 = 'abaaaabaab' # exemple qui qui nécessite le traitement de la fin mot4 = 'bbbabbaabbbb' mot5 = 'ma maman a mangé' code1 = LZ78(mot1) code2 = LZ78(mot2) code3 = LZ78(mot3) code4 = LZ78(mot4) code5 = LZ78(mot5) # Version inspirée de Audibert et Oussalah, livre Ellipse # On utilise une sous-fonction. Il me semble que les instructions # qu'elle contient auraient pu être codées dans le while principal (plus bas). # Dans le livre, il manque le traitement du cas où le mot courant est vide # à la fin du parcours. # Je remarque aussi qu'il est inutile que la sous fonction renvoie résultat : # cette liste est une variable mutable et on peut se contenter de la modifier # par l'appel à la sous-fonction. J'ai écrit la version LZ78_ter plus loin pour ça. # On utilise une sous-fonction et non pas une fonction séparée dans # le but suivant : les variables chaine, n, dico seront connues # par la sous-fonction sans qu'il soit besoin de les passer dans ses # paramètres. Ça ne marcherait pas avec une fonction à part. def LZ78_bis(chaine) : def compresser(resultat, i) : assert i < len(chaine) mot_courant = '' while i < n and mot_courant + chaine[i] in dico : mot_courant += chaine[i] i += 1 if i < n : alpha = chaine[i] resultat.append(dico[mot_courant]) resultat.append(alpha) dico[mot_courant + alpha] = len(dico) # Partie omise par Audibert et Oussalah pour le traitement de la fin elif mot_courant != '' : racourci = mot_courant[:-1] resultat.append(dico[racourci]) resultat.append(mot_courant[-1]) return resultat, i+1 n = len(chaine) i, resultat, dico = 0, [], {'': 0} while i < n : resultat, i = compresser(resultat, i) return resultat print(LZ78_bis(mot1)) print(LZ78_bis(mot2)) print(LZ78_bis(mot3)) print(LZ78_bis(mot4)) print(LZ78_bis(mot5)) def LZ78_ter(chaine) : def compresser(resultat, i) : assert i < len(chaine) mot_courant = '' while i < n and mot_courant + chaine[i] in dico : mot_courant += chaine[i] i += 1 if i < n : alpha = chaine[i] resultat.append(dico[mot_courant]) resultat.append(alpha) dico[mot_courant + alpha] = len(dico) # Partie omise par Audibert et Oussalah pour le traitement de la fin elif mot_courant != '' : racourci = mot_courant[:-1] resultat.append(dico[racourci]) resultat.append(mot_courant[-1]) return i+1 n = len(chaine) i, resultat, dico = 0, [], {'': 0} while i < n : i = compresser(resultat, i) return resultat print(LZ78_ter(mot1)) print(LZ78_ter(mot2)) print(LZ78_ter(mot3)) print(LZ78_ter(mot4)) print(LZ78_ter(mot5)) def LZ78_decompresse(code): # On construit le dico inverse à la volée dico_inv = {0 : ''} resultat = '' for i, u in enumerate(code) : print('i', i, 'u', u) if i % 2 == 0 : # dans ce cas, code[i] est un entier mot = dico_inv[u] # en prévision de la prochaine étape resultat += mot else : # dans ce cas, code[i] est est un caractère resultat += u p = len(dico_inv) dico_inv[p] = mot + u print('dico', dico_inv) print(resultat) return resultat LZ78_decompresse(code1) LZ78_decompresse(code2) LZ78_decompresse(code3) LZ78_decompresse(code4) LZ78_decompresse(code5) ######################################################################### #### ÉTUDE EXPÉRIMENTALE DU TAUX DE COMPRESSION ################### ######################################################################### import numpy as np import random as rd import matplotlib.pyplot as plt bases = ['A', 'C', 'G', 'T'] ## Fonction qui génère une chaîne de caractères de longueur $n$ dont les caractères sont ## aléatoirement choisis dans {'A','T','C','G'}. def genere(n) : chaine = '' for i in range(n) : chaine += rd.choice(bases) return chaine ## Fonction qui renvoie la renvoie longueur moyenne des listes obtenues ## par compression de Nessais chaînes générées aléatoirement. def longueur_moyenne(n, Nessais) : #longueurs = np.zeros(Nessais, dtype = int) somme_L = 0 # pour calculer la moyenne << à la main >>. for i in range(Nessais) : chaine = genere(n) code = LZ78(chaine) #longueurs[i] = len(code) somme_L += len(code) #return np.average(longueurs) return somme_L / Nessais print(longueur_moyenne(10000, 100)) valeurs_n = [i for i in range(0, 10001, 1000)] longueurs_moy_code = [] for n in valeurs_n : l_moy = longueur_moyenne(n, 50) longueurs_moy_code.append(l_moy) plt.figure(0) plt.clf() plt.plot(valeurs_n, longueurs_moy_code) plt.plot(valeurs_n, 0.38*np.array(valeurs_n))