Si un texte imprimé est justifié (sa largeur est figée), afin d'éliminer des espaces inutiles ou le débordement, on coupe les mots, et actuellement tous les logiciels d'édition en sont capables, dans la plupart de langages où ceci est nécessaire. Si les lignes sont longues, la justification équilibre les espaces, et le résultat est souvent acceptable même sans césures, mais pour le formatage en deux colonnes les "trous" deviennent visuellement gênants. L'algorithme le plus populaire a été écrit par Frank Liang, dans sa thèse de 1983 sous la direction de Donald Knuth, l'auteur du TeX, LE système de formatage des documents connu de tous les vrais gentlemen. Le système est utilisé par TeX/LaTeX, dans l'Open Office et Libre Office, et il existe aussi une variante Javascript, dont le fonctionnement automatique est montré ci-dessous. Lisez aussi cette page.
Exercice 0.
Voici le test. Importez la source, et installez le Hyphenator chez vous (ou accédez à ce script ailleurs). Modifiez la largeur des colonnes, vérifiez comment le remplissage des lignes change. (Ici le système de coupure insère dans les mots le "trait d'union conditionnel" HTML : ­, visible seulement quand la coupure a lieu).
| Sans césures | Avec césures (auto) |
|
Considérant que la reconnaissance de la dignité inhérente à tous les membres de la famille humaine et de leurs droits égaux et inaliénables constitue le fondement de la liberté, de la justice et de la paix dans le monde,
Considérant que la méconnaissance et le mépris des droits de l'homme ont conduit à des actes de barbarie qui révoltent la conscience de l'humanité et que l'avènement d'un monde où les êtres humains seront libres de parler et de croire, libérés de la terreur et de la misère, a été proclamé comme la plus haute aspiration de l'homme,
Considérant qu'il est essentiel que les droits de l'homme soient protégés par un régime de droit pour que l'homme ne soit pas contraint, en suprême recours, à la révolte contre la tyrannie et l'oppression, |
Considérant que la reconnaissance de la dignité inhérente à tous les membres de la famille humaine et de leurs droits égaux et inaliénables constitue le fondement de la liberté, de la justice et de la paix dans le monde,
Considérant que la méconnaissance et le mépris des droits de l'homme ont conduit à des actes de barbarie qui révoltent la conscience de l'humanité et que l'avènement d'un monde où les êtres humains seront libres de parler et de croire, libérés de la terreur et de la misère, a été proclamé comme la plus haute aspiration de l'homme,
Considérant qu'il est essentiel que les droits de l'homme soient protégés par un régime de droit pour que l'homme ne soit pas contraint, en suprême recours, à la révolte contre la tyrannie et l'oppression, |
Voici le forcing de césure :
Consi-dé-rant que la re-con-nais-sance de la di-gnité in-hé-rente à tous les membres de la fa-mille hu-maine et de leurs droits égaux et in-alié-nables consti-tue le fon-de-ment de la li-berté, de la jus-tice et de la paix dans le monde,
Consi-dé-rant que la mé-con-nais-sance et le mé-pris des droits de l'homme ont conduit à des actes de bar-ba-rie qui ré-voltent la conscience de l'hu-ma-nité et que l'avè-ne-ment d'un monde où les êtres hu-mains se-ront libres de par-ler et de croire, li-bé-rés de la ter-reur et de la mi-sère, a été pro-clamé comme la plus haute as-pi-ra-tion de l'homme,
Consi-dé-rant qu'il est es-sen-tiel que les droits de l'homme soient pro-té-gés par un ré-gime de droit pour que l'homme ne soit pas contraint, en su-prême re-cours, à la ré-volte contre la ty-ran-nie et l'op-pres-sion,
Consi-dé-rant qu'il est es-sen-tiel d'en-cou-ra-ger le dé-ve-lop-pe-ment de re-la-tions ami-cales entre na-tions,
Consi-dé-rant que dans la Charte les peuples des Na-tions Unies ont pro-clamé à nou-veau leur foi dans les droits fon-da-men-taux de l'homme, dans la di-gnité et la va-leur de la per-sonne hu-maine, dans l'éga-lité des droits des hommes et des femmes, et qu'ils se sont dé-cla-rés ré-so-lus à fa-vo-ri-ser le pro-grès so-cial et à ins-tau-rer de meilleures condi-tions de vie dans une li-berté plus grande, ...
La césure est très différente selon la langue, et on peut avoir l'impression que c'est un sujet très compliqué. On a des règles morphologiques, qui demandent à ce que les parties sémantiquement distinctes puissent être séparées, aisi même si une règle lexicale, purement structurelle (et d'habitude euphonique) demanderait, disons : "represen-tation", la morphologie peut suggérer "represent-ation", etc. Les règles changent avec le temps, et parfois les ambiguïtés persistent (surtout là où l'Académie d'un pays n'arrive plus à arriver à un consensus, car quelques vieillards gonflés, convaincus qu'ils savent comment la langue doit évoluer, se chamaillent...). Il y a des langues comme l'italien, où l'euphonie gagne, et les règles sont simples et peu nombreuses, et les langues où le lexique a été bâti par l'agglutination, et où toute règle a un nombre important d'exceptions. Faire un système de césure automatique est un challenge intellectuel d'envergure.
Ceci a inspiré d'abord Donald Knuth et ensuite Franklin Liang, son thésard, à concevoir un système universel, implémentable dans toutes les langues, et basé sur des motifs lexicaux. Supposons que dans notre langue, les mots qui ont à l'intérieur la combinaison abe, peuvent être scindés en ...a - be... ; aussi : a-ble.... Par contre, la combinaison able en fin du mot ne doit pas être séparée. On scinde ta-blette, mais jamais diable.
Une règle locale peut être invalidée par une autre : trans-amé-rique, mais tran-sac-tion, et trans-por-ter. Ensuite : mas-to-donte apos-trophe, mais dé-struc-tu-rer (et selon certains, "apostrophe" a été mal coupé, car "apo" et "strophe" sont des entités morphologiques...)
L'idée est d'assembler (manuellement ou semi-automatiquement) un certain nombre (des dizaines ou des milliers !...) de motifs (patterns) : combinaisons de lettres, où on trouve, intercalés, des petits nombres entiers : 1, 2, 3 ... L'absence d'un nombre équivaut zéro. Un nombre impair signifie que la coupure est permise, un nombre pair : interdite. Si les patterns interfèrent (plusieurs combinaisons déclarées ainsi se trouvent dans un mot, dans le même endroit – le nombre plus grand "gagne").
Exemples de patterns français : tran2s1o2, 1ni, .o4, 4fre., .dé3s2o3dé, etc. Le point symbolise le début ou la fin du mot. Ainsi, par ex., on interdit la coupure avant une syllabe muette terminant le mot, cam-bre-mer, mais chambre. Parfois on trouve des règles "culturelles / psychologiques" : dé-cons-truc-tion, mais construc-tion, devinez pourquoi...
Les patterns vous seront donnés, où vous allez les chercher sur le Web, tout est public et BIEN documenté. Dans http://www.ctan.org/tex-archive/language/hyphenation/ vous trouverez les listes de patterns dans la plupart de langues adaptées au TeX (ou systèmes équivalents). La liste pour le français aussi, bien sûr. Localement vous avez ce document. Son format n'est pas commode, on reviendra à la représentation des patterns dans votre programme ; ceci constitue une partie de votre travail.
Prenons un exemple en anglais, le mot : hyphenation. Voici les patterns stockés, qui sont "éligibles" pour ce mot. Sans nombres : hyph hen hena henat na nat tio io on. . Avec : hy3ph he2n hena4 hen5at 1na n2at 1tio 2io o2n. .
Voici l'appariement du mot et des patterns :
h y p h e n a t i o n
h y3p h
h e2n
h e n a4
h e n5a t
1n a
n2a t
1t i o
2i o
o2n
-----------------------
h y3p h e2n5a4t2i o2n
La dernière ligne qui ramasse les nombres en gardant le maximum, donne la réponse au problème de la coupure. La réponse est hy-phen-ation.
Exercice 1.
Étant donné un texte de quelques centaines (ou milliers, mais n'exagérez pas) de mots, et la liste de patterns de la langue française, tokeniser le texte (en éliminant les majuscules pour simplicité) et pour chaque mot trouver les points de césure, faire le découpage, et écrire le résultat.
hyph-fr.tex, construisez un fichier qui contient seulement les motifs :
.a4 'a4 .â4 'â4 ab2h .ab3réa 'ab3réa ad2h a1è2dre .ae3s4ch 'ae3s4ch 1alcool a2l1algi .amino1a2c 'amino1a2c .ana3s4tr 'ana3s4tr 1a2nesthési .anti1a2 ...En utilisant les expressions régulières, éliminez les commentaires TeX : tout ce qui commence par le caractère "%" jusqu'à la fin de ligne. Ensuite éliminez les espaces redondants. Finalement, éliminez
"\patterns{" et "}" et c'est tout.
Développons les détails de notre dernière remarque ci-dessus. Répétons, que les chiffres servent à localiser les points de coupure. Un pattern avec les nombres, comme a2l1algi n'est pas un motif "pur", la recherche ne le trouvera pas dans le mot-cible, disons, "talalgia" qui contient "alalgi". Encore un exemple :
. a l g o r i t h m .
4l1g4
l g o3
1g o
2i t h
4h1m
-----------------
4 1 4 3 2 0 4 1
a l-g o-r i t h-m
Avec ce format le programme doit séquentiellement parcourir le mot et les patterns, lettre par lettre, et accumuler les données partielles, ce qui est faisable, mais pénible (à mes yeux...). Mais si on sépare le motif 4l1g4 en "pur" : lg, on a la fonction standard Python : mot.find(sousCh) qui trouve l'indice où la sous-chaîne se trouve, ou -1 en cas d'échec. On a également la très riche panoplie d'expressions régulières ! Les chiffres, ici "414" peuvent être stockés séparemment, avec les traces de leurs positions.
Alors, une possibilité d'optimisation est la suivante. Pour chaque pattern découvert, séparer le fragment lexical, supprimer les chiffres (mais elles ne seront pas oubliées). Ainsi e2n1i2vr se transformera en enivr. Ce motif "pur" servira de clé. Les valeurs associées aux clés utiliseront les chiffres, et permettront d'identifier les positions des points légaux de césure. Pour chaque caractère du motif complet, on stocke une séquence des chiffres correspondants, où leurs positions sont évidentes, si on restaure les zéros implicits. Par exemple
'.pa3rent.' => '.parent.' : '000300000' '.su2b1é2' => '.subé' : '00020102' '1rô' => 'rô' : '100' 'stéréo1s2' => 'stéréos' : '000000102' 'e2n1i2vr' => 'enivr' : '02010200' 'hen4a' => 'hena' : '00040' 'hen5at' => 'henat' : '000500'etc.
02010200 associée à 'enivr' est représentée comme le dictionnaire {1: 2, 2: 1, 3: 2}.
Alors, si on cherche le pattern "henat" dans "hyphenation", on trouve l'indice 3 (comme avec "hena"). Le pattern correspond à la séquence 000500. Donc, à la position 3+0=3 dans le mot, on a zéro. Pour 3+1=4 : zéro, ... pour 3+3=6 : 5, ce qui dominera sur 4 découvert par "hena". La position 6, après le caractère 'n', devant "ation", est éligible à la coupure.
Cette partie du programme se réduit à une simple boucle sur le dictionnaire des patterns, avec la mise à jour d'une liste / dictionnaire de positions. Pour chaque mot on parcourt tous les patterns, et on accumule les positions de césure avec leurs "poids". Seulement les poids impairs comptent à la fin du processus.
Attention.
alié-nable, mais il décide de couper in-aliénable de cette manière, car il trouve seulement le premier NA des deux dans iNAliéNAble...