Discussion :

[ludo007]

Bonjour,
je voudrais choisir cette fonction polynomiale (p(cle)= cle(0)*z^0 + cle(1)*z(1) + ...... + cle(n-1)*z^(-1) ) ou une autre pour des chaines de caractères, mon seul problème est de pouvoir comprendre comment elle fonctionne, comment elle gère les collisions ,la taille de la table de hachage ces avantages et ces inconvénients et si possible être conseillé sur les différentes fonctions de hachage et celle les + efficaces.
merci et a bientôt

[Veovis]

Sauf erreur de ma part, es tu sur de ta fonction polynomiale, parce qu'elle ne veut rien dire, ou alors tu l'as sortie de son contexte ??? Normalement une clef de hachage est P(mot) = clef, et non l'inverse.

Comment les clefs de hachage fonctionne ? C'est tout simple elle prend un mot en argument et en fonction de ce mot et de ta fonction de hachage choisi va retourner une clef. Cette clef modulo la taille de ton tableau, te permettra de trouver la position du mot dans le tableau.

La collision n'est pas géré par la clef de hachage, elle doit être géré par ton programme. Mais une fonction de hachage particulièrement intéressante et bien choisi, te permettra d'éviter les collisions.

Il n'existe pas de clef de hachage efficace. Pour chaque problème, existe une clef de hachage spécifique.

[ludo007]

oui pour le p(clé)=... c'etait une erreur de tape je connais le fonctionnement des tables de hachage mais seulement je voudrais utilisé pour un TP une fonction de hachage qui m aide a voir que deux mots sont syntaxiquement proches (EX:ecole et ecoule) et et je pensais qu a la place de la fonction modulo la fonction de hachage polynomial pourrait plus m aider (HACHAGE POLYNOMIAL: P(MOT)=mot(0)*z^0 + mot(1)*z(1) + ...... + mot(n-1)*z^(-1) ) avec z un entier quelconque.
Je sais que mon programme doit gerer les collisions mais je voudrais une fonction de hachage plus pertinante pour un verificateur de mot.

[Veovis]

Tu peux toujours tenter de faire une fonction polynomiale, j'y crois pas trop, mais ca peut se tenter :

P(Mot) = Mot[0]*10^1 + Mot[1]*10^2 + Mot[2]*10^3 + ... + Mot[N]*10^N

Mot[X] étant un entier positif compris entre 1 et 26.

La fonction première d'une table de hachage n'est pas de voir si deux mots sont proches l'un de l'autre. Elle est surtout là pour ranger les éléments et pouvoir y accéder le plus rapidement possible.

Si tu veux savoir si un mot est proche d'un autre tu peux toujours voir du côté des algorithmes de Hamming ou Levenshtein.

[ludo007]

oki mais comment est ce qu'elle fonctionne ? quelle est la taille de la table pour cette fonction polynomiale ? les valeurs des clés varient entre ? et ? et puis j ai regardé pour l algorithme de hamming et Levenshtein et d autres mais laquelle me conseille tu?
merci

[Veovis]

oki mais comment est ce qu'elle fonctionne ?

Comment marche la fonction polynomiale ???

Code :

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

1
2
3
4
5
6
 
string mot = "salut";
int somme = 0;
for(int i = 0; i < mot.size(); i++) {
   somme += mot[i]*10^i
}

Est ce que cela t'aide ???

quelle est la taille de la table pour cette fonction polynomiale ? les valeurs des clés varient entre ?

Il n'y a pas de taille de la table dans cette fonction polynomiale. Une fois que tu as obtenue un résultat avec ta fonction polynomiale, tu fais : polynomiale%taille_table. Le modulo te permettra d'obtenir une clef comprise entre 0 et Max de la taille de ta table de hachage. Il faudrait que tu revoies tes cours de table de hachage et le modulo...

[ludo007]

merci pour tt j ai utiliséune fonction de hachage qui me renvoyait la taille de mes chaines de caractere et j ai utilisé la distance de levenshtein pour la similitude entre deux chaines mais ne considerant que les chaines de longueur +ou - proche de la chaine a comparer merci pour toute votre aide.