recherche dichotomique en C dans fichier Résolu/Fermé

Question

Bonjour, j'ai un petit problème en langage C... Je cherche à faire une recherche dans un fichier contenant un dictionnaire, c'et pour un programme de scrabble... Dnc j'ai besoin de faire une recherche dichotomique dans mon fichier pour savoir si le mot que j'ai a vérifier existe.
Le problème est que je ne sais pas vraiment comment utiliser la recherche dichotomique dans un fichier, puisque ça ne fonctionne pas de la meme manierre que dans un tableau.
Si vous savez comment faire et que vous avez du temps à me consacrer, merci d'avance!!!

batmat · Accepted Answer

ben, tu lis le fichier et tu le charges dans un tableau... (en RAM donc)@++Vous hésitez entre Linux et Windows ?Vous voulez dépenser du temps ou de l'argent ?

Lord Woden · Answer

Salut,

Avant tout je crois qu'il serait utile que tu précises exactement ce que tu veux dire dans "un fichier contenant un dictionnaire". Je veux dire qu'il faudrait préciser le type de format de fichier et la structure de données employé pour conserver ton dictionnaire.

En effet, comme tu parles de ta capacité à faire cette recherche dans un tableau mais pas un fichier je penses que c'est de là que vient ton problème?

@+ Lord Woden ;o)

batmat · Answer

De toute façon, à moins que ton fichier ne fasse plus de quelques Mo, il vaut mieux le charger en mémoire justement... sinon ta recherche va être extrêmement lente.

@++

Vous hésitez entre Linux et Windows ?
Vous voulez dépenser du temps ou de l'argent ?

dodie · Answer

oui, désolée, j'ai oublié de préciser.
C'est un fichier txt, qui contient environ 360 000 mots.
J'ai réussi à effectuer cette recherche avec un simple strcmp, mais il se trouve que cela ralentit notre programme de scrabble, donc je pensais effectuer une recherche dichotomique pour gagner su temps. Le problème de créer un tableau de mots contenant mon dico c'est que ce serait beaucoup trop lourd, alors je ne sais pas comment faire pour faire cette recherche dichotomique sans passer mon fichier txt en tableau.

j'espère avoir été un peu plus claire...

dodie · Answer

je vais peut etre vous paraître stupide, mais qu'est-ce que tu entends par passe le en ram? je comprends ce que tu veux dire, mais je ne vois pas du tout comment faire ça.
je ne suis pas très douée en C, en fait je n'ai commencé qu'il y a quelques moi et je reconnais que tout ce qui concerne la mémoire est un peu flou pour moi...

p.legal · Answer

J'ai fait un petit prog en basic et voici les resultats:

analyse du dico en cours...
Le programme a trouvé 369085 Mots dans le dico.
chargement en cours
100%
creation des phrases...
creation de la phrase 739 / 739
quel mot voulez-vous chercher
?MAISON
ce mot est bien dans le dico
temps de recherche : 141 ms
quel mot voulez-vous chercher
?ZYGOMATIQUE
ce mot est bien dans le dico
temps de recherche : 281 ms
quel mot voulez-vous chercher
?AVION
ce mot est bien dans le dico
temps de recherche : 0 ms
quel mot voulez-vous chercher
?MAISON
ce mot est bien dans le dico
temps de recherche : 141 ms
quel mot voulez-vous chercher
?LOIRE
ce mot est bien dans le dico
temps de recherche : 16 ms
quel mot voulez-vous chercher
?

j'ai un dico de 370 000 mots
je le charge en memoire dans un tableau puis je cree des phrases de 500 mots chacunes

enfin je teste la presence du mot que je cherche dans l'une de ces phrases.

si tu veux la source la voici:

        print "analyse du dico en cours..."
        open "dico.txt" for input as #dico
            while eof(#dico)=0
                scan
                line input #dico, mot$
                mot$=upper$(word$(mot$,1))
                if mot$=mot2$ then goto [reload.cnn]
                nb=nb+1
                if int(nb/5000)=nb/5000 then locate 1,2:print nb
                mot2$=mot$
                [reload.cnn]
            wend
        close #dico
        locate 1,2:print "Le programme a trouvé ";nb;" Mots dans le dico."
        print "chargement en cours"
        nbt=nb
        dim dico$(nbt)
        nb=0
        open "dico.txt" for input as #dico
            while eof(#dico)=0
                scan
                line input #dico, mot$
                mot$=upper$(word$(mot$,1))
                if mot$=mot2$ then goto [reload.cnt]
                nb=nb+1
                mot2$=mot$
                if int(nb*100/nbt)=nb*100/nbt then locate 1,4:print using("###",(nb*100/nbt));"%"
                dico$(nb)=mot$
                [reload.cnt]
            wend
        close #dico
        print "creation des phrases..."
        nbph=int(nbt/500)+1
        'print nbph
        dim ph$(nbph)
        trace 2
        for i=1 to nbt
            nump=int(i/500)+1
            if nump<>nump2 then
                nump2=nump
                locate 1,6:print "creation de la phrase ";nump;" / ";nbph
            end if
            ph$(nump)=ph$(nump)+" "+dico$(i)
        next i
    [suite]
        print "quel mot voulez-vous chercher"
        input r$
        r$=" "+upper$(r$)+" "
        t=time$("ms")
        for i=1 to nbph
            if instr(ph$(i),r$) then okmot=1:exit for
        next i
        t2=time$("ms")
        if okmot=1 then
            print "ce mot est bien dans le dico"
        else
            print "ce mot n'est pas dans le dico"
        end if
        print "temps de recherche : ";(t2-t);" ms"
    goto [suite]
    
    wait

c'est ecrit en Liberty BASIC, donc en C tu devrais exploser les temps, tout le monde sait que le basic, c'est lent ! (lol)

@++

DzarGol · Answer

y a pas moyen de créer une structure spéciale, genre un arbre binaire de recherche (basé sur le dichotomique, d'ailleurs), le stocker en mémoire au démarrage et faire ensuite des accès dessus pour la recherche? en C, ça devrait se programmer assez bien, et les structures ABR sont dans les plus rapides pour faire une recherche...

à voir... ;-)

(au fait, je suis moi aussi sur un projet de Scrabble en C, donc si vous trouvez une soluce en C, prévenez... ;-) )

@++

Marden · Answer

J'ai croisé un jour déjà lointain, l'auteur d'un site avec jeu en ligne, qui m'a dit que son dictionnaire, sans doute en Java, occupait moins de 500ko.
Je suppose qu'il s'agit d'une sorte d'arbre dont les clés sont d'abord à une lettre (sous-arbre dont les mots commencent par ...), etc. Les feuilles sont les mots du dictionnaire, mais on peut supposer que les féminins, les pluriels, les conjugaisons sont gérés par des pointeurs vers quelques règles de génération des terminaisons.
Je sais que le jeu proposé n'applique aucune stratégie, se contentant de proposer la solution rapportant le maximum de points, compte-tenu des lettres déjà en place, et autres multiplicateurs de la grille.
Mon meilleur score (je ne suis pas un spécialiste) est de -40 par rapport à celui de la "machine" !!!

Le site en question : http://duel-de-mots.com/

DzarGol · Answer

en fait, j'avais aussi trouvé une structure bizarre permettant de mettre l'ODS4 de 4Mo en 400Ko, mais c un algo assez compliqué... Il faut aller voir sur ce site : http://www.nongnu.org/eliot/

Recherche dichotomique en C dans fichier

9 réponses

Discussions similaires