Discussion :

[saad.hessane]

Bonjours tout le monde,
J'ai un petit problème d'algorithme.
Voilà, j'ai un dictionnaire de mots, et je veux vérifier que les occurrences de lettres fournies en entrées s'y trouve(dans le dictionnaire). Un peu comme dans le jeu "Des chiffres et des lettres" sur France 2.
Prenons un exemple : Je donne en entré ABC. Les occurrences de ces lettres sont :
ABC-ACB-BAC-BCA-CAB-CBA.
Les deux mots existant dans le dictionnaire sont BAC et CAB.
Comme première idée, j'ai pensé à utiliser la méthode humaine qui justement consiste à lister toutes les possibilités puis de chercher dans le dictionnaire avec une recherche dichotomique.
Mais là on a un algorithme très complexe. Je ne suis pas expert en complexité d'algorithme, mais pour N lettres fournies en entrées, je croies que nous avons N! possibilités...
Si vous avez une idée d'amélioration je suis preneur.

[ToTo13]

Bonjour,

tous les dictionnaires sont construit sous forme d'une table de hashage (interrogation en 0(1)).
Donc tu peux lister toutes tes combinaison et faire ton interrogation rapidement.

Je ne suis pas sûr qu'il existe des clefs de hashage qui prennent en compte la présence de certaines lettres plus que d'autres. Cela ferait perdre la faible complexité d'interrogation du dictionnaire.

[saad.hessane]

Et je suis obligé de lister toutes possibilités? N'y a t il pas possibilité de consulter la BD grâce à une regex ou autre?

[pseudocode]

Et je suis obligé de lister toutes possibilités? N'y a t il pas possibilité de consulter la BD grâce à une regex ou autre?

Heu non. On ne teste que les entrées en BD qui ont le même hash. Et si la BD est bien faite (index btree), lister toutes les entrées qui ont un hash donné est en o(log(n)) ou "n" est le nombre de hash differents.

[kael kael]

Tu peux avoir 26 compteurs pour chaque mot (si tu n'as que 26 lettres). Chaque compteur donne le nombre d'occurrences d'une lettre dans le mot.
Ensuite tu recherches tous les mots tel que le nombre de A est 1, le nombre de B 2, le nombre de C 0, ...

Autre possibilité, dans ta BD tu tries chaque mot (et tu stockes les 2 : le mot d'origine et le mot trié).
Ensuite, quand tu as un mot en entrée, tu le tries et tu recherches les mots, dans ta BD, qui correspondent à ce mot trié.

[droggo]

Gie,

Une solution pourrait être de maintenir une table d'anagrammes.

Pour chaque mot du dico, faire la suite classée des lettres, sans tenir compte des signes diacritiques (accents, cédille, ...).

Pour chaque suite de lettres ainsi obtenue, maintenir une liste des mots correspondant.

Ça ne me paraît pas gigantesque à faire, et ça accélérera très nettement la recherche comme tu veux la faire.

[saad.hessane]

Merci à vous tous, mais les hash & Co je n'y connais rien du tout.
La dernière idée me parait très bien.
Pour info, la longueur des mots sont entre 3 et 6 lettres, avec des caractères allant de 'A' à 'Z'. Donc ni accent ni cédille.
Pour chaque mot par exemple on pourrait mettre à coté le trie alphabétique de ses lettres.

AVOIR ===> AIORV
FAIRE ===> AEFIR

L'entrée aussi sera trié, pour s'écrire sur la même forme, avant d'être transmise à la requête. Vous en dites quoi?
Mais par exemple pour AVOIR, dedans il y a aussi le mot AIR, qui a pour signature AIR. Donc il faudra chercher toutes les occurrences de la signature de l'entrée. Vous en dites quoi de l'idée de droggo?