HASH sans collision ?

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:

---

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; }

---

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.

Ton exemple :

Code:

---

1 2 3

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

---

Mon exemple maintenant :

Code:

---

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

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

Citation:

---

Envoyé par suntsu

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

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 ? :)

En général, un hash est un nombre

dans ce cas, 32 caractères et en codant sur 8 bits par caractères, cela fait un nombre de 256 bits. C'est un peu gros pour rentrer dans un 'long int' ou même un 'long long int' ?

Citation:

---

Envoyé par zais_ethael

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.

Citation:

---

Envoyé par JolyLoic

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...

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.

Citation:

---

Envoyé par 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).

---

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.

Citation:

---

Envoyé par ram_0000

Ton exemple :

Code:

---

1 2 3

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

---

Mon exemple maintenant :

Code:

---

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:

---

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:

---

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 ?

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.

Citation:

---

Envoyé par suntsu

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/

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

Citation:

---

Envoyé par loufoque

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 ?

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.

Merci pour la contrib, a mon tour, je partage ce que j'ai trouvé...

http://google-sparsehash.googlecode....doc/index.html

http://code.google.com/p/google-sparsehash/

Ces deux urls concernent les solutions utilisées par le moteur de recherche de Google pour l'indexage de leur "LEXICON" c'est bien evidement une API C++

Comme je suis tétu je continue à tester ma méthode de base (DOUBLE de 16bits + INT 8bits soit 24bits) et là j'attaque un dictionnaire anglais de 60.000 mots...
Heureusement pour moi j'ai beaucoup de machine à ma disposition parceque çà prends du temps... Surtout que je n'ai pas trop regarder à optimiser mon horrible code :(

Pour avoir un visuel sur ce que fait mon essai :

Voilà j'ai mis 20 machines a contribution sur le dictionnaire anglais de 60.000 mots et il n'y a toujours pas de collision à l'horizon...
Demain j'ajouterai un dictionnaire de français et après demain, si je n'ai toujours pas de collision, un dictionnaire de néerlandais...
Cela fera dans les 250.000 mots...

Comme mon hashage doit fonctionner pour un nombre fini d'éléments d'une taille maximale correspondant au mot le plus long de mon dictionnaire et donc certainement inférieure à une longueur de 32 caractères et que ces mots doivent avoir un sens, j'ai bon espoir que mon système fonctionne malgré tout...

Je reste néamoins triste d'avoir choisi "math 2h/semaine" comme option pendant ma scolarité car j'aurais surement pu réaliser quelque chose de plus élégant...

En attendant j'essaye de me servir de ma tête pour imaginer comment réaliser une collision et de définir dans quel circonstance ce genre d'évènement peu arriver...

Aller j'y retourne !

Merci encore à tous pour vos commentaires ! et si vous en avez d'autres n'hésiter pas ;-)

Citation:

---

Envoyé par suntsu

Je reste néamoins triste d'avoir choisi "math 2h/semaine" comme option pendant ma scolarité car j'aurais surement pu réaliser quelque chose de plus élégant...

---

T'inquiètes, moi comme beaucoup de collègues avions 6h voir plus et ça ne nous empêche pas d'être nuls en maths :)

Avec ce que tu as expliqué, "GOD" et "DOG" devrait être une collision.

Citation:

---

Envoyé par Jean-Marc.Bourguet

Avec ce que tu as expliqué, "GOD" et "DOG" devrait être une collision.

---

Eu non...

DOG = 4 + 15 + 7 = 26
GOD = 7 + 15 + 4 = 26

DOG = (4+1) / (15+2) / (7+3) = 0,029411764705882352941176470588235
GOD = (7+1) / (15+2) / (4+3) = 0,067226890756302521008403361344538

HASH :: [DOUBLE][SUM]

DOG = [2.941176e-02][26]
GOD = [6.722689e-02][26]

Le HASH est bien différent :)

Allez, un petit pour la route : "ON" = "XCB"

Allez, un autre parce que c'est toi, un autre : "YYA" = "YBX"

J'en ai un plein chargement comme cela :P

Non, sérieusement, je pense que ton algo ne tient pas la route. Utilise ce qui existe.

Citation:

---

Envoyé par ram_0000

Allez, un petit pour la route : "ON" = "XCB"

---

ON = 15 + 14 = 29
XCB = 24 + 3 + 2 = 29

ON = (15+1) / (14+2) = 1
XCB = (24+1) / (3+2) / (2+3) = 1

HASH :: [DOUBLE][SUM]

ON = [1.000000e+00][29]
XCB = [1.000000e+00][29]

Le HASH est bien identique ! Bravo... Maintenant je suis triste ;-)

Ok mon entêtement n'a pas payé... Je m'incline sauf que si j'ajoute un controle sur la longueur...

ON = [2][1.000000e+00][29]
XCB = [3][1.000000e+00][29]

A mon avis cette fois-ci il te faudra 20 min ;-) non sérieusement, je laisse définitivement tombé cette idée... Mais encore une fois merci ! :)

PS: ta posté avant moi donc... oublie ce que j'ai dis à propos de la longueur...

Tu as fait un algo pour trouver les collisions ou juste papier et crayon ? Si t'a fait un algo, je le veux bien juste pour voir cela m'intéresse

Allez A+

Papier + crayon pour chercher les formules de collision

programme sur ordinateur pour chercher les solutions de ces formules

Cf un thread que j'ai lancé sur le forum Maths à ce sujet :

http://www.developpez.net/forums/sho...d.php?t=528152

Les hash cryptographiques sont par définition extrêmement résistants aux collisions (il faut brute-forcer pour en trouver).
Donc tu pourrais en utiliser un, mais c'est peut-être un peu overkill.

Et ça ne garantira pas non plus qu'il n'y aura pas une collision qui viendra par hasard.

Par contre, comme l'ensemble des mots est connu à l'avance, il est possible d'utiliser un générateur de hash parfait du moment que l'ensemble des valeurs de hachage possibles est au moins aussi grand que l'ensemble des mots à hacher...

Citation:

---

Et ça ne garantira pas non plus qu'il n'y aura pas une collision qui viendra par hasard.

---

C'est à peu près aussi probable que la Terre soit anéantie demain par un astéroïde.

Ram_0000,

Citation:

---

Envoyé par ram_0000

Cf un thread que j'ai lancé sur le forum Maths à ce sujet :

http://www.developpez.net/forums/sho...d.php?t=528152

---

Effectivement j'y vois comme un air de ressemblance ;)

C'est ce que tu as utilisé pour "cracker" mon Hash ?
Aie et bien cela confirme encore plus ce que tu me disais...
Bien que je sois certains ou presque que la chance que ces combinaisons soient des mots de la langue existant est très faible.

Je suis très content de l'approche "fine" et mathématique du problème !

Merci encore pour l'énergie dépensée

PS: L'algorythme ne tient pas compte du sens des combinaisons de caractère mais il peut être utile pour limité l'exploration des collisions => comparaison entre un dictionnaire et une liste contenant toutes les collisions possibles cela réduit de beaucoup la recherche.