Rechreche d'un mot a base de hachage
truono312
Messages postés
1
Date d'inscription
Statut
Membre
Dernière intervention
-
Hxyp Messages postés 401 Date d'inscription Statut Membre Dernière intervention -
Hxyp Messages postés 401 Date d'inscription Statut Membre Dernière intervention -
Bonjour,
je cherche une fonction pour rechercher un mot dans un texte grace a une table de hachage en C
je cherche une fonction pour rechercher un mot dans un texte grace a une table de hachage en C
A voir également:
- Rechreche d'un mot a base de hachage
- Trousseau mot de passe iphone - Guide
- Mot de passe - Guide
- Base de registre - Guide
- Mot de passe administrateur - Guide
- Mot de passe bios perdu - Guide
1 réponse
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..
