IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Algorithmes et structures de données Discussion :

Dictionnaires : comment les implémenter ?


Sujet :

Algorithmes et structures de données

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Nouveau candidat au Club
    Homme Profil pro
    Ingenieur mecanique
    Inscrit en
    Septembre 2016
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Ingenieur mecanique

    Informations forums :
    Inscription : Septembre 2016
    Messages : 2
    Par défaut Dictionnaires : comment les implémenter ?
    Bonjour tout le monde je suis nouveau sur le forum et j'espère que je suis tombé sur le bon. J'ai toujours été fasciné par les dictionnaires. ça fait longtemps que je cherche les méthodes dont les ils sont programmés: certains proposent des structures sous forme d'arbre arbre naire mais je pense que ces dernières consomment trop de mémoire dès que le contenu devient important par ailleurs je ne sais pas si on utilise une boucle de recherche qui a aussi le problème du temps de recherche.
    ma question est-ce que vous pouvez m'aider à comprendre comment sont programmés le dictionnaire pratiquement.
    Je vous remercie d'avance.

  2. #2
    Membre Expert
    Homme Profil pro
    sans emploi
    Inscrit en
    Janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : Janvier 2014
    Messages : 539
    Par défaut
    Bonjour,
    une structure particulièrement compacte pour stocker un lexique est le graphe dirigé acyclique, DAG pour les intimes. On préfère le terme de lexique (liste de mots) à dictionnaire (liste d'entrée avec des informations attachées).
    Un DAG est une structure compacte car il profite d'une sorte de factorisation des préfixes et des suffixes. Pour obtenir un DAG ce n'est pas trop trop compliqué, tout va dépendre de ton niveau en algo. On part d'un arbre n-aire qu'on implémente sous forme binaire (classiquement fils gauche-frère droit). Une fois cet arbre construit on peut le réduire en cherchant les sous-arbres identiques avec une recherche bottom top et en les fusionnant. On arrive à une structure nommée DAWG (direced acyclic word graph) utilisé dans de nombreux jeux de mots.
    Pour les jeux de mots où on peut «construire» un mot à partir du milieu (comme au scrabble) et en s'attachant à d'autres mots il y a ce qu'on appelle un GADDAG, le DAG va non seulement contenir les mots «normaux» mais aussi les mots décalés.
    Je pense que tu as déjà pas mal de sources d'infos à creuser N'hésite pas si tu as d'autres questions.

  3. #3
    Responsable Qt & Livres


    Avatar de dourouc05
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Août 2008
    Messages
    26 772
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : France, Val de Marne (Île de France)

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Multimédia et Internet

    Informations forums :
    Inscription : Août 2008
    Messages : 26 772
    Par défaut


    Si tu parles de la structure de données, tu pourrais trouver des éléments de réponse dans http://tcuvelier.developpez.com/tuto...es-donnees/#LV.
    Vous souhaitez participer aux rubriques Qt (tutoriels, FAQ, traductions) ou HPC ? Contactez-moi par MP.

    Créer des applications graphiques en Python avec PyQt5
    Créer des applications avec Qt 5.

    Pas de question d'ordre technique par MP !

  4. #4
    Nouveau candidat au Club
    Homme Profil pro
    Ingenieur mecanique
    Inscrit en
    Septembre 2016
    Messages
    2
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Localisation : Algérie

    Informations professionnelles :
    Activité : Ingenieur mecanique

    Informations forums :
    Inscription : Septembre 2016
    Messages : 2
    Par défaut
    Bonjour je trouve que finalement la définition de dictionnaire dans la programmation inclus tout type de donnee, moi je m'intéresse précisément au dictionnaire de définition linguistique où on a pas besoin d'insérer souvent des informations on a plutôt besoin de consulter juste la définition. Avec les arbres naire de 26 liaison chaqune pour une dixaine de niveu (mot le plus long ) alors la j'aurai besoin de la memoir du silicon valey. j' ai ponsé a supprimer les pointeurs non utilisés cequi reviens a creer une classe neud qui a just le nombre d'attributs necessaire (je ne sais pas si ca existe??? )
    Ou comment on fait pour reduir ces blancs car pour les supprimer il faut d'abord creer la totalite du dictionnaire qui est enorme.
    Merci

  5. #5
    Membre Expert
    Homme Profil pro
    sans emploi
    Inscrit en
    Janvier 2014
    Messages
    539
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 52
    Localisation : France, Moselle (Lorraine)

    Informations professionnelles :
    Activité : sans emploi
    Secteur : Conseil

    Informations forums :
    Inscription : Janvier 2014
    Messages : 539
    Par défaut
    Non, le vocabulaire est trompeur. Ce qu'en jargon informatique français on appelle dictionnaire est une structure de donnée particulière qui à une clé associe une ou plusieurs valeurs, en anglais on parlera de map en général et parfois de dictionary.

    Relis mon message qui fait la distinction entre un lexique et un dictionnaire. J'ai bien compris que tu parlais de lexique et que ta question portait sur une implémentation informatique d'un lexique. Tu surestimes énormément la taille d'un lexique en tant que tel et sa taille implémentée.

    Prenons le lexique ODS7 (officiel du scrabble 7ème édition). Il contient 393670 mots de 2 à 15 lettres. Le fichier fait 4.2Mo, autant dire que de nos jours c'est peanuts. Même si tu ne fais pas attention à ton implémentation et en étant très large, la structure en mémoire ne devrait pas dépasser la bonne centaine de Mo, ce qui est toujours de nos jours sur les plateformes classiques peanuts.
    Une implémentation avec un DAWG permet de tout faire tenir dans quelques Mo, car on tire profit de la redondance naturelle des langues (en français beaucoup de pluriels se forment en s, les verbes du 1er groupe on souvent les même terminaisons, …).

Discussions similaires

  1. Réponses: 6
    Dernier message: 11/07/2013, 12h04
  2. Réponses: 1
    Dernier message: 22/03/2013, 18h32
  3. Comment sont implémentées les listes Python ?
    Par rambc dans le forum Général Python
    Réponses: 8
    Dernier message: 15/12/2012, 14h17
  4. Réponses: 1
    Dernier message: 19/03/2008, 12h56
  5. Euler/Runge-Kunta: Comment les implémenter
    Par progfou dans le forum Algorithmes et structures de données
    Réponses: 21
    Dernier message: 27/02/2006, 22h52

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo