LZ78
LZ78 est l'algorithme de compression par dictionnaire proposé par Lempel et Ziv en 1978 ; il construit un dictionnaire explicite et code les données en paires (indice de dictionnaire, littéral).
Objectif
Il réalise une compression sans perte universelle au moyen d'un dictionnaire explicite ; c'est le prédécesseur direct de LZW.
Mécanisme
Il maintient un dictionnaire numéroté à partir de 1 ; en parcourant l'entrée, il trouve le plus long préfixe déjà présent dans le dictionnaire, émet (indice, caractère suivant) et insère ce préfixe plus le caractère dans le dictionnaire. Le dictionnaire est construit en ligne et n'a jamais besoin d'être transmis.
Cas d’usage
- Fondement de l'algorithme LZW
- Compression généraliste
- Analyse théorique et enseignement