Algorithme d'anagramme ??

**Muetdhiver** · 18/09/2002, 17h41

Bonjour, je cherche a écrire un programme qui trouve tous les anagrammes d'un mot par rapport a un dictionnaire (en php mysql).
mais je ne sais absloument pas comment m'y prendre, a savoir que pour calculé l'anagramme d'un mot de scrabble, (7 lettres), et faudrait théoriquement faire 7! opérations, soient plus de 5000 opérations. Avec un raccord (8!), on passe a 40 000 .... C'est vraiment trop bourrin, mais il doit exister des algorithme deja développés par des mecs a ce sujet (notamment en recherche opérationnelle nan ?).
Parceque ke je me vois mal prendre 7 lettres, et les permuter toutes en comparant avec une requete si c'est bien dans ma base de donnée, ca serait impossible....
Exmple avec 4 lettres :
IEAL -> trie alpha -> AEIL, puis :
AEIL
AELI
AIEL
AILE -> bon
ALEI
ALIE
-----> 6
6 * 4 lettres = 24 = 4!

....mais je vois pas comment faire autrement ??
Merci.
++

**Pierre Castelain** · 18/09/2002, 18h44

A première vue, comme ça, moi je procèderais à l'envers:
- compter le nombre d'occurence de chaque lettre,
- balayer tous les mots du dico (je ne pense pas que l'on puisse l'éviter),
- si le mot du dico n'a pas la même longueur on passe au suivant,
sinon on teste si les lettres sont présentes avec le même nombre d'occurence.

On doit pouvoir faire mieux, mais cela me parait un bon début. Je ne connais pas bien MySQL mais j'imagine que l'on doit pouvoir récupérer tous les mots d'une longueur donnée avec une requête adéquate. Cela permettrait de ne tester que ceux ayant une bonne probabilité.

**RuleZ** · 18/09/2002, 20h43

Oui, la solution de Pierre est la bonne

En gros, tu vas utilisé php pour construire une requête un peu lourde du style:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
SELECT mot 
FROM dictionnaire
WHERE LENGTH(mot) = [taille]
    AND mot LIKE '%A%'
    AND mot LIKE '%B%B%'
    AND mot LIKE '%D%';

C'est à dire que pour chaque lettre de l'alphabet, tu compte le nombre d'occurence dans le mot de départ et:
- si 0 occurence => rien
- sinon tu ajoute à ta requête AND MOT LIKE '% + [Lettre]% autant de fois que d'occurence de la lettre + '

**Ol'** · 18/09/2002, 20h59

En fait je pense qu'il serait plus rapide de coder chaque mot par une méthode indépendante de l'ordre des lettres et copier aussi ce code dans la base de données.

Par exemple, je propose
a -> 1
b -> 2
c -> 4 etc...

donc abc = 1+2+4

Je réaliserai la comparaison par rapport à ce code.

Si deux mots présentent le même code, on peut vérifier si ce sont des anagrammes

J'espère que cela pourra t'aider
Ol'

**RuleZ** · 18/09/2002, 21h22

Ya une méthode simple qui consiste à avoir un champs supplémentaire dans la table qui contiendrait le mot avec ses lettres ordonnées alphabétiquement:
LAPIN => AILNP
ECUREUIL => CEEILRUU

Suffit alors de transformet le mot à rechercher de la même façon, puis la recherche se fait tout seule par simple égalité avec le champs clef.

**DrQ** · 18/09/2002, 21h37

J'utiliserai une méthode similaire à celle de Rulez.
Je travaillerai par elimination.
Exemple :
Reprenons IEAL comme lettres de départ.

je regarde s'il existe au moins un mot commencant par I.
Si oui alors je regarde s'il existe au moins un mot commencant par IE.
Si non alors je regarde s'il existe au moins un mot commencant par IA.
Si non alors je regarde s'il existe au moins un mot commencant par IL.
Si oui alors je regarde s'il existe au moins un mot commencant par ILE.
Si oui alors je regarde s'il existe au moins un mot commencant par ILEA.
Si non alors je regarde s'il existe au moins un mot commencant par ILA.
Si non alors je regarde s'il existe au moins un mot commencant par E.
etc...

En fait j'effectue le même parcours que le premier que tu as présenté avec les factorielles comme nombre de tests à effectuer. Certains tests peuvent ne pas être fait car aucun mot ne commence de cette façon. Donc tu élimine toute une branche de tests à réaliser.

**Pierre Castelain** · 18/09/2002, 22h58

Envoyé par RuleZ

Ya une méthode simple qui consiste à avoir un champs supplémentaire dans la table qui contiendrait le mot avec ses lettres ordonnées alphabétiquement:
LAPIN => AILNP
ECUREUIL => CEEILRUU

Suffit alors de transformet le mot à rechercher de la même façon, puis la recherche se fait tout seule par simple égalité avec le champs clef.

Ca me parait une excellent idée. La complexité de la recherche est extrèmement réduite au prix d'une structure de donnée plus grande comme c'est souvent le cas. A priori, on devrait toutefois pouvoir améliorer ça en ne stockant pas le mot complet (celui dont les lettres sont ordonnées) mais un CRC ou un code équivalent permettant de déduire le nombre d'occurences de chaque lettre dans le mot.

**Muetdhiver** · 19/09/2002, 13h31

Oui !!!! merci vraiment de toutes ces précisions. Un tel forum est un vrai bonheur !

Ce que je retient, en faisant un peu la synthese de ce que vous m'avez dit, c'est qu'il y aurait deux solutions vraiment interessantes.
La premiere est simplement algorithmique en effet, comme le dis DRQ, c'est une bonne idée de procédé par élimination, sans faire tout les calculs. Dès qu'on a une lettre chere dans le tirage (W, Z, etc...) ca evite tout de suite enormement de calcul !!
Si on couple ca avec la sélection des mots qui ne font que N lettres, on gagne bcp de temps en effet

L'autre solution que je trouve excellente, c'est celle de Rulez, car en effet rajouter un champs avec les lettres ordonées est tres simples et ultra rapide en temps de requete. Le pb c'est un pb de poids, on génère deux dictionnaires au lieu de 1 ... mais qu'importe puisque pr 10 Mo sur un disk dur, c'est plus grand chose de nos jour.
En plus pour alléger, Pierre et Ol' ont raison, si on met une structure qui se base sur les codes, ca prendrait moins de place.
Mais peut on arriver à un code unique par combinaison ?
Car si le code est 8, je ne sais pas si cela correspondra a
1 + 2 + 2+ 3 "abbc"
ou 1 + 1 + 3 + 3 "aacc" , etc...
Le crc ? c'est a dire ?
parceque je sais calculer un CRC, mais je vois pas l'interet si on prend un polynome diviseur comme 100111, le crc sera sur 6 bits, et de plus je me demande si il serait unique, en fait pas un tout quand on y reflechis, enfin je sais pas sur ce point....

Maintenant que j'ai ces solutions, je me demande une chose, c'est comme rentrer un dictionnaire de 360 000 mots dans un base de donnée sql, chez un hebergeur gratuit !!! chez moi je lé fait en ligne de commande dans un console sql, ca prenait quelques secondes par lettre, mais avec phpMyadmin... enfin je vais poser cette question dans le forum sql pt etre lol.
encore merci.
++

**Musaran** · 20/09/2002, 06h14

Accompagne chaque mot d'un tableau de 26 compteurs d'occurences, un pour chaque lettre.
Comme ça risquerait d'être gros en BDD (je pense), il faut limiter la portée des compteurs, ou truquer un type.

Il faut voir ce qu'acceptent ton langage et ta base de données comme types.

On peut toujours le simuler sur un entier (de mémoire):

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
rng: rang de la lettre dans l'alphabet, à partir de 0.
max: nombre d'occurences différentes prisesn compte pour une lettre (0 inclus)
occ[]: tableau des occurences effective des lettres.
id: identifiant
 
^ puisance
mod modulo
 
id= somme_de_tous_les( max^rng * min(occ[rng],max-1) )
 
Ou en boucle avec des calculs moins lourds:
id= 0
poids= 1
pour chaque rng de 0 à 25
	id= id + poids * min(occ[rng],max-1)
	poids= poids * max

**Sarbacane** · 22/09/2002, 12h52

Une methode simple mais efficace pour lineariser la complexite de ton algorithme est de modeliser ton dictionaire par la representation intervallaire des arbres ("Interval Tree" en anglais). En effet les mots du dictionaire peuvent etre organises comme suis:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
Dico(Racine) ===> Noeud Nr 0
    Nombre_ de_Characteres ===> Noeud Nr 1
        Clef_Unique_ alphabétiquement_ordonnée ===> Noeud Nr 2 (cf. RuleZ)
            Mots_de_N_Characteres_Correspondant_A_Clef ===> Feuilles

Ainsi pour retrouver tous les mots de N lettres correspondant a l'anagramme Xi, il suiffit de trier alphabétiquement le vecteur Xi et de selectionner toutes les feuilles du sous Noeud de niveau 2 identique a Xi .
PS:
les Clefs Uniques alphabétiquement ordonnées ont une longueur <= Nombre_ de_Characteres; ie. les occurences (>1) d'un character ne sont pas pris en compte.
Exp: Allee |----> AEL

Example d'utilisation de la representation intervalaire des arbres Applique au SQL: http://sqlpro.developpez.com/Tree/SQL_tree.html
Cia!

mat.M · 23/09/2002, 11h20

As tu pensé à l'emploi de tables de hachage ??

**Muetdhiver** · 23/09/2002, 13h23

ca marche comment le hachage ? j'en entends parler souvent mais je me suis jamais penché sur la question.
Merci.
++

mat.M · 23/09/2002, 14h51

L'intérêt d'une table de hachage c'est par ex. selon une chaîne de caractêres en trouver une autre après avoir au préalable constitué la table.
C'est un moyen aisé pour constituer un dictionnaire ; sous Java il ya une classe particulière qui fait cela et en C++ parmi la Standard Template Library.Mais le pb sous Php je ne sais pas , peut-être existe-il une fonction toute faite quelque part sur Internet.
Par exemple avec les classes pour Windows de Microsoft ( MFC ) il ya la classe CMapStringToString :
CMapStringToString map;
map["Sunday"] = "Dimanche";
map["Monday"] = "Lundi";
map["Tuesday"] = "Mardi";
map["Wednesday"] = "Mercredi";

Cela ressemble à un tableau de chaines de caractêres . Mais on peut faire une recherche selon une clé représentée par une valeur chaîne :
CString string ; // classe de chaine de caracteres C++ des MFC
map.Lookup ("Sunday", string);// méthode de recherche de la classe
Et string vaut Dimanche...

**zwynx** · 23/09/2002, 19h14

Sinon, pour réduire la taille du dictionnaire, il y a une possibilité (en sacrifiant un peu de rapidité). Tu codes les mots eux-mêmes (LAPIN), mais avec l'ordre des mots du dictionnaire où les mots sont de type AILNP.
Tu réduis le temps de recherche, tout en gardant une petite taille.

**Musaran** · 24/09/2002, 00h56

Une table de hachage, cela consiste tout simplement à accompagner chaque entrée de ta base/table/conteneur/liste/ect d'un identifiant beaucoup plus court qui est calculé à partir de cette entrée de façon à être le plus représentatif possible (hash).

Pour recherchez un élément, on calcule son identifiant 'haché', et c'est lui qu'on recherche dans la liste (elle est organisée pour privilégier cela).

L'accès moyen est plus rapide, mais certains accès peuvent être beaucoup plus long car plusieurs éléments peuvent avoir le même identifiant, et il faut poursuivre avec une recherche classique.

Dans ton cas, on veut justement trouver toutes les entrées partageant le même identifiant, qui est précisément fait pour être le même pour des mots contenants les mêmes lettres en même nombre.

Si je ne me suis pas trompé, le calcul que j'ai proposé génère un tel identifiant 'anagramesque'.

En C++, on dispose du conteneur 'hash_map' qu'on peut paramétrer avec son propre calcul d'identifiant, et qui simplifie bien les choses.

**bouba64** · 25/09/2002, 17h02

Envoyé par Muetdhiver

Car si le code est 8, je ne sais pas si cela correspondra a
1 + 2 + 2+ 3 "abbc"
ou 1 + 1 + 3 + 3 "aacc" , etc...
++

Juste une remarque en passant par là,
Ol n'a pas dit a => 1, b=>2, c=>3 mais c=>4; il utilise une super suite (la somme des n premiers termes est strictement inférieure à au n+1 ème terme) ce qui rend le codage unique lorsque les lettres ne sont pas répétées.

**delphi-fan** · 04/11/2002, 11h21

D'une manière générale, le problème consiste à la base en une recherche itérative ou récursive.

Mais on peut modéliser ça avec des arbres, des fonctions de Hash, un dictionnaire et la connaissance implicite de la langue. Ex : après un Q il doit y avoir une voyelle ...

=> Ce processus s'appèlle techniquement la recherche d'HEURISTIQUES destinées à limiter l'exploration en profondeur (force brute).

Ce type de problème est particulièrement présent par exemple dans les échecs, où il faut absolument trouver des critères pour éliminer certaines branches de l'analyse, afin de conserver une durée de calcul raisonnable...

A+

**Exca** · 27/02/2005, 18h26

Désolé de remonter un topic aussi vieux mais je recherche l'algo pas à pas pour créer tous les anagrammes d'un mot sans le comparer à un dico de connées, je veux qu'il trouve toutes les solutions possibles même si le mot n'existe pas (je sais, c'est pas un anagramme dans ce cas mais bon...)

Merci ^^

**Denis++** · 27/02/2005, 23h39

Si c'est pour trouver toutes les solutions possibles, il n'y a pas d'autre solution que de produire toutes les permutations des lettres du mots (et c'est donc en n!, si n est la taille du mot).