Les algorithmes de compression par dictionnaire (en anglais : ) sont une classe d'algorithme de compression sans perte. Ils procèdent par la recherche de similitudes entre le texte à compresser (ou tout autre type de fichier à compresser) et un ensemble de chaines de caractères (ou tout autre type de donnée) contenues dans une structure de données appelée « dictionnaire » (souvent implémenté sous forme d'un trie). Quand une similitude est trouvée, le texte correspondant est remplacé par une référence vers l'emplacement de cette chaîne dans le « dictionnaire ».
Méthodes et applications 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 , 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(donc 40 bits), on pourrait gagner un facteur de l’ordre de 55%.
Exemples 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. Sourcedans dictionnaireadresseajoutvaleurAnon trouvé1A(0,A)vnon trouvé2v(0,v)enon trouvé3e(0,e)cnon trouvé4c(0,c)non trouvé5" "(0," ")Lnon(trouvé6L(0,L)Znon trouvé7Z(0,Z)7non trouvé87(0,7)8non trouvé98(0,8)trouvé en 5nnon trouvé10n(5,n)onon trouvé11o(0,o)unon trouvé12u(0,u)snon trouvé13s(0,s)trouvé en 5anon trouvé14a(5,a)vtrouvé en 2otrouvé en 11ntrouvé en 10strouvé en 13trouvé en 5utrouvé en 12ntrouvé en 10trouvé en 5dnon trouvé15d(0,d)
Références https://members.loria.fr/EJeandel/files/Codage/02-2x2.pdf
Catégorie:Algorithme de compression sans perte