Bienvenue sur le forum !

Si vous souhaitez rejoindre la communauté, cliquez sur l'un de ces boutons !

Qt 5 : 5.9.1 - Qt Creator : 4.3.1 - Qt Installer : 2.0.3 - JOM : 1.1.2 - Qt Build suite : 1.7.0 - VS Qt 5 : 2.0.0

[Qt4] Gestion d'un dictionnaire de mots

Salut,

J'ai juste un petit conseil à vous demander, j'aimerais savoir quelle est à votre avis la meilleure structure de données pour stocker un dictionnaire (de 360 000 mots) afin de pouvoir faire des traitements rapides sur celui-ci comme rechercher si un mot existe, retourner la liste des mots commencant ou finisssant par certaine lettre...

Je pensais le ranger dans une table de hashage (QHash) mais ce n'est pas très pratique pour trouver les mots commencant par "es" et finissant par "s" par exemple, alors je pense peut-être à une base de données (comme SQLite) mais je ne suis pas sur que c'est la meilleure solution, c'est pourquoi je vous sollicite !

Alors quelle structure utiliseriez-vous ?

PS : C'est pour un jeu de scrabble.

Réponses

  • December 2006 modifié
    Salut,

    Tu donnes l'exemple de "commençant ou finissant par", mais pour un scrabble, j'imagine que tu as aussi le "contient"? Le tout sur 0 à plusieurs contraintes possibles donc.
    Si c'est bien ça, je n'utiliserais aucune structure existante, je développerais la mienne :)
    La raison étant que tu vas passer ton temps à faire des recherches dans des chaînes de caractères, peu importe la solution que tu prennes. Le QHash est bien évidemment éliminable d'emblée; SQLite est la solution existante la plus appropriée.

    Edit: et encore non, j'ai dit une bêtise, SQLite n'est pas adapté car tu ne peux rechercher des lettres dans le désordre :/

    Reedit: je viens de penser qu'un bête grep avec une regexp sur une qstringlist pourrait faire l'affaire :D

    Rereedit: Je viens de découvrir ça: boost::multi_index C'est à cette solution que j'ai pensé en premier sans savoir qu'elle existait :)
    Donc, si tu veux pas te prendre la tête avec les RE, ça peut le faire aussi. A toi de faire des benches histoire de voir le plus rapide dans telle ou telle condition et d'en tirer tes conclusions.
  • Finalement je n'ai besoin pour l'instant que de tester l'existance d'un mot, c'est pour l'intelligence artificielle que je vais avoir besoin de plus et ca je ne me suis pas encore penché dessus !

    Tu penses franchement qu'un grep sur une QStringList c'est rapide ? J'ai pas testé mais j'ai des doutes, ca fait parcourir toute une liste (de 360000 elements :S) !

    Ah et il faudrait aussi que la création du dictionnaire soit rapide, qu'il n'y ait pas 30 secondes d'attente au lancement du programme, faut que je vois ca avec ce multi_index, j'ai pas encore lu.

    Sinon j'ai une question niveau licence, est-ce que j'ai le droit de distribuer un programme utilisant Qt sans distribuer mes sources ?
  • Le multi_index alors, ou une solution s'en approchant.
    bobti89 said:
    Sinon j'ai une question niveau licence, est-ce que j'ai le droit de distribuer un programme utilisant Qt sans distribuer mes sources ?
    Si tu utilises la version open source de Qt, c'est non.
  • SQLite serait un bon debut pour ton dictionnaire, apres a toi de maitriser le langage SQL.

    tu peux ensuite rechercher ( pour ce que tu donne en exemple ) :

    si un mot existe:
    SELECT id_word FROM WORDS WHERE LOWER( word ) = 'ton mot que tu trim et passe en minuscule'

    retourner la liste des mots commencant ou finisssant par certaine lettre
    SELECT id_word FROM WORDS WHERE LOWER( word ) LIKE 'ton expression en minuscule'

    trouver les mots commencant par "es" et finissant par "s"
    SELECT id_word FROM WORDS WHERE LOWER( word ) LIKE 'es%s'

    Les expressions regliere sur 360 000 mots jy croi pas trop :p

    P@sNox,
Connectez-vous ou Inscrivez-vous pour répondre.