Efficacité d'un algorithme de hachage de chaînes de caractères - Page 1

Je suis en train de réfléchir à une méthode de hachage de chaînes de caractères "efficace". Par efficace, j'entends le fait que, quand le nombre de chaînes hachées tend vers l'infini, la répartition des valeurs de hachage est homogène.


La seconde contrainte, c'est qu'il doit être rapide (je cherche en fait le meilleur compromis efficacité/rapidité).


Contexte : il faut produire une table de hachage de dimension assez faible (pas plus de 1024 éléments, 512 étant mieux).
On travaille sur des mots anglais.



Exemple : pour 10240 chaînes hachées sur 8 bits, j'aimerais que l'on trouve théoriquement :

- 40 fois la valeur 0b00000000
- 40 fois la valeur 0b00000001
- 40 fois la valeur 0b00000010
...
- 40 fois la valeur 0b11111111




MAJ du 12 octobre :

Après divers test, que vous pourrez lire au fil des pages de ce sujet de discussion, il s'avère que la fonction la plus intéressante* dans le contexte de ce fil de discussion, est fast_and_perfect_hash (elle est présentée au post ./170). Son nom est un peu prétentieux mais j'en prends la responsabilité

Elle est basée sur le fameux algorithme de Daniel Julius Bernstein (DJB). Pollux a considérablement optimisé en vitesse l'implémentation de base, et d'autres optimisations ont été apportées par Pen^2 et moi.
Attention, cette fonction optimisée ne fonctionne que si HASH_TABLE_SIZE est une puissance de 2 et qu'elle est inférieure ou égale à 1024. Sinon, utilisez DJBHash, la fonction originale de Daniel Julius Bernstein, qui est plus lente mais sans limites sur le modulo.

Pour les autres fonctions, vous pourrez prendre connaissance de leur efficacité dans les pages suivantes. Je n'en parle pas dans cette conclusion car, dans le contexte de ce fil de discussion, la plupart donne des résultats à peine meilleurs que la gagnante du test alors qu'elles sont beaucoup plus lentes.


Vous trouverez la source de toutes ces fonctions dans l'archive hashtest.zip, qui contient aussi et surtout la moulinette qui a permis le classement d'efficacité des fonctions.


Pour toutes les fonctions de hachage, il est mieux de les utiliser avec des modulos de nombres premiers (c'est à dire que HASH_TABLE_SIZE doit être premier). Il y a cependant 2 fonctions qui donnent de très bons résultats quand le modulo est particulier :

- Quand HASH_TABLE_SIZE vaut 256, 512 ou 1024 : fast_and_perfect_hash est la meilleure de toutes, comme cela est expliqué plus haut.

- Quand HASH_TABLE_SIZE vaut 256 : hash_toutcon. hash_toutcon produit une table aussi uniforme que DJBHash (1 point d'écart sur une variance d'à peu près 26) mais elle est plus rapide que DJBHash. Déroulée, elle serait donc forcément plus rapide que la gagnante du test (fast_and_perfect_hash).

Au début du paragraphe j'ai écrit qu'il était préférable de travailler avec des modulos de nombres premiers, et juste après je déclare que fast_and_perfect_hash et hash_toutcon sont les meilleures alors qu'elles utilisent des nombres pairs (et plus précisément : puissances de 2)... Quel est l'intérêt d'avoir une table de hachage dont la taille est une puissance de 2 ?
Cela accélère énormément le calcul final, celui que vous trouverez à la fin de chaque fonction. Le calcul d'un modulo est parmi les instructions les plus lentes à réaliser pour un microprocesseur. Quand le dénominateur d'un modulo est une puissance de 2, le calcul est sensiblement accéléré (on passe de 70 cycles processeur à 4 ou 6 cycles). Certes, la table est légèrement moins homogène, donc la recherche linéaire est un peu plus longue en moyenne (en pratique la différence d'homogénéité est très très faible, cf le comparatif du post ./216). Mais le temps gagné lors du calcul compense le temps perdu dans la recherche linéaire.
Cela est particulièrement vrai quand le nombre de collisions est raisonnable, par exemple quand 10.000 chaînes ou moins sont réparties sur une table de taille 1024. D'une manière générale, il semblerait que plus la table de hachage est grande, plus on a intérêt à lui donner une taille puissance de 2. En effet, le nombre moyen de collisions diminuant, la recherche linéaire est plus rapide et le léger défaut d'homogénéité est moins sensible, donc le temps gagné dans le calcul du modulo est plus flagrant.



* "la plus intéressante" = "donnant le meilleur compromis entre l'homogénéité de la table et la vitesse de calcul"
En l'occurrence, fast_and_perfect_hash produit la table de hachage la plus uniforme tout en étant la plus rapide.



Vous pouvez télécharger la moulinette de comparaison ici : Fichier joint : hashtest.zip

MD5 puis tu fais un xor de tous les bytes

a mon avis toutes les fonctions qui brassent suffisamment les données avec des xor ou des sommes sont efficaces.

Le MD5 c'est long à calculer ? Il me faut le meilleur compromis entre efficacité et vitesse de calcul

En me basant sur les fréquences moyennes d'apparition des lettres dans un texte anglais (cf ici), j'ai inventé une méthode (un peu lente par rapport à un hachage par simple addition des codes ASCII) qui donnerait peut-être de bons résultats.



Constatation :

Dans le lien donné ci-dessus, on observe que l'on trouve presque autant de lettres paires que de lettres impaires dans un texte anglais.
La somme des fréquences des lettres ayant un code ASCII pair est de 43,42 %
La somme des fréquences des lettres ayant un code ASCII impair est de 56,57 %



Exploitation :

J'ai donc pensé qu'en basant mon algorithme sur ce fait, j'obtiendrais une répartition à peu près homogène des valeurs de hachage.
, dans un int }

Voici mon idée :int hash_thib(const unsigned char *c)  // on suppose que la longueur des chaines est toujours
{                                      // multiple de 8, uniquement dans le but de simplifier l'algo
  unsigned char  h, result;
  int bit_index;

  result= 0;

  while (*c != 0) {
    h= 0;
    bit_index= 8;  // on travaille par blocs de 8 caractères

    while (bit_index-- > 0) {
       h= (h << 1) + (*c & 1);  // je pense avoir écrit cette ligne d'une manière claire...
                                // en fait, à la fin de la boucle, chaque bit de h représente
                                // la parité de la lettre correspondante dans le bloc
       c++;
    }

    result+= h;  // cette représentation de la parité des 8 caractères du bloc, on la
                 // considère comme une valeur. On l'additionne alors à la valeur du bloc précédent
  }

  return ((unsigned short)result);  // on renvoit le résultat, compris entre 0 et 255

(J'ai simplifié l'implémentation, car on parle d'algorithme. Il y a moyen de le coder d'une manière relativement plus rapide.)



Qu'en pensez-vous ?

Tiens la méthode de hashage de chaine de caractères que l'on retrouve chez A. V. AHO, R. SETHI, J. D. ULLMAN, du livre "Compiler, Principles, Techniques, and Tools" (et qui l'attribuent eux meme a P. J WEINBERGER) :

int hashpjw(const void *cle)
{
   const char *ptr = cle;
   int val = 0;

   while (*ptr != '\0')
   {
      int tmp;

      val = (val << 4) + (*ptr);

      if (tmp = (val & 0xF0000000))
      {
         val = val ^ (tmp >> 24);
         val = val ^ tmp;
      }

      ptr ++;
   }

   if ((val % PRIME_TBLSIZ) < 0)
   {
      return 0;
   }
   return val % PRIME_TBLTSIZ;
}

Alors a savoir que ce PRIME_TBLSIZ est la taille du tableau de hashage (cette fonction est a la base utilisé pour hasher du texte pour le mettre dans un tableau de hashage)

et cette fonction donne généralement de bon résultats

Ca a l'air pas mal au niveau de l'efficacité, merci

Mais j'ai peur que la calcul du hash soit trop long et que ça rende en pratique la recherche d'un symbole plus lente que si on cherchait avec un arbre binaire (ln n).

Bah, l'algorithme de recherche d'un symbole de ld-tigcc, c'est ça.

// Point the location to the appropriate symbol, if one is found.
SYMBOL *ResolveLocation (PROGRAM *Program, SECTION *Section, LOCATION *Location)
{
	if (Location->Symbol)
		return Location->Symbol;
	else
	{
		SECTION *CurSection;
		
		// For each section...
		for_each (CurSection, Program->Sections)
		{
			SYMBOL *CurSymbol;
			
			// For each symbol...
			for_each (CurSymbol, CurSection->Symbols)
			{
				// If the name matches, we have found the right symbol.
				if (CurSymbol->Exported && (!(strcmp (Location->SymbolName, CurSymbol->Name))))
				{
					// Set up the reloc accordingly, freeing its
					// destination string.
					Location->Symbol = CurSymbol;
					FreeLocationSymbolName (Section, Location);
					return CurSymbol;
				}
			}
		}
		
		return NULL;
	}
}

et il est ou le hachage la dedans?

C'est peut-être l'une des raisons de la lenteur de TIGCC Enfin bon, sur PC ça a peu d'importance.


J'ai trouvé ça sur wikipedia :

unsigned int hach_string(const char *str) 
{
        unsigned int hash = 5381; // DJB Hash
        const char *s;
        for (s = str; *s; s++) {
                hash = ((hash << 5) + hash) + tolower(*s);
        }
        return (hash & 0x7FFFFFFF)%HACH_TABLE_MAX;
}

Ils disent qu'elle donne une répartition des valeurs de hachage remarquablement homogène. En plus, elle me semble assez rapide (à condition que tolower(x) soit un simple accès à une table précalculée)



En fait, il faudrait pouvoir comparer les efficacités de tous ces algos (pour la vitesse on devine à peu près ce que ça donne à vue d'oeil). Je vais construire un petit code qui parse un gros fichier texte, puis hache les mots avec les différentes méthodes, et enfin calcule l'écart type des fréquences d'apparition de chaque valeur de hachage possible.

C'est bien l'écart type qui donnera une idée de l'homogénéité de chaque table ?

squalyl (./8) :
et il est ou le hachage la dedans?

Justement, il n'y en a pas.
Tout ça pour montrer que ça ne sert pas à grand chose d'optimiser le lookup d'un symbole, ld-tigcc fait une recherche linéaire et ça marche aussi.

Kevin, ça ne sert pas à grand chose dans TON contexte. J'ai une contrainte sur le temps de recherche à respecter.

Dis-donc, je sais pas ce que tu fais comme job, mais j'ose pas imaginer la lenteur des logiciels de ta boîte

bah ué on est d'accord bon, si il veut en faire un justement

Intéressant comme probleme.

Par efficace, tu veux surtout optimiser l'accès... Le temps d'attente en moyenne quand on cherche un symbole quoi. Donc pourquoi pas imaginer un truc qui renvoie plus rapidement les éléments les plus demandés (un peu à la Huffman peut etre?)

Kevin: en meme temps si tu as 100/1000 symboles la différence doit pas etre énorme par contre, des que tu te tape dans le million voir plus de symboles j'ose meme pas imaginer la vitesse de ton truc..

ça se trouve pas souvent dans un linker pour ti. Donc oui il a raison ça suffit, mais y'a pas de rapport avec la question de thi

(il a parlé de TI ?)

D'ailleurs sauf si j'ai mal lu, tu vises quelle plateforme Thibaut ?

(il a parlé de ld-tigcc)

(pour répondre à KK non ?)

Ximoon (./16) :

squalyl (./15) :
ça se trouve pas souvent dans un linker pour ti. Donc oui il a raison ça suffit, mais y'a pas de rapport avec la question de thi

(il a parlé de TI ?)

thi = thibaut je pense.

Ximoon (./16) :
D'ailleurs sauf si j'ai mal lu, tu vises quelle plateforme Thibaut ?

mmh.... un truc qui tourne pas très vite... 12 MHz je crois

onur (./13) :
Par efficace, tu veux surtout optimiser l'accès... Le temps d'attente en moyenne quand on cherche un symbole quoi. Donc pourquoi pas imaginer un truc qui renvoie plus rapidement les éléments les plus demandés (un peu à la Huffman peut etre?)

Pas con Il faudrait reprendre un peu le principe de la version progressive d'Huffman alors, car je dois tout faire à la volée.

Ah non malheureux ! Rien en vaut le clavier et l'écran d'une 92+

Thibaut (./9) :
C'est peut-être l'une des raisons de la lenteur de TIGCC Enfin bon, sur PC ça a peu d'importance.


J'ai trouvé ça sur wikipedia :

unsigned int hach_string(const char *str) 
{
        unsigned int hash = 5381; // DJB Hash
        const char *s;
        for (s = str; *s; s++) {
                hash = ((hash << 5) + hash) + tolower(*s);
        }
        return (hash & 0x7FFFFFFF)%HACH_TABLE_MAX;
}

Ils disent qu'elle donne une répartition des valeurs de hachage remarquablement homogène. En plus, elle me semble assez rapide (à condition que tolower(x) soit un simple accès à une table précalculée)



En fait, il faudrait pouvoir comparer les efficacités de tous ces algos (pour la vitesse on devine à peu près ce que ça donne à vue d'oeil). Je vais construire un petit code qui parse un gros fichier texte, puis hache les mots avec les différentes méthodes, et enfin calcule l'écart type des fréquences d'apparition de chaque valeur de hachage possible.

C'est bien l'écart type qui donnera une idée de l'homogénéité de chaque table ?

Personnellement, j'utilise comme itération :
(((h1) * 31421) + (h2) + 6927)
Comme çà, çà à l'air plus lent. Mais ca permet d'avoir un programme 15% plus rapide qu'avec la méthode que tu proposes (testé à l'instant) - d'un autre coté, je ne l'utilise pas que pour des chaines de caractères -.

Il faut poser une limite sur la longueur de la partie hachée des chaînes (à moins que dans ton contexte les mots aient un très long préfixe).

Mais pourquoi ne pas utiliser un arbre lexicographique plutôt qu'une table de hachage ?
Pour rappel, c'est un arbre dans lequel la clef correspond au chemin depuis la racine.
Par exemple, pour la chaîne "toto" on prend la branche "t" puis "o" puis "t" puis "o" pour accéder à l'élément associé.

Ça se coderait comme ça (y'a plein d'optimisations possibles) :

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

struct noeud;
struct noeud {
  struct noeud *leafs[256] ;
  void *v;
};

void* get (struct noeud *tree, char *k) {
  if (tree == NULL) {
    return NULL;
  }
  if (*k == '\0') {
    return tree->v;
  }
  return get (tree->leafs[*k], k + 1);
}

struct noeud* add (struct noeud *tree, char *k, void *v) {
  if (tree == NULL) {
    int i;
    tree = malloc (sizeof (struct noeud));
    for (i = 0;i < 256;i++) {
      tree->leafs[i] = NULL;
    }
    tree->v = NULL;
  }
  if (*k == '\0') {
    tree->v = v;
  } else {
    tree->leafs[(int) *k] = add (tree->leafs[(int) *k], k + 1, v);
  }
  return tree;
}

int main (int argc, char *argv) {
  char op[1000], k[1000], v[1000];
  struct noeud *dico = NULL;
  while (!feof (stdin)) {
    printf ("> ");
    fflush (stdout);
    scanf ("%s %s", &op, &k);
    if (strcmp (op, "set") == 0) {
      printf ("Enter value for \"%s\": ", k);
      fflush (stdout);
      scanf ("%s", &v);
      dico = add (dico, k, strdup (v));
    }
    if (strcmp (op, "get") == 0) {
      char *val = get (dico, k);
      if (val == NULL) {
        printf ("Not value associated to \"%s\"\n", k);
      } else {
        printf ("Value associated to \"%s\": \"%s\"\n", k, val);
      }
    }
  }
  printf ("\n");
  return 0;
}

En complexité pire cas, y'a pas photo (si v est le nombre de valeurs, tu as au pire "longueur de la clef" opérations avec un dico alors que tu as au pire v opérations avec une table de hachage) et en pratique dans certains cas et bien optimisé un dico peut être plus rapide.

Je n'ai pas très bien saisi. Chaque noeud de l'arbre comporte 36 (26 lettres + 10 chiffres) fils ?



PpHd : Merci pour ta suggestion et ton test de vitesse D'où viennent les valeurs de ta fonction ?
Au fait, pour la vitesse, si tu as 2 mn, je veux bien que tu testes ma fonction. L'implémentation complète et généralisée est celle-ci :

int hash_thib(const char *string, int length)
{
    unsigned char  h, result;
    unsigned char *c;
    int            i8, ir;


    i8= (unsigned int)length / 8;
    ir= (unsigned int)length % 8;

    c= string;
    result= 0;

    while (i8-- > 0) {
        h =     (*c++ & (unsigned char)1);
        h+= h + (*c++ & (unsigned char)1);
        h+= h + (*c++ & (unsigned char)1);
        h+= h + (*c++ & (unsigned char)1);
        h+= h + (*c++ & (unsigned char)1);
        h+= h + (*c++ & (unsigned char)1);
        h+= h + (*c++ & (unsigned char)1);
        h+= h + (*c++ & (unsigned char)1);
        result+= h;
    }

    h= 0;

    while (ir-- > 0) {
        h+= h + (*c++ & (unsigned char)1);
    }
    result+= h;

    return (result);
}

Pour l'efficacité (telle que définie au post ./1) je m'en charge. La moulinette est presque terminée.


PS : pour le tolower(), t'as fait comment ? Finalement je soupçonne (*s>='a' ? *s-('a'-'A') : *s) d'être plus rapide que table_lowchar[*s] en moyenne.

BookeldOr : J'ai regardé ton code. Tel qu'il est, on aurait besoin d'une quantité assez monumentale de mémoire pour s'en servir. En supposant l'arbre équilibré, avec des mots de 3 lettres, on arrive déjà à (4*256)³= 1 Go de mémoire

t's sûr (vraie question)

Ben si j'ai bien compris (j'ai pas regardé dans le détail), chaque noeud comporte 256 fils. Les fils étant des pointeurs, cela fait 4 octets par fils. D'où (4*256)³ octets.

C'est en fait un arbre qui représente toutes les combinaisons de P (profondeur) octets possibles. Autrement dit : tous les mots de P lettres possibles et imaginables au monde.

j'avais ecrit un code comme ca dans mon motus :-)

http://procvor.free.fr/upload/dico.rar

je classais les mots par offset, de 2 lettres je crois,
ca supporte aussi les lettres accentuées

je le trouvais assez rapide, mais bon c'etait un motus

nan mais on ne met que les branches de l'arbre qui mènent effectivement à un mot... Et on rajoute ces branches au fur et à mesure qu'on ajoute des mots dans la base