Rechreche d'un mot a base de hachage

Fermé
truono312 Messages postés 1 Date d'inscription dimanche 9 janvier 2011 Statut Membre Dernière intervention 31 octobre 2012 - 31 oct. 2012 à 01:20
Hxyp Messages postés 401 Date d'inscription vendredi 28 janvier 2011 Statut Membre Dernière intervention 27 avril 2014 - 3 nov. 2012 à 07:22
Bonjour,
je cherche une fonction pour rechercher un mot dans un texte grace a une table de hachage en C
A voir également:

1 réponse

Hxyp Messages postés 401 Date d'inscription vendredi 28 janvier 2011 Statut Membre Dernière intervention 27 avril 2014 54
3 nov. 2012 à 07:22
Bonjour,
Si vous cherchez une lib hash table/algo pouvez voir les réponses sur cette question : https://stackoverflow.com/questions/1138742/looking-for-a-good-hash-table-implementation-in-c
Si c'est pour savoir comment le faire vous même, le principe c'est d'attribuer un nombre à chaque mot et faire en sorte que ce nombre/code lui soit unique. Ça permet de "ranger" les mots dans un tableau en utilisant leur "code" pour les positionner. Et ce code sert donc aussi à y accéder directement; tableau[code]

Bout de code pour donner une idée :
#include <stdio.h>
#include <stdlib.h>

typedef struct{
    unsigned short int usit[0xFFFF][1];
}PSHT;

unsigned short int getCode(const char *s){
    unsigned short int h,x;
    union{
        unsigned short int usi;
        char c[2];
    }cv;
    x=0x1021; cv.usi=h=0;
    while(*s){
        if(!cv.c[0]) cv.c[0]=*s;
        else cv.c[1]=*s;
        if(cv.c[1]||!s[1]){
            h^=cv.usi^x;
            cv.usi=0;
        }
        s++;
    }
    return h;
}

PSHT *getFilePSHT(const char *path){
    FILE *f;
    char buff[256],mot[32];
    char *cban="\r\n\t ,.?!:;()[]{}<>\\\"";
    PSHT *psht;
    int i,iban,r,z=0;
    psht=malloc(sizeof(PSHT));
    if(!psht)exit(1);
    for(i=0;i<0xFFFF;i++)*psht->usit[i]=0;
    f=fopen(path,"rb");
    if(f){
        while((r=fread(buff,sizeof(char),256,f))){
            for(i=0;i<r;i++){
                for(iban=0;cban[iban];iban++)
                    if(buff[i]==cban[iban]){
                        iban=-1; break;
                    }
                if(iban>-1&&z<32){
                    mot[z]=buff[i];
                    z++;
                } else if(mot[z-1]){
                    mot[z]='\0';
                    printf("mot : %s | code : %d\n",mot,getCode(mot));
                    *psht->usit[getCode(mot)]=1;
                    z=0;
                }
            }
        }
        fclose(f);
    }else fprintf(stderr,"erreur fopen\n");
    return psht;
}

int psht_lfw(const char *word,PSHT *psht){
        return *psht->usit[getCode(word)];
}

int main(void){
    PSHT *psht;
    psht=getFilePSHT("fichier.txt");
    if(psht_lfw("voiture",psht))
        printf("le mot existe\n");
    else printf("le mot n'existe pas\n");
    free(psht);
    return 0;
}


La fonction de hashage getCode (faite à l'arrache non étudiée) pond un code en fonction d'un mot qu'on lui passe. Le type PSHT,pour la var usit est un tableau qui permet de stocker l'existence d'un mot (code/position mis à 1 si existe) dont le code aurait été lu dans le fichier. La fonction getFilePSHT permet de filtrer un fichier dans le tableau du type psht et le retourner. Et la fonction psht_lfw la recherche d'un mot dans le tableau c'est là qu'on voit le principe, le mot se transforme en position et on ne s'embête pas à parcourir tout un buffer ou un fichier pour savoir s'il existe.
Mais bon tout tient sur la fonction servant à générer un nombre suffisamment unique pour éviter les collisions ce qui est impossible car ça reste du hashage..
0