Compression de données/Codage par dictionnaire

Principe.
La compression par dictionnaire utilise le fait que certaines séquences d'octets consécutifs sont répétées.
Si une telle séquence a déjà été vue auparavant, au lieu de d'écrire la longue séquence, une référence à la séquence originale est écrite, donnant de manière la plus compacte possible le décalage où trouver la séquence à copier et sa longueur.
Algorithmes.
LZ77 et LZ78 sont deux algorithmes de compression de données sans perte proposés par Abraham Lempel et Jacob Ziv en 1977 et 1978 (d'où leurs noms).
Ces deux algorithmes posent les bases de la plupart des algorithmes de compression par dictionnaire, à tel point qu'on parle couramment d'algorithme "LZ" pour désigner un algorithme de compression par dictionnaire.
Ces algorithmes reposent de manière essentielle sur une mesure de complexité pour les suites de longueur finie, la complexité de Lempel-Ziv.
LZ77.
Principe.
LZ77 est un algorithme de compression par dictionnaire utilisant une fenêtre glissante ; les motifs déjà rencontrés dans la fenêtre sont remplacés par une référence à leur première apparition (typiquement, par une paire "(distance, longueur)").
Par extension, LZ77 est aussi utilisé pour désigner la famille des algorithmes de compression par dictionnaire utilisant une fenêtre glissante, comme LZSS et LZMA.
Description de l'algorithme LZ77.
Compression.
Étant donnée une séquence S à compresser, on l'écrit d'abord sous forme de plusieurs composantes Si juxtaposées.
Pour ce faire, on choisit un entier LS qui sera la longueur maximale d'un Si et un entier n > LS qui sera la taille du "buffer".
On initialise les n-Ls caractères du "buffer" par des zéros et on complète le "buffer" par les LS premiers caractères de S.
L'entier n-Ls est la taille de la fenêtre glissante (initialisée avec des zéros comme indiqué précédemment).
Pour trouver les Si, on réalise à chaque itération une production exhaustive de la sous-séquence de S la plus longue possible en prenant le contenu de la fenêtre glissante comme préfixe, avec ici la contrainte que la longueur de la séquence produite ne peut dépasser Ls.
Après initialisation de la fenêtre à zéro et en appliquant ce processus de production on obtient donc la séquence S1 de longueur L1<Ls puis on fait glisser la fenêtre en enlevant les L1 premiers caractères de la fenêtre glissante du "buffer" et en faisant entrer dans le buffer les L1 caractères suivants de S.
On répète ce procédé (production puis glissement de la fenêtre) pour trouver les autres Si jusqu'à arriver au bout de la séquence S.
Cette décomposition découpe S sous forme de composantes comme dans le processus de calcul de la complexité de Lempel-Ziv. 
À chaque étape i, après avoir trouvé Si par un processus de production, on lui affecte un mot de code qui sera sa représentation dans le fichier compressé. Ce mot de code n'est rien d'autre que le triplet (position, longueur, caractère) correspondant.
Chaque Si est ainsi codé par un triplet Ci,1Ci,2Ci,3 et sera représenté ainsi dans le fichier compressé. Le mode de représentation est donc le suivant :
Cet algorithme est étroitement lié au calcul de complexité de Lempel-Ziv. Après avoir fait précédé S de n-LS zéros, on ne fait en effet que décomposer S en composantes Si (qu'on remplace par leur mot de code) en prenant, à chaque étape, le contenu de la fenêtre glissante comme préfixe et en ayant une longueur maximale LS fixée pour toutes les composantes.
Vu que pi est un indice appartenant au préfixe (ici, la fenêtre glissante), il est compris entre 1 et n-LS et peut être représenté en base α par formula_1 α (n-LS)formula_2 caractères. De même, les Li étant bornés par LS, on a besoin de formula_1 α (LS)formula_2 caractères pour représenter Li-1.
Ci,3 étant un caractère unique, chaque Si sera représenté dans le fichier compressé par LC =formula_1 α (n-LS)formula_2+ formula_1 α (LS)formula_2 + 1 caractères.
Décompression.
La décompression est très semblable à la compression. 
Initialisation :
Après l'initialisation, à chaque étape i on répète Li -1 fois le processus suivant :
Vu que les Li - 1 premiers caractères de Si sont juste une copie de la partie de la fenêtre commençant à l'indice pi, on récupère par le processus ci-dessus les Li -1 premiers caractères de Si.
À ce stade, il ne nous manque que le dernier caractère de Si qui n'est rien d'autre que le dernier caractère (Ci,3) de Ci.
Ceci amène à la dernière phase de l'étape i qui consiste à :
On obtient ainsi Si en récupérant les Li derniers caractères de la fenêtre.
Après avoir appliqué ce processus à tous les mots de code Ci, la séquence S est obtenue en concaténant les Si.
Limites et utilisations.
LZ77 présente certains défauts, en particulier, si aucune chaîne n'est trouvée dans le dictionnaire, le symbole à compresser est alors codé par "position=0", "longueur=0", "nouveau symbole", c'est-à-dire qu'il occupe au lieu d'un seul dans le fichier original. Ce défaut est supprimé dans la variante LZSS.
L'algorithme LZ77 est notamment utilisé dans l'algorithme deflate (avant un codage de Huffman) et pour la compression des fichiers dans le système de fichier Windows NTFS.
LZ78.
LZ78 est un algorithme de compression par dictionnaire (publié dans ) utilisant un dictionnaire global (et non plus une fenêtre), construit de la même façon par le compresseur et le décompresseur, respectivement à la compression et à la décompression. Cela permet d'éviter le principal problème de son prédécesseur (LZ77) qui ne peut retrouver une chaîne de caractères si elle se trouve en dehors de la fenêtre.
Par extension, LZ78 est aussi utilisé pour désigner la famille des algorithmes de compression par dictionnaire utilisant un dictionnaire implicite, comme Lempel-Ziv-Welch.
LZ78 a eu moins de succès que LZ77, pour des raisons d'efficacité, et parce qu'il a été protégé par un brevet logiciel aux États-Unis.

Cosmologie/La masse et la relativité générale