Compression de Données - Data Compression

Principe de cette compression à la LZ77 (sur un exemple) :
Le mot à compresser 'abcdefgcdefgcdabcdgcgcgc' sera remplacé après compression par 'abcdefg{5,7}{14,4}gc{2,4}'.
En effet les 7 lettres entre crochets 'ab[cdefgcd]efgcdabcdgcgcgc' se retrouvent décalées de 5 places en 'abcdefg[cdefgcd]abcdgcgcgc'. Ce deuxième crochet sera remplacé par un lien noté '{5,7}' vers le premier, (le décalage est 5, la longueur est 7).
De même {14,4} correspond aux 4 lettres suivantes 'abcd' et {2,4} aux quatre dernières lettres 'gcgc'.
Remarques :
Les parties remplacées ont au minimum 4 lettres, (il fallait fixer une valeur minimale supérieure à 1).
La recherche d'une sous-chaîne identique ne se fait pas sur une fenêtre mobile de taille fixe mais sur la totalité de la partie déjà parcourue.

1. ADN, 2. Droits de l'homme et du citoyen (Préambule), 3. Poème de Rimbaud, 4. de Musset, 5. Zadig (Voltaire), 6. Compression Algorithm FAQ (extrait)
1. Chaîne circulaire de Debruijn,  2. Autre chaîne contenant tous les mots de longueur 6 sur un alphabet de 3 lettres. (page sur les chaînes de Debruijn).
(Pour les personnes intéressées : parfois une chaîne de Debruijn compressée par bzip2 peut l'être encore par gzip de manière spectaculaire 20736->2904->783 octets, d'autres fois l'ordre contraire gzip bzip2 sera plus efficace).
Un millier de chiffres environ des parties décimales 1. d'une fraction, 2. de Pi, 3. de la racine carrée de 2,
Quelques suites que l'on peut obtenir à la page Morphismes de mots.
1. Look and say, 2. Fibonacci, 3. Tribonacci, 4. Prouhet-Thue-Morse, 5. Pavage rythmique parfait d'ordre 3 et de dimension 26 (longueur 3x26), 6. PRP d'ordre 3 et de dimension 52.
(Observer les suites après compression !)


Musique midi obtenue en compressant (LZW) des textes.
LZ77 compression,
Documentations sur zlib, gzip, An Explanation of the DEFLATE Algorithm by Antaeus Feldspar
La page d'accueil de gzip par Jean-loup Gailly et Mark Adler.

La théorie de l'information fournit une mesure quantitative de la notion d'information apportée par un message (ou une observation). Cette notion fut introduite par Claude Shannon en 1948 afin d'étudier les limites du possible en matière de compression de données et de transmission d'informations au moyen de canaux bruités.

The Data Compression Resource on the Internet

High Compression Markov Predictive Coder

Charles Bloom

PPM (Prediction by Partial Match) is a classic compression algorithm. PPM predicts the probability of a given character based on the characters that immediately precede it. PPMZ is an efficient version of PPM. PPMZ has been developed and programmed in C by Charles Bloom.

The CTW-algorithm is a binary technique, invented by Frans Willems, Yuri Shtarkov and Tjalling Tjalkens, which was later extended for byte processing. The main idea is to weight the probabilities of several branches inside a tree in order to get a good probability estimation for the next symbol. The algorithm is optimal in the sense that it achieves the Rissanen (1984) lower bound.

ATTENTION: In contrast to PPM or BWCA, the CTW-method is patented!!!

Damien Debin

Zzip, a new compression tool still under development, can compress files with a very high compression ratio. Compared to Winzip 7.0, you can gain, at least, 15 %. Zzip has a lot of useful features (like support for file integrity tests, built-in multimedia detection/compression...).

Source code of Zzip/Zzlib is released under the GNU LGPL.

Zzip compression algorithm is mainly based on the Burrows-Wheeler Transform method developped by Mike Burrows and David Wheeler.

My freely available JBIG-KIT portable ANSI C library, which implements a highly effective lossless bi-level image compression algorithm based on context sensitive arithmetic coding, can be downloaded from ftp://ftp.informatik.uni-erlangen.de/pub/doc/ISO/JBIG/.

All you need to know about data compression. A fairly detailed look a RLE (Run Length Encoding), Huffman and LZW (after Lempel, Ziv and Welch) compression. The package consists of several coding/decoding examples plus a technical reference by D. Bourgin.

WinRAR is a powerful archive manager.

by Mark Nelson Dr. Dobb's Journal October, 1989

Journées de Mathématique et de Sciences Olivier Delgrange

www.cis.ohio-state.edu www.faqs.org

Part 2 of 3, Part 3 of 3