Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
24 septembre 2010 5 24 /09 /septembre /2010 13:26

Bonjour à tous,

Dans le cadre de ce blog, j'inaugure une section programmation. Je vais parler aujourd'hui de l'algorithme de compression de données LZW. C'est un algorithme très simple, ce qui me permettra de toucher un large public. La compression de données, tout le monde a une idée de ce à quoi ça sert : réduire la place occupée par des données. LZW est un algorithme de compression non destructeur, c'est-à-dire que les données compressées puis décompressées sont strictement identiques à l'original. Compresser avec LZW « n'abime pas » les données (contrairement au JPEG pour les images, ou au MP3 pour l'audio, par exemple). Cet algorithme est très célèbre, car il est au coeur du format d'image GIF, qui a secoué le web au début des années 2000. La société qui possédait le brevet sur cet algorithme s'est mise à menacer tous les éditeurs de navigateurs et de logiciels d'édition d'images pour non-paiement de royalties. C'est d'ailleurs ce qui a poussé à l'élaboration du format d'image PNG, qui est plus riche en fonctionnalités que le GIF et qui n'utilise pas LZW. Depuis 2004, ce brevet est tombé dans le domaine public, on peut donc utiliser LZW sans souci partout dans le monde.

 

Je ne vais pas détailler ici l'algorithme complet, la page Wikipédia qui y est consacrée serait de toute manière bien plus pédagogique que ma modeste prose. Je vais me contenter de fournir une implémentation de l'algorithme en Python en respectant les noms et les conventions qui sont utilisés sur Wikipédia. Ça permettra au lecteur de faire la correspondance entre le code et la description de l'algorithme plus facilement. Le choix d'un langage de haut niveau comme Python facilite la traduction de certaines opérations comme « ajouter au dictionnaire », puisque le langage possède un type dictionnaire intégré.

 

Compression

Voyons tout d'abord la compression des données. C'est le propos de la fonction « compress » :

 def compress(data):

dic = dict([[chr(i), i] for i in range(256)]) #Crée le dictionnaire initial

output = array.array('I') #liste de nombres en sortie

n = 256 #code de la prochaine combinaison

w = ""

for c in data:

wc = w + c

if wc in dic:

w = wc

else:

dic[wc] = n

n += 1

output.append(dic[w])

w = c

output.append(dic[w])

return output

 

C'est tout ? Oui. Le terrible algorithme qui a fait trembler le web au début des années 2000 peut être implémenté en 15 lignes de Python... Je vous laisse juges de savoir s'il était utile de faire tout un pataquès pour si peu. En tout cas, il est pratique, car il est suffisamment simple et concis pour être abordé dans le cadre d'un blog. :) Magie du typage dynamique, le paramètre data peut être une chaîne de caractères 8 bits, un objet array ou une liste d'octets. Pour des raisons d'efficacité mémoire, je préfère renvoyer un array plutôt qu'une liste. Voyons maintenant la décompression...

Décompression

Sans surprise, la décompression est tout aussi simple :

 def uncompress(data):

dic = dict([i, chr(i)] for i in range(256))

output = [dic[data[0]]]

n = 256

w = data[0]

for c in data[1:]:

try:

entry = dic[c]

except KeyError:

entry = dic[w]

entry += entry[0]

output.append(entry)

dic[n] = dic[w] + entry[0]

n += 1

w = c

return "".join(output)

 

Conclusion

L'implémentation présentée ici n'est pas complète. En effet je me suis intéressé ici à l'implémentation théorique de l'algorithme, qui renvoie comme résultat une liste d'entiers. Chacun de ces entiers va prendre une place fixe non optimale en mémoire (généralement 32 bits). Or un nombre comme 260 (par exemple) n'a besoin que de 9 bits pour être exprimé. La prochaine étape consistera donc à réduire leur volume en utilisant un codage à nombre de bits variable. Ce sera le sujet d'un prochain billet. Je proposerai alors le code source complet (et directement utilisable) de mon module LZW.

Merci de votre attention.

 

Partager cet article

Repost 0
Published by Olivier Pisano - dans Programmation
commenter cet article

commentaires

Présentation

Recherche

Liens