Algorithme de césure

Le premier livre sur la typographie en anglais à mentionner le besoin de césure est le Mechanick Exercices (1683) de Joseph Moxon. Cependant, il ne donnait aucune règle pour la césure. Un certain nombre de dictionnaires sont apparus mais étaient la plupart du temps des listes de mots[2].

Le premier programme de césure automatisé apparaît pour le premier système de typographie informatique[4] - [5] - [6] baptisé système BBR selon les initiales de l'équipe française qui en dépose le brevet en 1954[7] : Georges Bafour; ingénieur en chef des Manufactures de l'Etat à l'Imprimerie nationale, François-Henri Raymond, fondateur de la Société d'Electronique et d'Automatisme (laquelle met au point les premiers ordinateurs français) et André Blanchard qui joue ici le rôle de prête-nom pour le rédacteur réel du brevet, qui est Louis Chéreau (ce dernier ne pouvant signer puisqu'il travaille au service des brevets de la société LMT[8] qui produit le Lumitype). Le système de composition BBR est capable de produire des textes justifiés, ce qui représente alors une prouesse technique, mais il n'aura pas le succès commercial espéré par ses promoteurs.

Le programme de césure du système BBR s'appuyait sur les règles basiques de césure des mots français pour fonctionner. Il avait alors pour avantage d'être simple et de pouvoir diviser correctement la plupart des mots. Les inventeurs continue de le perfectionner dans les années suivantes, en travaillant à simplifier les règles typographiques qui le gouverne, d'autant que celles-ci sont implémentées selon une logique cablée « en dur » dans le système. Or, il ne gérait pas les exceptions : ce qui ne représentait pas un obstacle pour le français, s'avéra rédhibitoire pour la langue anglaise, dont les règles de césure sont beaucoup moins systématiques. Cette limitation, associée à l'évolution rapide de l'informatique et la réticence des imprimeurs français traditionnels, condamnèrent l'avenir du système BBR comme système de typographie professionnel.

En 1983 dans le cadre de sa thèse de doctorat en informatique à l'université de Stanford, aux États-Unis, Frank Liang s'est intéressé à la question et a conçu en WEB un programme efficace, nommé Patgen, pour la langue anglaise dont il décrit le fonctionnement dans sa thèse. Son idée a été de combiner les deux méthodes en utilisant un système de règles de césure et en créant un dictionnaire de sous-mots, ou dit de motifs (pattern). Ce dictionnaire est séparé en deux parties, une partie comporte un petit nombre de motifs correspondant aux règles et un grand nombre correspondant aux exceptions.

Ce travail de thèse intitulé « Word hy-phen-a-tion by com-put-er »[9] (en français, Cé-sure par or-di-na-teur) est réalisé sous la direction Donald Knuth, qui est lui-même le père du logiciel de typographie, TeX. Depuis 1977, Knuth avait inclus dans TeX un premier algorithme de césure basé sur 3 règles de bases (détection de préfixes, de suffixes ou de formes voyelle-consonne-consonne-voyelle). L'algorithme de Liang, parfois dénommé Knuth-Liang sera implémenté dans TeX puis LaTeX.

Plus tard, entre 1984 et 1985, alors que Jacques Désarménien se trouve à Stanford, il travaille sur les tables de motifs des mots en français en se basant sur les travaux et l'algorithme de Liang[10]. Il publiera ensuite ses résultats dans plusieurs articles tels que « La division par ordinateur des mots français : application à TeX »[11] ou encore « How to run T_EX in a French environment : hyphenation, fonts, typography »[12]. Il créa notamment un dictionnaire exhaustif des motifs de tous les mots existants ainsi que des exceptions.

La méthode utilisée alors était assez simple.

: les césures étaient autorisées n'importe où dans un mot sauf parmi les combinaisons de lettres suivantes.

• Avant deux consonnes, deux voyelles ou un x.
• Entre deux voyelles, une consonne et un h, un e et un r, un s et un autre s.
• Après deux consonnes où la première n'est pas l, m, n, r ou s.
• Après c, j, q, v, une consonne et un w, mm, lr, nb, nf, nl, nm, nn ou nr.

Cette règle fonctionnait relativement bien pour le français. En revanche, testé sur un dictionnaire anglais, il arrive, selon Liang[2], à trouver 70% des césures mais fait tout autant des erreurs de césure, Liang donne des exemples de mots mettant en échec cet algorithme : fundraising, algorithm...

L'implémentation dans TeX de l'algorithme de Frank Liang, le plus utilisé, procède en deux étapes afin de trouver une césure correcte [13] :

Avant toute chose, TeX vérifie que le mot concerné n'est pas une exception en regardant dans un dictionnaire définissant les points de césure pour les mots spéciaux. S'il n'en trouve pas, il passe à la reconnaissance de motifs (patterns). Ces motifs sont contenus dans un autre dictionnaire et correspondent à des ensembles de lettres redondants.

Avant toute chose, TeX entoure le mot concerné de marqueurs spéciaux. Prenons le mot coquelicot. Avec ces marqueurs, cela donne : . c o q u e l i c o t .. Ensuite il découpe le mot en sous-mots de longueur k, le découpage précédent correspondant à une longueur 1. Voici à titre d'illustration le découpage en longueur 2 et puis 3 :

. c co oq qu ue el li ic co ot t .

. co oqu que uel eli lic ico cot ot .

et ainsi de suite.

Chaque sous-mot (ou motif) de longueur k possède k+1 coefficients entier de poids de césure. Ce poids permet de savoir où il est préférable de couper le mot. Le coefficient est un chiffre compris entre 0 et 9 et est placé entre chaque lettre. Un poids de 0 signifie qu'il est absolument interdit de couper entre ces deux lettres, un poids pair désigne une interdiction de couper (comme 0) et un poids impair une préférence pour couper. Si deux motifs s'affrontent, celui ayant le plus de poids l'emporte.

Par exemple dans les mots périscope et discophile, nous avons le pattern scop. Cependant ils se coupent différemment, pé-ri-scope et dis-co-phile. Les motifs seront alors ₁s₂c₀o₀p₀, ₀i₂s₃c₀o₀p₀e₀ et ₀d₀i₃s₄c₀o₀p₀. Par défaut le 1^er schéma s'applique. S'il y a concurrence avec un autre motif, on choisit le motif avec les coefficients les plus grands.

Comme ces motifs sont dépendants des mots, il est donc impératif d'avoir un dictionnaire de mots (et d'exceptions) propre à chaque langue.

Pour l'implémentation de son logiciel Patgen, Liang a conçu une nouvelle structure de donnée, compacte, utilisant le même principe que les arbres préfixes (ou tries) indexés, le trie compacte ou packed trie. Cette structure de donnée en arbre est utilisée pour représenter les motifs d'un dictionnaire d'une façon compacte. Il arrive en effet à gagner de l'espace mémoire en éliminant entièrement les liens null généralement présents dans de telles structures de donnée[2].

Finalement, l'algorithme utilise un dictionnaire de 4500 motifs (pour la langue anglaise) qui est compilé dans un trie compact occupant 25 Kb de stockage mémoire. En comparaison, un dictionnaire non compressé utilise, pour le même nombre de pattern, 500 Kb.

• « TeX-Hyphen », Comprehensive Perl Archive Network, sur Comprehensive Perl Archive Network (consulté le 18 octobre 2005)
• « text-hyphen », RubyForge, sur RubyForge (consulté le 18 octobre 2005)
• « Knuth-Liang hyphenation for the PostScript language », anastigmatix.net, sur anastigmatix.net (consulté le 6 octobre 2005)
• « TeXHyphenator-J: TeX Hyphenator in Java » (consulté le 14 septembre 2006)
• « Hyphenation in Python, using Frank Liang's algorithm » (consulté le 10 juillet 2007)
• « Hyphenator.js-Hyphenation in JavaScript, using Frank Liang's algorithm » (consulté le 28 juillet 2015)
• « Tex::Hyphen - Perl implementation of TeX82 Hyphenation rules »
• « phpSyllable - PHP implementation of Frank Liang's algorithm »
• « Hyphenator - JavaScript implementation of Frank Liang's algorithm »
• « NHyphenator - C# version of Knuth-Liang hyphenation algorithm »