Forum Programmation.c fonction de hashage de chaine de characteres

Posté par  .
Étiquettes : aucune
0
15
juin
2008
Bonjour,

Je suis a la recherche d'une bonne fonction de hachage pour des chaines de characteres qui soit rapide (pas une fonction cryptographique).
Qui ait la propriete suivante:

Soit a et b 2 chaines de characteres.
Soit ab la concatenation de a et b:

hash(ab) = une fonction rapide a calculer a partir de hash(a) et hash(b)

L'idee c'est de pouvoir calculer le hash de la concatenation a partir du hash des sous chaines.

Quelqu'un a une idee?

  • # modulo

    Posté par  . Évalué à 5.

    La fonction de hashage la plus basique qui soit est la fonction modulo. si N est la taille du hash, tu as:

    hash(a) ≡ a [2^N] (formule 1)
    hash(b) ≡ b [2^N] (formule 2)

    hors tu sais que :

    ab = a*2^(8*taille_en_octets(b))+b (formule 3)

    et si on note :

    decal(b) = 2^(8*taille_en_octets(b))

    la formule 3 se réecrit en :
    ab = a*decal(b)+b (formule 4)

    d'ou :

    hash(ab) ≡ a*decal(b)+b [2^N] (formule 5)

    rappelons que (théorème 1) :

    si a1 ≡ b1 [n] et a2 ≡ b2 [n] => a1+a2 ≡ b1+b2 [n] et a1*a2 ≡ b1*b2 [n]

    et posons alors :

    hash(decal(b)) ≡ decal(b) [2^N] (formule 6)

    ce qui donne en multipliant la formule 1 et 6 à l'aide du théorème 1 :


    hash(a)*hash(decal(b)) ≡ a*decal(b) [2^N] (formule 7)

    en recomposant la formule 7 avec la formule 2 on obtient alors :

    hash(a)*hash(decal(b))+hash(b) ≡ a*decal(b)+b [2^N]

    on reconnait dans la partie de droite la formule 5, on en déduit imédiatement que :

    hash(ab) ≡ hash(a)*hash(decal(b))+hash(b) [2^N]

    j'espère que ça pourrra t'aider!

    • [^] # Re: modulo

      Posté par  . Évalué à 1.

      Merci pour ta reponse.
      Par contre je ne comprend pas comment je peux l'adapter au chaines de characteres.

      Tu proposes:
      hash(a) ≡ a [2^N]

      Est ce que ca veux dire que "a" dans ta formule est deja le hash d'une chaine.
      Si je comprend bien, je dois appliquer 2 hash different: un qui transforme la chaine en int (par example djb2 ( http://www.cse.yorku.ca/~oz/hash.html ), l'autre qui transforme cet int en un autre int (la fonction que tu proposes) .

      C'est bien ca?

      • [^] # Re: modulo

        Posté par  . Évalué à 3.

        la chaine de caractère est déjà un nombre en temps que telle. c'est une une suite d'octets quand on regarde sa représentation interne. ce qu'il te faut c'est donc une librairie qui travaille sur de grand nombres... et qui proposent généralement les fonctions de congruances (ou modulo). je n'en ai pas en tête là comme ça. une recherche sur google devrait t'aider.

        • [^] # Re: modulo

          Posté par  . Évalué à 2.

          En C, il me semble q'une chaine de char est juste un pointeur vers l'addresse du premier char.
          Ca me semble pas terrible d'utiliser cette addresse comme valeur pour la chaine.

          • [^] # Re: modulo

            Posté par  . Évalué à 2.

            Ah je viens de comprendre ton idee: la valeur de hash serait l'interpretation en int de la concatenation de tout les bits des chars qui forme la chaine.
            Dans ce cas la, il me semble beaucoup plus econome en temps de calcule d'utiliser un hash sur la chaine comme djb2 puis de re-hacher avec ta fonction pour obtenir la propriete recherche

            • [^] # Re: modulo

              Posté par  . Évalué à 1.

              non, le hash calculé par cette librairie ne possède pas les propriété que tu recherche. la hash de la concaténation ne fonctionnera pas, tu obtiendra un mauvais résultat. car
              djib2_hash(ab) ne possède pas les propriété de concaténation que tu recherche.... tout simplement

      • [^] # Re: modulo

        Posté par  . Évalué à 1.

        pour répondre plus spécifiquement à ta question, non la formule 1 est une formule de congruance. dans ton programme en c tu devra donc calculer avec une librairie sur les grand nombres :

        char* a = "une chaine";
        unsigned long long hash; // hash sur 64 bits => 2^64 =
        hash = modulo(a,18446744073709551616L);

        tu dois donc trouver une librairie capable de calculer le modulo de grand nombres, à toi de convertir ta chaine dans la représentation interne des grands nombres pour cette librairie.

        • [^] # Re: modulo

          Posté par  . Évalué à 1.

          Je suis en train d'ecrire un parseur qui separe tout les mots d'un flux.
          Donc a chaque espace, je cree un token qui contient le dernier mot.

          Je pourais faire un malloc puis strcpy du mot a chaque fois que je tombe sur un espace et considerer ca comme un token, mais je prefere calculer un hash puisque je n'ai pas besoin du mot en temps que tel, j'ai juste besoin d'etre capable de savoir si il est egal a un autre mot.

          Ensuite j'ai besoin de comparer une concatenation de mots avec une autre.

          Utiliser une librairie qui gere les grand nombre va de toute facon faire des malloc dans mon dos.
          L'idee c'est d'avoir un truc tres rapide et pas gourmant en memoire.
          Le tout est de trouver la bonne fonction de hash.

          • [^] # Re: modulo

            Posté par  . Évalué à 1.

            je crois que tu te trompe de solution, le calcul de hash sera toujours couteu si tu veux avoir la propriété de concaténation que tu souhaite.
            sauvegarde plutôt directement le pointeur ou encore mieux la position du mot que tu vient de trouver et sa taille dans une structure du genre :

            token {
            unsigned long position;
            unsigned long size;
            };

            fabrique ensuite une fonction capable de tester si plusieurs tokens correspondent à une chaine plus longue, elle pourrait avoir comme prototype :

            int compare_token_with_string(char* a_string, token* list_of_tokens) ;

          • [^] # Re: modulo

            Posté par  . Évalué à 0.

            > je prefere calculer un hash puisque je n'ai pas besoin du mot en temps que tel, j'ai juste besoin d'etre capable de savoir si il est egal a un autre mot.

            pour savoir si 2 mots sont égaux, il n'y a pas d'autre choix que strcmp.
            Même hash ⇏ Même objet
            mais
            Même objet ⇒ Même hash
            et sa contraposée :
            Pas même hash ⇒ Pas même objet

    • [^] # Re: modulo

      Posté par  . Évalué à 1.

      pour aller plus loin tu notera que decal(b) pose problème).
      Tu ne peux donc pas simplement calculer le hashde ab à partir du hash de a et de b.
      Il te faut retenir la taille en octets de la chaine originale.
      Donc à chaque fois que tu calcule le hash d'une chaine de caractère, tu devra retenir aussi sa taille. celà ne devrait pas poser de problème, il te suffirra d'encapsuler le tout dans une structure du genre ( si tu utilise un pour un long long pour le hash) :

      struct mata_hash {
      unsigned long long hash;
      unsigned long size;
      };

  • # facile

    Posté par  . Évalué à 0.

    L'idee c'est de pouvoir calculer le hash de la concatenation a partir du hash des sous chaines.

    hash(ab) = hash(a) + hash(b)

    ca ne te va pas ?
    pourtant ca correspond à ton enoncé.

    evidemment tu peux remplacer le + par -,/,x ou peut-etre une simple concatenation
    hash(ab) = hash(a) - hash(b)
    hash(ab) = hash(a) / hash(b)
    hash(ab) = hash(a) x hash(b)
    hash(ab) = concat(hash(a),hash(b))

    • [^] # Re: facile

      Posté par  . Évalué à 2.

      Ca marche, c'est vrai mais c'est une tres mauvaise fonction de hachage.

      • [^] # Re: facile

        Posté par  . Évalué à 3.

        c'est plus que mauvais. hash(ab) = hash(ba)... donc deux chaines qui auront les même caractères dans un ordre different auront le même hash, sans compter que ton hash ne sera pas borné avec une addition ou une multiplication... ce qui est inacceptable pour une fonction de hashage.... avec la division c'est encore pire,.. tu arrivera vite à un hash de zéro si b plus grand que a. même type de problème avec la soustraction.

  • # hash

    Posté par  . Évalué à 2.

    tu demandes une fonction de hashage sans donner le type de données a stocker (differenciation des entrées: noms, refs, etc..) , ni la quantité, et c'est important.

    Maintenant si tu veux un truc rapide, qui marche sur des chaines ayant des débuts identiques, et pour un nombre réduit d'entrées, un simple xor sur la chaine suffit.
    a[0]xor ... a[n]
    le xor des 2 hash donne le xor de la chaine
    et en plus du hash +1chaine te sort le hash de l'autre chaine

  • # la fonction de hash de Daniel J. Bernstein...

    Posté par  . Évalué à 2.

    vérifie la propriété que tu cherches : 
    unsigned int DJBHash(char* str, unsigned int len)
{
   unsigned int hash = 5381;
   unsigned int i    = 0;

   for(i = 0; i < len; str++, i++)
   {
      hash = ((hash << 5) + hash) + (*str);
   }

   return hash;
}
/* End Of DJB Hash Function */
    • on peut remplacer la constante initiale 5381 par n'importe quelle autre (appelons-là L comme level). 
    • hash = ((hash << 5) + hash) + (*str);
      est équivalent à 
      hash = 33*hash + (*str);
    du coup quand on a deux sous-chaines s1 et s2, on a la propriété suivante (si l1 et l2 sont leurs longueurs respectives) : 
    h(s1s2) = 33^l2*(h(s1) - L) + h(s2)
    y'a plus qu'à précalculer l'exponentiation rapide de base 33 et le tour est joué... fonction (très) rapide, relativement efficace et calculable récursivement à l'aide des valeurs des sous-chaines... mes 2 cents !

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.