Compression par dictionnaire

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche

Les algorithmes de compression par dictionnaire procèdent par la recherche de similitudes entre le texte à compresser et un ensemble de chaines contenues dans une structure de données appelée « dictionnaire », quand une similitude est trouvée, le texte correspondant est remplacé par une référence vers l'emplacement de cette chaîne dans la structure.

Méthodes et applications[modifier | modifier le code]

Pour le principe : on établit une liste de mots fréquents, pour compresser un fichier quand on trouve un mot dans la liste, on remplace ce mot par sa position dans la liste.

On peut trouver deux types de fonctionnement :

  • un dictionnaire calculé une fois pour toutes ;
  • un dictionnaire qui évolue.

Si on prend par exemple un texte en français, le français contenant environ 200 000 mots, pour coder l'ensemble de ces mots il suffirait en principe de 18

bits (218= 262144), un mot français contenant 5 caractères en moyenne, on pourrait gagner un facteur de l’ordre de 55%.

Exemples[modifier | modifier le code]

Lempel-Ziv-Oberhumer (LZO) est un algorithme de compression de données se focalisant sur la vitesse de décompression sans pertes à dictionnaire.

Avec LZ78 nous avons un dictionnaire mis à jour progressivement, à chaque étape, on cherche le mot le plus court qui ne soit pas présent dans le dictionnaire, on écrit la position du mot trouvé ainsi que la lettre à ajouter, on écrit le nouveau mot dans le dictionnaire puis on continue à partir de la suite.

dans dictionnaire ajout valeur
non trouvé 1 A (0,A)
non trouvé 2 v (0,v)
non trouvé 3 e (0,e)
non trouvé 4 c (0,c)
non trouvé 5 " " (0," ")
non(trouvé 6 L (0,L)
non trouvé 7 Z (0,Z)
non trouvé 8 7 (0,7)
non trouvé 9 8 (0,8)
trouvé en 5
non trouvé 10 " n" (5,n)
non trouvé 11 o (0,o)
non trouvé 12 u (0,u)
non trouvé 13 s (0,s)
trouvé en 5
non trouvé 14 " a" (5,a)
trouvé en 2
trouvé en 11
trouvé en 13
trouvé en 5
trouvé en 12
trouvé en 10
trouvé en 5
non trouvé 15 "vons un d" (0,d)

Références[modifier | modifier le code]

https://members.loria.fr/EJeandel/files/Codage/02-2x2.pdf