Chaque chercheur a des intérêts de recherche qui lui sont propres. Certains sont fascinés par les atomes, d'autres par les bactéries et leurs mœurs, d'autres encore par les étoiles. Moi, je m'intéresse à la compression de données, discipline que l'on pourrait classer dans les mathématiques appliquées, discipline que je vais vous faire découvrir dans cette série de billets. Je m'efforcerai de vous présenter la compression de données, ses concepts de base et ses défis tout en douceur, en évitant, autant se faire que peut, d'être trop « matheux ».

Pour ce premier billet, je vous propose d'aborder le sujet de la compression de données par son commencement historique, bien avant la « révolution de l'information », à une époque qui vous surprendra: le début du XIX^ème siècle.

Les précurseurs

Dès le XVIII^ème on s'est intéressé au problème de la communication rapide sur de grandes distances.

• En 1782, Dom Gauthey propose d'utiliser des tuyaux pour transporter la voix sur de grandes distances. La technique n'est pas mauvaise comme le montre une expérience utilisant un tuyau de pompe de 800 mètres de long, mais l'expérience n'alla pas plus loin. Louis XVI, la tête ailleurs, ne voulut pas financer le développement.

• Un autre français, Claude Chappe, propose de transmettre des messages à grande distance grâce à des tours surmontées d'un mécanisme qui imite les mouvements d'un sémaphore [1, p. 20-68]. Les deux bras simulés (opérés depuis l'intérieur de la tour) peuvent prendre plusieurs positions et un observateur distant note et décode les positions grâce à un télescope. En 1792, il inaugure un réseau qui couvre une partie de la France, réseau qui sera plus tard agrandi par Napoléon.

• Le Suédois Edelcrantz, quant à lui, propose en 1794 un télégraphe optique à volets. Comportant 9 ou 10 volets qui peuvent être ouverts ou fermés, le télégraphe d'Edelcrantz permet d'envoyer 512 ou 1024 signaux différents par configuration. Mais comme pour le télégraphe de Chappe, il doit être observé à distance par télescope.

Bien qu'intéressantes, ces technologies optiques souffrent d'un défaut majeur: elles doivent être visibles pour fonctionner! Les tours doivent être assez près les unes des autres pour être visibles en ligne droite et, pire, le système est à la merci des caprices de la météo: si le matin est brumeux, alors panne de télégraphe!

À la fin du XVIII^ème siècle, on cherche d'autres moyens de communiquer à grande distance qui ne seraient pas aussi assujettis aux caprices de l'atmosphère ou des heures. Une voie qui semble alors avoir de l'avenir, c'est l'électricité... mais à la fin du XVIII^ème siècle, on ne sait pas encore trop comment faire.

Plusieurs proposeront des « télégraphes électriques ». Dès 1774, Lesage proposera un mécanisme utilisant 24 câbles parallèles, chacun correspondant aux lettres de a à z (où il devait bien y avoir quelques lettres assimilées ou omises, comme peut-être i et j ou c et k) pour transmettre un message [1, p. 90-91]. Évidemment, cette mécanique est très coûteuse étant donné le nombre de câbles nécessaire. Ce n'est que bien plus tard, au début du XIX^ème siècle que l'on commencera à comprendre les phénomènes électriques suffisamment bien pour savoir les exploiter. Dans les années 1830, Samuel Finley Breese Morse (1791–1872), a une idée de télégraphe électromécanique. Il ne le sait pas encore, mais il fera l'histoire.

L'appareil de Morse

L'appareil de Morse est, par son principe, d'une simplicité déconcertante. À une extrémité d'une boucle de courant (dont une partie est en fait la mise à la terre), on trouve un contact opéré par un télégraphiste. Lorsque ce dernier ferme le contact, la boucle de courant se crée, activant, à l'autre bout, un électroaimant qui fait descendre un stylet et marque une bande de papier. Lorsqu'il ouvre le contact, le stylet remonte. Le télégraphe de Morse ne transporte qu'une information simple: la durée pendant laquelle le contact est ouvert ou fermé. Il s'agit d'en tirer le maximum. Nous y reviendrons dans un moment.

Cependant, si Morse a bien eu l'idée originale, il ne pas sait comment mener ses projets à terme seul. Peintre de renom, il n'impressionne cependant pas ses contemporains par ses dons d'ingénieur, que d'aucuns jugent plutôt limités [2]. Pour réaliser ses plans, il a besoin de fonds et d'expertise technique, et les deux lui font défaut. En 1837, cette aide trouve Morse: c'est Alfred Lewis Vail (1807–1859) qui, ayant tout compris de l'importance du télégraphe, veut participer à sa réalisation.

Les résumés rapides réduisent souvent Vail à un rôle secondaire d'assistant, mais ce ne serait pas lui faire justice. Bien au contraire! Morse lui doit beaucoup. C'est Vail qui baillera, avec sa famille, les fonds nécessaires au développement du télégraphe. C'est Vail, en partenaire d'affaires avisé qui fera fleurir l'entreprise de Morse. C'est Vail, en ingénieur astucieux, qui résoudra plusieurs des problèmes liés à la réalisation matérielle des télégraphes (car si le principe en est simple, la mise en œuvre s'avère pleine d'embûches). Mais, plus important encore, pour notre propos, ce serait à Vail que nous devons le « code Morse » [2].

Le problème du code

La première idée de code qui était venue à Morse était d'utiliser le télégraphe pour transmettre simplement des chiffres [1, p. 109]. Ces chiffres, encodés avec deux symboles, à savoir le point · (le contact est fermé brièvement) et l'espace (le contact est ouvert), sont combinés pour former des nombres, lesquels servent à trouver des mots dans une liste numérotée — un dictionnaire.

Cependant, cette solution comporte plusieurs défauts. D'abord, il est difficile de lire le message sans avoir recours au dictionnaire. Ensuite, le code est sensible au dictionnaire lui-même: il faut que les deux interlocuteurs partagent exactement le même dictionnaire s'ils veulent se comprendre, car si les listes diffèrent, les messages échangés deviennent inintelligibles.

Morse réalise rapidement la faiblesse de cette approche et l'idée est abandonnée au profit de codes alphabétiques: les séries de points, tirets et espaces vont maintenant servir à l'encodage de caractères alphabétiques, de chiffres, et d'autres symboles comme ?, !, etc., (plus tard, les variantes dites « continentales » vont prévoir des codes pour des symboles accentués et pour des ligatures comme Æ nécessaires pour certaines langues). Mais quel code choisir? Vail s'attaque au problème à l'automne 1837.

Une idée pourrait être d'utiliser un nombre fixe de points et de tirets pour encoder tous les symboles. Partons de l'hypothèse qu'il nous faille encoder les lettres (de a à z), les chiffres (de 0 à 9), les ponctuations et des symboles spéciaux comme les symboles monétaires. Nous arrivons rapidement à une cinquantaine de symboles. En utilisant des codes de longueur fixe, il ne nous faut pas moins de 6 points et tirets pour encoder la cinquantaine de symboles. Si nous voulions n'en utiliser que 5, nous ne pourrions encoder que 32 symboles différents, ce qui est insuffisant. (Pour comprendre pourquoi n points et tirets donnent 2ⁿ codes, il suffit d'assimiler le point · à zéro et le tiret — à 1, et de compter de 0 à 2ⁿ -1 en binaire. Je vous invite à en faire l'exercice pour vous en convaincre.)

L'idée de génie de Vail

Si utiliser des codes de longueur fixe séparés par des espaces est une solution tout à fait valide, elle semble quelque peu excessive. Très rapidement, on réalise qu'il laborieux d'encoder un message avec des codes de longueur fixe. Les symboles que l'on répète souvent sont encodés avec le même nombre de points et de tirets que les symboles que l'on ne voit que rarement.

N'y a-t-il donc pas de façon de faire mieux? Comment peut-on réduire l'effort d'encodage? Notre premier réflexe serait d'utiliser des abréviations, mais Vail ira beaucoup plus loin. En fait, il a une idée de génie: plutôt que d'utiliser des abréviations arbitraires, il va concevoir un code de longueur variable tel que les symboles les plus fréquents reçoivent les codes les plus courts et que les symboles les moins fréquents reçoivent des codes plus longs. Cette tactique permet d'écourter significativement les transmissions, d'autant plus lorsqu'elles sont composées de symboles fréquents!

Mais comment assigner la longueur des codes? Comment choisir les symboles qui recevront un code court et ceux qui recevront un code long? Vail comprend qu'il lui faut compter les fréquences relatives des lettres dans les textes pour trouver quelles lettres devraient recevoir les codes les plus courts. Sûrement a-t-il dû prendre un livre et commencer à compter les occurrences de chaque lettre... mais sans ordinateur, quel travail fastidieux! Il lui vient alors une idée qui lui sauvera tout ce labeur: il doit parler à un imprimeur. Mais pourquoi un imprimeur? Parce que les imprimeurs ont déjà résolu le problème de la fréquence des lettres il y a longtemps! En effet, pour imprimer un texte avec des caractères mobiles, il faut avoir chaque lettre en nombre suffisant, mais, par économie de moyen, on voudra en même temps en avoir le nombre minimum. La solution est toute simple: dans un jeu de caractères mobiles, on fond chaque caractère en proportion avec ce dont on a besoin. Nous y trouverons donc plusieurs exemplaires des lettres fréquentes, mais seulement quelques-uns pour les caractères qui sont rarement utilisés — exactement comme les tuiles au Scrabble!

L'histoire ne nous dit pas quelles fréquences relatives Vail trouva chez l'imprimeur, mais un jeu moderne [4] propose les caractères avec les quantités particulières suivantes:

e, 48 fois, a,i,n,o,r,s,t, 36 fois, h,l, 24 fois, d, 22 fois, c,f,m,.,virgule, 19 fois, b,g,p,w,y, 15 fois, j,k,v,-,', 9 fois, q,x,z,;,:,!,?, 6 fois.

Si Vail avait disposé d'un ordinateur, il aurait pu, comme moi, écrire un programme court dans son langage de programmation préféré, lire tout un corpus et obtenir une distribution très précise des symboles. Par exemple, j'ai utilisé tous les textes anglais du Project Gutenberg (une douzaine de gigaoctets en format texte simple) pour obtenir, en quelques secondes, une distribution des lettres de a à z. (pour voir la figure montrant la distribution, cliquez sur l'image de la clef et accédez à la galerie). Cette distribution est donc en accord avec la boîte de caractères mobiles de l'imprimeur, même s'il y a des variations mineures.

Armé de l'information recueillie chez l'imprimeur, Vail se met à la conception d'un code où se mêlent le point ·, le tiret court –, le tiret long — et trois types d'espaces [2,3]. L'espace court sert entre les points et tirets à l'intérieur d'un code, l'espace moyen sépare les symboles, et l'espace long sépare les mots. Vers la fin de 1837, il propose le code suivant [3]:

• A ·–
• B – ··
• C ·· ·
• D – ··
• E ·
• F ·– ·
• G – – ·
• H ····
• I ··
• J – ·– ·
• K – ·–
• L —
• M – –
• N – ·
• O · ·
• P ·····
• Q ··– ·
• R · ··
• S ···
• T –
• U ··–
• V ···–
• W ·– –
• X ·– ··
• Y ·· ··
• Z ··· ·
• 0 —
• 1 ·— — ·
• 2 ··— — ··
• 3 ···— — ·
• 4 ····—
• 5 – – –
• 6 ······
• 7 – – ··
• 8 – ····
• 9 – ··–

Ce code est beaucoup plus économe que le code naïf de longueur fixe, mais il est loin d'être parfait. D'abord, l'utilisation de traits de longueurs différentes – et — (comme des espaces courts, moyens et longs) rend le code ambigu dès que l'opérateur ne marque pas assez les différences. Ensuite, certains codes complets forment une partie d'un autre code, par exemple E (·), I (··), S (···) et H (····): une hésitation involontaire transformera un S en C (·· ·) ou en R (· ··). En fait, il suffit d'encoder un texte court (disons le simple mot « hello ») en utilisant le code ci-dessus pour se convaincre de la difficulté de réaliser un encodage parfait, surtout lorsqu'on considère que l'on doive opérer le mécanisme à cliquetis si typique des télégraphes!

Le code de Vail fut éventuellement remplacé par un code qui réduit de beaucoup les ambiguïtés — sans toutefois les éliminer totalement. D'abord, il n'y a plus que · et —, et l'espace moyen disparaît; il n'y a plus d'espace court dans les codes pour les symboles. Le code moderne est résumé dans le tableau suivant:

• A ·—
• B — ··
• C — ·— ·
• D — ··
• E ·
• F ··— ·
• G — — ·
• H ····
• I ··
• J ·— — ·
• K — ·—
• L ·— ··
• M — —
• N — ·
• O — — —
• P ·— — ·
• Q — — ·—
• R ·— ·
• S ···
• T —
• U ··—
• V ···—
• W ·— —
• X — ··—
• Y — ·— —
• Z — — ··
• 0 — — — — —
• 1 ·— — — —
• 2 ··— — —
• 3 ···— —
• 4 ····—
• 5 ·····
• 6 — ····
• 7 — — ···
• 8 — — ·
• 9 — — — — ·

Mais ce code, bien que plus robuste que celui proposé par Vail, laisse encore place à amélioration. L'assignation des codes est sous-optimale et nous utilisons encore trois symboles (le point, le tiret et l'espace) alors que nous allons montrer dans un prochain billet qu'il ne suffit que de deux symboles pour créer un code non ambigu et optimal.

Le code Morse et la compression de données?

Nous venons de voir que l'un des moments fondateurs de la compression de donnée est l'invention d'un code efficace pour communiquer sur de grandes distances et que cet évènement — qui semble résolument moderne — a eu lieu il y a presque deux cents ans! Mais pourquoi avoir choisi de commencer l'histoire aussi loin dans le temps et de parler du code Morse (devrait-on dire code de Vail?) plutôt que d'entrer le vif du sujet avec de « vrais » algorithmes de compression de données? Parce que le code Morse illustre à merveille plusieurs problèmes auxquels nous sommes confrontés avec la compression de données, comme l'optimalité du code, la non-ambiguïté et la résistance aux erreurs.

De plus, même si le code proposé par Vail est sous-optimal en ce qu'il ne donne pas le code le plus court possible en fonction de la fréquence relative des lettres (comme nous le montrerons dans un prochain billet), il n'en demeure pas moins qu'il représente la première (tentative de) réalisation d'une idée centrale à la théorie de la compression de données: les symboles fréquents reçoivent des codes courts et les symboles moins fréquents des codes plus longs. Et en compression de données, c'est toujours ce que nous cherchons: des codes astucieux qui permettent de trouver une nouvelle représentation des données, beaucoup plus courte, en moyenne, que la représentation originale.

La méthode choisie par Vail est aussi d'intérêt. Il n'a pas seulement inventé un code comme ça, il s'est appuyé sur une observation de la fréquence des lettres pour faire une conception rationnelle (quoiqu'encore maladroite) d'un code qui tente de minimiser explicitement une fonction objectif, à savoir la longueur moyenne des messages. C'est une approche profondément scientifique.

Un autre concept très important qui s'impose avec le code Morse comme dans la compression de données est le concept de décodage unique. Le code proposé par Vail n'est pas ambigu s'il est exécuté parfaitement, disons par une machine qui ne commet jamais d'erreur. Mais s'il est exécuté par un humain, la moindre hésitation, le moindre « flou artistique » peut rendre le code ambigu: çà un espace court devient un espace long, là un point pas assez appuyé devient un espace, ici encore un espace disparaît, et le message devient difficile, voire impossible, à décoder correctement. En compression de données, nous nous intéressons principalement aux codes que l'on dit uniquement décodables, c'est-à-dire ne peuvent pas être ambigus s'ils sont intacts (si le code est modifié ou abîmé par la transmission, cette propriété peut ne pas être garantie).

Enfin, on veut aussi construire des codes qui résistent au « flou artistique » des câbles et des mécanismes de transmission, c'est-à-dire qui résistent au bruit, aux modifications et aux pertes. Ces codes sont plutôt l'objet de la théorie du codage que de la compression de données, mais nous en parlerons tout de même dans un billet futur, car les deux sont intimement liés.

Aperçu du prochain épisode

Dans le prochain billet, nous allons poursuivre notre introduction à la compression de données en suivant le filon historique, mais nous ferons un bond de presque un siècle, pour reprendre notre histoire à la fin des années 1920.

Références

[1] Louis Figuier — Les merveilles de la science ou description populaire des inventions modernes, Tome II — Furne, Jouvet et C^ie, Paris (1868)

[2] Franklin Leonard Pope — The American Inventors of the Telegraph, with special references to the services of Alfred Vail — The Century Magazine, vol. XXXV, n° 6 (1888) p. 924--944

[3] Alfred Vail — The American Electro Magnetic Telegraph: with the reports of Congress, and a descrition of all Telegraphs known employing electricity or galvanism — Lea & Blanchard, Philadelphie (1845)

[4] Skyline Type