Données compressées par Ziv et Lempel en renvoyant au texte déjà envoyé

La compression classique était centrée sur le codage de Huffman, mais Huffman nécessite un modèle de probabilité des symboles construit avant de pouvoir coder. Jusqu'en 1977, la plupart des travaux supposaient que ce modèle devait venir de quelque part.

Dans « A Universal Algorithm for Sequential Data Compression », Jacob Ziv et Abraham Lempel, au Technion, ont montré que l'on pouvait se passer du modèle. L'encodeur conserve une fenêtre du texte récemment vu et la compare au tampon d'anticipation entrant ; une correspondance est écrite sous forme d'un décalage et d'une longueur, de sorte que la répétition ne coûte presque rien.

Le résultat est un schéma universel — il compresse n'importe quelle source sans statistiques préalables, car le dictionnaire est constitué des données elles-mêmes. L'article de 1977 est le classique qui a fait de la compression par dictionnaire la base de gzip, PNG et de la famille ZIP.

Renvoyer au texte déjà vu au lieu de le précalculer

Utiliser le texte déjà envoyé comme dictionnaire ne nécessite aucune table de probabilités précalculée.

Un seul jeton décalage-plus-longueur traite toute phrase répétée, longue ou courte.

Le schéma fonctionne sur des sources inconnues, il est donc universel plutôt qu'adapté à un type de fichier.

Ne construisez pas de modèle des données à l'avance ; laissez les données fournir leur propre structure au fur et à mesure. Une représentation autoréférentielle s'adapte à toute entrée, quelle qu'elle soit.

L'approche LZ est devenue le fondement de la compression sans perte moderne : LZ77 et son descendant LZ78/LZW alimentent gzip, zip, PNG et le flux DEFLATE utilisé sur le web. Les articles de Ziv et Lempel ont reçu le Golden Jubilee Technological Innovation Award 1997 de la IEEE Information Theory Society.