Comment fonctionne la compression de fichiers

Dans notre exemple précédent, nous avons sélectionné tous les mots répétés et les avons placés dans un dictionnaire. Pour nous, c’est la façon la plus évidente d’écrire un dictionnaire. Mais un programme de compression voit les choses tout à fait différemment : Il n’a aucun concept de mots séparés, il ne cherche que des modèles. Et afin de réduire la taille du fichier autant que possible, il sélectionne soigneusement les motifs à inclure dans le dictionnaire.

Si nous abordons la phrase sous cet angle, nous nous retrouvons avec un dictionnaire complètement différent.

Si le programme de compression scannait la phrase de Kennedy, la première redondance qu’il rencontrerait ne ferait que quelques lettres. Dans  » ask not what your « , il y a un modèle répété de la lettre  » t  » suivie d’un espace — dans  » not  » et  » what « . Si le programme de compression écrivait cela dans le dictionnaire, il pourrait écrire un « 1 » chaque fois qu’un « t » est suivi d’un espace. Mais dans cette courte phrase, ce modèle ne se produit pas suffisamment pour en faire une entrée intéressante, et le programme finirait donc par l’écraser.

La prochaine chose que le programme pourrait remarquer est « ou », qui apparaît à la fois dans « votre » et « pays ». S’il s’agissait d’un document plus long, l’écriture de ce motif dans le dictionnaire pourrait faire gagner beaucoup d’espace — « ou » est une combinaison assez courante dans la langue anglaise. Mais en parcourant cette phrase, le programme de compression découvrirait rapidement un meilleur choix pour une entrée de dictionnaire : Non seulement « ou » est répété, mais les mots « your » et « country » sont tous deux répétés, et ils sont en fait répétés ensemble, dans la phrase « your country ». Dans ce cas, le programme écraserait l’entrée du dictionnaire pour « ou » avec l’entrée pour « votre pays ».

L’expression « peut faire pour » est également répétée, une fois suivie de « votre » et une fois suivie de « vous », ce qui nous donne un modèle répété de « peut faire pour vous ». Cela nous permet d’écrire 15 caractères (espaces compris) avec une valeur numérique, alors que « votre pays » ne nous permet d’écrire que 13 caractères (espaces compris) avec une valeur numérique. Le programme écrase donc l’entrée « votre pays » en la remplaçant par « votre pays », puis écrit une entrée distincte pour « peut faire pour vous ». Le programme procède de cette manière, en recueillant toutes les informations répétées, puis en calculant les modèles qu’il doit écrire dans le dictionnaire. Cette capacité à réécrire le dictionnaire est la partie « adaptative » de l’algorithme LZ basé sur le dictionnaire adaptatif. La façon dont un programme fait réellement cela est assez compliquée, comme vous pouvez le voir par les discussions sur Data-Compression.com.

Qu’importe la méthode spécifique que vous utilisez, ce système de recherche en profondeur vous permet de compresser le fichier beaucoup plus efficacement que vous ne pourriez le faire en choisissant simplement des mots. En utilisant les modèles que nous avons sélectionnés ci-dessus, et en ajoutant « __ » pour les espaces, nous obtenons ce dictionnaire plus large :

Et cette phrase plus petite : « 1not__2345__–__12354 »

La phrase occupe maintenant 18 unités de mémoire, et notre dictionnaire en occupe 41. Nous avons donc compressé la taille totale du fichier de 79 unités à 59 unités ! Ce n’est qu’une façon de comprimer la phrase, et pas nécessairement la plus efficace. (Voyez si vous pouvez trouver une meilleure façon !)

Alors, quelle est la qualité de ce système ? Le taux de réduction des fichiers dépend de plusieurs facteurs, dont le type de fichier, sa taille et le schéma de compression.

Dans la plupart des langues du monde, certaines lettres et certains mots apparaissent souvent ensemble dans le même schéma. En raison de ce taux élevé de redondance, les fichiers texte se compressent très bien. Une réduction de 50 % ou plus est typique pour un fichier texte de bonne taille. La plupart des langages de programmation sont également très redondants parce qu’ils utilisent une collection relativement restreinte de commandes, qui vont souvent ensemble selon un modèle fixe. Les fichiers qui comprennent beaucoup d’informations uniques, comme les graphiques ou les fichiers MP3, ne peuvent pas être beaucoup compressés avec ce système, car ils ne répètent pas beaucoup de motifs (plus d’informations à ce sujet dans la section suivante).

Si un fichier a beaucoup de motifs répétés, le taux de réduction augmente généralement avec la taille du fichier. Vous pouvez le voir juste en regardant notre exemple — si nous avions plus de discours de Kennedy, nous serions en mesure de nous référer aux motifs de notre dictionnaire plus souvent, et ainsi obtenir plus de l’espace de fichier de chaque entrée. De même, des motifs plus omniprésents pourraient émerger dans les travaux plus longs, ce qui nous permettrait de créer un dictionnaire plus efficace.

Cette efficacité dépend également de l’algorithme spécifique utilisé par le programme de compression. Certains programmes sont particulièrement adaptés à la détection de motifs dans certains types de fichiers, et peuvent donc les compresser de manière plus succincte. D’autres ont des dictionnaires dans les dictionnaires, ce qui peut permettre une compression efficace pour les gros fichiers mais pas pour les petits. Bien que tous les programmes de compression de ce type fonctionnent avec la même idée de base, il y a en fait beaucoup de variations dans la manière de les exécuter. Les programmeurs tentent toujours de construire un meilleur système.

.