Principe de compression‑prédiction

Le texte explique que tout compresseur implémente implicitement un modèle de probabilité : le nombre de bits nécessaire pour coder un symbole vaut -log₂ p, où p est la probabilité estimée. gzip, qui utilise l’algorithme DEFLATE, attribue peu de bits aux séquences attendues (celles déjà présentes dans sa fenêtre) et beaucoup aux séquences inattendues. En mesurant la taille du fichier compressé len(gzip(context + candidate)), on obtient un score de vraisemblance pour une continuation donnée.

Mise en œuvre avec DEFLATE

DEFLATE travaille avec une fenêtre glissante de 32 KiB. Lorsqu’une suite de bytes correspond à une sous‑séquence déjà présente dans la fenêtre, l’algorithme encode un back‑reference très court au lieu de répéter les octets littéraux. L’auteur a « primé » gzip en injectant un corpus (par ex. tiny Shakespeare) dans cette fenêtre, puis a fourni un prompt tel que 

gzipt --corpus data/tinyshakespeare.txt --prompt $'MENENIUS:\n' --length 200
. Le texte généré montre que le compresseur reproduit des motifs du corpus, même si la sortie reste partiellement incohérente.

Génération par recherche en faisceau

Le simple choix du prochain octet qui minimise la taille compressée échoue parce que gzip ne renvoie que des longueurs entières ; plusieurs octets donnent le même score, créant du bruit de quantification. La solution consiste à explorer un horizon de plusieurs octets avant de « committer ». L’outil gzipt exécute une recherche en faisceau : à chaque itération il étend chaque continuation partielle avec chaque octet présent dans le corpus, calcule len(gzip(context + candidate)) pour chaque extension, puis ne conserve que les beam_width meilleures. Le contexte utilisé comprend la fenêtre du corpus plus les derniers octets générés, limitant ainsi les références à des positions trop lointaines qui seraient coûteuses à coder.

Limites et perspectives

Le modèle repose uniquement sur la redondance locale du texte ; il ne capture pas de dépendances sémantiques à longue distance, ce qui explique les répétitions verbatim observées lorsque la fenêtre contient le texte récemment émis. De plus, l’absence de paramètres appris empêche toute adaptation fine à des domaines spécifiques. Malgré ces contraintes, l’expérience confirme la théorie « compression = prédiction » et montre qu’un compresseur standard peut servir de base à un générateur de texte, à condition d’ajouter une stratégie de recherche adaptée. Le code complet, écrit en Python standard avec la bibliothèque zlib, est disponible sur GitHub pour reproduire les expériences.