Discussion :

[étoile de mer]

bonsoir à tous,
j'ai besoin d'une fonction de hachage performante afin de stocker les mots dans la table de hachage.
le probleme c'est que j'ai trouvé dans un forum une fonction de hachage exemple, je l'ai implémenté mais j'ai decouvert qu'il ya 2 mots qui ont la meme clé de ahchage ce qui à cuasé des collision.
qu'uelqu'un peut m'aider svp.
j'attend vos reponse.
voila la fonction de hachage:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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;
}

merci j'attends vos reponses.

[Jean-Marc.Bourguet]

1/ il y aura toujours des collisions
2/ elles sont plus probables que tu ne le penses, meme en considerant une fonction de hachage parfaite (cf le paradoxe des anniversaires)
3/ la plupart des donnees ne sont pas equalement distribuees, donc on peut se servir de ce biais pour adapter la fonction de hachage aux donnees
4/ On trouve facilement sur internet des fonctions et des articles analysant diverses fonctions et montrant que celle de l'auteur est la meilleure... (en cadeau: http://www.azillionmonkeys.com/qed/hash.html, http://isthe.com/chongo/tech/comp/fnv, http://burtleburtle.net/bob/hash/doobs.html, http://bretm.home.comcast.net/~bretm/hash/2.html)

[ciol2.6.12]

1/ il y aura toujours des collisions
2/ elles sont plus probables que tu ne le penses, meme en considerant une fonction de hachage parfaite (cf le paradoxe des anniversaires)

Je crois pas. En effet il y aura toujours des collisions, mais dans les faits, c'est très rare voir impossible, avec une bonne fonction de hachage (surtout si ce sont des mots qui ont un sens).

Mais là, je parle du hash code. Et lui, il parle de l'entrée dans la table de hachage. Sa table a une taille de 31 (cf le modulo 31), donc en effet il y aura toujours des collisions. Et dans une table de hachage, c'est normal.
Faudrait calculer la probabilité, le paradoxe des anniversaires dit juste que ce n'est pas 1/31, mais ça reste dans cet ordre de grandeur.

[Jean-Marc.Bourguet]

Meme avec des tables presque vides, il y a une probabilite non negligeable de collisions (plus de 50% pour une table de 365 entrees a partir de 23elements, donc un taux de remplissage de moins de 10%).

En pratique, ou ta table est tres largement sur-dimensionnée, ou le risque de collision est non negligeable ou tes donnees n'ont pas une distribution uniforme et ta fonction de hachage en profite.

Une petite table donnant pour differentes tailles le nombre d'elements qu'il faut pour avoir une probabilite de 50 et 90% de collision:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
    10      5      7
    20      6     10
    50      9     15
   100     13     22
   200     17     31
   500     27     48
  1000     38     68
  2000     53     96
  5000     84    152
 10000    119    215
 20000    167    304
 50000    264    480
100000    373    679
200000    527    960
500000    833   1518

[étoile de mer]

salut,
ban voilà c'est la fonction où je plante dont 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

[Ptitlex]

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

Salut,

Si j'ai bien tout compris, tu aurais besoin qu'on concatène des mots si :
- 2 mots se suivent au moins 2 fois

Je suppose que tu dois avoir une fonction qui parcourt ta table de hachage donc l'algorithme : Ce qui donnerai qqchose comme ça :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
 
// Déclaration de structure coordonnées (position et numéro de ligne) 
typedef struct c{
int pos;
int nl;
struct c *suivant;
}Coordonnees;
 
// Déclaration de la structure de liste (contient les coordonnées) 
typedef struct L2{ 
    int freq; 
	mots *m; 
	Coordonnees *c; 
	int entier;
	struct L2 *suivant; 
}Liste;
 
// Fonction qui parcourt la table de hach
void MaFonctionACompleter(Liste **TableHash) 
{
	// éléments courant lors du parcourir de la table
	Liste **current_ItemOf_TableHash = malloc (TAILLEHASH * sizeof *TableHash);
	// éléments qui va parcourir la table
	Liste **Next_ItemOf_TableHash = malloc (TAILLEHASH * sizeof *TableHash);
// Pareil pour les pointeurs sur les listes chainée : 
Coordonnees * currentPtrCoordonnees = malloc (sizeof *Coordonnees);
Coordonnees * otherPtrCoordonnees = malloc (sizeof *Coordonnees);
 
	// On dit que notre éléments courant de la table de hash pointe sur le premier éléments de la TableHash
	current_ItemOf_TableHash = TableHash; 
 
	// Tant qu'il y a des éléments, on continue à parcourir la table de hachage
	while(current_ItemOf_TableHash != null) 
	{
// on parcourt la liste chainée et on compare les éléments courant avec les autres
		Next_ItemOf_TableHash = current_ItemOf_TableHash + sizeof(TableHash); 
		while(Next_ItemOf_TableHash != null) 
		{
			while(current_ItemOf_TableHash->Liste != null)
			{
				currentPtrCoordonnees = current_ItemOf_TableHash->Liste->Coordonnees;
				while(Next_ItemOf_TableHash->Liste != null)
				{
					otherPtrCoordonnees = Next_ItemOf_TableHash->Liste->Coordonnees;
					if(currentPtrCoordonnees->nl ==  otherPtrCoordonnees-> nl && currentPtrCoordonnees->pos == (otherPtrCoordonnees->pos+1) )
{
cpt ++; 
if (cpt >= 2) 
{
// On concatène ici *********************
cpt = 0; 
}
}
					otherPtrCoordonnees = Next_ItemOf_TableHash->Liste->suivant;
				}
currentPtrCoordonnees = current_ItemOf_TableHash->Liste->suivant;
			}
			 =  
		Next_ItemOf_TableHash = ; 
	}
 
	// j'sais plus trop comment on va à l'élément suivant : 
	//soit : current_ItemOf_TableHash = current_ItemOf_TableHash + (sizeof *TableHash); 
	//soit : current_ItemOf_TableHash++; 
}

Bon, c'est sur qu'au niveau syntaxe, yaura des trucs à revoir mais l'état d'esprit y est ^^

Alex.