Abraham Lempel

Publié le 27 février 202327 février 2023 par Herve Kabla

Son nom ne dit rien à la majeure partie de l’humanité. Pourtant, par les travaux qu’il a menés sur les techniques de compression informatique, Abraham Lempel a joué un rôle essentiel dans l’essor de formats de données que nous utilisons au quotidien, sans savoir qu’il y a un peu de Lempel derrière tout cela.

Né en Pologne avant la guerre, Abraham Lempel est arrivé en Israel en 1948, où il suivit ses études, notamment au Technion. C’est probablement là-bas qu’il fit la connaissance de Jacob Ziv. Tous deux se sont intéressés aux algorithmes de compression de données, un enjeu majeur pour l’échange de données numériques, jusqu’à nos jours.

Car, et c’est un travers bien connu de l’humanité, plus on nous laisse de place, plus on a tendance à l’occuper. Ainsi, quelle que soit la capacité de stockage ou le débit d’échange de données, on aura toujours tendance à en faire un usage aux limites. Réduire la taille des données a été, est et restera une nécessité absolue.

À l’époque ou Lempel et Ziv officient, dans les années 1977-1978, les techniques de compression étaient encore rudimentaires. On utilisait encore, par exemple, des algorithmes consistant à reconnaître de longues plages homogènes pour les remplacer par un motif de plus petite taille – ce qu’on appelait le Run Length Encoding, ou RLE. Cela marche bien avec des motifs peu variés, mais beaucoup moins bien s’il n’existe pas de telles séquences homogènes.

Lempel et Ziv eurent alors l’idée d’utiliser un dictionnaire, et de coder chaque terme du dictionnaire par un nombre de bits variant avec la fréquence d’apparition du terme dans le document qu’on cherche à comprimer – je rappelle à mes lecteurs qu’il faut préférer comprimer à compresser. Cette approche par dictionnaire se révélait bigrement efficace, et offrait en outre un intérêt essentiel, par rapport à d’autres algorithmes de compression très efficaces : l’algorithme de Lempel et Ziv, qu’on finira par appeler par son petit nom LZ, était un algorithme sans pertes. Un document comprimé puis décomprimé avec ce type d’algorithme revient dans son format originel, ce qui n’est pas le cas avec les algorithmes de compression avec pertes (comme celui utilisé pour le format d’images JPEG).

Depuis les travaux de Lempel et Ziv, les techniques de compression n’ont eu de cesse de s’améliorer. Les termes et les formats employés sont même passés dans le langage courant. Mais qui sait encore que derrière un GIF se cache l’algorithme LZW, dérivé de LZ ?

Je me souviens avoir étudié un article de recherche sur des techniques de compression, à la fin des années 80, dans le cadre de mes études à Télécom Paris. Je ne me souviens malheureusement plus de quoi il s’agissait exactement, et si on y parlait de Lempel et de Ziv. Mais j’ai gardé un souvenir intense de ce papier, qui m’avait fait comprendre que pour qu’une compression soit optimale, il fallait faire varier le nombre de bits nécessaires pour représenter un terme en fonction de la fréquence d’apparition de ce terme dans le message qu’on cherchait à coder et comprimer, et donc de la redondance de son contenu.

Depuis, je ne cesse d’analyser les flux d’informations auxquels j’accède en fonction de leur redondance. Un flux très redondant, comme un discours politique, un message publicitaire ou une série Netflix, ne nécessite que peu de bits – bref, une capacité de traitement limitée suffit amplement pour en saisir la complexité. Un flux d’information riche et varié, comme un cours de maths en prépa, nécessite en revanche un très grand nombre de bits, donc une capacité de traitement beaucoup plus importante.

Bref, comprimer, c’est aussi décoder la richesse du contenant…