Overblog Suivre ce blog
Editer l'article Administration Créer mon blog
26 septembre 2010 7 26 /09 /septembre /2010 16:45

 

Bonjour à tous,

Nous avons vu l'autre jour que l'algorithme LZW était très simple à implémenter en Python : une quinzaine de lignes suffit pour coder la fonction de compression et la décompression n'est pas plus longue. Pour autant, nous nous sommes arrêtés à produire un tableau d'entiers de 32 bits en sortie de notre fonction de compression. Il s'agit maintenant de stocker ces entiers de manière à ce qu'ils tiennent le moins de place possible en mémoire.

Nous allons utiliser un codage très simple. L'algorithme LZW utilise un compteur qui s'incrémente pour identifier les combinaisons d'octets rencontrées. C'est la variable n des fonctions compress et uncompress. Cette valeur ne fait qu'augmenter au fur et à mesure. Les premiers nombres, de 256 à 511, ne nécessitent que 9 bits pour être représentés. Une fois qu'on aura dépassé cette limite, les nombres de 512 à 1023 nécessiteront 10bits, et ainsi de suite. On commence à 8 bits et chaque fois que l'on franchit une nouvelle limite, on double la quantité de nombres représentables en ajoutant un bit.

 

Codage

Nous allons coder n'importe quel nombre N par la valeur N+1. Ainsi, on s'assure qu'on ne pourra jamais rencontrer la valeur 0 dans la séquence codée. Le zéro sera utilisé pour signifier que l'on ajoute un bit supplémentaire pour représenter les nombres suivants. C'est ce que fait la fonction « pack » :

 def pack(seq):
nbits = 8 # nombre de bits par nombre
bits = array.array('B') # tableau de bits
output = array.array('B') # sortie codée

# convertit les entiers en liste de 0 ou 1
for n in seq:
if n+1 > 2**nbits-1: # si on dépasse la limite
b = _int_to_bits(0, nbits) # ajoute 0
bits.extend(b)
nbits += 1 # on utilise un bit de plus
b = _int_to_bits(n+1, nbits) # ajoute n+1
bits.extend(b)

# allonge la séquence sur un multiple de 8
while len(bits) % 8:
bits.append(0)

# code les bits 8 par 8 dans des octets.
index = 0
size = len(bits)
while index < size:
byte = _int_from_bits(bits[index:index+8])
output.append(byte)
index += 8
return output



Entiers et séquences de bits

La fonction pack fait appel à deux fonctions utilitaires pour convertir des nombres en suites de bits et vice et versa. Voici leur codes. Tout d'abord la fonction « _int_to_bits » :

 def _int_to_bits(num, nbits):
output = array.array('B')
for bit_index in range(nbits-1, -1, -1):
mask = 1 << bit_index
if num & mask:
output.append(1)
else:
output.append(0)
return output

 

Le paramètre « num » indique le nombre à convertir, le paramètre « nbits » est le nombre de bits à utiliser en sortie. La fonction inverse, ne prend qu'un seul paramètre, une séquence de bits dont on connait nécessairement la taille :

 def _int_from_bits(seq):
output = 0
nbits = len(seq)
for bit_index in range(nbits):
if seq[(nbits-1) - bit_index] == 1:
output |= 1 << bit_index
return output

 

Décodage

La fonction de décodage n'est pas plus compliquée que la fonction de codage :

 def unpack(seq):
bits = array.array('B')
output = [] # sortie décodée

# convertir les octets en suite de bits
for n in seq:
b = _int_to_bits(n, 8)
bits.extend(b)

index = 0
nbits = 8 # nombre de bits par nombre
size = len(bits)

# convertir les bits en entiers
while index < size:
limit = min(index+nbits, size)
i = _int_from_bits(bits[index:limit]) # bits -> nombre
if i == 0:
nbits += 1 # code les nombres sur un bit de plus
else:
output.append(i-1) # N -> N-1
index += limit-index
return output

Utilisation 

Pour tester le résultat de notre petite séance de codage, je vais utiliser le fameux faux texte latin Lorem ipsum  dans sa version populaire. Le tout se passe dans un shell Python interactif :

 >>> import lzw
>>> s = "Lorem ipsum [...] amet." # Je vous épargne les détails
>>> len(s)
2054 # la taille de la chaine non compressée
>>> sc = lzw.pack(lzw.compress(s)) # compresse et code le texte dans sc
>>> len(sc)
1197 # La version compressée par LZW tient presque deux fois moins de place :)
>>> s2 = lzw.uncompress(lzw.unpack(sc)) # décompression
>>> s2 == s
True # La preuve que tout marche bien ! Ouf !

Voilà nous avons fait le tour de l'algorithme, il est assez simple et fonctionne remarquablement bien sur du texte. J'ai testé celui-ci avec Python 2.6.5 sur Linux, mais il devrait marcher sans trop de modifications avec Python 3.

Merci de votre attention !

Partager cet article

Repost 0
Published by Olivier - dans Programmation
commenter cet article

commentaires

Kokol 13/04/2016 18:01

Bonjour,
je me demandais à quoi correspond le '<<' par exemple dans :
mask = 1 << bit_index,
impossible de trouver quoiqque ce soit a son sujet, pouvez vous m'éclairer?

Kokol 14/04/2016 11:12

Ah très bien, merci beaucoup!

Olivier 13/04/2016 18:34

Bonjour,

Il s'agit d'un décalage binaire vers la gauche. Ici on décale la valeur 1 de bit_index rangs vers la gauche.

https://fr.wikipedia.org/wiki/Op%C3%A9ration_bit_%C3%A0_bit#D.C3.A9calages_de_bit

Présentation

Recherche

Liens