[Algo] Fonction de hachage insensible à une permutation circulaire.

[invite252d2edc]

Bonjour,

Alors voilà, je cherche à créer un algo calculant l'empreinte d'un n-uplet.

Exemple:
(1 ; 0.75 ; -0.5 ; 0.5 ; -0.25 ; 0.25 ; 0) => fdsf54ds (exemple d'empreinte)

Je pense que cela correspond à une fonction de hachage (l'avantage pour moi, c'est de pouvoir comparer les empreintes plutôt que les n-uplets).

Le problème est le suivant :
il faut que la fonction de hachage soit insensible à une sorte de 'permutation circulaire', c'est à dire que les sept-uplets suivants doivent tous avoir la même empreinte :

(0 ; 0.75 ; -0.5 ; 0.5 ; -0.25 ; 0.25 ; 0) => fdsf54ds
(0.75 ; -0.5 ; 0.5 ; -0.25 ; 0.25 ; 0 ; 0.75) => fdsf54ds
(-0.5 ; 0.5 ; -0.25 ; 0.25 ; 0 ; 0.75 ; -0.5) => fdsf54ds
(0.5 ; -0.25 ; 0.25 ; 0 ; 0.75 ; -0.5 ; 0.5) => fdsf54ds
(-0.25 ; 0.25 ; 0 ; 0.75 ; -0.5 ; 0.5 ; -0.25) => fdsf54ds
(0.25 ; 0 ; 0.75 ; -0.5 ; 0.5 ; -0.25 ; 0.25) => fdsf54ds

Je ne sais pas comment le faire.
J'ai commencé par étudier une fonction f(a, b, c, d, e, f, g, h), mais je ne sais pas quoi choisir pour f.
Note: en d'autres termes, je cherche une fonction f qui vérifie :
f(a, b, c, d, e, f, g, h) = f(b, c, d, e, f, g, h, a) = f(c, d, e, f, g, h, a, b) = f(d, e, f, g, h, a, b, c) = f(e, f, g, h, a, b, c, d) = f(f, g, h, a, b, c, d, e) = f(g, h, a, b, c, d, e, f) = f(h, a, b, c, d, e, f, g)

Merci.
-----

[Médiat]

Bonjour,

(0 ; 0.75 ; -0.5 ; 0.5 ; -0.25 ; 0.25 ; 0) => fdsf54ds
(0.75 ; -0.5 ; 0.5 ; -0.25 ; 0.25 ; 0 ; 0.75) => fdsf54ds
(-0.5 ; 0.5 ; -0.25 ; 0.25 ; 0 ; 0.75 ; -0.5) => fdsf54ds
(0.5 ; -0.25 ; 0.25 ; 0 ; 0.75 ; -0.5 ; 0.5) => fdsf54ds
(-0.25 ; 0.25 ; 0 ; 0.75 ; -0.5 ; 0.5 ; -0.25) => fdsf54ds
(0.25 ; 0 ; 0.75 ; -0.5 ; 0.5 ; -0.25 ; 0.25) => fdsf54ds

Une solution bête : ordonner les n-uplets avant de hacher, dans votre cas c'est la ligne 3 qui sera hachée dans tous les cas.

[invite986312212]

non, ordonner ne correspond pas à une permutation circulaire.

[invite252d2edc]

Merci pour votre réponse !
J'ai effectivement pensé à "ordonner les n-uplets avant de hacher" mais suivant quels critères ? En effet, ce que je redoute, c'est qu'il y ai plusieurs solution (uplets) retenues et donc des hachages différents.

dans votre cas c'est la ligne 3 qui sera hachée dans tous les cas.

Selon quels critères ?


EDIT: ce que j'entends par ordonner les n-uplets, c'est les classer pour n'en garder que un (que l'on va ensuite hacher).

[A voir en vidéo sur Futura]

[invité576543]

Un algo possible, mais sûrement trop cher, est de combiner par une opération commutative les résultats des hachages de toutes les permutations circulaires.

[Médiat]

non, ordonner ne correspond pas à une permutation circulaire.

Je me suis mal exprimé (mais l'exemple aurait dû lever l'ambiguité):
je n'ai pas écrit "ordonner le n-uplet", mais "ordonner les n-uplets", j'aurais dû ajouter "correspondant aux différentes permutation circulaires du n-uplet à hacher".

[Médiat]

En effet, ce que je redoute, c'est qu'il y ai plusieurs solution (uplets) retenues et donc des hachages différents.

Attention ce qui suit n'est pas un algotithme optimal (loin de là) c'est juste pour mieux expliquer :
1) vous générez toutes les permutations circulaires, ce qui vous donne n n-uplets.
2) vous ordonnez ces n-uplets dans l'ordre lexicographique
3) vous hachez le premier.

[invité576543]

Mais l'idée d'ordonner le n-uplet puis hacher est une bonne idée, cela peut marcher si la relation d'ordre est totale, non?

Cela rend bien le résultat insensible à une permutation circulaire de l'entrée, non?

Il ne me semble pas important que le hachage soit celui d'une des permutations circulaires. Est-ce le cas?

[invite986312212]

j'avais compris que fitzy cherchait une fonction de R^n dans R, invariante par permutation circulaire des arguments mais injective sur l'ensemble quotient de R^n par le groupe des permutations circulaires. Si on abandonne l'injectivité on peut ordonner le n-uple en effet.

[invite252d2edc]

combiner par une opération commutative les résultats des hachages de toutes les permutations circulaires.

Oui, cela est intéressant !
Mais quel genre "d'opération commutative" ? Avez vous un exemple ?

Notez que j'ai dis qu'il s'agit d'une sorte de permutation circulaire.
Si on regarde les n-uplets de mon premier post, on s'aperçoit que la dernière valeur de chaque n-uplet est la même que le première valeur de ce n-uplet.
Je ne suis pas sûr que ce soit tout à fait cela une permutation circulaire.

[invite986312212]

la dernière valeur qui répète la première, tu peux la virer pusiqu'elle n'apporte aucune information et tu as bien des permutations circulaires.

[invite252d2edc]

Malheureusement, on ne peut pas ordonner les valeurs des n-uplets, on peut simplement faire la transformation que j'ai décrite dans mon premier message.

[invite252d2edc]

la dernière valeur qui répète la première, tu peux la virer pusiqu'elle n'apporte aucune information et tu as bien des permutations circulaires.

Oui en effet !

[invité576543]

Oui, cela est intéressant !
Mais quel genre "d'opération commutative" ? Avez vous un exemple ?

Le min, le max, l'addition, l'addition modulo 2 bit à bit (aka ou exclusif, aka addition dans Z/2Z[X]), ...

En complexité sur une machine usuelle, le moins coûteux doit être le dernier (ou exclusif bit à bit). Min et max ne coûtent pas plus cher, mais ont le mauvais goût de concentrer le résultat du hachage.

Notez que j'ai dis qu'il s'agit d'une sorte de permutation circulaire.
Si on regarde les n-uplets de mon premier post, on s'aperçoit que la dernière valeur de chaque n-uplet est la même que le première valeur de ce n-uplet.
Je ne suis pas sûr que ce soit tout à fait cela une permutation circulaire.

Non, ce n'est pas une permutation circulaire. Mais cela ne change pas grand chose aux différentes propositions, pour peu que la construction soit systématiquement "permutation circulaire des n-1 termes, puis concaténation du premier terme à la fin".

[Médiat]

Notez que j'ai dis qu'il s'agit d'une sorte de permutation circulaire.

Vous voulez que ce soit invariant par permutation circulaire ou non ?

Le fait que le dernier élément d'un n-uplet soit égal au premier ne change rien, c'est juste une notation qui fait que l'on répète le premier élément à la fin (peut-être pour indiquer qu'il s'agit d'un cycle, ce qui expliquerait votre désir d'invariance par permutation circulaire).

Il va de soi que dans la solution que je propose, il ne faut pas tenir compte de ce dernier élément pour construire les différentes permutations (mais du point de vue algorithmique, ce n'est, de toute façon, pas la meilleure solution, je le répète).

Si mon interprétation n'est pas la bonne, merci de préciser votre problème.

[Médiat]

Malheureusement, on ne peut pas ordonner les valeurs des n-uplets, on peut simplement faire la transformation que j'ai décrite dans mon premier message.

Vous voulez dire que l'on ne peut pas changer un n-uplet sauf par permutation circulaire ?
Si oui, je répète que ce n'est pas ce que je propose (je propose d'ordonner l'ensemble des n-uplets, et non d'ordonner un n-uplet) !

[invité576543]

Un autre point est s'il est recherché un hachage "efficace", donc prendre un algo réputé, bien testé quand à ses propriétés en collision (genre SHA-1), ou si on peut se contenter d'un hachage "tout venant".

Dans le dernier cas, un hachage commutatif simple peut faire l'affaire, comme le ou exclusif bit à bit des représentations binaires des réels en question.

Tel quel, ce n'est pas terrible, parce qu'il y a peu d'information dans les bits de poids fort.

Une amélioration consiste à faire le ou exclusif bit à bit des représentations binaires des f(x_i), avec f une fonction à choisir, de R dans 0..2^n-1, choisie pour "étaler" au mieux l'espace de départ.

[invite252d2edc]

Merci à vous !

@Médiat : absolument, je veux que ce soit invariant par permutation circulaire et on ne peut pas changer un n-uplet sauf par permutation circulaire.
Mais je persiste à penser que votre solution me convient :
je considère la permutation circulaire comme un phénomène parasite (duplication).
(Ce qui suit ne va sûrement pas être très clair)
Au final, je me fiche d'avoir un hachage identique pour chaque uplet issu d'une permutation circulaire, puisqu'en fait on génère toutes les permutations circulaires et on en garde que une (donc on a un unique hachage).
Exemple:
Si j'ai (0 ; 0.75 ; -0.5 ; 0.5 ; -0.25 ; 0.25)
1. je calcule les permutations circulaires
2. je les classes par ordre lexicographique : j'obtient (-0.5 ; 0.5 ; -0.25 ; 0.25 ; 0 ; 0.75)

Si j'ai (-0.25 ; 0.25 ; 0 ; 0.75 ; -0.5 ; 0.5)
1. je calcule les permutations circulaires
2. je les classes par ordre lexicographique : j'obtient (-0.5 ; 0.5 ; -0.25 ; 0.25 ; 0 ; 0.75) (la même chose quoi)

J'ai donc le même hache pour n'importe quelle permutation circulaire.


--

Je compte donc faire :
1. calcule les permutations circulaires
2. classement par ordre lexicographique
3. hachage du premier uplet du classement

[Médiat]

Je compte donc faire :
1. calcule les permutations circulaires
2. classement par ordre lexicographique
3. hachage du premier uplet du classement

En terme d'algorithme, il est sans doute plus efficace de chercher dans le n-uplet l'élément le plus petit, et s'il est unique, on peut tout de suite exhiber le bon n-uplet à hacher ; s'il n'est pas unique on compare deux éléments successifs à partir des différents "plus petits", s'il n'y a qu'un seul couple plus petit, c'est gagné, sinon on regarde 3 éléments et on continue.

Dans la pire solution, on doit quand même aller plus vite qu'en calculant toutes les permutations ; mais ce n'est qu'une question d'implémentation.

[invite7768d2d9]

Le min, le max, l'addition, l'addition modulo 2 bit à bit (aka ou exclusif, aka addition dans Z/2Z[X]), ...

Il faut faire attention quand même ici avec les opérations commutatives parce que l'on peut perdre totalement l'ordre des éléments de ton n-uplet.

Je veux dire, dans ce cas tu vas bien avoir


Mais tu risques d'avoir aussi


Ainsi qu'avec toutes les permutations possibles dans le n-uplet. La quantité d'information perdu est donc importante.

Je pense que l'idée de choisir un critère qui permet de prendre toujours la même rotation des éléments pour commencer le calcul est pas mal. Comme par exemple, effectuer la rotation qui place le plus petit élément en premier et ensuite faire son hachage. Par contre, ça pose problème si il y a plusieurs plus petits éléments...

[invite7768d2d9]

oups, mal lu.

Oui sur les resultats des différentes permutations, c'est une bonne idée

[invite252d2edc]

Ce sujet est plein de bonnes idées !

Merci à vous tous vous m'avez beaucoup aidé !