Discussion :

[ram-0000]

Bonjour,

Je cherche un algorithme permettant de trouver le premier mot dans un dictionnaire (trié alphabétiquement, c'est la moindre des choses pour un dictionnaire) commençant par une chaine de caractères donnée en paramètre.


Par exemple avec le dictionnaire suivant :

Code :

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

1
2
3
4
abdiquer
absenter
abstentionniste
abuser

la recherche de "abs" doit retourner "absenter" et pas "abstentionniste"

J'étais parti sur une idée de recherche dichotomique modifiée afin de prendre en compte ce type de recherche mais je me demande s'il n'y a pas un autre algo plus performant que ce que je pourrais bien faire.

Merci d'avance de vos éclairages

[Alexis.M]

Peut-être devrais-tu construire un arbre préfixe de ton dictionnaire avec les fils ordonnés dans l'ordre lexicographique

[ram-0000]

Peut-être devrais-tu construire un arbre préfixe de ton dictionnaire avec les fils ordonnés dans l'ordre lexicographique

Le dictionnaire est assez gros (21 000 mots) et je ne suis pas sûr d'avoir assez de mémoire pour le construire, c'est pour une application sur un Android.

[kwariz]

Salut,
21.000 mots c'est pas énorme, en plus avec un arbre préfixe tu "factorises" beaucoup, tu peux aussi "factoriser" les suffixes dans une certaine mesure. Jette un coup d'oeil sur les dawg : http://en.wikipedia.org/wiki/Directe...lic_word_graph


EDIT: suite à la réponse de Alexis.M, il est évident qu'il faut sérialiser ta structure et non la construire sur place à partir d'une liste de mots.

[Alexis.M]

en fait si tu ne stockes que l'arbre, ça devrait prendre moins de mémoire que le fichier texte et au niveau de la rapidité de recherche tu es linéaire avec le nombre de lettres du préfixe.

[souviron34]

Personellement je pense que :

J'étais parti sur une idée de recherche dichotomique modifiée afin de prendre en compte ce type de recherche mais je me demande s'il n'y a pas un autre algo plus performant que ce que je pourrais bien faire.

une recherche dichotomique bien programmée est supérieure, sans mémoire supplémentaire.. (log(n) pour 1 coup, log2(n) pour plus, voire 26 fois moins si on a déjà les limites des lettres).

Mais je ne suis pas spécialiste des arbres..

[kwariz]

Salut,

Je pense qu'avec une bonne implémentation d'un arbre préfixe avec les enfants triés lexicographiquement comme le propose Alexis.M, sans pousser jusqu'au dawg, sera plus compacte qu'un tableau de chaînes triées (surtout pour un dictionnaire de 210000 mots).
Les proportions dans lesquels ont peut profiter de la compression par prefixe (voire par suffixe) est variable et dépend non seulement des mots (ici un dictionnaire propose un grand nombre de mots ayant des préfixes communs), l'alphabet utilisé (on ne garde que des majuscules, ou on garde majuscules, minuscules, caractères accentués, ...), l'encodage utilisé (iso8859, utf8, ...).
Ça fait du boulot avant, mais faut voir à l'usage et faire des tests je pense.

[ram-0000]

Pour l'instant, j'ai réalisé une recherche par dichotomie avec une modification spécifique pour rechercher le premier mot commençant par la chaine recherchée. Avec un dico de 250 mots (pour l'instant), je trouve en 8 coups (ce qui est nettement mieux que mon 1er algo "brutal" qui itérait sur l'ensemble du dictionnaire.

Par contre, je vais regarder vers l'algo dawg, cela à l'air intéressant. Ce qui me pose problème, c'est le fait que je soit obligé de reconstruire cet arbre à chaque lancement (et aussi peut être le temps de construction.

De toute façon, je suis obligé d'emmener le dictionnaire dans l'application. Je ne peux pas me contenter uniquement de l'arbre (même s'il est construit extérieurement).

En tout cas, merci à tous pour vos réponses.

[kwariz]

Effectivement, si tu as de l'information supplémentaire comme des définitions cela peut être moins intéressant ... à moins d'utiliser l'arbre comme index ... mais ça peut compliquer les choses surtout si c'est pour une petite plateforme.