Catégorie : geek

Tableau comparatif des algorithmes

Labyrinthes : différents algorithmes

Tableau comparatif des algorithmes

Traduit en Français par moi-même. Les originaux sont fici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Caractéristiques des algorithmes de création de labyrinthes parfaits

Algorithme	Impasses %	Type	Focus	Sans biais ?	Uniforme ?	Mémoire	Temps	Solution %	Source
Unicursal	0	Arbre	Mur	Oui	Jamais	N^2	379	100.0	Walter Pullen
Retour-récursif	10	Arbre	Passage	Oui	Jamais	N^2	27	19.0	(Générique)
Chasse et tue	11 (21)	Arbre	Passage	Oui	Jamais	0	100 (143)	9.5 (3.9)	Walter Pullen
Division récursive	23	Arbre	Mur	Oui	Jamais	N*	10	7.2	John Perry
Arbre binaire	25	Ensemble	Les deux	Non	Jamais	0*	10	2.0	(Générique)
Sidewinder	27	Ensemble	Les deux	Non	Jamais	0*	12	2.6	Walter Pullen
Algorithme d’Eller	28	Ensemble	Les deux	Non	Non	N*	20	4.2 (3.2)	Marlin Eller
Algorithme de Wilson	29	Arbre	Les deux	Oui	Oui	N^2	48 (25)	4.5	David Wilson
Algorithme d’Aldous-Broder	29	Arbre	Les deux	Oui	Oui	0	279 (208)	4.5	David Aldous & Andrei Broder
Algorithme de Kruskal	30	Ensemble	Les deux	Oui	Non	N^2	33	4.1	Joseph Kruskal
Algorithme de Prim (original)	30	Arbre	Les deux	Oui	Non	N^2	160	4.1	Robert Prim
Algorithme de Prim (simplifié)	32	Arbre	Les deux	Oui	Non	N^2	59	2.3	Robert Prim
Algorithme de Prim (modifié)	36 (31)	Arbre	Les deux	Oui	Non	N^2	30	2.3	Robert Prim
Algorithme de l’arbre qui grandit	49 (39)	Arbre	Les deux	Oui	Non	N^2	48	11.0	Walter Pullen
Algorithme de la forêt qui grandit	49 (39)	Les deux	Les deux	Oui	Non	N^2	76	11.0	Walter Pullen

Ce tableau résume les caractéristiques des algorithmes de création de labyrinthes parfaits mentionnés ci-dessus. L’algorithme de labyrinthe unicursal (les labyrinthes unicursaux sont techniquement parfaits) est inclus à titre de comparaison. Voici les descriptions des colonnes :

Impasses : C’est le pourcentage approximatif de cellules qui sont des impasses dans un labyrinthe créé avec cet algorithme, lorsqu’il est appliqué à un labyrinthe orthogonal 2D. Les algorithmes dans le tableau sont triés selon ce critère. Généralement, créer en ajoutant des murs donne le même résultat que creuser des passages, cependant si la différence est significative, le pourcentage d’ajout de murs est indiqué entre parenthèses. La valeur de l’Arbre qui grandit peut en réalité varier de 10% (toujours choisir la cellule la plus récente) à 49% (toujours échanger avec la cellule la plus ancienne). Avec un facteur de course suffisamment élevé, le Retour-récursif peut descendre en dessous de 1%. Le pourcentage maximum possible d’impasses dans un labyrinthe parfait orthogonal 2D est de 66%, ce qui correspondrait à un passage unicursal avec une série d’impasses d’une unité de longueur de chaque côté.

Type : Il existe deux types d’algorithmes de création de labyrinthes parfaits : Un algorithme basé sur les arbres fait croître le labyrinthe comme un arbre, ajoutant toujours à ce qui est déjà présent, ayant un labyrinthe parfait valide à chaque étape. Un algorithme basé sur les ensembles construit où il le souhaite, gardant la trace des parties du labyrinthe qui sont connectées entre elles, pour s’assurer qu’il peut tout relier pour former un labyrinthe valide une fois terminé. Certains algorithmes comme la Forêt qui grandit font les deux en même temps.

Focus : La plupart des algorithmes peuvent être implémentés soit en creusant des passages, soit en ajoutant des murs. Quelques-uns ne peuvent être réalisés que d’une seule manière. Les labyrinthes unicursaux sont toujours créés par ajout de murs puisqu’ils impliquent de bissecter des passages avec des murs, bien que le labyrinthe de base puisse être créé des deux façons. Le Retour-récursif ne peut pas être fait en ajoutant des murs car cela tend à donner un chemin solution qui suit le bord extérieur, où l’intérieur entier du labyrinthe est attaché à la bordure par une seule tige. De même, la Division récursive ne peut être faite qu’en ajoutant des murs en raison de son comportement de bissection. Chasse et tue est techniquement uniquement réalisé par creusement de passages pour une raison similaire, bien qu’il puisse être fait par ajout de murs si un effort particulier est fait pour croître vers l’intérieur depuis tous les murs frontières de manière égale.

Sans biais : Ceci indique si l’algorithme traite toutes les directions et tous les côtés du labyrinthe de manière égale, où l’analyse du labyrinthe après coup ne peut révéler aucun biais de passage. L’Arbre binaire est extrêmement biaisé, où il est facile de voyager vers un coin et difficile vers son opposé. Le Sidewinder est également biaisé, où il est facile de voyager vers un bord et difficile vers son opposé. L’algorithme d’Eller tend à avoir un passage à peu près parallèle aux bords de début ou de fin. Chasse et tue est sans biais, tant que la chasse est faite colonne par colonne ainsi que ligne par ligne pour éviter un léger biais le long d’un axe.

Uniforme : Ceci indique si l’algorithme génère tous les labyrinthes possibles avec une probabilité égale. « Oui » signifie que l’algorithme est complètement uniforme. « Non » signifie que l’algorithme peut potentiellement générer tous les labyrinthes possibles dans un espace donné, mais pas avec une probabilité égale. « Jamais » signifie qu’il existe des labyrinthes possibles que l’algorithme ne peut jamais générer. Notez que seuls les algorithmes sans biais peuvent être complètement uniformes.

Mémoire : C’est la quantité de mémoire supplémentaire ou de pile nécessaire pour implémenter l’algorithme. Les algorithmes efficaces ne requièrent et ne regardent que la bitmap du labyrinthe elle-même, tandis que d’autres nécessitent un stockage proportionnel à une seule ligne (N), ou proportionnel au nombre de cellules (N^2). Certains algorithmes n’ont même pas besoin d’avoir le labyrinthe entier en mémoire et peuvent être étendus indéfiniment (ceux-ci sont marqués d’un astérisque). L’algorithme d’Eller nécessite le stockage d’une ligne, mais compense largement cela puisqu’il n’a besoin de stocker que la ligne courante du labyrinthe en mémoire. Sidewinder n’a également besoin de stocker qu’une ligne du labyrinthe, tandis que l’Arbre binaire n’a besoin que de garder trace de la cellule courante. La Division récursive nécessite une pile jusqu’à la taille d’une ligne, mais à part cela n’a pas besoin de regarder la bitmap du labyrinthe.

Temps : Ceci donne une idée du temps nécessaire pour créer un labyrinthe avec cet algorithme, les nombres plus bas étant plus rapides. Les nombres sont seulement relatifs les uns aux autres (l’algorithme le plus rapide étant assigné à la vitesse 10) plutôt qu’en unités spécifiques, car le temps dépend de la taille du labyrinthe et de la vitesse de l’ordinateur. Ces nombres proviennent de la création de labyrinthes de passages 100×100 dans la dernière version de Daedalus. Généralement, créer en ajoutant des murs prend le même temps que creuser des passages, cependant si la différence est significative, le temps d’ajout de murs est indiqué entre parenthèses.

Solution : C’est le pourcentage de cellules du labyrinthe que le chemin solution traverse, pour un labyrinthe typique créé par l’algorithme. Cela suppose que le labyrinthe fait 100×100 passages avec le début et la fin dans des coins opposés. C’est une mesure de la « sinuosité » du chemin solution. Les labyrinthes unicursaux ont une sinuosité maximale, puisque la solution traverse l’ensemble du labyrinthe. L’Arbre binaire a la sinuosité minimale possible, où le chemin solution traverse simplement le labyrinthe et ne dévie jamais ou ne cesse jamais de progresser vers la fin. Généralement, créer en ajoutant des murs a les mêmes propriétés que creuser des passages, cependant si la différence est significative, le pourcentage d’ajout de murs est indiqué entre parenthèses.

Source : C’est la source de l’algorithme, ce qui signifie par qui il est nommé, ou qui l’a inventé ou popularisé. Certains sont listés comme « génériques », ce qui signifie qu’ils sont si évidents qu’ils ont été imaginés ou implémentés par de nombreuses personnes indépendamment. Walter Pullen a nommé « Chasse et tue », mais n’a pas inventé la technique, dont on peut trouver des implémentations datant de nombreuses années.

Labyrinthes Sidewinder

Labyrinthes : différents algorithmes

Labyrinthe Sidewinder

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Labyrinthe Sidewinder

Cet algorithme simple est très similaire à l’algorithme de l’arbre binaire, et seulement légèrement plus compliqué. Le labyrinthe est généré ligne par ligne : Pour chaque cellule, décidez au hasard de creuser un passage vers la droite. Si un passage n’est pas creusé, alors considérez le passage horizontal qui vient d’être complété, formé par la cellule actuelle et toutes les cellules à gauche qui ont creusé des passages menant jusqu’à elle. Choisissez au hasard une cellule le long de ce passage, et creusez un passage vers le haut à partir de celle-ci (qui doit être la cellule actuelle si la cellule adjacente n’a pas creusé). Alors qu’un labyrinthe en arbre binaire monte toujours depuis la cellule la plus à gauche d’un passage horizontal, un labyrinthe Sidewinder monte depuis une cellule aléatoire. Alors qu’un arbre binaire a les bords supérieur et gauche du labyrinthe formant un long passage, un labyrinthe Sidewinder n’a que le bord supérieur formant un long passage. Comme l’arbre binaire, un labyrinthe Sidewinder peut être résolu de manière déterministe sans erreur de bas en haut, car à chaque ligne, il y aura toujours exactement un passage menant vers le haut. Une solution à un labyrinthe Sidewinder ne reviendra jamais sur elle-même ou ne visitera jamais une ligne plus d’une fois, bien qu’elle « serpente de côté en côté ». Le seul type de cellule qui ne peut pas exister dans un labyrinthe Sidewinder est une impasse avec le passage orienté vers le bas, car cela contredirait le fait que chaque passage montant mène au début. Un labyrinthe Sidewinder a tendance à avoir une solution élitiste, où le bon chemin est très direct, mais il y a beaucoup de longs faux chemins descendant du haut à côté de lui.

Labyrinthes en arbre binaire

Labyrinthes : différents algorithmes

Labyrinthes en arbre binaire

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Labyrinthes en arbre binaire

C’est fondamentalement l’algorithme le plus simple et le plus rapide possible, cependant les labyrinthes qu’il produit ont une texture très biaisée. Pour chaque cellule, creusez un passage soit vers le haut, soit vers la gauche, mais pas les deux. Dans la version avec ajout de murs, pour chaque sommet ajoutez un segment de mur menant vers le bas ou vers la droite, mais pas les deux. Chaque cellule est indépendante de toutes les autres cellules, où vous n’avez pas besoin de vous référer à l’état des autres cellules lors de sa création. Par conséquent, c’est un véritable algorithme de génération de labyrinthe sans mémoire, sans limite de taille du labyrinthe que vous pouvez créer.
C’est fondamentalement un arbre binaire au sens informatique, si vous considérez le coin supérieur gauche comme la racine, où chaque nœud ou cellule a un parent unique qui est la cellule au-dessus ou à gauche de celle-ci. Les labyrinthes en arbre binaire sont différents des labyrinthes parfaits standards, puisqu’environ la moitié des types de cellules ne peuvent jamais exister en eux. Par exemple, il n’y aura jamais de carrefour, et toutes les impasses ont des passages pointant vers le haut ou vers la gauche, et jamais vers le bas ou vers la droite.
Le labyrinthe a tendance à avoir des passages menant en diagonale du coin supérieur gauche au coin inférieur droit, ce qui rend le labyrinthe beaucoup plus facile à naviguer du coin inférieur droit vers le coin supérieur gauche. Vous pourrez toujours voyager vers le haut ou vers la gauche, mais jamais les deux, donc vous pouvez toujours voyager de manière déterministe en diagonale vers le haut et vers la gauche sans rencontrer d’obstacles. C’est en voyageant vers le bas et vers la droite que vous rencontrerez des choix et des impasses. Notez que si vous retournez un labyrinthe en arbre binaire à l’envers et traitez les passages comme des murs et vice versa, le résultat est fondamentalement un autre arbre binaire.

Algorithme de la Division récursive

Labyrinthes : différents algorithmes

Algorithme de la Division récursive

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de la Division récursive

Cet algorithme est un peu similaire au retour-récursif, puisqu’ils sont tous deux basés sur une pile, sauf que celui-ci se concentre sur les murs plutôt que sur les passages. Commencez par créer un mur horizontal ou vertical aléatoire traversant la zone disponible dans une rangée ou une colonne aléatoire, avec une ouverture placée au hasard le long de celui-ci. Ensuite, répétez le processus de manière récursive sur les deux sous-zones générées par le mur de division. Pour de meilleurs résultats, privilégiez le choix horizontal ou vertical en fonction des proportions de la zone, par exemple une zone deux fois plus large que haute devrait être divisée plus souvent par un mur vertical. C’est l’algorithme le plus rapide sans biais directionnel, et peut même rivaliser avec les labyrinthes en arbre binaire car il peut terminer plusieurs cellules à la fois, bien qu’il ait le défaut évident de longs murs traversant l’intérieur. Cet algorithme est une forme de labyrinthes fractals imbriqués, sauf qu’au lieu de toujours créer des labyrinthes de taille de cellule fixe avec des labyrinthes de même taille dans chaque cellule, il divise la zone donnée de manière aléatoire en un labyrinthe de taille aléatoire 1×2 ou 2×1. La division récursive ne fonctionne pas comme un creuseur de passages, car cela aboutirait à un chemin de solution évident qui suit soit le bord extérieur, soit traverse directement l’intérieur.

Algorithme de Prim (modifié)

Labyrinthes : différents algorithmes

Algorithme de Prim (modifié)

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de Prim (modifié)

C’est l’algorithme de Prim pour produire un arbre couvrant minimal, modifié de sorte que tous les poids des arêtes soient les mêmes, mais également implémenté en regardant les cellules plutôt que les arêtes. Il nécessite un espace de stockage proportionnel à la taille du labyrinthe. Pendant la création, chaque cellule est d’un des trois types : (1) « Dedans » : La cellule fait partie du labyrinthe et a déjà été creusée, (2) « Frontière » : La cellule ne fait pas partie du labyrinthe et n’a pas encore été creusée, mais est à côté d’une cellule qui est déjà « dedans », et (3) « Dehors » : La cellule ne fait pas encore partie du labyrinthe, et aucun de ses voisins n’est « dedans » non plus.

Commencez par choisir une cellule, la mettre « dedans », et définir tous ses voisins comme « frontière ». Continuez en choisissant une cellule « frontière » au hasard, et en creusant vers elle à partir d’une de ses cellules voisines qui sont « dedans ». Changez cette cellule « frontière » en « dedans », et mettez à jour tous ses voisins qui sont « dehors » en « frontière ». Le labyrinthe est terminé quand il n’y a plus de cellules « frontière » (ce qui signifie qu’il n’y a plus de cellules « dehors » non plus, donc elles sont toutes « dedans »).

Cet algorithme donne des labyrinthes avec un facteur « rivière » très bas avec beaucoup d’impasses courtes, et une solution plutôt directe. Le labyrinthe résultant est très similaire à l’algorithme de Prim simplifié, avec seulement la subtile distinction que les indentations dans l’arbre en expansion ne sont remplies que si cette cellule frontière est sélectionnée au hasard, contrairement au fait d’avoir trois fois plus de chances de remplir cette cellule via une des arêtes frontières menant à elle. Il s’exécute également très rapidement, plus rapidement que l’algorithme de Prim simplifié car il n’a pas besoin de composer et de maintenir une liste d’arêtes.

Algorithme de Prim (simplifié)

Labyrinthes : différents algorithmes

Algorithme de Prim (simplifié)

Traduit en Français par moi-même. Les originaux sont ici.
Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de Prim (simplifié)

C’est l’algorithme de Prim pour produire un arbre couvrant minimal, simplifié de telle sorte que tous les poids des arêtes sont les mêmes. Il nécessite un espace de stockage proportionnel à la taille du labyrinthe. Commencez avec un sommet aléatoire. Continuez en sélectionnant au hasard une arête de passage reliant le labyrinthe à un point qui n’en fait pas encore partie, et attachez-la au labyrinthe. Le labyrinthe est terminé quand il n’y a plus d’arêtes à considérer. Comme les arêtes n’ont pas de poids et ne sont pas ordonnées, elles peuvent être stockées dans une simple liste, ce qui signifie que la sélection d’éléments dans la liste est très rapide et ne prend qu’un temps constant. Par conséquent, c’est beaucoup plus rapide que l’algorithme de Prim original avec des poids d’arêtes aléatoires. La texture du labyrinthe produit aura un facteur « rivière » plus faible et une solution plus simple que l’algorithme de Prim original, car il se répandra uniformément à partir du point de départ comme du sirop versé, au lieu de contourner et de s’écouler autour des groupes d’arêtes de poids plus élevé qui ne sont pas couverts avant plus tard. Copy

Algorithme de Prim (original)

Labyrinthes : différents algorithmes

Algorithme de Prim (original)

Traduit en Français par moi-même. Les originaux sont ici.

Si vous voyez des fautes d’orthographe ou des corrections à apporter signalez-le moi je me ferai un plaisir de vous écouter !

Algorithme de Prim (original)<

C’est l’algorithme de Prim pour produire un arbre couvrant minimal, opérant sur des poids d’arêtes aléatoires uniques. Il nécessite un espace de stockage proportionnel à la taille du labyrinthe.

Fonctionnement de l’algorithme :

Commencez avec n’importe quel sommet (le labyrinthe final sera le même quel que soit le sommet de départ).
Continuez en sélectionnant l’arête de passage ayant le plus petit poids qui relie le labyrinthe à un point qui n’en fait pas encore partie.
Attachez cette arête au labyrinthe.
Le labyrinthe est terminé quand il n’y a plus d’arêtes à considérer.

Pour sélectionner efficacement l’arête suivante, une file de priorité (généralement implémentée avec un tas) est nécessaire pour stocker les arêtes frontières. Malgré cela, cet algorithme est relativement lent, car la sélection d’éléments et la maintenance du tas nécessitent un temps logarithmique (log(n)).

Par conséquent, l’algorithme de Kruskal, qui produit également un arbre couvrant minimal, peut être considéré comme meilleur, car il est plus rapide et produit des labyrinthes avec une texture identique. En fait, avec la même graine de nombres aléatoires, des labyrinthes identiques peuvent être créés avec les algorithmes de Prim et de Kruskal.

11 avril 2024

JavaScript hack update

Mise à jour en pur JavaScript hacks

Voici une petite mise à jour en vanilla JS qui fait la même chose que ce que j’ai mis ici.

function emptyBody() {
    document.body.innerHTML = '';
}
function getRandomInt(max) {
    return Math.floor(Math.random() * Math.floor(max));
}
function addNewAvatar() {
    let curr = getRandomInt(5000);
    return function() {
        const img = document.createElement('img');
        img.src = `https://avatars.githubusercontent.com/u/${curr}`;
        img.style.maxWidth = '50px';
        img.style.display = 'inline-block';
        img.style.float = 'left';
        img.style.margin = '0';
        img.style.padding = '0';
        document.body.appendChild(img);
        curr += (1 + getRandomInt(3));
        setTimeout(addNewAvatar(), 100);
    };
}
emptyBody();
setTimeout(addNewAvatar(), 100);

La loi des abstractions qui fuient

Nb : j’ai toujours été très admiratif de Joël Spolsky (créateur de Trello qu’il a revendu $425M) et de ses articles excellents. Il l’a retiré de son wiki mais il est toujours disponible ici, sur Webarchive.

Je me permets de le copier coller, avec de très légères modifications, car il est excellent – cela n’est que mon opinion bien sûr.

Il y a une part de magie dans l’ingénierie de l’Internet sur laquelle vous vous appuyez tous les jours. Elle œuvre au niveau du protocole TCP, un des blocs constitutifs fondamentaux de l’Internet.

TCP est un moyen de transmettre des données qui est fiable. Par cela, je veux dire : si vous envoyez un message sur un réseau en utilisant TCP, il arrivera à destination et ne sera ni tronqué ni corrompu.

Nous utilisons TCP pour beaucoup de choses, comme accéder à des pages web ou envoyer du courrier électronique. La fiabilité de TCP est ce qui permet à tous les mails excitants d’escrocs est-africains d’arriver à destination en parfait état. Ô joie.

Par comparaison, il existe une autre méthode de transmission de données appelée IP, qui est peu fiable. Personne ne vous garantit que vos données arriveront à destination et qu’elles ne seront pas endommagées avant d’arriver. Si vous envoyez une série de messages avec IP, ne soyez pas surpris que seulement la moitié d’entre eux arrive, et que certains d’entre eux arrivent dans un ordre différent de l’ordre d’envoi, et que d’autres soient remplacés par des messages alternatifs, contenant peut-être des photos d’adorables bébés orangs-outangs, ou plus probablement beaucoup de fatras illisible ressemblant au champ objet d’un spam taiwanais.

Et voici la part de magie : TCP fonctionne au-dessus d’IP. En d’autres termes, TCP est obligé de se débrouiller pour envoyer des données de manière fiable en utilisant uniquement un outil peu fiable.

Pour illustrer en quoi ceci est magique, considérez le scénario suivant issu du monde réel, moralement équivalent quoique quelque peu déraisonnable.

Imaginez que nous ayons un moyen d’envoyer des acteurs de Broadway à Hollywood, qui consiste à les mettre dans des voitures et à les conduire à travers le pays. Certaines de ces voitures s’écrasent, tuant les pauvres acteurs. Parfois les acteurs se saoulent en chemin et se rasent la tête ou se font des tatouages sur le nez, devenant de ce fait trop laids pour travailler à Hollywood, et fréquemment, les acteurs arrivent dans ordre différent de l’ordre initial, car ils ont tous pris des routes différentes. Maintenant imaginez un nouveau service intitulé Hollywood Express, qui livre des acteurs à Hollywood en garantissant (a) qu’ils arrivent à destination (b) dans l’ordre et (c) en parfait état. La part de magie est que Hollywood Express ne dispose d’aucune autre méthode pour livrer les acteurs que la méthode peu fiable qui consiste à les mettre dans des voitures et les conduire à travers le pays. Hollywood Express fonctionne en vérifiant que chaque acteur arrive en parfait état et, dans le cas contraire, appelle la maison mère pour demander qu’un jumeau identique de l’acteur soit envoyé pour le remplacer. Si les acteurs arrivent dans le désordre, Hollywood Express les remet dans l’ordre. Si un grand OVNI faisant route vers la zone 51 s’écrase sur l’autoroute du Nevada, la rendant impraticable, tous les acteurs qui devaient passer par-là sont re-routés via l’Arizona et Hollywood Express n’avertit même pas les réalisateurs californiens de ce qui est arrivé. Pour eux, il semble simplement que les acteurs mettent un peu plus de temps que d’habitude pour arriver, et ils n’entendent même pas parler du crash de l’OVNI.

Voilà, approximativement, la magie de TCP. C’est ce que les informaticiens aiment appeler une abstraction : une simplification de quelque chose de beaucoup plus compliqué qui se trame dans l’ombre. A ce qu’il paraît, une part importante de la programmation des ordinateurs consiste à élaborer des abstractions. Qu’est-ce qu’une bibliothèque de chaînes de caractères ? C’est une manière de simuler que les ordinateurs peuvent manipuler des chaînes de caractères aussi facilement qu’ils manipulent des nombres. Qu’est-ce qu’un système de fichiers ? C’est une manière de simuler qu’un disque dur n’est pas vraiment un ensemble de plateaux magnétiques en rotation capables de stocker des bits à certains endroits, mais plutôt un système hiérarchique de dossiers-dans-des-dossiers, qui contiennent eux-mêmes des fichiers individuels, qui à leur tour contiennent une ou plusieurs chaînes d’octets.

Revenons à TCP. Tout à l’heure, dans un souci de simplicité, j’ai raconté une petite fable et certains d’entre vous ont maintenant de la fumée qui sort par les oreilles parce que cette fable est en train de les rendre fous. J’ai dit que TCP garantissait que votre message arrive à destination. En fait, il ne le garantit pas vraiment. Si votre serpent apprivoisé a mâchouillé le câble réseau relié à votre ordinateur et qu’aucun paquet IP ne peut passer, alors TCP ne peut rien faire contre ça et votre message n’arrivera jamais. Si vous avez rudoyé les administrateurs système de votre entreprise et qu’ils se sont vengés en vous reliant à un concentrateur surchargé, seulement certains de vos paquets IP vont passer et TCP va fonctionner, mais tout sera vraiment lent.

C’est ce que j’appelle une abstraction qui fuit. TCP essaie de fournir une abstraction complète d’un réseau sous-jacent peu fiable, mais parfois le réseau fuit à travers l’abstraction et vous sentez des choses contre lesquelles l’abstraction ne peut pas vraiment vous protéger. Ce n’est qu’un exemple de ce que j’ai intitulé la Loi des Abstractions qui Fuient :

Toute abstraction non triviale, à un certain degré, fuit.

Les abstractions échouent. Parfois un peu, parfois beaucoup. Il y a des fuites. Les choses tournent mal. Cela arrive tout le temps quand vous avez des abstractions. Voici quelques exemples :

Quelque chose d’aussi simple que de parcourir un tableau à deux dimensions de taille importante peut avoir des performances radicalement différentes si vous le faites horizontalement plutôt que verticalement, en fonction du « sens de la fibre » — une direction peut résulter en beaucoup plus de défaillances de page que l’autre direction, et les défaillances de page sont lentes. Même les programmeurs en assembleur sont censés pouvoir faire semblant de disposer d’un vaste espace d’adressage, mais la mémoire virtuelle leur rappelle que ce n’est qu’une abstraction, qui fuit quand il y a une défaillance de page et que certains accès mémoire prennent beaucoup plus de nano-secondes que d’autres.
Le langage SQL est censé faire abstraction des étapes des procédures nécessaires pour interroger une base de données, en les remplaçant par la possibilité de définir simplement ce que l’on veut et de laisser la base de données trouver les étapes des procédure pour l’obtenir. Mais dans certains cas, les requêtes SQL sont des milliers de fois plus lentes que d’autres qui sont logiquement équivalentes. Un célèbre exemple de cela est que certains serveurs SQL sont nettement plus rapides si vous spécifiez « where a=b and b=c and a=c » plutôt que si vous spécifiez seulement « where a=b and b=c », même si le résultat est identique. Vous n’êtes pas censé devoir vous occuper de la procédure, mais seulement de la spécification. Mais parfois l’abstraction fuit et mène à des performances horribles et vous devez sortir l’analyseur de plan de requête et étudier ce qui ne va pas et trouver comment rendre votre requête plus rapide.
Même si certaines bibliothèques réseau comme NFS ou SMB vous permettent de traiter des fichiers sur des machines distantes « comme s’ils » étaient locaux, parfois la connexion devient très lente ou tombe et le fichier cesse de se comporter comme s’il était local, et en tant que programmeur vous devez écrire du code pour prendre cela en compte. L’abstraction « un fichier distant c’est la même chose qu’un fichier local » fuit. Voici un exemple concret pour les administrateurs système UNIX. Si vous placez les répertoires home des utilisateurs sur des disques montés en NFS (une abstraction), et que vos utilisateurs créent des fichiers .forward pour transmettre leur courrier électronique ailleurs (une autre abstraction), et que le serveur NFS tombe pendant que des nouveaux courriers arrivent, les messages ne seront pas transmis car le fichier .forward sera introuvable. La fuite dans l’abstraction aura en fait laissé s’échapper quelques messages.
En C++, les classes de chaînes de caractères sont censées vous permettre de faire semblant que les chaînes de caractères sont un type de données à part entière. Elles tentent de faire abstraction du fait que les chaînes de caractères sont difficiles à manipuler et vous permettent d’agir comme si c’était aussi facile qu’avec des entiers. Presque toutes les classes C++ de chaînes de caractères surchargent l’opérateur » + » et vous pouvez écrire s + "toto" pour les concaténer. Mais vous savez quoi ? Peu importe à quel point elles essaient, il n’y a pas sur Terre de classe C++ de chaînes de caractères qui vous permette d’écrire "toto" + "titi", car les chaînes de caractères littérales en C++ sont toujours des char*, jamais des chaînes. L’abstraction a créé une fuite que le langage ne vous permet pas de reboucher. (De manière amusante, l’histoire de l’évolution de C++ au fil du temps peut être décrite comme l’histoire des tentatives pour reboucher les fuites dans l’abstraction des chaînes de caractères. Pourquoi ne pouvaient-ils pas simplement ajouter une classe de chaîne de caractères native au langage lui-même? Cela m’échappe pour le moment.)
Et vous ne pouvez pas conduire aussi vite quand il pleut, même si votre voiture a des essuie-glaces et des phares et un toit et un chauffage, qui tous vous permettent de ne pas vous inquiéter du fait qu’il pleut (ils font abstraction de la météo), mais zut, vous devez faire attention à l’aquaplaning et parfois la pluie est si forte que vous ne pouvez pas voir très loin devant vous et donc vous roulez plus lentement quand il pleut, parce qu’on ne peut jamais faire complètement abstraction de la météo, à cause de la loi des abstractions qui fuient.

Une des raisons pour lesquelles la loi des abstractions qui fuient est problématique est qu’elle implique que les abstractions ne nous simplifient pas vraiment la vie autant qu’elles le devraient. Quand je forme quelqu’un à être programmeur C++, ce serait bien si je n’avais jamais à lui parler des char* et de l’arithmétique des pointeurs. Ce serait bien si je pouvais aller tout droit aux chaînes de caractères STL. Mais un jour il va devoir écrire le code "toto" + "titi", et des choses vraiment bizarres vont se passer, et je vais devoir m’arrêter et tout lui apprendre sur les char* de toutes façons. Ou un jour il va essayer d’appeler une fonction de l’API Windows qui est documentée comme ayant un argument OUT LPTSTR et il ne sera pas capable de comprendre comment l’appeler jusqu’à ce qu’il ait tout appris sur les char*, et les pointeurs, et l’Unicode, et les wchar_t, et les fichiers d’en-tête TCHAR, et tout ce fatras qui fuit.

Lors de l’enseignement de la programmation COM, ce serait bien si je pouvais juste leur apprendre comment utiliser les assistants de Visual Studio et toutes les fonctionnalités de génération de code, mais si quoi que ce soit tourne mal, ils n’auront pas la moindre idée de ce qui s’est passé et de comment le corriger et réparer. Je vais devoir tout leur apprendre sur IUnknown et les CLSID et les ProgID et … ah, l’humanité !

Lors de l’enseignement de la programmation ASP.NET, ce serait bien si je pouvais juste leur apprendre qu’ils peuvent double-cliquer sur des choses et ensuite écrire le code qui s’exécute sur le serveur quand l’utilisateur clique sur ces choses. En fait ASP.NET fait abstraction de la différence entre écrire le code HTML pour traiter le clic sur un hyper lien (<a>) et le code pour traiter le clic sur un bouton. Problème : les concepteurs d’ASP.NET devaient cacher le fait qu’en HTML, il n’y a pas moyen de soumettre un formulaire avec un hyper lien. Ils font cela en générant quelques lignes de JavaScript et en attachant un contrôleur d’événement « onclick » au lien. L’abstraction fuit, pourtant. Si l’utilisateur final a désactivé JavaScript, l’application ASP.NET ne fonctionne pas bien, et si le programmeur ne comprend pas ce qu’ASP.NET fait comme abstraction, il n’aura simplement aucun indice sur ce qui ne va pas.

La loi des abstractions qui fuient implique que chaque fois que quelqu’un arrive avec un nouvel outil magique de génération de code qui est censé nous rendre tous super-efficaces, vous entendez plein de gens dire « apprends d’abord comment le faire manuellement, et après utilise l’outil magique pour gagner du temps ». Les outils de génération de code qui prétendent faire abstraction de quelque chose, comme toutes les abstractions, fuient, et la seule façon compétente de s’accommoder des fuites est d’apprendre comment les abstractions fonctionnent et ce dont elles font abstraction. Ainsi les abstractions nous font gagner du temps lors du travail, mais elles ne nous font pas gagner du temps lors de l’apprentissage.

Tout ceci implique que paradoxalement, alors même que nous avons des outils de programmation de plus en plus haut niveau avec des abstractions toujours meilleures, devenir un programmeur compétent devient de plus en plus difficile.

Lors de mon premier stage chez Microsoft, j’ai écrit des bibliothèques de chaînes de caractères pour Macintosh. Une tâche typique : écrire une version de strcat qui retourne un pointeur sur la fin de la nouvelle chaîne. Quelques lignes de code C. Tout ce que j’ai fait était directement issu du K&R — un bouquin peu épais sur le langage de programmation C.

Aujourd’hui, pour travailler, j’ai besoin de connaître Visual Basic, COM, ATL, C++, InnoSetup, les rouages d’Internet Explorer, les expressions régulières, COM, HTML, CSS, et XML. Rien que des outils de haut niveau comparés aux vieux trucs de K&R, mais j’ai toujours besoin de connaître les trucs de K&R ou alors je suis fichu.

Il y a dix ans, nous pouvions imaginer que de nouveaux paradigmes de programmation rendraient la programmation plus facile aujourd’hui. En fait, les abstractions que nous avons créées au fil des années nous permettent d’aborder de nouveaux ordres de complexité dans le développement logiciel, que nous n’avions pas à aborder il y a dix ou quinze ans, comme la programmation d’interfaces graphiques ou la programmation réseau. Et alors que ces fabuleux outils, comme les langages modernes de type objet, nous permettent d’effectuer beaucoup de travail incroyablement vite, soudain un jour nous devons régler un problème là où l’abstraction a fuit, et cela prend 2 semaines. Et quand vous devez embaucher un programmeur pour faire majoritairement du VB, ce n’est pas suffisant d’embaucher un programmeur VB, parce qu’il restera collé au goudron chaque fois que l’abstraction VB fuira.

La loi des abstractions qui fuient nous met des bâtons dans les roues.

Unicode : le minimum absolu que tout développeur doit savoir

Je me permets de le copier coller, avec de très légères modifications, car il est excellent – cela n’est que mon opinion bien sûr.

Le minimum absolu que tout développeur doit absolument, positivement savoir sur Unicode et les jeux de caractères (aucune excuse !)

Par Joël Spolsky

Vous ne vous êtes jamais posé de questions sur cette mystérieuse balise Content-Type ? Vous savez, celle que vous êtes supposé mettre en HTML, et dont vous n’avez absolument jamais su ce qu’elle veut dire ?

Vous n’avez jamais reçu un email de vos amis en Bulgarie avec pour objet » ???? ?????? ??? ???? » ?

J’ai été atterré de découvrir combien de développeurs ne sont absolument pas au jus à propos du monde mystérieux des jeux de caractères, encodages, Unicode et tous ces trucs-là. Il y a quelques années, un beta-testeur se demandait si le programme pourrait traiter des messages emails en japonais. En japonais ? Ils ont des emails, en japonais ? J’étais même pas au courant. Quand j’ai regardé de près au contrôle ActiveX que nous avions acheté pour parser les messages email au format MIME, nous avons découvert qu’il faisait très exactement ce qu’il ne fallait pas faire avec les jeux de caractères, et nous avons dû écrire du code vraiment héroïque pour défaire la mauvaise conversion qu’il effectuait et la refaire correctement. J’ai alors évalué une autre librairie du commerce, et elle avait elle aussi une implémentation complètement naze des codes de caractères. J’ai contacté le développeur de ce package et il pensait en gros qu’ « ils ne pouvaient rien y faire ». Comme beaucoup de programmeurs, il aurait bien voulu que ce sujet disparaisse de lui même, d’une manière ou d’une autre.

Mais il ne disparaîtra pas. Quand j’ai découvert que l’outil de développement web le plus populaire, PHP, avait une ignorance à peu près totale de ces questions d’encodage de caractères, qu’il utilisait d’une manière insouciante 8 bits pour les caractères, rendant de fait presque impossible le développement d’applications web internationales facilement, je me suis dit « trop, c’est trop ».

J’ai donc une annonce à vous faire : si vous êtes un programmeur, et que vous ne possédez pas les bases des caractères, des jeux de caractères, de l’encodage et d’Unicode, et que je vous attrape, je vais vous punir en vous faisant éplucher des oignons pendant 6 mois dans un sous-marin. Je vous jure que je le ferai.

Et encore une chose:

CE N’EST PAS SI DIFFICILE.

Dans cet article je vais vous donner exactement ce que tout programmeur en activité devrait savoir. Tout ce mélange « texte à plat = ascii = tout caractère est sur 8 bits » n’est pas seulement faux, c’est sans espoir, et si vous êtes encore en train de programmer de cette façon, vous ne valez pas mieux qu’un docteur qui ne croit pas aux microbes. Faites moi le plaisir de ne pas écrire une ligne de code de plus jusqu’à ce que vous ayez fini de lire cet article.

Avant de commencer, je devrais vous prévenir que si vous êtes l’une de ces rares personnes qui savent tout de l’internationalisation, vous allez trouver mon exposé un petit peu trop simplifié. Je veux vraiment juste donner ici un minimum afin que tout le monde puisse comprendre ce qui se passe et puisse écrire du code qui ait un espoir de fonctionner avec du texte dans n’importe quelle autre langue qu’une version d’anglais n’incluant aucun mot accentué. J’attire également votre attention sur le fait que la manipulation des caractères est seulement une minuscule partie de tout ce qu’il faut pour créer des logiciels qui fonctionnent dans toutes les langues, malheureusement je ne peux écrire que sur une chose à la fois, alors aujourd’hui ce sont les jeux de caractères.

Un point de vue historique

La façon la plus facile de comprendre tout ça est d’avancer chronologiquement.

Vous vous dites probablement que là je vais parler de ces très vieux jeux de caractères comme EBCDIC. Hé bien non. EBCDIC n’est pas vital pour vous. Nous n’avons pas à remonter si loin dans le temps.

La table ASCII

Il y a de cela presque longtemps, alors qu’Unix était inventé et que K&R écrivaient Le langage C, tout était très simple. EBCDIC était en train de disparaître. Les seuls caractères qui comptaient étaient ces bonnes vieilles lettres anglaises non accentuées, et nous avions un code pour elles appelé ASCII qui pouvait représenter chaque caractère à l’aide d’un nombre entre 32 et 127. L’espace était le 32, la lettre « A » la 65, etc. On pouvait facilement stocker ça sur 7 bits. Beaucoup d’ordinateurs, à cette époque, utilisaient des mots de 8 bits, ce qui fait que non seulement vous pouviez stocker n’importe quel caractère ASCII, mais vous aviez un bit entier à dépenser, que, si vous étiez vicieux, vous pouviez utiliser pour vos propres besoins déviants: les mous du bulbe de chez WordStar ont utilisé ce bit de poids fort pour indiquer la dernière lettre d’un mot, réellement, condamnant ainsi WordStar aux textes anglais uniquement. Les codes en dessous de 32 étaient appelés non imprimables et étaient utilisés pour les jurons. Je plaisante. Ils étaient utilisés pour les caractères de contrôle, comme le 7 qui faisait biper l’ordinateur et le 12 qui provoquait l’expulsion d’une feuille hors de l’imprimante, et l’aspiration d’une nouvelle.

Et tout cela était bel et bon, tant que vous êtes anglophone.

Parce que ces mots mémoire avaient de la place pour 8 bits maximum, beaucoup de gens se sont mis à penser « Bon sang, on peut utiliser les codes 128-255 pour nos propres besoins ». Le problème, c’est que beaucoup de gens ont eu cette idée au même moment, et qu’ils avaient chacun leur propre petite idée de quoi devait aller où dans cet espace de 128 à 255. L’IBM-PC avait quelque chose qui allait devenir connu comme le jeu de caractères OEM qui fournissait des caractères accentués pour les langues européennes et une brassée de caractères semi-graphiques… Des barres horizontales, des barres verticales, des barres horizontales avec des petites babioles suspendues à droite, etc., et vous pouviez utiliser ces caractères représentant des lignes pour fabriquer d’élégantes boîtes de dialogue et des lignes sur l’écran, que vous pouvez peut être même voir encore tourner sur un très vieux PC dans le pressing du coin. En fait dès que des gens ont commencé à acheter des PC en dehors d’Amérique toutes sortes de jeux de caractères OEM différents ont été imaginés, qui utilisaient tous les 128 caractères du haut pour leurs propres besoins. Par exemple sur certains PC le caractère 130 affichait un é, mais sur les ordinateurs vendus en Israël c’était la lettre hébreu Gimel (ג), ce qui fait que quand des américains envoyaient leurs C.V. en Israël ils étaient reçus comme des « csums ». Dans de nombreux cas, comme le russe, il y avaient beaucoup d’idées différentes de ce qu’ils fallait faire avec les 128 caractères du haut, ce qui fait que vous ne pouviez même pas interchanger de manière fiable des documents russes entre eux.

Cet OEM ouvert à tous finit par être codifié par le standard ANSI. Dans le standard ANSI, on était d’accord sur ce qu’il fallait faire en dessous de 128, qui était vraiment très proche de l’ASCII, mais on gérait les caractères à partir de 128 de plein de façons différentes, selon où on vivait. Ces différents systèmes furent appelés des pages de codes. Par exemple en Israël DOS utilisait une page de codes appelée 862, alors que les utilisateurs grecs utilisaient la 737. C’était la même chose en dessous de 128, mais différent au dessus, là où les lettres rigolotes habitaient. Les versions nationales de MS-DOS avaient des douzaines de ces pages de codes, capables de prendre en compte n’importe quoi de l’anglais à l’islandais , et il y avait même quelques pages de code « multi-langues » qui pouvaient faire de l’espéranto et du galicien sur le même ordinateur ! Houah ! Mais avoir, disons, de l’hébreu et du grec sur le même ordinateur était une impossibilité totale à moins d’écrire son propre programme capable d’afficher n’importe quoi à l’aide de bitmaps graphiques, parce que l’hébreu et le grec réclamaient des pages de codes ayant des interprétations différentes des nombres du haut.

Pendant ce temps, en Asie, des choses encore plus dingues étaient faites pour prendre en compte le fait que les alphabets asiatiques avaient des milliers de lettres, qui ne pourraient jamais tenir sur 8 bits. En fait, la solution trouvée fut un système bordélique appelé DBCS, « double byte character set », le jeu de caractères à double octet, dans lequel certaines lettres étaient stockées sur un octet, et d’autres sur deux. Il était facile de se déplacer vers l’avant à l’intérieur d’une chaîne, mais quasi impossible de reculer. Les programmeurs étaient encouragés à ne pas utiliser s++ et s-- pour se déplacer en avant et en arrière, mais plutôt d’appeler des fonctions, comme les AnsiNext et AnsiPrev sous Windows, qui savaient comment se débrouiller avec tout ce foutoir.

Mais même alors, beaucoup de gens se contentaient de prétendre qu’un octet était un caractère et qu’un caractère c’était 8 bits, et que du moment que vous ne déplaciez jamais une chaîne d’un ordinateur vers un autre, ou que vous ne parliez pas plus d’une langue, en gros ça marchait toujours. Mais bien sûr, dès qu’Internet apparut, déplacer une chaîne d’un ordinateur vers un autre devint un lieu commun, et tout ce merdier se cassa la figure. Heureusement, Unicode avait été inventé.

Unicode

Unicode fut un effort courageux pour créer un jeu de caractères unique qui inclurait tout les systèmes d’écriture raisonnables de la planète et quelques autres fictifs comme le Klingon, également. Certaines personnes sont persuadées à tort qu’Unicode est simplement un code 16-bits où chaque caractère tient sur 16 bits et qu’il y a donc 65536 caractères possibles. En fait, ce n’est pas correct. C’est le mythe le plus commun à propos d’Unicode, donc si vous pensiez ça, ne vous en faites pas.

En fait, Unicode possède une façon différente d’appréhender les caractères, et vous devez comprendre cette façon qu’Unicode a d’appréhender les choses, ou rien ne vous semblera clair.

Jusqu’à maintenant, nous sommes partis du principe qu’à une lettre correspondaient des bits qu’on pouvait stocker sur disque ou en mémoire.

A -> 0100 0001

En Unicode, une lettre correspond à quelque chose appelé un point de code (ou numéro de caractère, ou valeur scalaire Unicode) qui n’est qu’un concept théorique. Comment ce point de code est représenté en mémoire ou sur disque est une tout autre histoire.

En Unicode, la lettre A est un idéal platonicien. Elle flotte dans les cieux :

« A »

Ce A platonicien est différent de B, et différent de a, mais le même que A et A, et A. L’idée que A dans la police Times New Roman est le même caractère que le A dans la police Helvetica, mais différent de « a » en minuscule, ne semble pas tellement sujet à discussion, mais dans certaines langues, se demander simplement ce qu’une lettre est peut entraîner des controverses. Est-ce que la lettre allemande ß est une véritable lettre, ou juste une façon tordue d’écrire ss ? Si la forme d’une lettre change à la fin d’un mot, est-ce une lettre différente ? La langue hébreue répond oui, l’arabe non. Enfin bon, quoi qu’il en soit, les brillants membres du consortium Unicode ont réfléchi à tout cela durant la dernière décennie ou presque, à grand renfort de débats hautement politiques. Vous n’avez pas donc plus à vous en préoccuper. Ils ont déjà pensé à tout.

Toute les lettres platoniciennes de tous les alphabets se sont vues attribuer un nombre magique par le consortium Unicode qui s’écrit comme ceci: U+0645. Ce nombre magique est appelé un point de code. Le U+ signifie « Unicode », et les nombres derrière sont en héxadécimal. U+FEC9 est la lettre arabe Ain. La lettre anglaise A est la U+0041. Vous les trouverez toutes à l’aide de l’utilitaire charmap sous Windows, ou en visitant le site web d’Unicode.

Il n’y a pas de véritable limite au nombre de lettres qu’Unicode peut définir et ils sont réellement allés au delà de 65536, ce qui fait que toutes les lettres Unicode ne peuvent pas tenir sur deux octets, mais de toute façon c’était un mythe, alors…

OK, alors disons que nous avons une chaîne :

Hello

qui, en Unicode, correspond aux cinq points de code :

U+0048 U+0065 U+006C U+006C U+006F.

Juste une poignée de points de code. Des nombres, en fait. Jusque là nous n’avons rien dit sur comment stocker ou représenter ça en mémoire ou dans un message email.

Encodages

Et c’est là que les encodages interviennent.

La première idée pour l’encodage d’Unicode, celle qui a abouti au mythe des deux octets, fut: Hé, on n’a qu’à stocker ces nombres sur deux octets chacun! Hello devient donc:

00 48 00 65 00 6C 00 6C 00 6F

D’accord ? Pas si vite ! Est-ce que ça ne pourrait pas être :

48 00 65 00 6C 00 6C 00 6F 00

Hé bien, techniquement, oui, je pense bien que ça pourrait, et, en fait, les premiers « implémenteurs » voulaient pouvoir stocker leurs points de code Unicode en mode « poids fort derrière » [high-endian] ou « poids fort devant » [low-endian], selon que leur CPU était plus rapide ou plus lent dans l’un ou l’autre, et c’était bonnet blanc et blanc bonnet, et cela faisait déjà deux façons de stocker de l’Unicode. Alors les gens furent obligés d’en arriver à la convention bizarre de placer les caractères FE FF au début de toutes les chaînes Unicode ; on appela ça une marque d’ordre des octets Unicode (Unicode Byte Order Mark) et si vous intervertissiez vos octets de poids faible et fort ça donnait FF FE, et les gens qui lisaient votre chaîne savaient qu’ils devraient intervertir tous les autres octets. Pfff. Et toutes les chaînes Unicode en liberté dans la nature ne possèdent pas cette marque d’ordre des octets au début.

Pendant un moment il semblait que tout cela aurait pu suffire, mais les programmeurs se plaignaient toujours. « Regarde moi tous ces zéros! », disaient-ils, parce qu’ils étaient américains et qu’ils regardaient des textes en anglais qui utilisaient rarement des points de code au dessus de U+00FF. Et puis c’étaient des hippies libéraux en Californie qui voulaient préserver (sarcasme). Si ç’avait été des Texans, peu leur aurait importé de bâfrer deux fois la quantité d’octets. Mais ces mauviettes de Californiens ne pouvaient pas supporter l’idée de doubler la quantité de stockage nécessaire pour des chaînes, et puis, de toute façon, il y avait ces foutus documents, dehors, qui utilisaient tous ces jeux de caractères ANSI et DBCS, et qui allait convertir tout ça ? Moi? [NdT: En français dans le texte]. Pour cette seule raison, un tas de gens décidèrent d’ignorer Unicode pendant plusieurs années et pendant ce temps les choses empirèrent.

Aussi fut inventé le brillant concept UTF-8. UTF-8 était un autre système pour stocker en mémoire vos chaînes de points de code Unicode, ces nombres U+ magiques, en utilisant des mots de 8 bits. en UTF-8, chaque point de code de 0 à 127 est stocké sur un seul octet. Seuls les points de code à partir de 128 et au delà sont stockés en utilisant 2, 3, en fait jusqu’à 6 octets.

Tout ceci a pour effet de bord très net qu’un texte anglais en UTF-8 ressemble exactement à sa version en ASCII, alors pour les américains il n’y a pas le moindre problème. Seul le reste du monde doit endurer le gage. Pour reprendre notre exemple, Hello, qui était U+0048 U+0065 U+006C U+006C U+006F, sera stocké comme 48 65 6C 6C 6F, ce qui est, le croiriez-vous, exactement comme si c’était stocké en ASCII, et en ANSI, et en n’importe quel jeu de caractères OEM de la planète. Maintenant, si vous êtes assez intrépide pour utiliser des lettres accentuées, ou des lettres grecques, ou des lettres Klingon, vous devrez utiliser plusieurs octets pour stocker un seul point de code, mais les américains ne s’en apercevront jamais. (UTF-8 a aussi cette agréable propriété qu’un vieux code de traitement de chaînes voulant utiliser un octet 0 en tant que null-terminateur ne tronquera pas les chaînes).

Je vous ai déjà indiqué trois façons d’encoder de l’Unicode. Les méthodes traditionnelles « stockez-moi-ça-sur-deux-octets » sont appelées UCS-2 (à cause des deux octets) ou UTF-16 (à cause des 16 bits), et vous devez toujours vous demander si c’est de l’UCS-2 à poids fort derrière [high-endian] ou de l’UCS-2 à poids fort devant [low-endian]. Et puis il y a une autre norme norme UTF-8 qui possède en plus l’agréable propriété d’être respectueuse si vous avez l’heureuse coïncidence de posséder à la fois des textes anglais et des programmes lobotomisés qui ne sont absolument pas au courant qu’il existe autre chose que l’ASCII.

Il y a en fait une poignée d’autres manières d’encoder Unicode. Il y a quelque chose qui s’appelle UTF-7, qui ressemble beaucoup à UTF-8 mais qui garantit que le bit le plus haut est toujours à 0, de manière à ce que si vous devez passer Unicode à travers une sorte de système email totalitaire qui pense que 7 bits c’est bien assez, merci, il pourrait encore se faufiler sain et sauf. Il y a UCS-4, qui stocke chaque point de code en 4 octets, qui a l’agréable propriété que tous les points de code sont stockés sur le même nombre d’octets, mais, bon sang, même un Texan ne serait pas assez intrépide au point de gaspiller autant de mémoire.

Et en fait, à partir du moment où vous vous figurez les choses en terme de lettres platoniciennes idéales représentées par des points de code Unicode, ces points de code Unicode peuvent être encodés dans n’importe quel schéma d’encodage de la vieille école ! Par exemple, vous pourriez encoder la chaîne Unicode pour Hello (U+0048 U+0065 U+006C U+006C U+006F) en ASCII, ou avec le vieil encodage OEM grec, ou avec l’encodage ANSI hébreu, ou avec n’importe lequel des centaines d’encodages déjà inventés, à un détail près : certaines lettres pourraient bien ne pas s’afficher ! S’il n’y a pas d’équivalent pour le point de code Unicode que vous essayer de représenter avec l’encodage que vous utilisez, vous obtenez généralement un petit point d’interrogation: ? ou, si vous êtes vraiment bon, une boîte. Alors, vous obtenez quoi? -> �