Discussion :

[suntsu]

Bonjour,

J'essaie actuellement de générer une sorte de fonction de hashage qui permettrait d'attribuer un ID unique à chaque mots d'un dictionnaire.

Dans le code ci-dessous, les mots sont aléatoires et sont longs de 32 caractères, pour l'instant chacun de mes processeurs fait une recherche de collision pour déterminer si mon algorythme est fiable pour des dimensions de mots raisonnables (maximum 32 caractères).

Le principe est simple:
Imaginons un mot de 4 caractères: ACDB où A=1, C=3, D=4, B=2, ensuite, on additionne la position avec la valeur : A=1+1, C=3+2, D=4+3, B=2+4 donc 2, 5, 7, 6. Après cela je réalise l'opération suivante : (((2 / 5) / 7) / 6) et j'obtiens 0,00952380...
Bon évidement c'est la base, en définitive on arrive sur des mots de 32 caractère avec des valeurs proches de 10^(-50).

çà fait 12 heures que mes processeurs tournes et toujours pas de collisions en vue...
Ma méthode est très empirique et encore bien imparfaite comme vous le verez dans le code ci-dessous le programme ne fait que 10^6 combinaisons mais ce n'est qu'un exemple.

En fait ce que je voudrais avoir c'est une critique de ma méthode qui me permettrai de savoir si il y a une grosse faille bien visible que je n'aurais pas vue ou si finallement, le seul moyen de savoir ne serait pas effectivement d'énumérer toutes les possibilités...

Voilà j'en appel à tous les matheux pour éclairer le pauvre noob de l'algèbre que je suis...

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
 
#include <cstdlib>
#include <ctime>
#include <iostream>
 
using namespace std;
 
int main()
{
    srand((unsigned)time(0));
    char content[] = "abcdefghijklmnopkrstuvwxyz-:-/";
    int factor=32;
    long cycle=1024*1024; 
    int random_integer=0; 
    int lowest=1, highest=sizeof(content)-1;
    int range=(highest-lowest)+1;
    int global[factor];
    char the_word[factor]; 
    long z=0;
    int sum;
    double proto_hash;
    double X_SPACE = 5.43817e-046; // factor 32
 
    while (z < cycle)
    {
          cout << "[" << z << "]";
          int i=0;
          sum=0;
          while (i < factor)
          {
                random_integer = (rand()%highest);
                global[i] = i + random_integer;
                sum += random_integer; 
                the_word[i] = content[random_integer];
                cout << content[random_integer];
                i++;
          }
          cout << " <=> ";
          i=0;
          proto_hash = global[0]+1;
          while (i < factor)
          {
                // cout << global[i];
                proto_hash /= (global[i] + 1);
                i++;
          }
          cout << factor << "-" << proto_hash << "-" << sum << endl;
          if (X_SPACE == proto_hash)
          {
               cout << "MATCH WITH THIS : " << endl;
               cout << "fnd:tauonhusfvv/xhvougxsrety:ddg <=> 32-5.43817e-046-470" << endl;
               system("pause");       
          }
          z++;
    }
    return 0;
}

[zais_ethael]

Si tu veux arrêter de te casser la tête boost fournis des biblios pour hasher des objets (il y a aussi boost::crc, j'ai jamais très bien compris la différence).
Néanmoins, conceptuellement, un algo de hashage sans collisions ça n'existe pas, quel que soit le système que tu conçois il faut toujours envisager l'hypothèses d'avoir deux objets qui ont le même code de hashage.
Ce n'est pas forcément une grosse contrainte, une fois que l'objet est trouvé il suffit de vérifier qu'il est bien celui qu'on cherche. Néanmoins on ne peut pas vraiment se servir d'un code hashé comme identifiant unique au sens SGBDR du terme.

[ram-0000]

Ton exemple :

Code :

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

1
2
3
 
ACDB où A=1, C=3, D=4, B=2
res = 2 / 5 / 7 / 6 = 0,0095238095238095238095238095238095

Mon exemple maintenant :

Code :

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

1
2
3
 
CHDB où C=3, D=4, B=2, H=8
res = 4 / 10 / 7 / 6 = 0,0095238095238095238095238095238095

10 minutes pour chercher et trouver au moins une collision par une approche mathématique de la chose, je pense que tu peux arrêter ton programme

Désolé, ces algorithmes ne sortent pas que d'une bonne idée, il faut aussi de très bonnes connaissances en mathématiques

[suntsu]

Ben oui j'ai de serieuse lacune de ce coté là... snif... En tout cas merci pour la réponse !

J'ai trouvé plein de source d'algo et je crois que finalement je vais pas réinventé la roue et que je vais utiliser ce qui existe...

Encore merci en tout cas !

Bonne journée

[ram-0000]

J'ai trouvé plein de source d'algo et je crois que finalement je vais pas réinventé la roue et que je vais utiliser ce qui existe...

Cela me parait plus raisonnable de se reposer sur des solutions déjà éprouvées

[droggo]

Foe,

Avec des mots jusqu'à 32 caractères, un "hash" sans collision est facile à concevoir : les mots eux-mêmes.

Si lors de l'ajout d'un mot il s'avère qu'il est déjà là, on ne l'ajoute pas.

Trop simple ?

[suntsu]

Ton exemple :

Code :

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

1
2
3
 
ACDB où A=1, C=3, D=4, B=2
res = 2 / 5 / 7 / 6 = 0,0095238095238095238095238095238095

Mon exemple maintenant :

Code :

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

1
2
3
 
CHDB où C=3, D=4, B=2, H=8
res = 4 / 10 / 7 / 6 = 0,0095238095238095238095238095238095

10 minutes pour chercher et trouver au moins une collision par une approche mathématique de la chose, je pense que tu peux arrêter ton programme

Désolé, ces algorithmes ne sortent pas que d'une bonne idée, il faut aussi de très bonnes connaissances en mathématiques

Oops je n'avais pas communiquer ce détails... en fait j'ajoute aussi un check_sum à la fin de mon float... et j'indique la longueur au début aussi.

Et çà donne quelque chose du genre:

Code :

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

1
2
3
ACDB où A=1, C=3, D=4, B=2 =>1+3+4+2 = 10
res = 2 / 5 / 7 / 6 = [4]-[0,00952380]-[10]

Code :

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

1
2
3
CHDB où C=3, D=4, B=2, H=8 =>3+4+2+8 = 17
res = 4 / 10 / 7 / 6 = [4]-[0,00952380]-[17]

Qu'en pensez-vous ?

[ram-0000]

Je suis intimement persuadé, que c'est une fausse bonne idée. Effectivement la découverte de collision est plus compliquée, au lieu de 10 mn, cela sera 1/4 d'heure.

Si le jeu en vaut vraiment la chandelle (quelques milliers/millions d'erros à gagner), je trouverai une collision.

[JolyLoic]

Néanmoins, conceptuellement, un algo de hashage sans collisions ça n'existe pas, quel que soit le système que tu conçois il faut toujours envisager l'hypothèses d'avoir deux objets qui ont le même code de hashage.

Ca peut exister, il suffit simplement qu'il y ait au moins autant d'éléments dans l'ensemble d'arrivée que dans l'ensemble de départ. Par exemple, pour coder des mots du dico, il suffit de prendre comme algorithme qui à chaque mot associe sa position dans le TLFi, ce qui fait un hash-code compris entre 1 et 100000...

A part ça, pour le posteur initial, utiliser un double pour une clef de hachage est probablement une mauvaise idée, les calculs sur des nombres flottants étant particulièrement difficiles à faire correctement.

[zais_ethael]

Par exemple, pour coder des mots du dico, il suffit de prendre comme algorithme qui à chaque mot associe sa position dans le TLFi, ce qui fait un hash-code compris entre 1 et 100000...

Ce qui part sur une idée similaire à celle de droggo mais sous une autre forme. Je ne pense pas qu'on puisse parler de hashcode si il s'agit en fait de l'expression binaire des données ou de la position dans une base de données...

[JolyLoic]

Pour moi, un algorithme de hash est une application de l'ensemble de départ vers un ensemble d'arrivée dont la représentation informatique demande moins d'espace que l'ensemble de départ. Cet ensemble d'arrivé doit être aisément manipulable (des entiers entre et N, oui, des doubles, bof). Le cas particulier où l'application est bijective décrit un algorithme de compression (ou de cryptage si l'ensemble d'arrivée a la même taille que l'ensemble de départ).

Maintenant, un bon algorithme de hash demande d'être rapide à s'exécuter, ce qui n'est pas le cas de ce que je proposais par recherche dans un dico...

Pour revenir sur terre, si le but est de hasher des mots, par opposition à des chaînes quelconques, il y a peut-être à y gagner en utilisant le fait que seulement 26 caractères différents sont à coder (je suppose des maj sans accents), ce qui fait pour des mots de 10 lettres max 47 bits de stockage. On doit pouvoir faire encore mieux en codant la notion de syllabe. Ca reste trop gros pour être directement utilisable, il faut donc hasher ce résultat partiel. Je ne sais pas si hasher une compression de la chaîne peut avoir de l'intérêt par rapport à hasher la chaîne directement.

[suntsu]

Pour moi, un algorithme de hash est une application de l'ensemble de départ vers un ensemble d'arrivée dont la représentation informatique demande moins d'espace que l'ensemble de départ. Cet ensemble d'arrivé doit être aisément manipulable (des entiers entre et N, oui, des doubles, bof).

Exactement, en fait pour tout vous dire j'ai écris en Web Crawler relativement similaire à celui de google avec pour but qu'il remplisse un base de donnée SQL. Lorsque j'ai conçu la base de donnée j'ai un peu (beaucoup) surestimé la vitesse d'accès au données par le moteur de recherche (page client style google) et donc maintenant que j'ai une DB avec 100.000 page web qui fait 2,7Go ben çà prends de 5 à 250 secondes pour obtenir un résultat... Je me suis donc documenter sur le site de l'université de Stanford pour en savoir plus sur la structure des données et le fonctionnement de Google... Et ce qui m'a frapé c'est qu'ils hashes sur 24bit les mots de la langue et s'en servent comme ID unique (WORDID) et qu'ils hashes sur 32bit les urls (DOCID)...
pour plus d'infos je vous conseil ces document en anglais :

GOOGLE_1
GOOGLE_2
GOOGLE_3

Comme vous pourrez le lire dans le document ci-dessus, au lieu de faire une recherche sur un mot, le mot dans votre querie google va être transformer en un WORDID et va être recherchée dans les deux index google (foward/inverted) d'où un gain subtanciel de performance. Sur 24bit ils encodent 14 millions de hashes correspondant au même nombre de mots ce qui ne pose pas de problème.

je crois que je vais me basé sur les travaux de Bob Jenkins en matière de hashage.

[Jean-Marc.Bourguet]

Qu'en pensez-vous ?

Ca m'a l'air d'être invariant suite à des permutations. Pas idéal pour une fonction de hachage.

En passant deux références qui peuvent t'aider à analyser ta méthode... http://home.comcast.net/~bretm/hash/, http://murmurhash.googlepages.com/

[loufoque]

Ce que tu veux, c'est une fonction de hashage parfaite.
Il y a des outils qui permettent d'en générer.

[ram-0000]

Ce que tu veux, c'est une fonction de hashage parfaite.
Il y a des outils qui permettent d'en générer.

Des liens SVP ?

[Jean-Marc.Bourguet]

On va se contenter de celui-ci: http://en.wikipedia.org/wiki/Perfect_hash_function, mais je ne suis pas aussi sûr que Loufoque que ce soit le problème de suntsu.