Répondre à la discussion
Affichage des résultats 1 à 22 sur 22

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



  1. #1
    fitzy

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

    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.

    -----


  2. Publicité
  3. #2
    Médiat

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

    Bonjour,
    Citation Envoyé par fitzy Voir le message
    (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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  4. #3
    invite986312212
    Invité

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

    non, ordonner ne correspond pas à une permutation circulaire.

  5. #4
    fitzy

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

    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).
    Dernière modification par fitzy ; 03/08/2010 à 10h12.

  6. #5
    invité576543
    Invité

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

    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.

  7. A voir en vidéo sur Futura
  8. #6
    Médiat

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

    Citation Envoyé par ambrosio Voir le message
    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".
    Dernière modification par Médiat ; 03/08/2010 à 10h22.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  9. Publicité
  10. #7
    Médiat

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

    Citation Envoyé par fitzy Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  11. #8
    invité576543
    Invité

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

    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?

  12. #9
    invite986312212
    Invité

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

    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.

  13. #10
    fitzy

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

    Citation Envoyé par Michel (mmy) Voir le message
    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.

  14. #11
    invite986312212
    Invité

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

    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.

  15. #12
    fitzy

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

    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.

  16. Publicité
  17. #13
    fitzy

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

    Citation Envoyé par ambrosio Voir le message
    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 !

  18. #14
    invité576543
    Invité

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

    Citation Envoyé par fitzy Voir le message
    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".
    Dernière modification par invité576543 ; 03/08/2010 à 10h55.

  19. #15
    Médiat

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

    Citation Envoyé par fitzy Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  20. #16
    Médiat

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

    Citation Envoyé par fitzy Voir le message
    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) !
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  21. #17
    invité576543
    Invité

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

    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(xi), avec f une fonction à choisir, de R dans 0..2n-1, choisie pour "étaler" au mieux l'espace de départ.
    Dernière modification par invité576543 ; 03/08/2010 à 11h07.

  22. #18
    fitzy

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

    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
    Dernière modification par fitzy ; 03/08/2010 à 11h21.

  23. Publicité
  24. #19
    Médiat

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

    Citation Envoyé par fitzy Voir le message
    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.
    Je suis Charlie.
    J'affirme péremptoirement que toute affirmation péremptoire est fausse

  25. #20
    shyzen

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

    Citation Envoyé par Michel (mmy) Voir le message
    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...

  26. #21
    shyzen

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

    oups, mal lu.

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

  27. #22
    fitzy

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

    Ce sujet est plein de bonnes idées !

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

Sur le même thème :

Discussions similaires

  1. Problème du plus court chemin ( Algo de dijkstra, algo A*)
    Par mathrider dans le forum Mathématiques du supérieur
    Réponses: 3
    Dernier message: 12/06/2010, 10h25
  2. Fonction circulaire reciproque.
    Par Mikihisa dans le forum Mathématiques du supérieur
    Réponses: 5
    Dernier message: 21/12/2009, 14h24
  3. Etude de la fonction circulaire tan(x)
    Par monkeyfonky dans le forum Mathématiques du collège et du lycée
    Réponses: 6
    Dernier message: 17/05/2009, 09h51
  4. aire circulaire et fonction polynome !
    Par amelhi dans le forum Mathématiques du collège et du lycée
    Réponses: 3
    Dernier message: 02/11/2007, 15h50
  5. Hachage
    Par GalacticSwirl dans le forum Mathématiques du supérieur
    Réponses: 0
    Dernier message: 12/03/2006, 09h54