Читать книгу Informationswissenschaft: Theorie, Methode und Praxis / Sciences de l'information: théorie, méthode et pratique - Группа авторов - Страница 37

Une famille d’algorithmes d’un type différent existe. Ce sont les algorithmes basés sur l’utilisation d’un dictionnaire. La stratégie consiste à parcourir le mot à compresser à la recherche de chaînes de caractères qui apparaissent dans un dictionnaire. Lorsqu’une telle chaîne de caractères est trouvée, elle est remplacée par le numéro d’index ¹¹ de la chaîne. Par exemple, admettons qu’il existe un dictionnaire pour le français contenant 99 999 mots au plus. Et supposons que le mot:

— «algorithme» arrive en 2415^ème position dans ce dictionnaire;

— «compression» arrive en 10 324^ème position;

— «de» arrive en 11 112^ème position;

— «dictionnaire» arrive en 12 956^ème position;

— «un» arrive en 74 454^ème position.

Dans ce cas, la phrase

«L’algorithme de compression LZW utilise un dictionnaire.» peut être codée de la manière suivante:

«L’*2’415*11 112*10 324*LZW*utilise*74 454*12 956*.», car «L’», «LZW», «utilise» et «.» ne se trouvent pas dans le dictionnaire considéré.

Examinons l’efficacité de cet algorithme. La phrase qu’il faut coder est constituée de 56 caractères. En utilisant le code ASCII, on constate que 448 bits sont requis pour coder ce texte. Calculons maintenant le nombre de bits nécessaires lorsque l’on profite du dictionnaire. Comme il faut 17 bits ¹² pour coder les nombres jusqu’à 100 000, on doit utiliser 18 bits pour coder les mots qui se trouvent dans le dictionnaire. En effet, il faut 1 bit supplémentaire pour indiquer si ce qui suit correspond à un index ou à un mot codé en ASCII. Les mots présents dans le dictionnaire étant au nombre de 5, cela nous donne 90 bits. De plus, les quatre chaînes de caractères codées en ASCII nécessitent respectivement 22,30,62 et 14 bits, puisqu’il faut 1 bit pour indiquer que ce qui suit est codé en ASCII, 5 bits pour indiquer la longueur du code ASCII, puis le code ASCII. On arrive à un total de 218 bits. On constate qu’il a effectivement été possible de compresser efficacement la phrase proposée.

Ci-dessus, c’est un dictionnaire traditionnel qui a été utilisé. Pour augmenter l’efficacité de l’algorithme, les dictionnaires utilisés contiennent en réalité des chaînes de caractères ¹³ qui n’ont pas nécessairement de signification. De plus, la conception à l’avance d’un dictionnaire peut être irréalisable lorsque les données ne sont pas des données textuelles. C’est typiquement le cas des images. Il n’est pas évident qu’il soit possible de trouver des arrangements de couleurs qui reviennent régulièrement dans toutes les images. Pour cette raison, il est nécessaire de définir des algorithmes capables de construire un dictionnaire différent pour chaque image. Pour éviter la transmission du dictionnaire entre le codeur et le décodeur de l’image, il s’agit de le construire selon une procédure permettant au décodeur de reconstruire le dictionnaire au fil du décodage.

Par exemple, le codeur peut démarrer avec un dictionnaire vide ou par défaut (constitué des lettres de l’alphabet par exemple). Ensuite, en cours de codage, le codeur cherche dans le dictionnaire le mot le plus long qui correspond à la chaîne de caractères qu’il doit coder. Supposons que la prochaine chaîne de caractères à coder soit «couleurs» mais que seul le mot «coule» soit déjà présent dans le dictionnaire. Dans ce cas, le codeur code uniquement le début, à savoir «coule», du mot «couleur», et le codeur précise que la lettre suivante est le u. Ensuite il ajoute le mot «couleu» au dictionnaire, et il s’attaque à la prochaine chaîne de caractères à coder. Dans notre cas, il s’agit de «rs» et de ce qui suit. Ainsi, le dictionnaire est en constante évolution, en fonction des redondances qui apparaissent.

Parmi les algorithmes faisant appel à une procédure de ce genre, on trouve les algorithmes précurseurs LZ77 et LZ78, publiés par A. Lempel et J. Ziv en 1977 et 1978 respectivement. Par la suite, une variante de ces algorithmes a été publiée en 1984 par T. Welch. Cet algorithme est connu sous le nom de LZW et est probablement le plus fameux des algorithmes de la famille LZ, qui regroupe les variantes de LZ77 et de LZ78.

Plutôt qu’une efficacité ciblée sur un type de donnée très particulier, les algorithmes de la famille LZ ont tendance à être efficaces sur des données de tout type. Cette caractéristique en fait un algorithme «tout-terrain», très utile lorsqu’il s’agit de compresser différents types de données ensemble. Toutefois, lorsqu’il s’agit de compresser un type de données bien précis, il existe souvent un algorithme plus efficace.