[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
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
A voir également:
- [C] table de hachage
- Table ascii - Guide
- Table des matières word - Guide
- Table des annexes word ✓ - Forum Word
- Table des matières et table des annexes - Forum Word
- Table des caractères - Guide
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 569
20 août 2008 à 16:51
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)
je ne comprends pas.
c'est justement le rôle de la fonction de hachage.
mot ----- Fonction hachage ------> Entier
entier = F(mot)
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
20 août 2008 à 20:23
en fait voila mon essai: là ya pas d'erreur
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
#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
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
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.
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.
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
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
tu peux m'aider un peu plus svp.
je suis encore debutante.
merci
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 569
20 août 2008 à 22:06
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.
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.
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
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
c'est a dire va etre une enorme table non?
oula c'est trop dur
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 569
20 août 2008 à 22:23
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.
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.
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
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
faut que je cherche maintenant sur google sa structure ca r je connais pas c'est nouveau pour moi.
merci Lamiiiiiiiiiiiiiiiiiiiiiii
té super
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 569
20 août 2008 à 22:29
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 ;-)
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 ;-)
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
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?
Résolution des collisions par chaînage.
c'est au autre type ?
qu'en pense tu?
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 569
20 août 2008 à 22:43
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
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
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
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?
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?
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 569
>
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
20 août 2008 à 22:56
Alors, ajoute un champ dans la structure, et ne te casse plus la tête ;-)
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
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,
;)
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,
;)
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 569
>
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
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.
Je regarderai demain, à moins qu'il n'y a pas d'autre personnes qui le ferront.
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
20 août 2008 à 23:23
merci :)
voila la main.c
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
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
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
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.?
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 569
20 août 2008 à 22:54
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é.
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é.
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
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
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
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
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.
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.
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
10 juil. 2011 à 23:34
et si ce n'est pas la spécialité de cette forum adresse moi à une autre svp
20 août 2008 à 17:06
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