Forum INFOMATH
Vous souhaitez réagir à ce message ? Créez un compte en quelques clics ou connectez-vous pour continuer.
Le Deal du moment : -24%
PC Portable Gaming 15.6″ Medion Erazer Deputy ...
Voir le deal
759.99 €

Structure données Vs. Dictionnaire de mots

+2
informix
Napoléon
6 participants

Aller en bas

Structure données Vs. Dictionnaire de mots Empty Structure données Vs. Dictionnaire de mots

Message par Napoléon Sam 27 Oct - 21:37

Structure de données Vs. Dictionnaire

On se propose dans ce topic de faire une ptite recherche sur la meilleure structure de données qu'on doit utiliser pour charger un dictionnaire de mot dans la mémorie de l'ordinateur.

Structure données Vs. Dictionnaire de mots Dictionnaire
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue999/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par Napoléon Sam 27 Oct - 21:40

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.

afro
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue999/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par informix Dim 28 Oct - 11:56

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
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 6286
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par methodiX Dim 28 Oct - 18:06

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 confused
ou je me trompe? scratch

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...? scratch
methodiX
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par informix Mer 31 Oct - 23:30

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...
informix
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 6286
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par methodiX Dim 4 Nov - 0:45

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 !!!!!
methodiX
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par manianis Dim 4 Nov - 23:57

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
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6015
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue999/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par informix Lun 5 Nov - 1:07

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.
informix
informix
Nombre Rationnel
Nombre Rationnel

Nombre de messages : 399
Réputation : 4
Points : 6286
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par manianis Lun 5 Nov - 18:57

Voici une page Wikipedia qui explique les tables de hachage :

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

manianis
Nombre Réel
Nombre Réel

Masculin
Nombre de messages : 975
Localisation : Tunisie
Réputation : 4
Points : 6015
Date d'inscription : 11/10/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue999/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (999/1000)

http://manianis.sitesled.com/

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par Alkhawarizmi Ven 8 Mai - 13:22

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.

Alkhawarizmi
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 13
Localisation : sewf
Réputation : 9
Points : 5463
Date d'inscription : 06/05/2009

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par Alkhawarizmi Ven 8 Mai - 13:27

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.

Alkhawarizmi
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 13
Localisation : sewf
Réputation : 9
Points : 5463
Date d'inscription : 06/05/2009

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par Napoléon Ven 8 Mai - 17:01

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) ...
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue999/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par Alkhawarizmi Dim 10 Mai - 4:01

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.

Alkhawarizmi
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 13
Localisation : sewf
Réputation : 9
Points : 5463
Date d'inscription : 06/05/2009

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par Napoléon Mar 12 Mai - 1:11

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?
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue999/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par moudhafer Mer 26 Mai - 4:14

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 Smile
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 Wink

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
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 35
Localisation : france
Réputation : 0
Points : 5124
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par Napoléon Mer 26 Mai - 12:33

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 Smile
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 Wink

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
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue999/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par Napoléon Mer 26 Mai - 18:16

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.
Napoléon
Napoléon
Admin
Admin

Masculin
Nombre de messages : 2934
Localisation : Tunisie
Réputation : 122
Points : 7632
Date d'inscription : 19/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue999/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (999/1000)

https://infomath.1fr1.net

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par moudhafer Jeu 27 Mai - 1:47

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 Sad
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
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 35
Localisation : france
Réputation : 0
Points : 5124
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par methodiX Jeu 27 Mai - 13:00

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 Sad
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.
methodiX
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par moudhafer Dim 30 Mai - 16:04

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
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 35
Localisation : france
Réputation : 0
Points : 5124
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par methodiX Dim 30 Mai - 17:23

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.

Structure données Vs. Dictionnaire de mots Dico_a10


Poursuivons la discussion.
methodiX
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par moudhafer Dim 30 Mai - 18:52

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.

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 35
Localisation : france
Réputation : 0
Points : 5124
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par moudhafer Dim 30 Mai - 19:23

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
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 35
Localisation : france
Réputation : 0
Points : 5124
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par methodiX Mar 1 Juin - 0:45

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 Smile 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.
methodiX
methodiX
Admin
Admin

Masculin
Nombre de messages : 1260
Localisation : Le couloir de l'école polytechnique de Tunis
Réputation : 68
Points : 7014
Date d'inscription : 22/03/2007

Feuille de personnage
Capacité linguistique:
Structure données Vs. Dictionnaire de mots Left_bar_bleue1000/1000Structure données Vs. Dictionnaire de mots Empty_bar_bleue  (1000/1000)

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par moudhafer Mar 1 Juin - 19:07

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 Wink

moudhafer
Entier Naturel
Entier Naturel

Masculin
Nombre de messages : 58
Age : 35
Localisation : france
Réputation : 0
Points : 5124
Date d'inscription : 26/05/2010

Revenir en haut Aller en bas

Structure données Vs. Dictionnaire de mots Empty Re: Structure données Vs. Dictionnaire de mots

Message par Contenu sponsorisé


Contenu sponsorisé


Revenir en haut Aller en bas

Revenir en haut

- Sujets similaires

 
Permission de ce forum:
Vous ne pouvez pas répondre aux sujets dans ce forum