Trichons au jeu des anagrammes vivants

J'ai une petite solution en OCaml. Je n'ai pas encore regardé les sources qui ont été postées jusque ici (je n'ai pas réussi à extraire le 7z de QuentinC), donc mes excuses pour toute redondance avec une solution existante.

Je construit un trie (arbre lexicographique) représentant le dictionnaire, et je fais un parcours en largeur (BFS) sur ce trie. J'avais des idées de comment aller plus loin, mais comme les performances sont déjà satisfaisantes je me suis arrêté là pour l'instant.

Mon programme met 3 secondes à charger le dictionnaire, et ensuite 11 secondes supplémentaires à ne pas trouver de chemin entre "a" et "zythums" (les premiers et derniers mots).

La partie du code dont je suis fier est la visite de tous les voisins d'un nœuf. Intuitivement on sent qu'on peut calculer facilement l'ensemble des mots à distance 1 quand on manipule un trie, mais j'ai mis du temps à trouver une formulation jolie de l'algorithme de parcours. Voilà ce que ça donne maintenant ("bag" est un multi-ensemble de lettres représenté par une string triée, i est un indice dans cette chaîne et next bag i renvoie le prochain indice valide):

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

let visit bag trie k =
  let rec edit bag prev cur i trie k =
    let next, i' =
      if after_end bag i then None, i
      else (Some (get bag i), next bag i) in
    (* either we do an edition on the current letter,
       and continue with the rest of the word unchanged *)
    let continue trie = follow_from bag i trie k in
    remove cur trie continue;
    add cur next trie continue;
    replace prev cur next trie continue;
    (* or we follow the current letter unchanged,
       and do an edition on the rest of the word *)
    if next <> None then begin
      follow cur trie @@ fun trie ->
      edit bag cur next i' trie k
    end
  in
  if after_end bag 0
  then edit bag None None 0 trie k
  else edit bag None (Some (get bag 0)) (next bag 0) trie k

Coucou !

En attendant que mon serveur Olympe se rétablisse et que la nuit me porte conseille pour la suite, je vous propose deux screenshots de mon petit projet :

Mon projet est de créer des graphes interactifs en HTML5/Canvas.

1. L'utilisateur lance la page et tape dans un formulaire de saisie les deux mots qu'il veut joindre.
2. L'algorithme recherche rapidement le meilleur chemin possible.
3. Une fois trouvé il affiche le premier graphe (correspondant au premier mot).
4. Le mot suivant se trouve dans une autre couleur et l'utilisateur clique dessus.
5. Le graphe suivant apparaît. Et on revient au cas d'utilisation n°4.

On peut bien entendu cliquer sur un autre mot. Et même avoir accès au mot "parent" selon la navigation.

Actuellement, j'ai seulement les graphes.

Problèmes techniques possibles :

• La rapidité du Javascript pour ce genre projet (à voir).
• L'affichage, on voit que mon programme ne gère pas très bien les surcharges (textes & bulles).
• Le pointeur souris - ça peut demander quelques réglages.

L'algorithme utilisé:

Soit A le mot initial, B le mot recherché et C le mot testé.

J'utilise trois filtres:

• UE: -1, Min: -1, Max: -1
• UE: 0, Min: 1, Max: 1
• UE: -1, Min: 0, Max: 0

Explication : UE (unité élémentaire) correspond à la conservation des lettres - 0 indique que toutes les lettres de A doivent figurer dans C. Contrairement à -1 ou l'algorithme peut délaisser une lettre. Les indicatifs Min et Max correspondent à la taille du mot. Facile, 1 on gagne une lettre et -1 on en perd une.

Si un des filtres est positif, le mot est sauvegardé. Vous noterez que dans les anagraphes, j'ai passé l'UE du premier filtre à 0 -> j'élimine ainsi les mots plus petit.

Voici par exemple "âme" avec l'UE correctement réglé ('me' vient de se rajouter) :

En testant les filtres dans une boucle, j'applique aussi une fonction pour les anagrammes.

compteur = 0

BOUCLE i < A.length

A_count = substrCount(A, A[i]);

C_count = substrCount(C, A[i]);

compteur += 1 SI A_count <= C_count SINON 0

FIN BOUCLE

La valeur retourné par le compteur sera vérifié grâce à la variable UE. Hé oui, la fameuse conservation des caractères.

La fonction substrCount est identique en PHP : on compte le nombre de sous-chaîne dans une variable.

Des questions ? Des idées ? Je posterai le script dès que possible et puis faut que j'avance tout ça.

EDIT

Olympe est revenu, voici la page de test : http://yarflam.olympe.in/Dev/Anagraph/?q=table.

Vous patienterez un peu la première fois, le temps que le dictionnaire soit sauvegardé en cache dans le navigateur. Il se peut aussi que la résolution ne soit pas adapté à votre support. Je tâcherai de régler ces deux soucis d'esthétismes très prochainement.

Pour l'utiliser, vous pouvez taper votre mot dans la barre d'adresse - ?q=zeste par exemple.

(je n'ai pas réussi à extraire le 7z de QuentinC), donc mes excuses pour toute redondance avec une solution existante.

Pas de risque, j'ai codé en java et je suis plutôt nul en programmation fonctionnelle.

Pour extraire des 7z, http://www.7zip.org/ Au besoin je peux faire un zip.

C'est excellent ce que tu as fais Yarflam, j'attends le résultat avec impatience

Salut, J'ai personnellement testé le système suivant (désolé si ça a été fait, j'ai pas compris tout les algos utilisés par certains… j'ai l'impression que ça a été mentionné mais jamais implémenté)

On construit un graphe dont les nœuds sont les classes d'équivalence pour la relation "est un anagramme de" et dont les arrêtes sont telles que si $S_1$ et $S_2$ sont reliées alors il existe $m_1 \in S_1$ et $m_2 \in S_2$ tels que $m_1$ est un anagramme de $m_2$. Ce graphe est plutôt très gros mais se construit assez rapidement. Il ne reste plus qu'à y faire un BFS pour trouver le plus court chemin. La moitié de ma RAM ayant malheureusement eu la riche idée de me lâcher je ne peux pas faire beaucoup de tests, mais j'ai l'impression que je bénéficie beaucoup de la paresse de Haskell (qui permettrait de ne pas générer tout le graphe), si quelqu'un peut m'éclairer là dessus ce serait avec plaisir.

Le code fait une centaine de lignes et est ici. Si vous avez des commentaires, n'hésitez surtout pas !

@gasche : tes liens sont cassés :/

Merci NougatRillettes, il s'agit d'un bug dans le markdown de ZdS qui ne reconnaît pas les : au milieu d'une URL. J'ai contourné le bug en utilisant leur encodage %3A à la place, donc les liens sont maintenant vivants.

Edit: rapport de bug envoyé.

Est-il possible d'expliquer un peu plus ce que le code fait ? Je pense comprendre l'intuition (qui est aussi donnée dans les commentaires) mais ne comprend pas la traduction en OCaml.

Déjà, comment est-ce qu'on peut chercher dans le trie si bag est trié ? Deuxième difficulté, la continuation, qui cache notamment l'appel à k, ce qui n'aide pas à la compréhension. Je vais bien finir par y arriver.

Plutôt que de construire en mémoire une structure de donnée qui représente l'ensemble des voisins, le code transforme cette donnée en du contrôle: il traverse la liste de ces voisins et leur applique une fonction arbitraire k. Du code de la forme foo k; bar k est donc à comprendre comme une disjonction : "un voisin est soit un nœud atteint par foo, soit un nœud atteint par bar". Enfin on peut jouer selon ses préférences sur la double vue, voir cela plutôt comme une fonction déclarative avec cette traduction, ou plutôt comme un itérateur.

Les nœuds de l'arbre sont indexés par le 'bag' trié. Ce qui permet ce code c'est qu'il y a une description simple et naturelle de l'ensemble des voisins triés à partir de la valeur triée – pas besoin de retraduire dans l'ensemble mots non-triés pour faire ce calcul.

Si tu prends le mot AACD par exemple, l'ensemble des voisins obtenus en transformant la lettre C (on peut transformer au plus une lettre si on reste à distance 1) est défini par la séquence de lettres qui le remplace dans le nouveau mot:

• suppression: séquence vide (résultat ACD)
• insertion (après la lettre): séquence C[C-D], où [C-D] représente une lettre entre C et D, condition nécessaire pour respecter l'ordre dans le mot (résultats ACCD et ACDD)
• remplacement: séquence [A-D] (AAAD, AABD, AACD, AADD; le mot initial apparaît, mais la condition sur la distance pendant le parcours l'éliminera, de même qu'elle évite les redondances)

Les bornes respectant l'ordre sont déterminées par la lettre suivante (pour l'insertion) et la lettre précédente et suivante (pour le remplacement). Sur papier il faut aussi gérer le cas "ajout tout au début" et "ajout tout à la fin", mais en fait on peut magiquement ne pas s'en soucier en prenant des char option comme "lettre précédente / lettre suivante", où la lettre précédente None représente le vide de début de mot, et la lettre suivante None le vide de fin de mot. Avec les bonnes définitions du reste, ça passe tout seul.

Merci beaucoup, c'est beaucoup plus clair. Jolie fonction.

Les nœuds de l'arbre sont indexés par le 'bag' trié. Ce qui permet ce code c'est qu'il y a une description simple et naturelle de l'ensemble des voisins triés à partir de la valeur triée – pas besoin de retraduire dans l'ensemble mots non-triés pour faire ce calcul.

Ah, et tu insères word.bag au lieu de word.raw dans le trie (eestz au lieu de zeste), j'avais mal lu le code.

• suppression: séquence vide (résultat ACD)

Tu voulais dire AAD ?

• insertion (après la lettre): séquence C[C-D], où [C-D] représente une lettre entre C et D, condition nécessaire pour respecter l'ordre dans le mot (résultats ACCD et ACDD)

Oooh, compris, merci.

• remplacement: séquence [A-D] (AAAD, AABD, AACD, AADD; le mot initial apparaît, mais la condition sur la distance pendant le parcours l'éliminera, de même qu'elle évite les redondances)

C'est [A-Z] non ?

Je ne comprends pas ce que tu veux dire ici.

Bonsoir,

Pour celles et ceux qui passent encore par ici j'ai codé une solution en C, voici le code

Le programme s'exécute en 3 phases

• Lecture du dictionnaire (au format ISO8859-1, nom du fichier passé en argument au programme), en sortie on récupère un tableau des mots convertis en majuscules avec suppression des caractères autres que des lettres (exemple -) et remplacement des caractères accentués

• Création d'un graphe dont chaque sommet contient la liste des mots étant des anagrammes l'un de l'autre, la clef du sommet est l'anagramme avec les lettres triées. Les liens avec les autres sommets existants sont ajoutés suivant la relation "anagramme vivant de" à chaque création d'un nouveau sommet. Dans chaque sommet la liste des mots et des liens sont des tableaux de pointeurs.

• Traitement des requêtes de l'utilisateur : v [MOT] pour visualiser un sommet du graphe contenant MOT. p [MOT1] [MOT2] pour visualiser le chemin entre MOT1 et MOT2 (utilisation d'un algo de parcours du graphe BFS). q pour quitter le programme.

Les phases 1 et 2 prennent 15 secondes au total sur mon PC, le temps d'exécution des requêtes utilisateurs est ensuite quasiment instantané.

Exemple de visualisation du sommet contenant le mot FAIRE et recherche du chemin entre IRE et HYDROTHERAPIQUE

? v FAIRE

Size 5

Key AEFIR

Words (4) FAIRE FERAI FIERA FRAIE

Links (77) BEFIR ABFIR AEIR AAEIR ABEIR ACEIR ADEIR AEEIR AEGIR AEILR AEIMR AEIN R AEIPR AEIRR AEIRS AEIRT AEIRZ ABEFR ACEFR ADEFR ADEFI AEFIN AEFIT AFIKR AEFNR ACFIR ACEFIR AEFINR AEFRT AEFRX AEFIL AEFR AEFIRS AEFIRT AEFRS AEFILR EEFIR AEFL R AEFMR AEFIMR AEFRR AEFIRR EFIR AEFIIR EFIRS EFFIR AEFGI EFGIR AEFGIR EFILR EFI MR EFIRX AEFIRX AFILR AFIOR EFIOR AFIR AFIRS AEFPR AEFRY EFINR AFIMR AFIPR EFIPR AFIRR EFIRR EFIRT AFIRU EFIRU AEHIR AFINR EFIKR AEFIM AEFIPR AEIRV CEFIR AFIRT

? p IRE HYDROTHERAPIQUE

Path IRE AIRE ACIER ACIERS CALIERS ARTICLES ARTICULES CLOUTERAIS OCTUPLERAIS COMPILATEURS COMPLIQUATES CYTOPLASMIQUE SPASMOLYTIQUE ASYMPTOTIQUES ASYMPTOTIQUE HYPOSTATIQUE HYPOTHEQUAIS HYPOTHEQUAS HYPOTHEQUES HYPOTHEQUEES DESHYPOTHEQUE DESHYPOTHEQUER DESHYPOTHEQUERA DESHYPOTHEQUERAI HYDROTHERAPIQUES HYDROTHERAPIQUE

? q

Voilà si vous voulez plus d'infos n'hésitez pas

Bonjour,

Je suis tombé sur ce sujet il y a peu de temps, et le problème me parait très intéressant.

L'idée de générer le graphe en prétraitement est tentante, mais il faut ruser sinon c'est du $O(n^2)$. La solution a base de trie proposée plus haut est vraiment bien à mon avis, mais je voudrais présenter une approche différente de ce qui a été proposé, même si elle n'est clairement pas aussi efficace.

Le fait que l'on considère les anagrammes comme des mots équivalents permet de représenter les mots comme des vecteurs dans un espace de dimension 26 (pour les 26 caractères de l'alphabet). A partir de là, on peut définir les trois transitions autorisées en employant la notion de distance euclidienne entre 2 vecteurs, de la façon suivante :

• si $dist(v_1, v_2) = 1$, on a soit un ajout soit une suppression entre les deux mots ;
• si $dist(v_1, v_2) = \sqrt{2}$, on a soit 2 ajouts, soit 2 suppressions, soit un ajout et une suppression, le dernier cas correspondant à une substitution.

Ainsi, pour chaque vecteur $v_i$, les vecteurs correspondants aux mots autorisés à partir de là de trouvent à une distance maximale de $\sqrt{2}$. Si l'on dispose d'une structure efficace pour rechercher les plus proches voisins d'un vecteur dans un espace, il devient possible d'exploiter le modèle vectoriel pour parcourir le graphe efficacement.

Une telle structure existe, je pense au KD-tree. Malheureusement ce type d'arbre n'est réellement efficace que pour un espace de dimension réduite, et l’intérêt reste minime dans notre cas. Toutefois, j'ai testé mon idée en python (parce que c'est fun), et ça fonctionne, mais le chargement du graphe complet est tout de même atrocement lent (un bon quart d'heure chez moi).

Bonjour,

Étant débutant, j'ai trouvé cet exercice intéressant pour l'entraînement. J'ai donc essayé de le résoudre sans m'aider des conseils posté dans ce sujet.

Mon programme fonctionne en listant tous les chemins possibles, tout d'abord les chemins à deux mots, puis à trois mots, et ainsi de suite jusqu'à ce qu'un mot corresponde à la cible, arrêtant ainsi le processus. A partir de là, il me suffit d'afficher le dernier chemin trouvé.

Mais, gros problème, cela ne semble absolument pas performant. Exemple avec sobre > ivre :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

Loading words...
  Opening file dico.txt
  Copying words from file
  Converting to ASCII
  Done! (336531 words loaded in 0.612 seconds)

Please enter the first word: sobre
Please enter the last word: ivre

Looking for the shortest path from SOBRE to IVRE
  Found 174 paths of 2 words (in 0.044 seconds)
  Found 1754 paths of 3 words (in 5.803 seconds)
  Found 3704 paths of 4 words (in 13.409 seconds)

Path: SOBRE BERS BRIE IVRE 
Duration: 19.256 seconds

Ainsi, le temps pour trouver un chemin de plus quatre mots est quasiment interminable…

A votre avis, est-ce que le concept de "chercher tous les chemins" est mauvais ? Où est-ce que mon code n'est juste pas du tout optimisé ?

Encore plus surprenant, si je supprime le teste qui empêche un mot d'être pris plusieurs fois, le processus est relativement plus rapide (mais toujours pas assez) malgré le fait qu'il ait environ vingt fois plus de chemins :

1
2
3
4
5
6
7

Looking for the shortest path from SOBRE to IVRE
  Found 174 paths of 2 words (in 0.044 seconds)
  Found 26588 paths of 3 words (in 4.487 seconds)
  Found 78165 paths of 4 words (in 11.008 seconds)

Path: SOBRE BERS BRIE IVRE 
Duration: 15.539 seconds