Trouver tous les anagrammes d'un mot (avec dico)

Soyez le premier à donner votre avis sur cette source.

Vue 131 729 fois - Téléchargée 1 554 fois

Description

Pour l'exe et le dico (trop lourd pour le site), telecharger http://perso.club-internet.fr/jbe/anagrammes.zip

Ben comme annoncé dans le titre de la source ce programme a pour but de vous faire devenir imbattable dans la résolution d'anagrammes (sans avoir à se prendre la tete inutilement ;-D ).
On commence par charger un dico : j'en ai trouvé un de 146.000 mots gratuitement il y a longtemps, je remercie chaleuresement le ptit gars qui a ecrit tout ca (même si certains mots n'existent pas et que d'autre ne font pas partie du dico c'est deja une bonne base !).
Tout le prog repose sur la notion d'arbres : chaque node (noeud) de l'arbre du dico represente une lettre et les leafs (feuilles) sont les mots finaux (ils representent le mot obtenu en alignant toutes les lettres des parents dans l'ordre de parenté). Une fois cette arbre construit (ce qui n'est pas tres long malgré la masse de travail), on peut commencer la recherche d'anagramme a proprement parler.
Encore une fois, c'est un arbre qui fait tout le travail : chaque node possede un champ Text qui contient toutes les lettres de l'anagramme pas encore utilisée dans cette partie de l'arbre, et donc chaque node crée un enfant par lettre pas encore utilisée pour lequel le champ Text ne contient plus une de ces lettres. (J'ai bien peur de n'etre clair que pour moi meme... :-S).

Mais bon, contruire tout l'arbre des anagramme, c'est long (le nombre du mot est en n!, avec n la longueur), et verifier si chaque mot qui en resulte appartient au dico, ca l'est encore plus ! C'est pourquoi on met a parti les arbres pour nous accelerer le boulot : l'info c'est comme la botanique, le but c'est de bien tailler les arbres :D => Les elements de l'arbre des anagramme conserve un pointeur vers le mot du dico correspondant, et dès qu'on s'apercoit qu'il n'existe aucun mot du dico possible avec les combinaisons commencées on ne continue pas a creer l'arbre. Exemple : j'entre l'anagramme TRUCS. On commencer a creer l'arbre et en s'apercevant qu'aucun mot ne commence par TC ou CT ou meme RC on elague pas mal la chose...

Voila j'espere avoir réussi a expliquer a peu pres le principe et vous permettre de bientot briller en societé :)

Source / Exemple :


Je met juste la déclaration des differents objets des arbres pour avoir une idée du code

type  //DICTIONNAIRE
  TDicoNodeStyle = (nsDicoNode,nsDicoLeaf);
  PDicoNode = ^TDicoNode;

  TDicoNode = class(TObject)
  private

  public
    Parent : PDicoNode;
    Level : integer;
    Child : array[0..26] of TDicoNode;
    ChildCount : integer;
    Style : TDicoNodeStyle;
    Letter : integer;
    Text : string;
    procedure AddWord(str: string);
    constructor Create(str : string; c : integer; Par : PDicoNode); virtual;
    destructor Destroy; override;
  end;

type  //ANAGRAMMES
  TAnaNodeStyle = (nsNode,nsLeaf,nsNone);
  PAnaNode = ^TAnaNode;

  TAnaNodeList = class;

  TAnaNode = class(TObject)
  private
  
  public
    Parent : PAnaNode;
    PDico : PDicoNode;
    Child : TAnaNodeList;
    Level : integer;
    Style : TAnaNodeStyle;
    Letter : char;
    Text : string;
    constructor Create(str : string; c : char; Par : PAnaNode; PDic : PDicoNode); virtual;
    destructor Destroy; override;
  end;

  TAnaNodeList = class(TObjectList)
  private
    function GetItem(Index: Integer): TAnaNode;
    procedure SetItem(Index: Integer; const Value: TAnaNode);
  public
    property Items[Index: Integer]: TAnaNode read GetItem write SetItem; default;
  end;

Conclusion :


J'ai remarqué la présence de doublons lorsqu'un mot contient plusieurs fois la meme lettre, et je vais essayer d'y remedier bientot (mais je chercher encore un moyen efficace de le faire, si vous avez une idée je suis preneur...). Sinon evitez juste d'entrer n'importe quoi dans le champ de texte (les lettres suffisent :P).

Codes Sources

A voir également

Ajouter un commentaire

Commentaires

Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
24
"1 dizaine de lignes" QU'ON VOIT dans le listing, mais combien de Ko STL qui bossent dans l'exe...
Grande plaisanterie que tout cela.
Messages postés
1
Date d'inscription
jeudi 8 juillet 2004
Statut
Membre
Dernière intervention
9 janvier 2010

Y a quand même beaucoup plus simple pour retrouver les anagrammes d'un mot.
Il suffit de trier les lettres d'un mot dans l'ordre lexicographique.
Exemple :
amer -> aemr
rame -> aemr
mare -> aemr
maree -> aeemr

Les anagrammes auront donc la même empreinte (le même hash).
On range çà dans une table de hachage (une std::map par exemple)
On a accès en temps constant à la liste des anagrammes d'un mot en calculant son hash
C'est ultra compacte. Le programme tient en une dizaine de ligne.
LireDico(const File *iDico,std::map<string,string>& oTable )
string hash,mot;
while(!NotEnded(iDico) )
LectureLigne(iDico,mot)
CalculerEmpreinte(mot,hash)
oTable.insert(hash,mot);

CalculerEmpeinte(const string& iMot, string& oHash)-> string
...

RetrouverAnagrammes(const string& iMot,
const std::map<...>& iTable,
std::list<string>& oAnagrammes)
string hash;

CalculerEmpreinte(iMot,hash);
std::map<...>::iterator it=iTable.find(hash);
while ( it!= iTable.end() )
oAnagrammes.push_back(it->second);

Voilà franchement 5 minutes à coder et beaucoup plus rapide (a optimiser si on veut en compressant les mots)
Messages postés
120
Date d'inscription
mardi 8 juillet 2008
Statut
Membre
Dernière intervention
1 décembre 2010
1
Bsr, Trois année plus tard, je ne trouve pas le dictionnaire, particulièrement pour tester la vitesse d'exécution (quand l'arbre grandit), par ce que j'ai réalisé presque le même travail mais en utilisant des bases de données!
Messages postés
1
Date d'inscription
vendredi 2 décembre 2005
Statut
Membre
Dernière intervention
2 décembre 2005

Bonjour a tous, je vais vous avouez que depuis le debut, tout ce que vous parlez me semble du chinois =S... je ne mis connais pas beaucoup en informatique mais je voudrais savoir comment utiliser ce programme qui me serais bien utile pour les anagrammes.Le problème est que : je le télécharge et ensuite quand il vien le temp de l'ouvrir après l'avoir ''d'ézipé'' mon ordinateur me dit que je ne peut l'ouvrir et qu'il me faut un autre programme.... je ne comprend pas comment faire... svp aidez moi à être capable de l'utiliser .
Messages postés
21042
Date d'inscription
jeudi 23 janvier 2003
Statut
Modérateur
Dernière intervention
21 août 2019
24
Pas du VB mais C et ASM.
Ce n'est pas le langage mais du format de fichier dont je te parlais, 1 mot par ligne oblige à une recherche de fin de ligne pour extraire le mot suivant. Essaie avec une table en début de fichier indiquant combien de chaque longueur et ainsi tu peux coller tous les mots et les extraire juste au moment de la recherche, plus besoin de tout mettre en mémoire et c'est hyper rapide.
Afficher les 11 commentaires

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (Abened)