PseudonymesLuc Maranget1 |
Le but de ce projet est l'écriture d'un programme Pseudo qui prend en arguments des mots et affiche toutes les anagrammes « prononçables » de ces mots. On aura ainsi par exemple :
%java Pseudo polytechnique lycophiquenet lycophiquente polytechnique pytholiquence
Et même :
% java Pseudo école polytechnique cellet hypoconiquée cellée hypoconiquet cellée hypocontique cellicoque néophyte celliquée cynophote celliquée hypocento cellophote cyniquée cellophyte coéquine ...
Les anagrammes sont tout simplement les permutations des lettres d'un mot. Parmi toutes ces permutations, nombreuses sont celles qui ne présentent pas d'intérêt car elles ne ressemblent pas à des mots français. Prenons au hasard le mot polytechnique, l'anagramme ceehilnopqtuy n'est pas bien excitante. En revanche, nectophylique est une anagramme qui ressemble à un mot français.
Une façon assez simple d'examiner la question de savoir si une suite de lettres ressemble à un mot français est de vérifier que tous ses sous-mots sont des sous-mots de mots français. Fixons un entier w à une valeur adéquate, par exemple w=4. Dès lors, nectophylique ressemble à un mot français car tous ses sous-mots de longueur w sont bien des sous-mots de mots français.
Afin de renforcer la vraisemblance de nos anagrammes on demande en outre des débuts et des fins de mots qui sont des débuts et des fins de mots de mots français. Ici, nect est un début de mot plausible, à cause de nectar, et ique est une fin plausible, à cause de acrylique.
Pour engendrer toutes les anagrammes « françaises » nous allons construire un automate qui engendre un sur-langage approprié : les suites de lettres dont les sous-mots de taille w sont des sous-mots de mots français, et qui débutent et finissent par un début et une fin de taille w d'un mot français.
Les mots français sont donnés par un dictionnaire, c'est-à-dire une liste de mots français. Soit par exemple :
Fixons w=4 et considérons les sous-mots qui peuvent apparaître dans une anagramme de polytechnique.
Les sous-mots initiaux sont indiqué par « ^ » et les sous-mots finaux par « $ ».
On fabrique facilement (par insertion répétée dans un arbre), les deux automates qui reconnaissent respectivement les sous-mots initiaux et les autres sous-mots (voir la figure 1).
Les états finaux des automates sont grisés, ils correspondent aux sous-mot qui peuvent apparaître en position finale. Notons au passage qu'il peut exister des mots de taille w, auquel cas des états finaux apparaîtront aussi dans l'arbre des sous-mots initiaux.
Il reste à enchaîner les sous-mots, considérons par exemple le sous-mot (initial) nect. Dans les suites de lettres que nous voulons produire, il se poursuit par tous les sous-mots de la forme ect?, où ? est une lettre quelconque. Autrement dit, on ajoute une transition non-étiquetée dans l'automate, qui va de l'état correspondant au sous-mots nect vers le sous-arbre dont la racine correspond au sous-mot ect. Cette transition supplémentaire est illustrée par la figure 2. La figure illustre une autre de ces transitions non-étiquetées : celle qui exprime le prolongement de ophy en phyl ou phyt. Une fois toutes les transitions de prolongement ajoutées aux deux arbres des sous-mots, on obtient l'automate de la figure 3.
On notera que, dans un souci de clarté, la majeure partie de l'arbre des sous-mots internes n'est pas représentée directement mais par les préfixes qui correspondent aux chemins menant vers les sommets conservés sur la figure.
L'automate de la section précédente engendre donc un langage : les mots dont les sous-mots (de taille w=4) sont certains sous-mots de mots français. Ce langage contient celui que nous recherchons (les anagrammes plausibles) mais ne s'y limite pas nécessairement. Par exemple, l'automate de la figure 3 engendre le mot nectophyte qui n'est pas une anagramme de polytechnique (une lettre « t » est en trop et il manque des lettres). Plus généralement il peut se trouver que le langage engendré par l'automate des sous-mots comporte un nombre infini de mots, même si ce n'est pas le cas dans notre exemple.
Heureusement, il est aisé d'engendrer les mots du langage d'un automate donné qui sont par ailleurs des anagrammes d'un mot donné. Il suffit de parcourir la structure de l'automate en maintenant un stock de lettres. Le stock est initialisé par les lettres du mot à anagrammer. Lors du parcours, effectuer une transition (étiquetée) de l'automate entraîne la consommation d'une lettre du stock. Évidemment, seules sont possibles les transitions qui consomment une lettre effectivement présente dans le stock. Une anagramme est reconnue lorsque que l'automate se trouve dans un état final et que le stock de lettres est vide. Si par exemple, nous représentons un tel parcours de l'automate de la figure 3 sous la contrainte de consommer les lettres de polytechnique, nous obtenons l'arbre de la figure 4 dont les sommets sont décorés par le stock présent à chaque étape du parcours.
Dans cette figure, on remarque que l'essai chlo… échoue en raison de l'absence d'une transition, tandis que l'essai nectophy… échoue en raison du stock de lettres qui interdit la répétition de la lettre « t ».
Comme indiqué par l'exemple initial, le programme produit des anagrammes composées de plusieurs mots. Pour réaliser ces anagrammes il suffit d'enchaîner les parcours contraints de l'automate des sous-mots. Ainsi, dans le cas « école polytechnique », on recherche les anagrammes composées de deux mots et formées de toutes les lettres du stock {c,c,e,e,e,é,h,i,ℓ,ℓ,n,o,o,p,q,t,u,y}.
En fait, on procède quasiment comme dans le cas d'un mot. On construit d'abord l'automate des sous-mots du dictionnaire. Ensuite, on lance un parcours contraint de l'automate, comme à la section 2.2, mais en acceptant tous les mots correspondant aux états finaux — autrement dit sans exiger un stock de lettres vide. Pour chacun de ces premiers mots on relance un parcours contraint de l'automate des sous-mots, en prenant le stock de lettres courant lorsque le premier mot a été engendré. Ici, puisque deux mots sont demandés, on arrêtera les parcours et affichera le résultat lorsqu'un état final est atteint et que le stock de lettres est vide.
Considérons le cas simple des sous-mots ^abab, ^baba, ^abab$, ^baba$, abab et baba, abab$ et baba$ — c'est-à-dire des sous-mots abab et baba pouvant occuper toutes les positions possibles dans un mot. L'automate est alors le suivant :
On vérifie facilement que cet automate engendre les mots des formes abab, ababa, ababab,… et baba, babab, bababa,… — c'est à dire toutes les suites de longueur supérieure ou égale à quatre et formées d'alternances de a et de b, ou de b et de a.
On s'intéresse ensuite aux anagrammes doubles de « aaaaa bbbbb » (soit deux mots issus du stock composé de cinq a et cinq b). On lance donc le premier parcours, contraint selon le stock initial, le premier mot engendré est abab avec un stock restant de trois a et trois b. Donc, les seconds mots possibles sont ababab et bababa. Au final on obtiendra le résultat suivant.
abab ababab abab bababa ababa babab ababab baba baba bababa
On remarque et c'est important, que les anagrammes n'apparaissent qu'une seule fois, compte non-tenu de l'ordre des mots dans les anagrammes. Autrement dit, les anagrammes présentées sont des ensembles distincts de mots. Par exemple, la liste ci-dessus ne comprend pas l'anagramme « ababab abab » équivalente, à l'ordre des mots près, à l'anagramme « abab ababab » qui est bien présente.
Dans cette section nous examinons une technique possible pour éviter la production d'anagrammes multi-mots redondantes. Ce n'est qu'une possibilité. Donc, si on regarde de plus près la liste d'anagrammes donnée ci-dessus, on voit que les mots des anagrammes sont dans l'ordre croissant du dictionnaire.
Il est possible de produire directement une telle liste en considérant des parcours contraints non seulement par un stock de lettres mais aussi par un mot minimal. Autrement dit les mots produits par le parcours doivent majorer (au sens large) un mot donné. Considérons par exemple la dernière anagramme produite ci-dessus « baba bababa ». Le second parcours s'opère sous la double contrainte d'épuiser le stock formé de trois a et trois b, et de produire des mots plus grands que baba. La figure 5 illustre un tel parcours, où sont indiqués, pour chaque état, le stock restant et le mot à majorer.
On observe que la première transition étiquetée a n'est pas effectuée en raison de la contrainte de produire des mots supérieurs ou égaux à baba. En effet tous les mots qui commencent par a sont certainement strictement inférieurs à baba qui commence par b. On observe aussi que l'absence de la contrainte d'ordre est exprimée à l'aide d'un mot minimal vide (noté є). Dans la figure, le mot vide apparaît dès que les mots engendrés admettent pour préfixe un mot supérieur ou égal à baba, c'est-à-dire ici dès que le préfixe baba est atteint.
Écrire le programme Pseudo répondant à l'interface2 suivante :
Usage: java Pseudo [options]* nom_1 ... nom_n Les options sont : -v, affiche des messages sur le fonctionnement, peut être répété. -w n, largeur de la fenêtre [n >= 2, défaut 5] -d dico, change le dictionnaire [défaut ./nv.txt]
Le programme Pseudo prend n mots en arguments , et écrit sur la sortie standard les anagrammes de n mots qui épuisent les lettres des n mots passés en argument. Les mots des anagrammes seront des mots dont tous les sous-mots sont des sous-mots de taille w (option -w) des mots du dictionnaire (option -d). En outre les sous-mots initiaux et finaux de taille w des mots des anagrammes seront des sous-mots de mots du dictionnaire de taille et de position identiques. Les anagrammes multi-mots ne seront donnés qu'une fois, au sens défini à la section 3 que les anagrammes sont des ensembles distincts de mots.
Ce document a été traduit de LATEX par HEVEA
