L'algorithme de Liang pour la division des mots par ordinateur

#Sommaire

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. J'ai pu la lire, 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'ue 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. En fin on peut encore gagner de la place en remarquent 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ébarassé 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 exceptions, et ces exceptions sont enregistrées sous forme de motifs.

Ainsi, pour reprendre l'exposé de Désarménien, d'un mot à diviser on extraiera tous les sous-mots, qui seront confrontés au dictionnaire des motifs, constitué préalablement. Les lettres d'un groupe qui constitue un motif seront 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.

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.

Les programmes de Liang ont été traduits dans à peu près tous les langages de programmation, en voici une version dans mon langage préféré.