Site WWW de Laurent Bloch
Slogan du site

ISSN 2271-3905
Cliquez ici si vous voulez visiter mon autre site, orienté vers des sujets moins techniques.

Pour recevoir (au plus une fois par semaine) les nouveautés de ce site, indiquez ici votre adresse électronique :

TeX, LaTeX et la thèse de Franklin Mark Liang :
L’algorithme de Liang pour la division des mots par ordinateur
et l’article de Jacques Désarménien
Article mis en ligne le 13 juillet 2010
dernière modification le 30 août 2015

Le problème de la division des mots est compliqué

« Il y a des problèmes dont on trouve tout de suite une solution simple mais approchée, voire naïve et pour lesquels une solution complète nécessite une approche autrement plus sérieuse. La division des mots, c’est-à-dire la coupure des mots en fin de ligne d’un texte, est de ceux-là. C’est tellement vrai que lorsque l’on parle de ce problème à un enseignant d’informatique en université, la réplique est presque invariablement la même : Où est le problème ? Mes étudiants de DEUG, ou de licence, font ça en TP ».

Ces lignes de Jacques André introduisaient en 1986 l’article de Jacques Désarménien La division par ordinateur des mots français : application à TeX, (Technique et Science Informatiques 1986/04). L’article, en ma possession mais malheureusement toujours pas disponible en ligne librement, expliquait toute la difficulté du sujet et en exposait la solution, basée sur un mystérieux « algorithme de Liang », dont je ne trouvai pas le moyen de consulter la documentation, sauf à me rendre à la bibliothèque de l’Université Stanford pour y emprunter la thèse de Ph.D. soutenue en 1983 par Frank Liang, Word Hy-phen-a-tion by Com-put-er ; les tirets à l’intérieur des mots de ce titre y indiquent les positions légitimes de césure, nous utiliserons cette notation dans la suite.

Depuis 2004, mais je ne m’en suis avisé que récemment, Frank Liang a autorisé la mise en ligne d’une photocopie de sa thèse, de piètre qualité mais lisible. Il était d’ailleurs déjà possible d’en lire un résumé dans le TeXbook de Donald Knuth, à l’annexe H (page 515 de la traduction française de Jean-Côme Charpentier). J’ai donc lu récemment le texte intégral, pour constater que la substance relative à la division des mots m’en avait déjà été délivrée par l’article de Désarménien.

Ranger efficacement des mots (ou des motifs)

En fait, les trois quarts des 44 pages de texte de la thèse (sans compter les annexes qui incluent le programme de génération des motifs de césure et la table des motifs) sont consacrés à des trésors d’ingéniosité algorithmique destinés à gagner quelques milliers d’octets en mémoire, efforts dont l’auteur se dispenserait sans doute en grande partie s’il devait recommencer ce travail sur un ordinateur contemporain. Aussi le lecteur impatient des aspects linguistiques et typographiques peut-il sans dommage passer directement à la section suivante.

Pour stocker des mots ou des motifs (fragments de mots, patterns), Liang utilise les arbres de recherche (digital search trees), ou tries, une structure de données qui peut être envisagée comme un arbre m-aire, où m est le nombre de lettres de l’alphabet sur lequel sont définis les mots. Les recherches sont effectuées caractère par caractère, avec à chaque nœud une alternative à m branches.

Comme les informaticiens préfèrent les arbres binaires, Liang passe ensuite du trie m-aire au trie chaîné implanté par un arbre binaire, où l’alternative à m branches est réalisée par une séquence de comparaisons, à chaque nœud si le caractère qui s’y trouve est « bon » on passe au fils droit, au fils gauche sinon.

Liang implante son trie chaîné dans un tableau à m colonnes, une par lettre de l’alphabet. La première ligne du tableau contient, dans chaque case qui correspond à une lettre qui est l’initiale d’un ou de plusieurs mots, le numéro d’une ligne dont les cases qui correspondent aux secondes lettres de chacun de ces mots indiqueront des numéros de ligne où se trouveront des pointeurs vers les lignes correspondant aux troisièmes lettres, et ainsi de suite. Une marque spéciale indique qu’une case correspond à la dernière lettre du mot considéré.

Le tableau ainsi obtenu est plein de cases vides : pour gagner de la place Liang regroupe les lignes dont les cases occupées sont dans des colonnes différentes, ce qui lui impose d’indexer chaque case avec la lettre précédente du mot auquel elle correspond. Enfin on peut encore gagner de la place en remarquant que beaucoup de mots partagent un suffixe commun, et qu’en remontant dans le trie en partant des feuilles on doit pouvoir fusionner les subtries communs, non sans identifier, dans une table associative, les nœuds équivalents. Bref, ces trésors d’ingéniosité algorithmique récursive permettent à Frank Liang de faire tenir son algorithme et sa table de classement des mots ou des motifs, qui sont loin d’être simples, en très peu de place. L’originalité des méthodes employées justifie pleinement la présence de cet exposé dans une thèse de Ph.D.

Césure

Après ce long préambule consacré aux structures de données propres à stocker les mots et les motifs, l’opération de césure elle-même (hyphenation en anglais) fait l’objet d’un exposé assez laconique. Deux méthodes sont envisageables : définir et appliquer des règles, ou constituer un dictionnaire exhaustif où chaque mot, accompagné de ses différentes formes dérivées, figurera annoté des points de césure autorisés. Notons que le problème des formes dérivées, s’il est simple en anglais moderne, débarrassé de la plupart des flexions et variations des formes verbales, est nettement plus complexe en français.

Nous avons appris à l’école les règles de césure des mots français, et d’ailleurs ce sont elles que l’on retrouve dans le programme de césure du premier système de typographie informatique conçu dès 1954 par une équipe française menée par F.H. Raymond et G. Bafour. Un programme qui repose uniquement sur ces règles aura l’avantage de la simplicité, et il permettra de diviser correctement la plupart des mots.

Néanmoins, ces règles acceptent un certain nombre d’exceptions, qui
produiront autant d’erreurs, inacceptables pour un système de typographie professionnel. Ainsi, nous explique Jacques Désarménien, après avoir compilé tous les manuels typographiques et grammaticaux qu’il a pu trouver, épis-copal sera divisé selon une règle phonétique, cependant qu’épi-scope, plus moderne, sera divisé selon une règle étymologique. Le groupe ill est insécable lorsqu’il représente un son mouillé comme dans grillage, mais pas dans vil-lage. De même pour le groupe gn, insécable sauf dans stag-nant où le g et le n sont prononcés séparément. Encore les manuels ne sont-ils pas unanimes sur ces points délicats.

L’idée, géniale, de Frank Liang fut de combiner la méthode des règles avec celle du dictionnaire, en constituant non pas un dictionnaire des mots à diviser, mais un dictionnaire des sous-mots, qui sont enregistrés sous forme de motifs. Ce dictionnaire comportera un petit nombre de motifs correspondant aux règles, et un plus grand nombre de motifs correspondant aux exceptions et aux exceptions des exceptions. Comment le motif de l’exception pourra-t-il prendre le pas sur le motif de la règle, c’est ce que nous allons voir.

Ainsi, pour reprendre l’exposé de Désarménien, pour diviser un mot on extraiera tous ses sous-mots, qui seront confrontés au dictionnaire des motifs, constitué préalablement. Les lettres d’un groupe qui constitue un motif sont séparées par des coefficients entiers de 0 à 9 qui indiquent la désirabilité ou la non-désirabilité d’une coupure à cet endroit. En fait 0, qui indique « pas de coupure », sera omis. Les nombres impairs indiquent les coupures autorisées, les nombres pairs (dont 0, omis) les coupures interdites. Lorsque plusieurs coefficients fournis par différents motifs sont en concurrence pour une même position de césure éventuelle, le plus grand l’emporte. Ainsi, la présence dans le dictionnaire des motifs vil3l et avil4l permet la césure de vil-lage et interdit celle de gravil/lon. Le e ouvert non accentué de té-les-cope le distingue de mi-cro-scope, qui ne se coupera pas non plus comme dis-co-phile, ce qu’indiquent 1s2cop, e2s3cop, di2s3cop.

Désarménien s’est rangé à l’avis du Memento typographique de C. Gouriou, « qu’il est préférable, surtout dans les ouvrages destinés aux élèves, d’éviter de conserver en fin de ligne des syllabes malsonnantes ou prêtant à des interprétations regrettables », et il a introduit les motifs +con4 et +cons4 à cet effet.

Régularité comparée des différentes langues

Pour engendrer le dictionnaire de motifs, Frank Liang a écrit le programme Patgen, auquel il faut fournir une liste de mots préalablement divisés, dont il inférera un dictionnaire de motifs apte à les reproduire. Les bons dictionnaires anglais ou américains mentionnent pour chaque mot les points de césure acceptables, mais pas les dictionnaires français. En outre, un tel dictionnaire existât-il,
qu’il ne fournirait sans doute pas les césures des formes dérivées, dont la langue française est riche. Bref, Jacques Désarménien a préféré écrire directement les motifs nécessaire à la production du dictionnaire désiré. Ce travail (de romain) est décrit en détail dans l’article, il a fait alterner essais de programmes et compilation manuelle de motifs au fur et à mesure qu’apparaissaient les césures inattendues.

Une fois tout ce travail fait et que l’on croit toucher au but, surgit un autre problème : avec TeX, la césure dépend de la police de caractères ! En effet le traitement des ligatures et des crénages n’est pas sans effet, Désarménien a dû adapter les polices.

Aucun programme de division des mots ne peut prétendre à la perfection, puisqu’aussi bien les langues humaines sont d’une flexilbilité infinie, qu’en outre elles varient dans le temps et dans l’espace et que leurs différents locuteurs ne sont pas forcément d’accord entre eux sur les usages. Certains sont carrément non-programmables : en anglais record se coupe re-cord s’il s’agit du nom et rec-ord s’il s’agit du verbe. Donc il s’agira, pour chaque langue, d’établir un dictionnaire de motifs de taille raisonnable et qui ne laissera subsister qu’un tout petit nombre d’exceptions résiduelles, la plupart des logiciels de composition donnant la possibilité de diviser « à la main » les mots trop rétifs.

À la fin de son article Jacques Désarménien nous livre une comparaison intéressante. On peut estimer que le nombre de motifs qu’il faut introduire dans le dictionnaire, pour traiter des cas d’exception par exemple, est une mesure de l’irrégularité de l’orthographe de la langue considérée. La diffusion de TeX/LaTeX a conduit de nombreux chercheurs à construire des dictionnaires adaptés à d’autres langues que l’anglais, et ils se sont réunis à Côme en 1985 pour comparer leurs résultats.

Le dictionnaire de Désarménien pour le français comporte 804 motifs, dont 412 pour les césures étymologiques. Pour l’anglais il en faut 4 447, près de 10 000 pour l’allemand, mais seulement 88 pour l’italien, langue dont l’orthographe plus régulière a été fixée au XIXe siècle seulement, selon des principes sans doute plus rationnels.

Ce n’est que si l’on ne s’est jamais posé la question que cette question de la division des mots peut sembler ancillaire. Comme Bernard Gaulle nous le rappelait, par exemple dans son article de 1994 dans les Cahiers GUTenberg n° 18, Commentaires sur la portabilité des documents (LA)TEX, la méthode et les choix de division des mots ont une importance primordiale pour la qualité typographique d’un texte, ainsi que pour l’adaptation d’un système de composition à une langue particulière.

Les programmes de Liang ont été traduits dans à peu près tous les langages de programmation et utilisés pour d’autres systèmes de composition que TeX et LaTeX, en voici une version dans mon langage préféré. Je l’ai adaptée pour le compilateur Bigloo et Manuel Serrano l’a incorporée à Hop. Le code est là.