Comparaison par hash

Bonjour,

Je me trouve face à un dilemme conçernant le choix d'un algorithme approprié pour une tâche. Mon programme doit recevoir en entrée un tableau de longueur inconnue contenant des chaînes séparées avec des délimiteurs (delimiter separated values). Donc, j'ai une fonction map() qui indexe chaque « string » dans un tableau de pointeurs, remplaçant au passage le délimiteur avec un caractère nul ('\0'). À la fin de la fonction map(), je connais le nombre de chaînes à traiter.

Ce que je dois faire, ensuite, c'est : comparer les chaînes entre elles pour voir si il y a des chaînes redondantes. Or, il se peut bien qu'il y ait 10000 chaînes à traiter, de longueurs variables, comme il pourrait en avoir 10…

J'ai pensé utiliser un algorithme de hash dans la fonction map() pour enregistrer le hash de toutes les chaînes et ensuite comparer uniquement les hash… car je ne peux me résoudre à utiliser le bon vieux strcmp(). Ce serait trop long dans les cas extrêmes.

Donc, quel hash utiliser? J'aimerais que le hashing soit rapide, donc il me faut un algorithme assez rapide et sans trop de collisions. J'avais pensé à CRC32, mais comme on ne connaît pas la longueur des chaînes et que les possibilités du CRC32 sont couvertes que dans un int, j'ai bien peur qu'il y ait des collisions…

S.V.P., aidez-moi.

Merci,

Array.

Bonsoir,

Citation:

---

J'avais pensé à CRC32, mais comme on ne connaît pas la longueur des chaînes et que les possibilités du CRC32 sont couvertes que dans un int, j'ai bien peur qu'il y ait des collisions...

---

C'est un peu le principe du hash, cela dit. Une fonction de hachage est une application surjective. Le problème n'est pas tant qu'il y ait des collisions, mais plutôt que celles-ci ne se produisent pas avec des chaînes trop proches, et qu'elles ne soient pas trop fréquentes. Si cette dernière condition est remplie en particulier, alors tu peux te permettre de faire suivre cette opération par une comparaison des chaînes pour voir s'il s'agit ou non d'un faux positif. Tout l'intérêt résidant dans le fait que cela doit demeurer exceptionnel.

Citation:

---

S.v.p. Aidez-moi

---

Je vais peut-être dire une bêtise mais le plus censé ne consisterait-il pas à trier tes chaînes au moment où tu les lis ? Le classement se ferait en une passe et tu saurais immédiatement, à chaque fois, s'il y a des doublons ou pas.

Malheuresement, ce serait trop long, de 1, et de deux, il y a une priorité dans les chaînes qui doit absolument être gardée.

Voilà cependant que j'ai pensé à utiliser le CRC32 suivi de Adler32 (qui est plus rapide), et ranger le tous dans une variable long long 64 bit.
Comme en plus, dans la fonction map(), les longueurs des chaînes sont calculées, je pourrais également faire une struct du genre

Code:

---

struct mystruct { int crc32, int adler32, int size, char *strbytes }

---

Tu peux résoudre le problème de tri très facilement grâce à une LUT : tu initialises un vecteur(N,2) contenant les indices de tes chaînes, et tu tries la deuxième colonne en fonction des chaînes indexées par la valeur contenue dans la cellule. Par contre, du coup, ta map n'est pas forcément le container le plus adapté, il faudra peut-être privilégier un vecteur à la place (il te faut en effet les indices des chaînes pour créer la LUT).

De cette façon, tu vas :

• Conserver l'ordre initial de tes chaînes (ce qui est important dans ton cas).
• Avoir malgré tout une liste correspondante triée.
• Supprimer les doublons avec une liste triée devient trivial, et est en complexité O(N).

Pour le principe de hachage, de toutes façons, tu n'aurais pas été mieux loti (et, au passage, un bête CRC16 serait certainement amplement suffisant de toutes façons). En effet : comment associer la clé à la chaîne ? Via une sorte de LUT, qu'il aurait fallu ... trier de toutes façons ! ;)

Certes, tu vas échanger sur ce coup des comparaisons de chaîne avec des calculs de hachage. Il serait étonnant que la solution que je te propose soit plus lente, SAUF si les chaînes sont massivement semblables (ex : chaînes de plusieurs centaines de caractères qui ont toutes des dizaines de caractères en commun).

A ta place, je ferais ceci :

• Lecture des chaînes et rangement dans le container de façon triée (insertion triée, donc), ce qui devrait être moins pénalisant que le tri après chargement complet.
• Maintien de façon simultanée de la LUT correspondante. Le point difficile est là, il faudra penser à utiliser des références / pointeurs dans la 2ème colonne pour ne pas péter le lien.
• Passe de suppression des doublons : pour éviter les nombreux resize du vecteur, tu peux là encore créer une (sorte de) LUT qui ne contiendra QUE les chaînes uniques, dans l'ordre d'arrivée grâce à la LUT primaire.

Hmmm,

Cette dernière solution, il est vrai, est la meilleure, à quelques modifications près: En combinant un CRC32 au tri, les chaînes à proximité avec le même CRC seront nécessairement pareilles, et même je peux utiliser dans ce cas Adler32, qui est bcp plus rapide pour un peux moins de résistance.

Donc, tri puis Adler32 au passage.
Pourquoi un hash au passge? Parce que les chaînes, en effet, peuvent varier d'un min de 1 caractère pour 512 caractères.

Mais pour avoir une lookup table, il me faut être en C++ non?
Or je veux un code CPP-free (i.e. en C90 pur, voire C99), donc, serais-ce possible quand même, sans vecteur C++???

J'attends vos rép!

Array


P.S.

Citation:

---

Pour le principe de hachage, de toutes façons, tu n'aurais pas été mieux loti (et, au passage, un bête CRC16 serait certainement amplement suffisant de toutes façons). En effet : comment associer la clé à la chaîne ? Via une sorte de LUT, qu'il aurait fallu ... trier de toutes façons !

---

J'avais pensé à faire un array de structures ayant, de 1, un pointeur sur le début de toutes les chaînes avec, de 2, le crc assoicié à la chaîne pointée.

Citation:

---

Envoyé par Array

Cette dernière solution, il est vrai, est la meilleure: En combinant un CRC32 au tri, les chaînes à proximité avec le même CRC seront nécessairement pareilles, et même je peux utiliser dans ce cas Adler32, qui est bcp plus rapide pour un peux moins de résistance.

---

Inutile : à part si tu as des données en quantité absolument colossale (je parle d'une cardinalité approchant le MILLION, là, avec des problèmes de dispersion largement plus problématiques), un CRC sur un domaine d'au moins quatre fois la cardinalité moyenne est habituellement suffisant. Ici, tu parles de 10.000 chaînes, donc un CRC16 est très certainement amplement suffisant.
De toutes façons, je pense que la solution d'une LUT permettant le tri est supérieure à une comparaison par fonction de hachage, vu le volume et le type des données que tu manipules.

Citation:

---

Envoyé par Array

Mais pour avoir une lookup table, il me faut être en C++ non?

---

Pourquoi donc ?? :mrgreen: J'implémentais des LUT en ASM, et sans problèmes, donc je ne pense pas vraiment que le faire en C soit un souci... ;)
C'est un bête tableau dont l'indice correspond à une valeur d'entrée, et le contenu de la cellule à la donnée de sortie, ni plus, ni moins. En général, si l'on veut une double association (pouvoir convertir dans un sens et dans l'autre), on "jointe" logiquement deux vecteurs, mais c'est la seule subtilité possible que je vois dans une LUT...

Le seul problème que tu auras en C, c'est la non-allocation automatique du vecteur. Il te faudra donc jouer avec des realloc de granularité suffisante, et je ne saurais trop te conseiller de rendre cette granularité paramétrable dans ton code (#define de préférence) afin de pouvoir optimiser les perfs sans devenir dingue.

Citation:

---

Envoyé par Array

Or je veux un code CPP-free (i.e. en C90 pur, voire C99), donc, serais-ce possible quand même, sans vecteur???

---

Implémenter un vecteur auto-allouant en C n'est pas très difficile, tout passe par le realloc. Tu n'as pas à te soucier, à priori, de la possibilité de réduire le vecteur (il ne peut que grandir).
Le seul problème "réel" se situe dans l'insertion triée, en fait, faudra faire le code soigneusement. Tu peux toujours, dans un premier temps, faire l'essai en triant après chargement complet, juste histoire de mettre l'algo au point.

Citation:

---

Inutile : à part si tu as des données en quantité absolument colossale (je parle d'une cardinalité approchant le MILLION, là, avec des problèmes de dispersion largement plus problématiques), un CRC sur un domaine d'au moins quatre fois la cardinalité moyenne est habituellement suffisant. Ici, tu parles de 10.000 chaînes, donc un CRC16 est très certainement amplement suffisant.

---

1)
Nope, pas de million, juste 10000 gros max.
Juste que j'ai un peux peur d'utiliser CRC16 parce que, si, par exemple, dans un cas certes limite, j'ai deux chaînes triées, et que, par exemple, seul le 100ème caractère est différend entres les deux chaînes, alors... il pourrait y avoir des chances de collision?
Je ne suis juste pas assez avancé en calcul de probabilité, POUR L'INSTANT, pour évaluer la probabilité.

Voilà pourquoi je relance sur cette avant-dernière - du moins c'est ce que je crois - question: CRC16, en es-tu sur?

2)
L'algo de tri? Lequel? qsort()?


Merci!

Citation:

---

Envoyé par Array

Juste que j'ai un peux peur d'utiliser CRC16 parce que, si, par exemple, dans un cas certes limite, j'ai deux chaînes triées, et que, par exemple, seul le 100ème caractère est différend entres les deux chaînes, alors... il pourrait y avoir des chances de collision?

---

Les collisions sont un risque INÉVITABLE lorsque l'on utilise du hachage. Tu ne peux EN AUCUN CAS ne pas gérer ce cas de figure.

Citation:

---

Envoyé par Array

Je ne suis juste pas assez avancé en calcul de probabilité, POUR L'INSTANT, pour évaluer la probabilité.

---

La théorie du CRC te garantit que la dispersion est "grande", bien plus qu'avec de simples sommes ou combinaisons logiques primaires. Cependant, elle n'est pas parfaite. C'est un problème de distance de Hamming, qui relève de maths de (relativement) haut niveau. En tout cas, un CRC32 est supérieur à un Adler32, et j'ai tendance à penser que le CRC16 se situerait entre les deux plutôt que "en dessous" de Adler.

Au pire, tu peux prévoir un code un minimum adaptatif (typedef sur le type "crc_t", et fonctionS de calcul utilisant un type natif + cast), et tester le pourcentage de collisions avec un CRC16 et un CRC32. Cela m'étonnerait que l'ordre de grandeur des collisions soit très différent entre les deux. C'est un test "rapide" à faire en prenant une liste "maximale" de chaînes, et en effectuant bourrinement les deux calculs dessus.

Ceci étant dit, n'oublie pas que les deux solutions (hachage et LUT de tri) sont en exclusion mutuelle : implémenter l'une rend l'autre inutile.

Citation:

---

Envoyé par Array

L'algo de tri? Lequel? qsort()?

---

Pourquoi pas ? C'est loin d'être le plus mauvais algo possible... Tu peux lui spécifier ta propre méthode d'ordonnancement, donc tu peux lui passer ta LUT et utiliser, comme critère, un strcmp sur le pointeur contenu dans la LUT.
En cas de test avec une insertion triée, c'est à toi de gérer la méthode d'insertion "manuellement", car il n'y a pas de fonctions de ce genre en C standard.

Tout est clair. :zoubi:
Sauf... :aie:

Citation:

---

Ceci étant dit, n'oublie pas que les deux solutions (hachage et LUT de tri) sont en exclusion mutuelle : implémenter l'une rend l'autre inutile.

---

Ce que je croyais faire, c'est: dans map(), construire le tableau trié, mais pour chaque string, également faire un crc16, le mettre dans une struct unissant le pointeur sur char, le size et le crc16, foutre la struct dans ledit tableau.

Parce que, comme ça, dans la fonction de comparaison, si j'ai bcp d'éléments de même crc16, je comparerais juste le string de début et le string de fin de la séquence crc16 identiques.

Que voulais-tu dire?
J'ai du en manquer un bout - désolé.


Merci bcp!

Array

Citation:

---

Envoyé par Array

Que voulais-tu dire?
J'ai du en manquer un bout - désolé.

---

Ben au lieu d'un CRC, tu y mets une référence (un pointeur en C, donc) vers la chaîne/structure d'origine. Dans l'opérateur de tri, tu vas déréférencer le pointeur pour obtenir la chaîne à comparer, et utiliser un bête strcmp dessus (son résultat est déjà compatible avec qsort()).

Citation:

---

Le problème n'est pas tant qu'il y ait des collisions, mais plutôt que celles-ci ne se produisent pas avec des chaînes trop proches

---

A noter au passage qu'un algorithme de hashage cryptographique comme MD5 élimine ce problème. Bon c'est moins rapide qu'un CRC.

Citation:

---

Ce que je croyais faire, c'est: dans map(), construire le tableau trié, mais pour chaque string, également faire un crc16, le mettre dans une struct unissant le pointeur sur char, le size et le crc16, foutre la struct dans ledit tableau.

---

+1
Compare aussi sur le size en cas d'égalité de CRC.

Le nombre de "grands" strcmp devrait être ridiculement petit.
En fait, quand on a le même CRC, le plus probable est une divergence assez importante du contenu des chaines (c'est à dire une grande majorité de caractères différents un peu partout dans les chaines). Donc, dans quasiment tous les cas de CRC identiques, le strcmp devrait s'arréter très vite.