[C] table de hachage

Fermé
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 - 20 août 2008 à 14:30
ellahakbar Messages postés 2 Date d'inscription dimanche 10 juillet 2011 Statut Membre Dernière intervention 10 juillet 2011 - 10 juil. 2011 à 23:34
Bonjour,
j'ai une table de hachage qui contient les mots extrait du texte, avec leurs liste de coordonnées
voila sa declaration:
typedef struct L2{ 
    int freq; 
	mots *m; 
	Coordonnees *c; 
	struct L2 *suivant; 
}Liste; 
 

en fait je lis le texte ligne par ligne et a chaque mouveau mot je le stocke dans la table en stokant la liste des position des mots.
le probleme c'est que je voudaris accorder à chaque mots un entier. comme ca apres je dfais mes traitement avec les entier.
vous pouvez m'aider à faire cette fonction. car j'en ai aucune idée sauf ajouter un champ "entier " à la structure .
merci

15 réponses

lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 567
20 août 2008 à 16:51
Salut,

je ne comprends pas.
c'est justement le rôle de la fonction de hachage.

mot ----- Fonction hachage ------> Entier

entier = F(mot)
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
20 août 2008 à 17:06
merci Lami d'avoir repondu,
au debut j'avais l'idee d'utiliser les clé de hachage(fonctionde hachage) pour manipuler les mots, or j'ai constaté que 2 mots different ont le meme clé de hacahge.
ce qui va engendrer des probleme apres.
car les mots sont different.
donc j'ai eu l'idee d'attribué à chaque mot un numero.tu vois?
merci infiniment
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
20 août 2008 à 20:23
en fait voila mon essai: là ya pas d'erreur
#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<assert.h>


#include "table_hash.h" 
#define TAILLEHASH 307 
#define NBRSEQ 10 
#define SEUIL 3 
#define SEUIL 3 

int main (void)

{   unsigned int pt;
int i;
int j;

char c;
   Liste **TableHash = malloc (TAILLEHASH * sizeof *TableHash); // allocation memoire pour la table de hachage
   if (TableHash != NULL)
   {
      pt = HashCode (".");  // pour marquer que le "." est signe de fin de la ligne
      {
         int i;
         for (i = 0; i < TAILLEHASH; ++i)
            TableHash[i] = NULL;
      }// initialisation de la table de hach à null
 
      printf ("debut du programme \n" "----------------------------------\n");
 
      {
         FILE *F = fopen ("C:\\essai.txt", "r");  // lecture d'un fichier texte 
         if (F != NULL)
         {
            char mot[100];
 
            printf
               ("Ouverture du Fichier \n"
                "----------------------------------\n");
            while (fscanf (F, "%s", mot) == 1)
            {
               unsigned int cle = HashCode (mot); // calcul de la clé de hachage du mot
              printf ("%u-", cle);
              assert (mot != NULL);
               assert (TableHash != NULL);
               j=j+1;
                
 
               if ((cle != pt)&& (!ChercherMotDansTableHash (TableHash, mot)))  // verifier si le mot<> "." et il                                                                                                   n'est     pas present dena la table
             
                {
                   
                  TableHash[cle] = InsertionEnTete(TableHash[cle],mot);//insertion du mot sans la table 
                  TableHash[cle]->entier=j;   pour attribuer un entier au mot allant de 0 à n
                  printf("%i", TableHash[cle]->entier);
                  
                  
                

                  
               
               }
               printf ("\n");
            }
            fclose (F);
            F=fopen("C:\\essai.txt","r"); 
	        PosLigne(F,TableHash);
	        AfficherTableHash(TableHash);  
         }
      }
   }
   scanf("%s",c);
   return 0;
  
}


bon le probleme ici c'est que lorsquil affiche bien le mot, ses coordonnes mais l'entien il m'affiche une suite de chifre.
ya un probleme au niveau de j
quelqun peut m'aider svp
0
Mahmah Messages postés 496 Date d'inscription lundi 17 septembre 2007 Statut Membre Dernière intervention 22 juin 2010 125
20 août 2008 à 21:23
Bonjour,

Vite fait en passant car ce n'est pas (/plus) ton problème. Une fonction de hachage peut en effet associer un même entier à deux objets différents, on dit alors qu'il y a une collision La table de hachage doit en principe gérer les collisions, soit en ayant non pas un objet associé à un entier mais une liste d'objets. La recherche se fera alors par la fonction de hachage pour trouver la liste puis en parcourant celle-ci en comparant cette fois les objets de la liste à l'objet donné en paramètre de la recherche. Soit, lorsqu'une collision intervient, on place simplement l'objet au prochain indice disponible dans la table. La recherche se fait cette fois par la fonction de hachage, puis en comparant les objets dans les cases suivantes tant que l'objet voulu n'est pas trouvé. (ou une case vide)

Le passage par la fonction de hachage permet de conserver une bonne performance pour la recherche dans la table en limitant très vite les choix possibles.

M.

PS: La solution 2 est moins laborieuse.
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
20 août 2008 à 21:29
merci baeacoup, mais ca l'air un peu compliqué,
tu peux m'aider un peu plus svp.
je suis encore debutante.
merci
0

Vous n’avez pas trouvé la réponse que vous recherchez ?

Posez votre question
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 567
20 août 2008 à 22:06
Salut,

Soit, lorsqu'une collision intervient, on place simplement l'objet au prochain indice disponible dans la table.

Je pense que Mahmah fait référence aux tables de hachage à adressage ouvert.

L'inconvénient de ce type de table, c'est qu'elle est fixe.
Mais dans ton cas vu que tu veux avoir un seul mot pas case tu dois peut être penser à créer une table à adressage ouvert.
A savoir que t'es obligé de choisir depuis le début une taille assez grande pour ne pas tomber dans le cas de manque d'espace pour un nouveau mot.
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
20 août 2008 à 22:14
merci Lami , mas j'ai un fichier texte de 2go!!!!!!
c'est a dire va etre une enorme table non?
oula c'est trop dur
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 567
20 août 2008 à 22:23
Re,

avec une table de hachage chaînée tu alloues de façon dynamique l'espace pour ton fichier de 2 Go
mais au moins, la solution est optimale puisque tu ne risque pas d'allouer plus d'espace que nécessaire

en revanche si tu dois allouer un tableau à taille fixe tu dois d'abord voir combien des mots tu as (en éliminant les doublons bien sûr)
sinon tu choisi un taille assez grande pour être sur que tu ne vas pas louper un mot, mais en ce cas tu risques d'allouer d'espace que tu ne vas jamais utilisé

à toi de faire le compromis et de voir ce qui te conviens.
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
20 août 2008 à 22:26
ben je pense la 2eme ;)
faut que je cherche maintenant sur google sa structure ca r je connais pas c'est nouveau pour moi.
merci Lamiiiiiiiiiiiiiiiiiiiiiii
té super
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 567
20 août 2008 à 22:29
Salut,

en fait si tu fait ça, tu changeras tout
j'avais l'impression que tu as fini ton projet ;-)

si jamais tu ne trouveras pas, peut être que j'aurais le temps l'week-end prochain de t'expliquer le fonctionnement, ou peut être qu'un autre membre le fera ;-)
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
20 août 2008 à 22:35
regarce ca LAmi
Résolution des collisions par chaînage.
c'est au autre type ?
qu'en pense tu?
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 567
20 août 2008 à 22:43
Résolution des collisions par chaînage.
Ben, c'est ça que tu as fait jusqu'à maintenant.
Je la préfère.

Le problème c'est que veux un mot par case, donc pas des collisions.

En ce cas même si tu utiliseras toujours la table de hash chaînée, tu seras d'allouer à la table la taille égale avec le nombre de mots de ton fichier.

Tu as dit 2 Go?!
Ben 2 Go ce n'es rien.
Parlons pas de Go mais de nombres.

Que feras-tu si tu sera obliger de faire une table pour 2*10^10 mots?!
L'idéal c'est sans collision, mais en réalité il faut tout simplement gérer les collisions.

Donc si tu ne veux pas des collisions, en fait si tu veux que les collisions soient gérer par l'attribution d'un autre index, alors sache que c'est la méthode des hash par adressage ouvert.

Il faut savoir faire un compromis.
Perso, j'aurai préféré de gérer les collisions en restant avec la table de hash chainée
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
20 août 2008 à 22:54
je sais pas moi, peut etre je suis allée un peu plus loin,
mais l'essentiel pour moi c'est d'accorder à chaque mot un entier. c'est l'important.
car apres je vais faire des traitement sue ces entier là.
au dernier temps je ferais le matching; c'est a dire attribur à chaqure entier son mot.
vous voyez?
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 567 > stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009
20 août 2008 à 22:56
Alors, ajoute un champ dans la structure, et ne te casse plus la tête ;-)
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2 > lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019
20 août 2008 à 23:00
oui c'est ce que j'ai fait ce matin;)
j'ai ajout un champ entier à ma structure mais lors de l'affichage de la table , il m'affiche des entier bizarre pour chaque mot:
au lieu de 1 pour le 1er, 2 pour le second,...
c'est la cause de mon post au fait,
;)
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 567 > stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009
20 août 2008 à 23:02
Ben, affiche ce qui ne fonctionne pas, et on verra.
Je regarderai demain, à moins qu'il n'y a pas d'autre personnes qui le ferront.
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2 > lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019
20 août 2008 à 23:23
merci :)
voila la main.c

#include<stdio.h> 
#include<stdlib.h> 
#include<string.h> 
#include<assert.h>


#include "table_hash.h" 
#define TAILLEHASH 307 
#define NBRSEQ 10 
#define SEUIL 3 
#define SEUIL 3 

int main (void)

{   unsigned int pt;
int i;
int j;

char c;
   Liste **TableHash = malloc (TAILLEHASH * sizeof *TableHash);
   if (TableHash != NULL)
   {
      pt = HashCode (".");
      {
         int i;
         for (i = 0; i < TAILLEHASH; ++i)
            TableHash[i] = NULL;
      }
 
      printf ("debut du programme \n" "----------------------------------\n");
 
      {
         FILE *F = fopen ("C:\\essai.txt", "r");
         if (F != NULL)
         {
            char mot[100];
 
            printf
               ("Ouverture du Fichier \n"
                "----------------------------------\n");
            while (fscanf (F, "%s", mot) == 1)
            {
               unsigned int cle = HashCode (mot);
             printf ("%u-", cle);
              assert (mot != NULL);
               assert (TableHash != NULL);
              
                
 
               if ((cle != pt)&& (!ChercherMotDansTableHash (TableHash, mot)))
               {
                         j=j+1;
                   
                  TableHash[cle] = InsertionEnTete(TableHash[cle],mot);
                  TableHash[cle]->entier=j;
                  printf("%i", TableHash[cle]->entier); 
               }
               printf ("\n");
            }
            fclose (F);
            F=fopen("C:\\essai.txt","r"); 
	        PosLigne(F,TableHash);
	        AfficherTableHash(TableHash);
         }
      }
   }
   scanf("%s",c);
   return 0;
  
}

unsigned int HashCode (char  *ligne)
{
   unsigned int Code = 0;
   size_t const len = strlen (ligne);
   size_t i;
 
 //  printf ("ligne = '%s'\n", ligne);
 
   for (i = 0; i < len; i++)
   {
      Code = ligne[i] + 31 * Code;
   }
   return Code % 101;
}


 unsigned int ChercherMotDansTableHash (Liste ** TableHash,char *mot)
{
   int found = 0;
   unsigned int cle = HashCode (mot);
   Liste *p;
   assert (cle < TAILLEHASH);
   for (p = TableHash[cle]; !found && p != NULL; p = p->suivant)
   {
 
     // printf ("p=%p\n", (void *) p);
      assert (p != NULL);
     assert (p->m != NULL);
      assert (p->m->mot != NULL);
      found = strcmp (p->m->mot, mot) == 0;
   }
   return found;
}
mots *InsertionEnTeteMot(mots *m,char mot[50]){ 
	mots *nouveau; 
	nouveau = (mots *) malloc (sizeof(mots)); 
	strcpy(nouveau->mot,mot); 
	nouveau->suivant = m; 

	return nouveau; 
}
Liste *InsertionEnTete(Liste *L,char *mot){ 
	Liste *nouveau; 
	nouveau = (Liste *) malloc (sizeof(Liste)); 
	nouveau->freq=0; 
	nouveau->m=NULL; 
	nouveau->m=InsertionEnTeteMot(nouveau->m,mot); 
	nouveau->m = InsertionEnQueueMot(nouveau->m,mot);
	nouveau->suivant = L; 
	nouveau->c = NULL; 
	return nouveau; 
} 





mots *InsertionEnQueueMot(mots *m,char mot[50]){ 
	mots *nouveau; 
	nouveau = (mots *) malloc (sizeof(mots)); 
	strcpy(nouveau->mot,mot); 
	nouveau->suivant = NULL; 
	
	if(m==NULL)
		return nouveau; 
	else
	{
		m->suivant = nouveau;
		return m;
	}
} 
void PosLigne(FILE *F,Liste **TableHash)  
{   
	char s[50];   
	int nl,pos,i;   
	Liste *p;   
	Coordonnees *c;   
	int trouve =0;   
	nl=pos=1;   
	for(i=0;i<TAILLEHASH;++i)   
		if(TableHash[i]!=NULL)   
			for(p=TableHash[i];p!=NULL;p=p->suivant)   
			p->freq=0; 
			while(fscanf(F,"%s",s)==1)  
			{   
				for(i=0;i<TAILLEHASH;++i)   
				{  
					if(TableHash[i]!=NULL)   
					{  
						for(p=TableHash[i];p!=NULL;p=p->suivant)   
						{  
							Coordonnees *x;//ou Coordonnees x; sans le *  
							if(strcmp(p->m->mot,s)==0)   
							{
                                                       
								/*Avant l'insertion*/  
								trouve=0; 
								for(x=p->c;x!=NULL;x=x->suivant)   
									if(x->nl == nl) //même ligne   
										trouve=1;   
									if(trouve==0)   
										p->freq=p->freq+1;    
									p->c=InsertionEnTeteCoordonnee(p->c,nl ,pos);    
							}   
						}   
					}  
				}  
				/*ici :p*/  
				if(fgetc(F)=='\n')  
				{   
					++nl; // ou nl++; ça change rien  
					pos=0;   
				}   
				++pos;//pareil ou pos++; ça change rien non plus  
			}  
} 
Coordonnees *InsertionEnTeteCoordonnee(Coordonnees *C,int nl ,int pos){ 
	Coordonnees *nouveau; 
	nouveau = (Coordonnees *) malloc (sizeof(Coordonnees)); 
	nouveau->pos = pos; 
	nouveau->nl = nl; 
	nouveau->suivant = C; 
	return nouveau; 
} 
void AfficherTableHash(Liste **TableHash){ 
	int i; 
	for(i=0;i<TAILLEHASH;++i) 
		if(TableHash[i] != NULL){ 
			printf("Conteneur %d \n",i); 
			AfficherListe(TableHash[i]); 
			printf("----------------------------------\n"); 
		} 
} 
void AfficherListe(Liste *L){ 
	Liste *p; 
	for(p=L;p!=NULL;p=p->suivant){ 
		AfficheMot(p->m); 
		printf("%d : ",p->freq); 
		AfficherCoordonnees(p->c); 
		printf("%d : ", p->entier);
	} 
} 
void AfficheMot(mots *m){ 
	mots *p; 
	for(p=m;p!=NULL;p=p->suivant) 
		printf("%s ",p->mot); 
	printf("\n"); 
	/*if(m!=NULL)
	{
		AfficheMot(m->suivant);
		printf("%s ",m->mot);
	}*/

	
} 
void AfficherCoordonnees(Coordonnees *C){ 
	Coordonnees *p; 
	for(p=C;p!=NULL;p=p->suivant) 
		printf(" (%d,%d) ",p->nl,p->pos); 
	printf("\n"); 
}

cela dnas le header
ifndef TABLE_HASH 
#define TABLE_HASH 
 
typedef struct c{ 
	int pos; 
	int nl; 
	struct c *suivant; 
}Coordonnees; 
 
typedef struct L{ 
	char  mot[50]; 
	Coordonnees *c; 
	
	struct L *suivant; 
}Liste1; 
 
typedef struct m{ 
	char mot[50]; 
	struct m *suivant; 
}mots; 
 
typedef struct L2{ 
    int freq; 
	mots *m; 
	Coordonnees *c; 
	int entier;
	struct L2 *suivant; 
}Liste; 



voila le reultat:
debut du programme
--------------------------------------------
ouverture du fichier
----------------------------------------------
74-50330661
75-50330662
64- // je vois pas c'est quoi ce nombre
conteneur74
bonjour bonjour
1 :<1,1>
50330662/// je vois pas d'où il vient de ce nombre normallement il affiche0
---------------------------------------
les les
1 : <1,2>
50330662/// je vois pas d'où il vient de ce nombre normallement il affiche1
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
20 août 2008 à 22:47
ok mais t'as une idée comment gerer les collision dans le cas de table de hachage chainée.?
0
lami20j Messages postés 21331 Date d'inscription jeudi 4 novembre 2004 Statut Modérateur, Contributeur sécurité Dernière intervention 30 octobre 2019 3 567
20 août 2008 à 22:54
Ben, on l'a déjà fait.
A savoir que chaque élément de la table pointera en fait sur une liste chaînée qui contiendra les éléments de la liste

suppons que tu as les mots

titi et baba

et que
titi et baba on le même code, par exemple 203

alors l'élément situé à la position 203 va pointée sur titi
et quand on testera le mot baba alors il sera insérer dans la liste après titi (il s'agit de la liste correspondant au index 203)

c'est ça la résolution des collisions

L'idéal dans le sens faisable sera d'avoir un équilibre.
Par exemple pour une table de 13 éléments, que les mots soient répartis de façon équilibré (que le listes on un nombre d'éléments presque équivalent)

Sinon, peut être qu'avec un arbre tu t'en sortira pas mal, chaque mot étant un nœud dans l'arbre (en évitant les doublons)
Comme ça tu n'auras pas des coulissions, chaque mot aura son emplacement mémoire. Mais pour gerer ça risque d'être compliqué.
0
stroumpf Messages postés 289 Date d'inscription mardi 17 juin 2008 Statut Membre Dernière intervention 1 mars 2009 2
21 août 2008 à 13:16
salut,
ban voilà c'est la fonction où je plante depuis 1 ans et j'espere trouver une solution :(
j'ai une table de hachage qui contietndes mots et leurs liste de coordonees:
chaque mot a sa propre liste de coordonnées (num-ligne, position)

bonjour(1,2)(2,4)
les (1,3)(2,5)(4,6)
amis (2,6)(3,5)(4,7)
je dois generer à partir de cette table de hachage des liste de 2 mots en faisant la jointure des mots de la table de hachage: on joint les mot qui ont le meme num-ligne et que la position du dernier mot>position du 1er mot:
par exemple on trouve là:
bonjour les (1,3)(2,5)
bonjour amis(2,6)
les amis(2,6)(4,7)
bon là j'arrive à faire cela , MAIS mon directeur ma dit qu'il faut faire un test sur les position
Si les position de 2 mots sont successif en moin 2 fois on met les 2 mots dans la meme cellule par exemple là "bonjour les "dans la meme cellule car (1,2)(1,3)(2,4)(2,5)
donc comme resumé j'arrive pas comment faire ce test là
c'est troooooooop compliqué pour moi
0
ellahakbar Messages postés 2 Date d'inscription dimanche 10 juillet 2011 Statut Membre Dernière intervention 10 juillet 2011
10 juil. 2011 à 23:28
Bonjour,

j'ai un probleme de meme type , je veux dire le hachage, je veux savoir comment créer un table de hachage dans la jointure par hachage, notons que cette jointure se fais dans deux phases: une phase de création de la table de hachage par la plus petite relation disant R, et une phase de scan pour tester les tuples de la plus grande relation disant S avec la table de hachage.

j'ai lu que pour créer une table de hachage sur la relation R , on applique une fonction de hachage sur l'attribut de jointure de R , aprés le résultat obtenu c l'indice du paquet où on doit poser le tuple , mais j'ai pas bien compri comment créer cette table, parceque normalement la structure de cette table sur java est contienne deux champs champ clé et champ valeur.

ok je ne sais pas si j'ai bien expliqué ou non, j'espere que quelque parmi vous a une idée sur la jointure par hachage.

SVP aidez moi.
0
ellahakbar Messages postés 2 Date d'inscription dimanche 10 juillet 2011 Statut Membre Dernière intervention 10 juillet 2011
10 juil. 2011 à 23:34
et si ce n'est pas la spécialité de cette forum adresse moi à une autre svp
0