Discussion :

[pekka77]

Bonjour,

Imaginez une liste très longue de mots par exemple. Mon but est de créer un algorithme qui permet de filtrer cette liste à partir de plusieurs caractères afin de trouver la correspondance exacte. Il faut que cet algorithme soit très performant.
Un exemple pour etre un peu plus clair :
J'ai une liste de noms (stockée dans une bdd par exemple) et un formulaire ou je dois entrer un nom. Celui-ci doit correspondre à un des noms contenu dans la liste. Au fur et à mesure que je tape le nom, une liste de plus en plus réduite m'est proposé (on peut imaginer que cette liste n'est affichée que lorsque celle-ci se réduit à 10 noms)

Selon vous quelle est la meilleure manière de procéder ? Auriez vous un algorithme à me proposer ?

On m'a conseillé de me pencher sur les trigrammes...
Qu'en pensez-vous ?

Merci beaucoup pour vos réponses

[PRomu@ld]

Je pense à un tri radix ...

Tout dépend de la structure de donnée pour stoquer les données. Si tu as un dictionnaire (un arbre), le tout est de parcourir ton arbre pour y descendre au fur et à mesure que tu tappes les lettres ...

[Betatesteur]

j'opterai pour une recherche par dichotomie. (rapide qui t'éviterai des test à n'en plus finir vu que ces une grosse bdd genre 40000 mots)

[SLE]

j'opterai pour une recherche par dichotomie. (rapide qui t'éviterai des test à n'en plus finir vu que ces une grosse bdd genre 40000 mots)

C'est très bien mais une recherche par dichotomie nécessite une liste TRIEE ! Or je ne suis pas certain que sa liste le soit !

[Betatesteur]

autant pour moi
http://www.di.ens.fr/~granboul/enseignement/mmfai/algo2000-2001/tp4/tp4.html
c'est à peu près ça.

Mais si t'as tes 40000 mots dans une SGBDR ils seront forcement trié. pourquoi ne pas utiliser le sql pour faire ton appli.???

[10_GOTO_10]

Un autre moyen pour éviter le tri est de stocker les mots dans un arbre AVL. Ca garantit une optimisation de la recherche (mais au prix d'un peu de gaspillage de mémoire).

Pour en savoir plus, clique ici, par exemple

[pekka77]

Ah je vois que c'est un sujet qui attire les réponses. C'est super.
J'ai oublié de préciser une chose très importante. J'aimerai que la liste des noms qui s'affichent tolère des fautes d'orthographe.
Par exemple, si "DUPONT" se trouve dans la liste, il doit s'afficher si je commence par taper "DUIPO" (insertion de caractère)
Voilà l'élément que je voulais rajouter.
Je vais maintenant regarder plus en détail les solutions que vous me proposez.

Merci bcp !

[Graffito]

Bonjour,

On a droit aux orthographes voisines ca change tout !!!

Pour les orthographes exactes, j'ai implémenté du temps où les machines ramaient un arbre avec un niveau par lettre (tout les mots étant terminés par un caractère de fin spécial) qui présentait d'excellente performances.

Exemple (caractère de fin #) pour les mots A AU AMI BU

Code :

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

1
2
3
4
5
6
7
8
9
<racine>
|
A------------B
|            |
#-M-U        U
  |          | 
  I          #
  |
  #

Pour les orthographes approchantes, le problème est d'autant plus complexe qu'on ne connait que le début du mot. Il faudrait vérifier si les caractères dèjà tapés correspondent "à peu prés" au début des mots du dico.

Pour déterminer l'algorithme de parcours le plus adapté, il faut d'abord définir avec précision le critére de proximité (proportion de lettre communes, ordre des lettres, doublement de lettre, accents, ...) entre le début de mot tapé et un mot quelconque du dictionnaire.

[Mucho]

Si j'étais toi j'irais voir du coté de la bio-informatique,

je me rappelle d'avoir utilisé plein d'algorithmes de reconnaissance de chaîne de caractères pour les recherches dans les chaînes d'acides nucléiques :

du genre rechercher ACC*GT dans

AGTTCGGTAAATTGGAAGCCCTAAAGCTAGCTAGCAATAAGCTAAGCTAGAACTAAGATATTTTCGA

où une étoile peut vouloir dire n'importe quoi ou rien.

[SLE]

Est-ce que cet article peut t'intéresser ?

http://www.codeproject.com/useritems/Soundex.asp

@+