> lz77 | sliding | window <
// LZ77 – compression à fenêtre glissante avec références de dictionnaire
Codage par dictionnaire
Réutilise les motifs répétés via des références de décalage et de longueur.
Fenêtre glissante
Maintient une fenêtre mobile pour trouver les plus longues correspondances.
Algorithme de base
Constitue la base de ZIP, GZIP, DEFLATE et PNG.
>> informations techniques
Comment fonctionne LZ77:
LZ77 maintient une fenêtre glissante de données récemment vues. Pour chaque position, l’algorithme cherche dans la fenêtre la sous-chaîne la plus longue qui correspond. S’il en trouve une, il émet une référence (décalage, longueur, caractère suivant). Sinon, il émet un littéral (0,0,caractère). Les motifs répétés sont ainsi remplacés par de courtes références, ce qui permet une compression sans perte.
Exemple LZ77:
Text: "ABCABCABC" Window=4, Lookahead=4 Position 0: 'A' - no match → (0,0,A) Position 1: 'B' - no match → (0,0,B) Position 2: 'C' - no match → (0,0,C) Position 3: 'ABC' - matches at offset 3 → (3,3,A) Position 7: 'BC' - matches at offset 3 → (3,2,) Output: (0,0,A)(0,0,B)(0,0,C)(3,3,A)(3,2,)
Pourquoi utiliser LZ77 ?:
- ▸Compression sans perte
- ▸Aucune connaissance préalable des données requise
- ▸S’adapte aux motifs de vos données
- ▸Implémentation relativement simple
- ▸Base de nombreux algorithmes de compression modernes
>> questions fréquentes
Qu’est-ce que LZ77 ?
LZ77 est un algorithme universel de compression de données sans perte publié par Abraham Lempel et Jacob Ziv en 1977. Il remplace les répétitions dans le flux par des références à une copie unique déjà présente dans le flux non compressé.
Comment fonctionne la fenêtre glissante ?
La fenêtre glissante est composée d’un tampon de recherche (données déjà traitées) et d’un tampon de lookahead (données à compresser). L’algorithme cherche dans le tampon de recherche la plus longue correspondance avec le début du tampon de lookahead, puis émet une référence ou un littéral.
LZ77 vs algorithmes modernes ?
LZ77 est la base de nombreux algorithmes de compression modernes. DEFLATE, utilisé dans ZIP et GZIP, combine LZ77 avec le codage de Huffman. LZSS réduit la redondance de LZ77, tandis que LZ78 et LZW construisent le dictionnaire différemment tout en suivant les mêmes principes.
Quelles tailles de fenêtre choisir ?
Les tailles de fenêtre typiques varient entre 32 et 64 Ko pour des données générales. Des fenêtres plus grandes trouvent plus de correspondances mais consomment davantage de mémoire et de temps. DEFLATE utilise 32 Ko. Le tampon de lookahead est souvent de 256 à 512 octets. La taille idéale dépend des motifs de répétition de vos données.
// Exemple détaillé
| # | Offset | Length | Next | Output |
|---|---|---|---|---|
| 1 | 0 | 0 | a | a |
| 2 | 0 | 0 | b | b |
| 3 | 0 | 0 | r | r |
| 4 | 3 | 1 | c | a + c |
| 5 | 2 | 1 | d | a + d |
| 6 | 7 | 4 | — | abra |
// Exemples de code
Input abracadabra (positions 0..10)
Token (offset, length, next)
offset = distance back into the window, length = bytes copied
Decode copy `length` bytes starting `offset` back, then append `next`
(the copy may overlap its own output, e.g. (1,5,x) repeats a byte)
Window the sliding search buffer; deflate/gzip use 32 KiB
>> Autres questions
Q : Que signifie le triplet (décalage, longueur, caractère) ?
R : Le décalage indique de combien on recule dans la fenêtre déjà vue, la longueur le nombre d’octets copiés, et le caractère est le prochain octet nouveau. Le décodeur reconstruit ainsi la sortie pas à pas.
Q : Pourquoi la copie peut-elle se chevaucher ?
R : Si le décalage est inférieur à la longueur, la copie lit des octets qu’elle vient d’écrire. Cela crée des répétitions : (1, 5, x) produit cinq fois le caractère précédent.
Q : Où LZ77 est-il utilisé ?
R : LZ77 est au cœur de DEFLATE (gzip, zlib, PNG, ZIP) et, sous forme de variantes, de LZ4, Snappy, Zstandard et Brotli. La taille de la fenêtre et la stratégie de recherche déterminent taux et vitesse.