Structure données Vs. Dictionnaire de mots

Biensûr, on ne va pas se contenter du stockage du dictionnaire dans la mémoire de l'ordinatoire, mais aussi, on doit prévoir:

• La recherche d'un mot
  
• L'ajout, modification, suppression
  
• Le tri du dictionnaire selon un ordre donné
  

La structure qu'on cherche doit présenter de très bonnes performance au niveau de toutes (ou la majorité) des routines citées ci-dessus.

Je pense que la meilleure structure pour charger un dictionnaire dans la mémoire c'est les arbres vu qu'ils exigent au pire des cas un déscente de profondeur LOG(n)/LOG(2) où n est le nombre d'information dans l'arbre (exemple: le nombre de mot du dictionnaire)

La chose que je dois faire des recherches dessus, c'est quel type d'arbre est plus adéquat pour les diverses opérations sur le dictionnaire: chargement, ajout, recherche, suppression...

J'essaierai de me documenter sur ce point.

informix a écrit:Je pense que la meilleure structure pour charger un dictionnaire dans la mémoire c'est les arbres vu qu'ils exigent au pire des cas une déscente de profondeur LOG(n)/LOG(2) où n est le nombre d'information dans l'arbre (exemple: le nombre de mot du dictionnaire)

il faut préciser que log(n)/log(2) est la complexité de la recherche d'un élément dans "un arbre binaire" et non pas dans tout type d'arbre
ou je me trompe?

La chose que je dois faire des recherches dessus, c'est quel type d'arbre est plus adéquat pour les diverses opérations sur le dictionnaire: chargement, ajout, recherche, suppression...
J'essaierai de me documenter sur ce point.

Je pense que ça dépend de la conception. càd de ce qu'on va stocker dans l'arbre: des mots, ou des lettres...?

Je ne pense pas qu'on peut répondre par dire:
Telle structure est la meilleure (absolue) pour représenter un dictionnaire dans la mémoire. Pour la simple raison qu'un jour J, on peut inventer une structure plus adaptée que celle qu'on a choisie.
De plus, dans tout problème il y a le compromis: si on optimise la vitesse (le nombre d'opération de calcul...) on consomme plus d'espace mémoire et inversement...

je propose détudier chaque structure à part...

En séquentiel = un dictionnaire d'un million de mot nécessite au max un million d'opération de lecture/comparaison de la mémoire.
En arbre binaire= ca ne nécessite que 20 actions.

Quelle différence !!!!!

Moi j'opte pour une table de hasahge plutôt qu'un arbre. Les problèmes avec ses table sont :
- une clé de hashage adaptée
- la taille initiale de la table

manianis a écrit:Moi j'opte pour une table de hasahge plutôt qu'un arbre. Les problèmes avec ses table sont :
- une clé de hashage adaptée
- la taille initiale de la table

J'aime bien connaître les tables de hashage. Leurs définitions et leurs utilisations ? J'ajouterai un topic demain.

Voici une page Wikipedia qui explique les tables de hachage :

http://fr.wikipedia.org/wiki/Table_de_hachage

informix a écrit:Je ne pense pas qu'on peut répondre par dire:
Telle structure est la meilleure (absolue) pour représenter un dictionnaire dans la mémoire. Pour la simple raison qu'un jour J, on peut inventer une structure plus adaptée que celle qu'on a choisie.
De plus, dans tout problème il y a le compromis: si on optimise la vitesse (le nombre d'opération de calcul...) on consomme plus d'espace mémoire et inversement...

je propose détudier chaque structure à part...

Pas tres convaincant comme argument. Il y a bien des resultats qui nous disent que certaines operations ne peuvent pas etre implantees meilleur que certains algorithmes (+ data structures). Par ex, on sait que pour faire une tri base sur l'utilisation d'une relation d'ordre sur les element, la meilleure complexite qu'on peut atteindre est O(n log(n)). Ceci est independant des structures de donnees. Dans ce sens merge-sort, heapsort et companie sont optimals. Bien sur Bucketsort ne satisfait pas l'hypothese de l'utilisation de l'ordre, c'est pour ca qu'il a aussi une autre classe de complexite.

Al.

manianis a écrit:Moi j'opte pour une table de hasahge plutôt qu'un arbre. Les problèmes avec ses table sont :
- une clé de hashage adaptée
- la taille initiale de la table

Le dictionnaire ne peut pas etre "grand" alors. En general pour ce genre de trucs je crois qu'on utilise les a-b trees (pour a=2 et b=3 en general). Les donnees peuvent etre assez grandes et la repartitiion de l'arbre sur le disque permet l'utilisation persque parfaite des blocks. C'est Bayer and McKinsey. Bayer a aussi fait les B, puis R-trees pour ce genre de trucs.

Al.

Je me souviens que j'ai développé un petit Soft qui charge un dictionnaire de plus de 500.000 mots. J'ai utilisé les arbres binaires. La durée de chargement ainsi que toutes les opérations sur les mots: recherche, ajout, suppression etc... sont très très rapides (moins d'une 1 pour charger tout le dico) ...

nabiL a écrit:Je me souviens que j'ai développé un petit Soft qui charge un dictionnaire de plus de 500.000 mots. J'ai utilisé les arbres binaires. La durée de chargement ainsi que toutes les opérations sur les mots: recherche, ajout, suppression etc... sont très très rapides (moins d'une 1 pour charger tout le dico) ...

Maintenant je me rend compte que le probleme c'est ce charger le truc dans la memoire (donc les donnnees ne peuvent pas etre assez grandes ded toutes facon --- grand de l'ordre de centaine de gigas, enfin pour le moment).

Bien sur ces trucs dependent des operations qu'on veut faire, mais moi j'opetrais pour les suffix-trees, si les entrres du dictionnaire sont des "strings". Ou un des tries en general.

Al.

Pour ceux qui ne connaissent pas les suffix-trees:
http://en.wikipedia.org/wiki/Suffix_tree

Est-ce que tu peux argumenter pourquoi tu as choisi les suffix-trees comme structure de données de stockage du dictionnaire?

j'ai vu quelques uns qui proposent les arbres binaires!!!!! mais c'est pas possible avec les arbres binaires(je vois ca personnelement)il faut utiliser les arbres generaux en commencant par le noeud vide,et en mettant aux feuilles un marquer de fin de mot(la feuille est le bas de l'arbre c a dire chaque noeud sans fils)
et l'avantage des arbres c'est qu'on va utiliser les fonctions recursives qui sont trééééés facile a ecrire
pour la recherche on parcourt la liste des fils du noeud juska trouver la premiere lettre du mot,si on la trouver on reappelle notre fonction sur l'arbre trouvée et sur le mot en supprimant la premiere lettre,et la recherche est fructueuse si on tombe sur une feuille et en meme temps le mot est vide

voila un exemple c le dictionnaire qui contient les mots indormatique,information,indispensable,lol,long longueure et longue avec le marqueur du fin qui est * et le noeud du debut qui contient +
----------+-----------------
/ \
/ \
i l
| |
| o
n | \
/ \ l \
/ \ | n
d f * \
| | g---u
i o | \
| | * e--u--r
s r | \
| | * e--*
p m
| |
e a
| |
n t
| |
s i
| |\
a o \
| | \
b n q
| | |
l * u
| |
e e
| |
* *

moudhafer a écrit:j'ai vu quelques uns qui proposent les arbres binaires!!!!! mais c'est pas possible avec les arbres binaires(je vois ca personnelement)il faut utiliser les arbres generaux en commencant par le noeud vide,et en mettant aux feuilles un marquer de fin de mot(la feuille est le bas de l'arbre c a dire chaque noeud sans fils)
et l'avantage des arbres c'est qu'on va utiliser les fonctions recursives qui sont trééééés facile a ecrire
pour la recherche on parcourt la liste des fils du noeud juska trouver la premiere lettre du mot,si on la trouver on reappelle notre fonction sur l'arbre trouvée et sur le mot en supprimant la premiere lettre,et la recherche est fructueuse si on tombe sur une feuille et en meme temps le mot est vide

voila un exemple c le dictionnaire qui contient les mots indormatique,information,indispensable,lol,long longueure et longue avec le marqueur du fin qui est * et le noeud du debut qui contient +
----------+-----------------
/ \
/ \
i l
| |
| o
n | \
/ \ l \
/ \ | n
d f * \
| | g---u
i o | \
| | * e--u--r
s r | \
| | * e--*
p m
| |
e a
| |
n t
| |
s i
| |\
a o \
| | \
b n q
| | |
l * u
| |
e e
| |
* *

Tu te trompes si tu dis: Ce n'est pas possible avec Arbres Binaires !

Regarde ce lien : http://fr.wikipedia.org/wiki/Arbre_binaire

et qui t'as dit que l'arbre binaire du dictionnaire est formé d'uniquement 26 noeuds ?!

On peut stocker un dictionnaire à une taille arbitraire dans un arbre binaire former par les préfixes communs des mots.

Les mots AAB, AAC, AAXYZ ont tous les mêmes préfixes "AA".

Ce qui en découle que "AA" occupe deux noeuds successifs, et permet d'avancer dans la recherche des 3 mots cités dans l'exemple.

Je ne sais si tu as saisi notre point de discussion ou non: on parle de la faisabilité de stocker un dictionnaire de mots sous forme d'arbre binaire.
Toi tu dis NON. et moi je dis OUI.

oui mais la question au debut c'est propser une structures de données,moi j'ai proposé les arbres generaux et j'ai dessiner un bon dictionnaire qui est claire mais lorske j'ai publié mon commentaire ca c'est perdu
et a propos les arbres binaires c'est pas une trés bonne idée,car a la base dans les arbres binaires chaque element on le trouve qu'une seule fois,ça a la base mais aprés on peut tout modifier.
et j'ai pas dit NON j'ai dit c'est pa la meilleur idée pour implementer les recherches et les ajouts

moudhafer a écrit:oui mais la question au debut c'est propser une structures de données,moi j'ai proposé les arbres generaux et j'ai dessiner un bon dictionnaire qui est claire mais lorske j'ai publié mon commentaire ca c'est perdu
et a propos les arbres binaires c'est pas une trés bonne idée,car a la base dans les arbres binaires chaque element on le trouve qu'une seule fois,ça a la base mais aprés on peut tout modifier.
et j'ai pas dit NON j'ai dit c'est pa la meilleur idée pour implementer les recherches et les ajouts

Pas très convaincant !!! Tu as des preuves ?
Je vote pour "les arbres binaires" plus appropriés que "Arbres généraux" pour un dictionnaire.

re
en fait propos les arbres binaires je vois pas comment tu va les implémenter??imaginons on veut ecrire le dictionnaire "abc"..on va mettre au premier noeud "a" et on va mettre dans son fils droit "b" (arbre binaire de recherche) et dans le fils droit de "b" on va mettre "c",ok il n'y a pas de probleme jusqu'a maintenant,et si on veut ajouter le mot "abd" ???je vois pas comment on va l'ajouter???
je t'ajoute,l'avantage des arbres binaires est que la recherche est en log(n),alors pour garder cette propriété il faut à chaque suppréssion ou ajout d'un nouveau mot il faut effectuer les opérations de reéquilibrage,ce qui est un peu lourd puisqu'on va faire beaucoup d'ajout et de suppréssion.
Propos mon idée avec les arbres généraux,il suffit de bien implementer la structure de l'arbre,surtout la structure de la forêt(liste des arbres fils) on implemente une liste chainée triée avec ajout et suppression et recherche en place.

moudhafer a écrit:re
en fait propos les arbres binaires je vois pas comment tu va les implémenter??imaginons on veut ecrire le dictionnaire "abc"..on va mettre au premier noeud "a" et on va mettre dans son fils droit "b" (arbre binaire de recherche) et dans le fils droit de "b" on va mettre "c",ok il n'y a pas de probleme jusqu'a maintenant,et si on veut ajouter le mot "abd" ???je vois pas comment on va l'ajouter???
je t'ajoute,l'avantage des arbres binaires est que la recherche est en log(n),alors pour garder cette propriété il faut à chaque suppréssion ou ajout d'un nouveau mot il faut effectuer les opérations de reéquilibrage,ce qui est un peu lourd puisqu'on va faire beaucoup d'ajout et de suppréssion.
Propos mon idée avec les arbres généraux,il suffit de bien implementer la structure de l'arbre,surtout la structure de la forêt(liste des arbres fils) on implemente une liste chainée triée avec ajout et suppression et recherche en place.

Bonjour,
Tant qu'il y a équivalence entre arbre binaire et arbre n-aires, la faisabilité avec les arbres binaires ne doit plus poser de problèmes. Je ai créé un exemple illustratif d'un arbre binaire qui contient les mots suivants:

ABC, BAC, BCA et CA.




Poursuivons la discussion.

salem
mais ça c'est pas un arbre binaire de recherche!!!dans ce cas les recherches d'un mot ne resteront pas en O(log(n)),dans ce cas la recherche sera en O(n) il faut parcourir tout les noeuds au moins un fois,c pas un peu couteux???

Je sais que ce n'est pas un arbre binaire de recherche. Mais il est binaire d'après l'équivalence prouvée entre N-aire & Binaire.

C'est la même complexité qu'avec les arbre n-aires généraux.

Tout dépend des mots du dictionnaire. Plus ils ont des préfixes en commun, plus le dictionnaire est léger (un nombre réduit de noeuds ou feuilles).

Même avec les arbres généraux la recherche est en O(n).

Question ouverte

Pour un dictionnaire quelconque contenant "m" mots de longueurs variant de 1 à 5 lettres, peut-on calculer/estimer le nombre maximal de comparaisons pour chercher un mot de longueur 5. Le problème peut être mal posé, proposer des rectification si c'est le cas.

en addition c'est quoi le marquer du fin et debut de chaque mot?personnelement je vois que ce dictionnaire contient les mots :ABC,ABAC,ABACA et ABCA

moudhafer a écrit:en addition c'est quoi le marquer du fin et debut de chaque mot?personnelement je vois que ce dictionnaire contient les mots :ABC,ABAC,ABACA et ABCA

Dans l'image, les noeuds en bleu contiennent des marqueur de fin du mot.
Par contre, il n'y a pas de marqueur de début d'un mot. Comme dans les arbres n-aires, tous les mots ont la même racine qui est le vide ou une lettre bidon "$".

Je connais un étudiant qui a développé ça en JAVA. Je ne sais pas s'il a publié son applet sur Internet ou non. Un genre de correcteur orthographique ou syntaxique simple pour la langue française.

d'accord,j'ai compris.moi aussi je l'ai developpé en ocaml,avec les fonctions d'ajout supression et recherche.je vais poster sur le forum un peu de code et quelques jeux d'essai