Algorithme de hachage de chaine de caractère
Dans le cadre de mon stage, je suis amené à trouvé un algorithme de dédoublonnage d'une table de la BDD contenant des chevaux.
Je suis d'abord tout bêtement parti de la manière suivante. Je rapatrie la table avec les champs qui m'intéresse dans un tableau associatif (id_du_cheval/nom_du_cheval). Puis je lance la fonction de levenstein() qui compare 2 a 2 chaque entrée de ma table et mesure le degré de ressemblance des noms. Grâce à 2 for() imbriquée je fais des comparaison mais l'aglo est en O(n²) avec n le nombre d'occurence.
Donc sur un petit nombre d'occurrence, l'algo se porte bien : 5sec / 600 occurrences. Le problème c'est que la table en contient 16 000 et la ça décolle à près de 15min 8O!
Après une petite discussion avec mon responsable, celui-ci m'a fait comprendre qu'il serait plus judicieux d'ordonner correctement les données lors de la copie de la table plutôt que de la copier brut. Il voudrait que je trouve une fonction de hachage sur le nom des chevaux qui me permette d'accéder plus rapidement à des chevaux qui se ressemble.
Exemple:
toto et toti => aurait une clé de hachage quasi identique
robert et rober => aussi
Ainsi, plus besoin de comparer 2 à 2 chaque occurrence et faire exploser le nombre de comparaison exponentiel. A chaque clé correspondrait un ou plusieurs chevaux que je pourrai regrouper et considérer comme doublon.
C'est un peu long et même si c'est très clair dans ma tête je comprend que ça ne le soit pas vraiment pour vous. Je voudrais de juste de l'aide quand a l'élaboration de la fonction de hachage sur les chaines de caractère.
Je vous remercie par avance
