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
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
A voir également:
- Rechreche d'un mot a base de hachage
- Voir mot de passe wifi android - Guide
- Mettre un mot de passe sur un dossier - Guide
- Mot de passe administrateur - Guide
- Trousseau mot de passe iphone - Guide
- Identifiant et mot de passe - Guide
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
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 :
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..
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..