LTAL, Projet : Coupure des mots

Idée : Concevoir et implémenter en Python l'algorithme de Knuth-Liang de césure automatique des mots. Vous devez écrire un programme qui lit une liste de mots (par ex. un texte), et qui imprime ces mots avec le signalement des césures considérées légales, par ex. :

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, ...

Pour vos tests prenez quelques textes littéraires en français, sur lesquels nous avons travaillé, différents de la "Déclaration". Si vous désirez, comparez votre solution avec le résultat fourni par le Javascript, mentionné ci-dessous. Quelques petites différences peuvent persister, vous ne traiterez pas des exceptions.

Introduction

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.

Voici le test. Modifiez la largeur de la page, 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,

La technique est relativement compliquée, car les règles de césure sont souvent hétérogènes, phonétiques, morphologiques et étymologiques (sémantiques), avec plusieurs exceptions. En Italien la division assez mécanique en syllabes, euphonique, domine largement (coupure avant une consonne). Mais en Polonais ou en Français, la sémantique des fragments des mots est plus importante que les syllabes, et les règles sont plus de dix fois volumineuses.

Patterns de Liang

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.... 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. 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.

La coupure

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.

Méthode de travail

Nous n'allons pas économiser la mémoire grâce aux tries qui partagent les préfixes, ou par d'autres méthodes. Nous n'allons pas non plus chercher des méthodes très optimisées de recherche et d'identification des sous-chaînes. Avec Python standard, le projet est réalisable en 2 - 3 demi-journées. N'hésitez à poser des questions.

Préparation des patterns

Possibles optimisations

Un pattern comme a2l1algi n'est pas un motif "pur", la recherche ne le trouvera pas dans le mot-cible, disons, "talalgia" qui contient "alalgi". Répétons, que les chiffres servent à localiser les points de coupure. 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 positiions.

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é dans un dictionnaire de recherche. 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. Compléter ainsi le dictionnaire. La liste contient autour de 1140 patterns, ce qui n'est pas exorbitant aujourd'hui. (Mais il y a 30 ans, ce n'était pas évident...) On peut stocker une liste numérique : [1, 0, 0] au lieu de '100', ce qui est plus rapide, mais plus gourmand en mémoire.

Mieux, on peut stocker un dictionnaire avec les positions comme clés. La séquence 02010200 associée à 'enivr' est représentée comme le dictionnaire {1: 2, 2: 1, 3: 2}.

Étape principale

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.

Retour à l'index