Traitement de la langue et structures de données

En attendant les ordinateurs quantiques, l’informatique a peut-être eu son Newton, en tous cas les structures de données et leurs principaux algorithmes sont presque définitivement théorisées depuis les trois premiers volumes de The Art of Computer Programming de Donald Knuth (première édition en 1973). La théorie a pénétré l’enseignement, notamment avec Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms ; mais aussi l’industrie, il suffit de lire le niveau des programmeurs qui se répondent aux questions de performances sur StackOverflow. Si la théorie est complète, il reste pourtant des gisements d’optimisation, dans cette réalité où l’on se salit les mains, ce que des chercheurs en informatique appellent parfois : l’ingénierie. À partir du même système théorique, certains professionnels arrivent à régler plus efficacement les mêmes  problèmes, cela ne s’explique pas par la chance ou le mystère d’un tour de main, la théorie doit manquer des faits. Le traitement de gros corpus textuels s’analyse ainsi en une multitude d’objets avec beaucoup de propriétés, les mots. La difficulté principale du traitement de la langue n’est pas seulement de réduire la complexité computationnelle  (éviter O(n²), tirer O(n) vers O(log n), en espérant O(1)), mais aussi, dans la gestion de la mémoire. Toute la théorie de Knuth est établie sur un langage virtuel proche de l’assembleur, théoriquement irréprochable, mais même dans le déterminisme absolu de la gravitation universelle de Newton, il suffit de 3 planètes de masse équivalente pour produire des situations cahotiques (le problème des 3 corps). Tout utilisateur en fait l’expérience quotidienne sur un ordinateur abordable, avec pourtant les logiciels les mieux débogués, le moment arrive où la machine s’étouffe, où le disque grésille, le clavier gèle ; l’ordinateur range sa maison parce qu’il ne s’y retrouve plus. Après avoir écrit une librairie de traitement du français, Alix, il me semble que le secret de l’efficacité n’est pas seulement mathématique, mais physique, dans la gestion des flux. Cet article décrira quelques structures de données classiques, et d’autres moins documentées, selon leur utilité pour le traitement de la langue. Le texte sera tourné pour essayer d’intéresser tous types d’esprits, certes les programmeurs, mais aussi des linguistes, des littéraires, cet honnête homme introuvable de l’âge classique, ces humanistes dont la qualité est d’être leur nature, c’est-à-dire plus simplement, des curieux.  On disserte beaucoup sur les produits et les effets du Numérique, il est plus rare d’analyser le code qui en est la cause.

Liste de fréquence et table de hachage

cat sade_justine1791.txt | tr " ’,.?!()" "\n\n" | sort | uniq -c | sort -n

Cette célèbre ligne de code illustre la puissance du système UNIX, dès sa version 5 (1973),  et les idées brillantes de Douglas McIlroy (1932–…) et Ken Thompson (1943–…). Ce dernier, à 74 ans, continue à inventer, chez Google avec son vieux comparse Rob Pike (1956–…), ils écrivent le chapitre auquel Knuth a renoncé, la programmation parallèle, en dessinant le langage Go. Mais que fait ce code ?

Ceux qui savent vont sauter le passage, ceux qui ne savent pas ne comprendront pas plus sans avoir manipulé ; le commentaire d’une ligne de programme est un exercice de rhétorique incertain. Il peut pourtant s’inspirer d’ancêtres prestigieux, et notamment, du Ménon. L’intention de Platon n’y est pas d’expliquer les mathématiques, pourtant, il utilise une construction géométrique, le doublement de la surface d’un carré, pour expliquer sa théorie de la compréhension. Certains hacks de programmeurs méritent ainsi de rejoindre la culture commune, pour servir de paradigme à d’autres raisonnements.

Ménon, construire le carré de surface double

La ligne de code ci-dessus donne les mots les plus fréquents de la Justine 1791 de Sade : 5287 de, 2586 la, 2389 que, 2182 et, 2167 le, 2141 à, 1753 il… Rien de bien licencieux, ce ne sont que des mots grammaticaux. Si on fouille plus bas dans la liste, ça ne l’est pas bien plus : dit, Thérèse, homme, monsieur, madame, femme, fille, nature, vertu, crime… Ce texte est un problème intéressant pour le traitement de la langue, parce que tout le monde sait de quoi il parle, et pourtant cela se montre difficilement avec des procédures statistiques élémentaires, contrairement à la Justine 1799, beaucoup plus obsessionnelle puisque dans les 30 premiers mots non grammaticaux on trouve déjà : cul, vit, foutre, fesses… mais ce n’est pas le sujet.

Pour dégager cette liste, la ligne de code utilise plusieurs astuces remarquables. D’abord, les instructions sont chaînées. Ce sont chacune des programmes indépendants, originellement écrits en assembleur, le langage du microprocesseur. L’idée sous UNIX était de proposer des programmes réutilisables, parce qu’ils sont combinables, en branchant la sortie de l’un à l’entrée de l’autre. Le signe qui dit cela est le “pipe”, ‘|’. Cette idée de génie, car cet ingénieur ne manque d’engin, relève moins des mathématiques que de la plomberie. Mais peut-être que l’on manque ici l’origine de plusieurs innovations mathématiques importantes, tenant moins à des conceptions très abstraites, qu’à des notations pratiques, démultipliant les possibilités de la démonstration, en allégeant la conscience par des symboles plus faciles à manier. On pourrait ainsi écrire une histoire informatique des mathématiques, et considérer par exemple, que la géométrie analytique de Descartes, qui ramène la noblesse des figures à l’algèbre des arabes, est un fameux hack permettant à n’importe quel lycéen de calculer des coniques qui torturaient le cerveau des classiques. Le programmeur est une sorte de pédagogue pour intelligences très limitées, les ordinateurs, il cherche les rares formulations que ses élèves peuvent comprendre.

cat commence par lire le texte et envoie le flux à la suite du process. tr (translittérer), remplace des lettres une à une. La syntaxe est astucieuse, et l’on devine comment le programmeur à imaginé un aspect élégant de l’instruction. Les deux arguments obligatoires sont des chaînes de caractères. Dans la Justine qui entre, toutes les occurrences du premier caractère du premier argument seront remplacées par le premier caractère du second argument, et ainsi de suite pour les suivants. Ainsi, toutes les espaces seront remplacées par des sauts de ligne (\n, c’est un code inévitable, peu importe ici). L’objectif est de diviser les mots en les sortant à un par ligne. Le deuxième caractère est l’apostrophe, qui aussi remplacée par un saut de ligne (même dans prud’homme). Avec un tel contrat, un programmeur normalement formé va automatiquement se demander, que faut-il faire si les arguments sont de tailles inégales ? L’attitude bête est de lancer une erreur, l’intelligence est d’en faire de l’expression. Pour tr, tous les caractères du premier argument auquel il ne correspond rien dans le deuxième argument, sont remplacés : par rien. Dans le programme de tr, cela coûte très peu de lignes, et pour son utilisateur, cela ouvre à des élégances d’écriture, qui sont comme des gestes professionnels rodés par l’usage. Ici, les caractères suivants sont les ponctuations simples du français, collées aux mots, qui sont ainsi supprimées. À ce stade du programme, à peu près tous les mots du textes sont séparés et placés sur une ligne différente. Le texte est devenu un long tableau d’une seule colonne de mots, dans l’ordre du texte.

Par cette astuce, un texte est devenu une donnée tabulaire, ce qui permet d’employer un autre jeu d’instructions. La suite se joue autour de uniq. Ce programme boucle sur toutes les lignes de son entrée pour en traiter les doublons. Il peut les supprimer, les signaler, ou ici, il en donne le compte. Soit par exemple cette série en entrée (un, un, un, de, de, de, de, un), uniq -c en sort la série (3 un, 4 de, 1 un). Le programme a juste compté les mots identiques qui se suivent, mais il ne fait pas attention s’ils reviennent plus tard. C’est insatisfaisant pour nous, mais la fonction reste ainsi élémentaire, et très efficace. Quand les mots sortent du tr, ils sont dans l’ordre du texte (un, chien, est, un, chien), le premier sort les met en ordre alphabétique (chien, chien, est, un, un), produisant sac de mots ayant perdu toute syntaxe mais au format attendu par uniq : (2 chien, 1 est, 2 un). Il suffit ensuite de trier la liste sur la première colonne, portant le nombre, et on obtient les mots les plus fréquents (1 est, 2 chien, 2 un), et nous obtenons la classique liste de fréquences, avec les mots les plus nombreux, à la fin.

Le programme sort a bonne réputation, il implémente l’algorithme tri fusion (merge sort) de John von Neumann (1945), illustration du principe diviser pour régner (divide and conquer, D&C) 1. diviser le problème, 2. régner = résoudre les sous-problèmes, 3. combiner les solutions. Le problème d’un tri est de diminuer le nombre de tests entre éléments, c’est sur cette opération que la complexité computationnelle est évaluée. Dans le pire des cas, sur une liste de n éléments, on imagine que chacun serait comparé à tous les autres, ce qui donne un degré de complexité O(n²), augmentant de plus en plus vite le temps de traitement au fur et à mesure que la liste augmente. Merge sort est réputé avoir une complexité  O(n  log n), c’est à dire qui progresse un peu plus vite que le nombre d’éléments, mais pas trop. Cette performance s’obtient en commençant par diviser la liste en éléments uniques, qui sont en un sens des sous-listes nécessairement en ordre, puisqu’elles n’ont qu’un élément, puis de fusionner ces listes deux à deux, en établissant un ordre commun. En effet, deux listes pré-triées diminuent largement le nombre d’opérations pour bien les ranger. Soit par exemple ces deux séries de 4 éléments : A=(2, 4, 7, 8), B=(1, 3, 5, 6). Pour les ranger en ordre, il faut un casier avec 8 emplacements prédéfinis C=(_, _, _, _, _, _, _, _). Le premier emplacement, C1, sera nécessairement A1 ou B1, inutile d’aller chercher plus loin dans les sous-séries, puisqu’elles sont rangées. Il suffit de munir les séries d’un compteur pour continuer les tests, B1 < A1, donc C1 = B1, au tour suivant pour affecter C2, on comparera A1 et B2, et ainsi de suite. On retrouve le même type d’opération élémentaire à bas coût que dans uniq. C’est brillant, mais quand l’application commence, les problèmes arrivent et la satisfaction intellectuelle est frustrée.

Sur une machine normale de 2017, tr ou uniq prennent environ 70 ms pour traiter Justine (~700 Ko), ils sont de complexité O(n), mais sort, théoriquement assez performant, O(n log n), prend 1 500 ms. La notation O rend compte des tests, beaucoup de la copie et la circulation de données. Pour un corpus 100 fois plus gros, par exemple l’année 1938 du journal La Croix (~71 Mo), tr passe à 6 410 ms, et sort prend 200 000 ms,  3’21”, et il y aurait 63 autres année à traiter (1880 à 1944). Faut-il attendre des heures, acheter un gros serveur ? En observant mieux le comportement de sort, on découvre qu’il écrit continuellement sur le disque, ce qui diminue son empreinte dans la mémoire vive, mais l’expose aux lenteurs de la mécanique. En effet, ce programme est célèbre parce qu’il supportait des entrées massives, dépassant la mémoire de l’ordinateur, pour par exemple trier des bandes magnétiques. Cette commande s’en sortira toujours, mais peut-être pas au meilleur prix.

Relier les 9 points avec une ligne brisée de 4 segments. Solution géométrique, solution physique.

 

Ce programme UNIX pour sortir les mots les plus fréquents d’un fichier texte est élégant, à base d’algorithmes efficaces, mais il n’est pas scalable, il monte mal en puissance. Plusieurs stratégies viennent à l’esprit. On peut reprogrammer le sort pour qu’il traite tout en mémoire, mais on risque tout de même de frapper les limites de la machine. On pourrait alors adopter une stratégie de conquête par la division, la clé résidant dans l’algorithme de fusion entre les listes de fréquences. Soient deux textes A et B, on peut en tirer deux tables, A : (10 à, 8 de, 3 je, 8 un), et B : (55 à, 44 de, 25 il, 39 un). Si A et B sont triées dans l’ordre des mots, il suffit d’avancer sur l’un et l’autre, comme dans la fusion du merge sort, pour produire une liste fusionnée qui additionne les effectifs pour chaque entrée (complexité O(n)).

Mais ces approches restent bloquées dans l’idée initiale de trier toutes les occurrences, or, en quoi est-ce nécessaire pour l’objectif final ? Il est beaucoup plus économique de viser directement le résultat, un dictionnaire de mots comportant chacun un compteur. La machine à compter se résumerait à faire circuler le texte mot à mot, à ajouter les mots nouveaux au dictionnaire, ou à incrémenter une entrée existante. Le problème, en ce cas, est de retrouver rapidement un mot dans une liste.

Dans une liste en désordre, s’assurer qu’un item est absent force à tester tous les éléments, c’est une opération O(n), à répéter pour chaque occurrence. Cela risque de ne pas être efficace, même si la liste des formes différentes est moins longue que toutes leurs occurrences dans un texte. Pour gagner du temps, les dictionnaires sont en ordre alphabétique, on les ouvre un peu au milieu et on regarde si le mot cherché est avant ou après, progressant par tâtonnements et dichotomies. Les enfants connaissent cet algorithme avec le jeu devine un nombre. Entre 0 et 9, il suffit au maximum de 4 tests répondant par égal, supérieur ou inférieur pour trouver n’importe quel des chiffres, ainsi pour trouver  8, on teste d’abord 5 (inférieur), puis 7 (inférieur), puis 9 (supérieur), donc 8 (égal). Entre 0 et 999, le nombre de tests n’est pas multiplié par 100, il en faut 10, par exemple pour retrouver 0 : 500, 250, 125, 62, 31, 15, 7, 3, 1, 0. On arrive à une complexité O(log n). C’est pas mal, il y a mieux.

Hans Peter Luhn (1896–1964), travaillant sur la recherche d’information et l’indexation plein-texte chez IBM, est généralement crédité pour les fonctions de hachage (1953). Cette trouvaille, inspirée de la cryptographie, permet de retrouver rapidement un objet dans une liste, que ce soit pour nous un mot, mais aussi un chiffre, les noms de domaines sur Internet, ou bien tous les objets d’un programme pour un compilateur, à un coût constant O(1), quelle que soit la taille du dictionnaire. Pour un élément en entrée, la fonction calcule un nombre, pas nécessairement unique pour chaque élément, mais qui est réparti de manière à peu près homogène. Pour de la cryptographie, c’est un échec, le message est encodé, mais il se confond avec d’autres ; pour les structures de données, le facteur intéressant est la répartition homogène. Un exemple réel va aider. Soient 100 000 notices de bibliothèque, avec une cote sur 8 chiffres, qui va de 30 000 056, à 44 332 854. Comment faire 1 000 paquets pas trop inégaux ? On ne sait pas trop ce qui préside à la distribution des préfixes (entre 300 et 443), par contre, prendre les trois derniers chiffres, entre 000 et 999, s’avère une fonction très rapide à calculer, parfaitement déterministe, qui répartit très bien la collection (entre 80 et 120 items par paquets). On voit tout de suite que cela diminue le nombre de tests, il suffit d’aller chercher dans chaque paquet, qui sera gardé en ordre. Mais cela épargne un autre coût, le maintien de l’ordre. Le point n’a pas été abordé plus haut, mais lorsque l’on doit par exemple insérer des noms de personnes dans une liste sans en savoir à l’avance le nombre, il faut régulièrement recopier la liste après chaque insertion. On peut essayer de garder des espaces, des signets, par exemple prendre un répertoire alphabétique, mais il se trouve toujours des pages trop pleines, et d’autres très vides. Une bonne fonction de hachage diminue non seulement le temps de recherche, mais aussi celui d’insertion, parce que l’on peut prévoir à l’avance l’espace de chaque paquet, puisque la répartition sera homogène. Pour des mots, une fonction de hachage pourrait dire que c’est comme des nombres dont les chiffres seraient le code des lettres. Les fonctions de hachage qui s’appuient sur les préfixes ou les suffixes n’ont pas une répartition homogène, par exemple beaucoup plus de mots commencent par d que par z ; de même beaucoup finissent en ment. Dans son chapitre sur le hachage (TAOCP, vol. 3, 6.4, p. 513), Knuth a posé les bases mathématiques pour évaluer une fonction de hachage, mais même après la seconde édition (1998), il se garde de proposer une solution définitive. Plus de 40 ans après Luhn, le langage Java, déployé sur plus de 5 milliards de machines, n’a plus changé sa fonction String.hashCode() depuis sa version 1.2 (1998). L’efficacité n’est pas mathématiquement prouvée, mais elle semble expérimentalement stabilisée. Il n’y a aucune raison linguistique, mais cela fonctionne, c’est une boucle qui ajoute le code de chaque caractère à un total multiplié par 31. Il ne suffit pas d’inventer le principe du moteur à explosion pour trouver la meilleure forme de vilebrequin, mais en effet, le Hash est peut-être bien le moteur de la civilisation des données.

Le langage Java est le plus propre à examiner les structures de données classiques ; car d’une part il en propose d’excellentes, pensées par les meilleurs programmeurs, contrairement au langage C où il ne se dégage pas de standards ; et d’autres part, il en propose  plusieurs, dans un système articulé et documenté, contrairement aux langages moins typés, comme Perl, PHP, Python ou Javascript. L’expérience acquise par les auteurs du langage Java depuis plus de 20 ans permet d’avoir du recul et de considérer qu’il s’agit d’un bon état de l’art. J’ai passé du temps à chercher d’autres structures plus efficaces pour des mots. J’ai implémenté une table hachage (HashMap), spécialisée pour des nombres entiers, un peu plus rapide, afin de stocker des vecteurs, mais rien qui imposerait que cela intègre le langage et lui fasse perdre sa cohérence. J’ai essayé de stocker les mots dans un réseau, comme un chemin à travers l’alphabet, je n’ai réussi qu’à être 5 à 10 fois plus lent qu’un Hash, et généralement plus compliqué. Ces errements ne furent pas inutiles, ils serviront plus bas,  mais ils m’ont convaincu que dans l’état actuel de l’informatique, rien ne semble plus efficace que l’implémentation native d’un HashMap dans son langage préféré, pour stocker le dictionnaire des quelques centaines de milliers de formes d’une langue.

En résumé, ne triez jamais, supportez le désordre le plus longtemps possible. Il reste pourtant une tâche attendue de la liste de fréquence qui n’est pas remplie par un Hash, il ne donne pas les mots avec le plus gros effectif. Mais est-il bien nécessaire de tout trier si on ne veut que les 20 premiers ? La tâche semble utile, je n’ai pas trouvé d’objet d’usage un peu général, les manuels d’algorithmie s’attardant plus souvent sur les recherches de minimum, maximum, ou médiane (pour les statistiques). Si un TopN est couplé à un Hash qui ne conserve aucune information de classement, il faut avoir lu au moins une fois toutes ses entrées pour en extraire les 20 premières, la complexité O(n) semble difficilement évitable, mais cela ne se fait plus qu’une fois, à la fin, le temps passé ici à optimiser n’apporterait pas beaucoup aux performances du programme.

Locutions et gestion de la mémoire

La ligne de commande plus haut relève d’une représentation de la langue assez élémentaire. Les mots sont séparés d’espaces, la ponctuation est nettoyée, les majuscules ne sont pas interprétées, l’apostrophe est toujours coupée, et le trait d’union ne l’est jamais. Il faut en réalité un automate plus subtil. Soit par exemple l’expression « N’est-ce pas ? ». En un premier temps, on voudrait au moins la suite suivante de termes  (N’=ne, est, ce, pas, ?). Notons d’abord que l’automate devra traiter les caractères un à la fois, pour réagir intelligemment à la ponctuation, aux tirets et aux apostrophes, ou aux majuscules. On peut aussi se demander si n’est-ce pas n’est pas une expression figée, comme parce que, ou même chemin de fer d’intérêt local (4 occurrences dans À la Recherche du temps perdu). L’informatique étant d’abord logique avant d’être statistique, il n’est pas simple de quantifier un degré de figement, mais il y a une définition opérationnelle à peu près convenable d’une locution : suite de termes pouvant avoir la nature d’un mot. Autrement dit, en ordre de fécondité, on aura des locutions fonctionnant comme des conjonctions, des prépositions, des adjectifs, des adverbes, des verbes, ou des noms. Les dictionnaires de locutions sont impossibles à finir, mais il suffit de quelques milliers d’entrées pour évacuer les cas les plus massifs d’équivoque, par exemple la préposition au milieu de, que même Claude Bernard peut employer,  « quelques morceaux de viande au milieu d‘une masse demi-liquide et pultacée », alors qu’il donne un sens conceptuel très fort au substantif milieu : « il y a en physiologie deux milieux à considérer : le milieu macrocosmique, général ou extérieur, et le milieu microcosmique, particulier à l’être vivant, organique et intérieur ». Le problème semble pourvoir se résoudre avec des Hashs, mais très vite, la gestion de la mémoire vient brouiller les espérances.

#!/usr/bin/python
texte = ""
while i < 1000000 :
    provisoire = texte
    texte = provisoire+" "
    i += 1

Ce programme, en langage Python, ne fait rien de très intéressant, il construit un texte d’un million d’espaces, en les ajoutant un à un (un gros roman pèse à peu près 1 million de caractères). Puisque l’analyse linguistique d’un texte se fait caractère par caractère, il est important d’assurer la boucle avant d’y greffer des tests. Si un chronomètre est glissé, par exemple tous les 10 000 caractères, l’opération, qui a l’air élémentaire, devient de plus en plus longue. Les programmeurs auront remarqué une écriture un peu étrange, le texte qui grossit est d’abord affecté à la variable provisoire, qui sert ensuite à la concaténation. La même boucle, avec une expression qui ne passe plus par une variable provisoire « texte = texte + “ ” », sera dès le début 10 fois plus rapide, et ne deviendra pas plus lente. Ce problème de la concaténation des chaînes est constaté dans la plupart des langages qui délèguent la gestion de la mémoire à un ramasse-miettes (garbage collector). Un tel cas semble contradictoire avec l’apparence O(n) de l’écriture, et le temps O(n²) constaté. Il faut rappeler que Knuth écrit toutes ses démonstrations-programmes dans le langage d’un processeur théorique, MIX, dont les interactions avec registres, mémoire vive et mémoire de masse, sont entièrement explicites et contrôlées ; c’était l’expérience des programmeurs dans les années 1960. Aujourd’hui, les programmes s’écrivent dans des langages plus évolués, l’écriture masque la machine de Turing que tout ordinateur n’a pas cessé d’être. Une chaîne de caractères est une séquence d’octets, quelque part dans la mémoire. Le programme, et le système dans lequel il s’exécute, doivent savoir où la chaîne commence, où elle finit, pour éviter qu’un autre programme viennent l’effacer. Ce texte qui commence vide, le programme ne dit pas à l’avance qu’il va comporter un million de caractères, alors l’exécution doit pallier à l’implicite, en promenant le texte dans la mémoire,  pour s’assurer d’avoir toujours de la place pour le nouveau caractère. L’apparente complexité O(n) de l’algorithme cache en réalité les opérations de recopie du texte qui grossit, produisant une croissance O(n²) qui deviendrait vite étouffante. Mais alors, pourquoi l’écriture « texte = texte + “ ” » reste en O(n) ? C’est une courtoisie du moteur Python, apparue avec la version 2.5 (2005), 15 ans après la première version du langage. Face aux pratiques réelles des utilisateurs, surpris par le décalage entre la simplicité de ce qu’ils écrivaient et les performances constatées, Python, comme PHP, ont traité différemment les chaînes de caractères qui sont destinées à grossir. Java a tout de suite alerté ses utilisateurs, dès le JDK1.0, en offrant l’objet StringBuffer. Le principe est d’ouvrir une chaîne mutable, qui d’avance prévoit un peu plus de place que sa taille initiale, et qui augmente au fur et à mesure de la demande, en se donnant toujours un peu de large, comme quand on donne du mou à la laisse de son chien. Une String s’ajuste bien à un mot dans un dictionnaire, dont l’orthographe ne changera pas au cours de l’exécution du programme, mais pour des chaînes transitoires, comme par exemple le moteur qui cherche les locutions, il vaut mieux penser avec des chaînes mutables, comme StringBuffer. Le langage Python est très prisé des linguistes, mais en ne présentant pas explicitement cette distinction entre deux types de chaînes, il expose le traitement de gros corpus à des déconvenues. La seule solution, c’est d’avoir compris le problème dans un langage plus exigeant, comme C ou Java, ce qui revient à ne plus écrire ce que l’on pense. Peut-être est-ce une nécessité de toute écriture, que chaque mot soit informé d’une langue ancienne, dont les résonances augmente l’effet du texte.

Cette expérience critique, au sens classique de discriminante, ne réfute pas l’algorithmie classique, mais y ajoute de prévoir l’effet des instructions malloc() en C, de new en Java, ou de deviner le bytecode exécuté sous un programme Python ou PHP. L’efficacité s’obtient en prévoyant le plus possible à l’avance les cases mémoire dont un traitement a besoin, en limitant l’allocation dynamique. Pour analyser un texte, on conseillera désormais de le placer entièrement en mémoire, dans une seule variable. Un texte étant une donnée humaine, il y a des distances prévisibles, comme les livres, les dossiers, qui évitent des surprises dépassant la mémoire des ordinateurs actuels (contrairement à des données physique, comme par exemple de l’observation spatiale). Sur cette chaîne de caractères, le programme d’analyse doit se comporter comme une sorte de machine de Turing qui ne fait pas de copeaux, pas un rabot mais une glissière de fermeture éclair. Dans le principe le plus pur, la glissière est une chaîne mutable qui enregistre un mot caractère par caractère, s’arrêtant à la rencontre d’une espace ou d’une virgule, et redémarrant une fois que le mot a été envoyé aux traitements suivants. Il est critique ici de ne pas produire une nouvelle chaîne pour chaque mot.

Cet automate dédié à une langue et un alphabet sera toujours plus efficace que les machines précompilées, comme les expressions régulières. On peut en effet y glisser plusieurs optimisations, notamment pour tester le type des caractères (majuscules et minuscules, espaces, ponctuations…).  L’Unicode propose un code unique pour la plupart des caractères qui s’impriment, le français, comme le grec ou le chinois peuvent se coder sur 2 octets, de 0 à 65535 (216). Les caractères sont rangés en plusieurs classes, comme lettres majuscules, espaces, ponctuations, mais les blocs ne sont pas contigus, et parfois mélangés, pour des raisons historiques. L’alphabet latin sans accents se place entre 64 et 127, mais il comporte aussi la ponctuation des téléscripteurs, comme les crochets ou les accolades. Dans le bloc suivant, dit Latin-1, de 128 à 255, on trouvera à peu près toutes les lettres nécessaires au français, par exemple le ‘æ’, mais pas le ‘œ’, qu’il faut chercher au milieu des lettres spécifiques du hongrois, et il faut courir jusque 8192 pour trouver les tirets quadratins. Une fonction qui donne la classe d’un caractère selon son code demandera plusieurs tests. On pourrait imaginer un Hash limité aux seuls caractères prévisibles d’une langue, il est encore plus rapide d’alimenter un long tableau de 65536 cases, qui pour chaque position de l’Unicode donne des traits utiles au traitement linguistique. En effet, l’accès à ce tableau est quasiment une opération unitaire du microprocesseur, lecture d’une case mémoire à partir de son adresse. Un esprit précis remarquera que dans 65K cases, beaucoup ne sont pas utiles pour le français. En effet, mais qu’est-ce que 65Ko quand la mémoire moyenne d’un ordinateur est presque 100 000 fois plus grande (4Go) ? Le temps gagné vaut largement la mémoire perdue, cet objet est 500 fois plus rapide que le code natif de Java, Character.isLetter( char c ), il permet aussi de préciser des classes non prévues par l’Unicode, comme voyelle et consonnes (pour la prosodie), ou ponctuation de phrase (., ?, !, …). Ce hack illustre ce que sont les bonnes et les fausses économies, l’informatique est une école de gestion. Un tel dispositif se comprend bien en C, même si l’Unicode n’y est pas natif ; mais en PHP, les tableaux sont trop lourds, comme les listes par défaut de Python (mais il est possible de contourner cette limitation du langage avec la librairie array). Le traitement du texte a besoin de l’algorithme le plus rapide possible pour tester chaque caractères un à un, et réagir aux débuts et fins de mots.

Donc, notre glissière courre sur les caractères du texte, pour alimenter une chaîne mutable. Ce procédé est suffisant pour compter les formes dans leurs flexions, par exemple les verbes conjugués, mais on pourrait souhaiter compter d’autres choses, par exemple, les lemmes, pour avoir les verbes à l’infinitif, ou les catégories morphosyntaxiques. On a vu qu’un HashMap pouvait contenir tout le dictionnaire d’une langue, avec pour clé la forme telle que rencontrée dans le texte, et pour valeurs, différentes colonnes comme lemme, catégorie, et pourquoi pas : une fréquence, une version phonétique, une analyse morphologique, ou des traits sémantiques. La limite n’est pas le modèle informatique mais les données fiables que l’on peut mobiliser pour tout le lexique. Reste un point ici qui pourrait faire revenir beaucoup de copeaux. Il est de bonne pratique que la clé d’un Hash ne soit pas mutable. En effet, on ne retrouve pas un mot dans un dictionnaire où l’orthographe change, comme si les lettres d’un Larousse partaient se promener ou s’effaçaient. Donc, en Java en tous cas, il vaut mieux que la clé de HashMap soit une String, qui possède sa fonction de hachage, sa méthode de comparaison pour retrouver un élément dans un casier ordonné, et sa méthode d’égalité. Malheureusement, les chaînes mutables natives en Java (StringBuffer ou StringBuilder) n’ont pas ces méthodes, les auteurs du langage n’ont pas prévu notre besoin, et ont certainement pensé à diviser clairement les contrats, pour se faire comprendre de leurs utilisateurs, et éviter qu’un stagiaire casse tout un développement industriel parce qu’il a trouvé une super astuce. Cependant, par une chance non documentée, les concepteurs de Java n’ont pas imposé une parfaite homologie entre l’objet utilisé pour la clé dans le HashMap, et celui que l’on peut utiliser pour tester si la clé existe ; tout est dans le contrat très ouvert de la méthode HashMap.containsKey( Object key ), qui accepte n’importe quel objet. De plus, les tests ne sont pas effectués par la clé contenue dans le HashMap, ici String, mais par l’objet du testeur. Pour l’usage le plus naturel, entre deux String, cela ne fait aucune différence, mais pour nous, cela permet d’écrire une classe de chaîne mutable compatible avec String, évitant de recréer un langage parallèle. Je ne sais pas si cela résulte d’autres contraintes,  si au moment de faire ce choix, un auteur très expérimenté a anticipé ce besoin. En ce cas, voilà une leçon de morale professionnelle, soyez consciencieux, même dans les détails que personne ne voit, quelqu’un vous remerciera. Ainsi, la glissière empile les caractères d’un mot dans un chaîne mutable, et sans excès de recopies en mémoire. La recherche de ce mot en formation dans le Hash du dictionnaire reste à coût O(1), pour ramener différentes informations lexicales.

Ce programme permet de faire un lemmatiseur honorable, notamment parce qu’avec une information de fréquence obtenue sur un corpus lemmatisé (merci lexique.org) on peut choisir un lemme plausible pour des homographes. Soit par exemple la forme est, cela peut être le point cardinal, ou une conjugaison du verbe être. Ce lemmatiseur statistique décidera que ce sera toujours le verbe être, car c’est la solution la plus fréquente, même s’il y a quelques erreurs. D’autres logiciels utilisent cette approche, notamment IRaMuTeQ, elle est rapide, et au final, pas beaucoup moins précise qu’un classique gratuit, beaucoup plus intelligent, plus lent, comme TreeTagger. Cette approche par dictionnaires a un autre avantage, contrairement à un apprentissage machine sur corpus, les erreurs sont prévisibles, et donc plus faciles à corriger. Cette entrée est largement suffisante pour résoudre le problème initial de cette section, les locutions.

Un dictionnaire de locutions pourrait être stocké dans un seul Hash,  à la réserve que les mots arrivant un à un depuis le texte, il faudrait en tester plusieurs, 2 pour trouver parce que , jusque 6 pour chemin de fer d’intérêt local. À chaque occurrence, cela ferait obligatoirement 5 tests. Cela ne semble pas efficace, d’autant qu’il y aura un coût mémoire pour agréger les différents candidats à retrouver dans le dictionnaire. Des statistiques en corpus montrent rapidement que les locutions commencent souvent par les mêmes mots, et qu’une grande partie des mots ont très peu de chances de démarrer une locution. Il faudrait donc le dictionnaire de tous les premiers mots des locutions, et un seul test suffit à éliminer la plupart des cas. En programmation, on gagne à sortir le plus vite possible, « ce qui est fait, est fait, et n’est plus à faire ». Mais que faire lorsque l’on sait qu’un mot peut commencer une citation ? Afin de ne pas créer inutilement d’objets, le dictionnaire des locutions peut être stocké comme un réseau de mots. Soit le nœud à dans un Hash à la racine, la préposition peut introduire plusieurs locutions comme à cet égard, à cause de, ou à travers. Au nœud à correspond un autre Hash avec tous les deuxièmes mots des locutions en à, comme partir, pour à partir de, et à partir de là. Une boucle et quelques tests suffisent à trouver la locution la plus longue. Cette structure n’est pas standard dans les langages, elle est connue dans  la littérature comme Trie depuis 1959 (René de la Briandais). L’implémenter soi-même permet de coller au plus proche de la donnée source, que tout s’engrène sans user les dents ou réclamer trop de graisse.

Terminons par une structure de données un peu plus exotique, une cyclic double linked list (double liste chaînée cyclique) qui sert de pignon de sortie au lemmatiseur. Le principe est d’avoir autant de places que le nombre de mots de la plus longue locution, pour aller en exploration avant, plus un peu de réserve. Le texte étant une chaîne, les places sont chaînées. Un pointeur donne le mot courant, mais ne revient jamais en arrière, on peut juste avancer dans le texte. Quand un mot est passé, pour ne pas recréer de nouveaux objets, son emplacement est remis en tête de chaîne, dans une pioche de places disponibles, d’où l’idée de cycle. Si une locution est trouvée, elle est ramenée en entier à la position de son premier mot, qui est raccroché à la position du mot juste après la locution, les positions intermédiaires repartant à l’avant dans la pioche.  Il n’y a rien de renversant pour la théorie informatique, mais cela illustre que savoir ses gammes aide à trouver la forme la plus juste pour son problème, en sortant des design patterns et autres commandements industriels du bien programmer.

Conclusion

Quelques amis bienveillants ont trouvé ce texte parfois dur à suivre. Que le lecteur soit assuré que je n’ai jamais cherché à l’impressionner avec des abstractions, cela témoigne juste de ce que devient un cerveau moyen qui fréquente trop la machine. Ce billet n’est pas un cours, mais un témoignage, une histoire qui s’est vraiment passée, même si les péripéties ne sont pas toujours palpitantes. En tous cas, ça fonctionne dans un programme (la librairie Alix). Plusieurs m’ont dit que cela gagnerait à être plus illustré. Il se trouve beaucoup de schémas pour expliquer les structures de données, mais ils sont toujours orientés vers la pédagogie d’un objet figé. Ce serait un défi de rhétorique visuelle de pouvoir, non pas seulement décrire les hacks, mais les rendre vivants, inspirants. Il est probable que si je retrouve un cours d’informatique, cette page sera plus illustrée. J’en retiens en tous cas que l’enseignement de la programmation doit continuer à revenir aux fondamentaux des structures de données, et de leurs algorithmes, et que le traitement de la langue offre une classe de problèmes presque jamais abordés dans les classiques de l’informatique,  plus souvent écrits par et pour des informaticiens. J’ai désormais posé, au moins pour moi, que la complexité computationnelle, O(n²…1), n’est pas le seul critère de l’optimisation. Il faudrait concevoir un programme comme un organisme qui n’a pas seulement la complexité de son milieu intérieur, mais aussi un environnement avec lequel optimiser les échanges, en diminuant notamment, les appels au disque et l’allocation de mémoire ; et enfin, cela devient un objet social, qui communique avec d’autres programmes, qui ne sont plus seulement maîtres ou serviteurs, fournisseurs ou clients, mais aussi, depuis le parallélisme, collègues ; au service des intérêts humains. Au coût actuel du Giga octets et avec les langages concurrents comme Java et Go, il faudrait faire évoluer le cadre conceptuel. Je n’ai pas le modèle théorique de ma pratique. J’espère en tous cas que ce billet contribue à populariser la culture informatique en communiquant la certitude que l’ordinateur logique a des lois aussi inflexibles que la résistance des matériaux ou la mécanique des fluides, et qu’un programme mal fait ne se paie pas seulement en énervement de l’utilisateur, mais aussi en électricité, et en réchauffement de la planète. L’efficacité algorithmique est un commandement écologique.


Frédéric Glorieux

Ingénieur informatique

More Posts - Twitter - Flickr

Publié par

Frédéric Glorieux

Ingénieur informatique

3 réflexions au sujet de « Traitement de la langue et structures de données »

  1. À propose de « Cette idée de génie, car cet ingénieur ne manque d’engin, relève moins des mathématiques que de la plomberie. »,
    probablement oui que cette solution s’est imposée par la pratique plus que par la théorie, du simple constat de l’importance et de la flexibilité de composer des petits programmes réutilisables pour faire émerger des programmes puissants et fiables.
    En tout cas on peut au moins observer à postériori que les pipelines de processus Unix forment une catégorie, c’est à dire l’objet mathématique permettant la composition par excellence. Confère https://arxiv.org/pdf/1405.3073.pdf

    L’un des langages en vogue qui exploite le plus la théorie des catégories est Haskell, il est d’ailleurs carrément fondé sur la catégorie de la composition des fonctions via un lambda calcul (aka. programmation fonctionnelle) plutôt que sur la machine de Turing (aka. programmation impérative) comme Oracle/Java. Incidemment Haskell fut en 2001 remplacé par Sun/Java à l’Université du Texas, ce qui fit écrire à Edsger W. Dijkstra une de ses nombreuses lettres qui résonnent encore fortement de nos jours : http://chrisdone.com/posts/dijkstra-haskell-java et qui se termine par ces mots : « It is not only the violin that shapes the violinist, we are all shaped by the tools we train ourselves to use, and in this respect programming languages have a devious influence: they shape our thinking habits. »

    Haskell n’est pas exempt de barrières techniques notamment celles pour « deviner ce qui se compile sous un programme »,
    mais ce langage facilite énormément l’expressivité et la reconnaissance par autrui des structures mathématiques omnipotentes pour favoriser la composition des programmes. Notamment la composition de ceux écrits par une multitude de personnes indépendantes (aka. bibliothèques ou libraries). Par exemple les fonctions sans état, les fonctions avec effets de bord sur le système (IO), la fusion associative (Monoid), les containers (Functor), les contextes statiques (Applicative), les contextes dynamiques (Monad), et autres lieux communs de notre inconscient mathématique. Ce que les autres langages en vogue peuvent parfois permettre mais moins consciemment et beaucoup plus difficilement.

    Tout cela se ressent positivement en termes de fiabilité et de maintenance, surtout couplé à un système de typage qui écarte de nombreux programmes invalides.

    1. Merci pour votre réflexion.

      Pardon pour cette boutade sur l’engin, je l’ai pris dans le sens médiéval http://cnrtl.fr/definition/dmf/engin?idf=dmfXhgYrmXart.revusYenXha;str=0

      Mon métier du document m’amène à pratiquer un langage fonctionnel avec assiduité, XSLT, que j’ai enseigné souvent, et qui en effet perturbe les gens qui ont appris à programmer en impératif. Je ne pratique pas Haskell, mais vous me donnez envie de me mettre à un langage fonctionnel.

      Je suis entièrement d’accord avec vous, un langage donne des limites de ce que l’on croit possible. Si j’étais doué pour ça, je rêverais de penser dans plusieurs langues humaines. De ce que je comprends de l’assembleur (que je peux lire mais n’écrit plus), le paradigme fonctionnel n’est pas opposé à l’efficacité. Un processeur ressemble à une machine de Turing, certes, avec un nombre fini de registres, des opérateurs logiques et la ligne de la RAM, mais ce qu’il exécute n’a pas besoin de lui ressembler. On fait bien traiter du signal analogique à un ordinateur, ce qui serait passé pour contre-emploi absurde pour des électroniciens du passé (qui certes ne prévoyaient les vitesses de traitement d’aujourd’hui).

      Pour les mois prochains, je médite un billet sur le traitement informatique de la temporalité dans la langue. Je vois le problème, pas la solution. Il y a une longue tradition de statistiques lexicales, mais le modèle est inadapté, les mots ne sont pas une population qui vaquent à leurs opinions, un texte est une chaîne. Pratiquer un langage fonctionnel pourrait m’ouvrir à d’autres manières de réfléchir. Des raisons m’invitent à m’intéresser à Scala, est-ce déconseillé ?

  2. Malheureusement, je ne parle pas le Scala, je sais juste que comme OCaml il n’est pas exclusivement fonctionnel mais également impératif (contrairement à Haskell, qui techniquement n’a d’ailleurs pas eu le choix, puisque utilisant par défaut l’évaluation paresseusse des arguments des fonctions). Cependant, ayant beaucoup pratiqué OCaml je n’apprécie plus du tout la possibilité de faire de l’impératif, c’est-à-dire de pouvoir écrire une fonction dont la valeur ne dépend pas uniquement de ses arguments. Certes, pouvoir ainsi aller tout modifier depuis n’importe où peut en première analyse faciliter l’écriture sans se prendre la tête à calculer qui a besoin de quoi, surtout de petits programmes, mais dès que le programme sert à en faire des plus gros, l’effort cognitif pour maîtriser la complexité devient ingérable. Or de même qu’il est préférable de ne pas construire sa maison avec les mêmes matériaux que ceux de la cabane du potager, de même les paradigmes séduisants à petite échelle, peuvent l’être beaucoup moins à grande échelle… Et je ne parle même pas ici de l’échelle de l’exécution parallèle ou concurrente… Dès qu’on ne garde pas la complexité dans des proportions mesurées, la dette technique n’est pas loin…
    Surtout que nous autres mortel·les sommes plus souvent des cerveaux paresseux et faillibles que des génies mécaniques et omniscients… Du coup, j’apprécie fortement d’utiliser des langages (voire des sous-langages type DSL (Domain-Specific Language) ou Embedded DSL) davantage exigeants pour l’humain mais parce que davantage analysables par la machine, tout simplement pour nous protéger de nous mêmes — de nos erreurs les plus probables, tout en étant juste assez expressifs pour répondre à nos besoins.

    Pour générer des documents, j’utilise aussi principalement du XSLT (après être passé par les usuels MarkDown, CMark et AsciiDoc, qui pour des gros documents exigeants ne sont à mon avis pas aussi flexibles, ergonomiques et outillés que du bon vieux XML), surtout que Firefox ou Chromium compilent le XSLT-1.0 à la volée, ce qui rend les documents presque aussi facile à bidouiller que du Javascript. Mais à mon humble avis le XSLT manque d’un sérieux système de typage, en plus de nous imposer une syntaxe qui pique les yeux (avec beaucoup plus de bruit que de signal). Mon expérience personnelle avec, commence par l’utilisation de DocBook pour customiser AsciiDoc, puis de DocBook seul, et puis au final d’en venir à réécrire de fond en comble un autre outil en XSLT parce que sans système de typage la complexité écrasante de DocBook me dépassait, et donc je préfèrais avoir tout en tête de zéro… Et même comme ça, quand je replonge dans mon propre code quelques mois après… Heureusement que je me donne des conventions, mais je préfère quand le typage est là à la rescousse…

    Pour en revenir a Scala/Haskell, je pense aussi que comme toujours un critère important est l’outillage déjà existant par rapport à nos besoins. Non seulement bien sûr les outils imposés par notre éventuelle dette technique, mais aussi les outils facilitant le développement : est-ce que le langage s’intègre bien avec mon éditeur de texte préféré ? (Haskell a hdevtools et hlint) Est-ce que le gestionnaire de bibliothèques est ergonomique ? Garantit une reproductibilité parfaite des programmes chez les autres ? (Haskell a stack et Nix) eEst-ce qu’on trouve facilement des ressources pour apprendre ou poser des questions ? (Haskell est l’un des langages dont on parle le plus sur Stackoverflow). Bref, ce genre de considérations externes au langage en lui-même, mais cruciales pour la productivité.

    D’ailleurs j’y pense, pour quelqu’un manipulant des documents textuels, un exécutable (et bibliothèque) Haskell incontournable est Pandoc : https://pandoc.org/ Un peu usine à gaz, mais bon, faut dire aussi qu’il gère beaucoup de formats bien différents.

    Pour conclure entre Scala et Haskell, eh bien, autant apprendre les deux ! Car même si vous continuez au final avec Scala, je suis prêt à parier que de vous être confronté à l’approche d’Haskell sur des micro-projets à côté se ressentira positivement sur votre code Scala ;-)

    http://www.huffingtonpost.com/aaroncontorer/haskell-the-language-most_b_4242119.html
    https://github.com/bitemyapp/learnhaskell/blob/master/guide-fr.md

Laisser un commentaire

Votre adresse de messagerie ne sera pas publiée.