Discussion :

[Nico87]

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 !

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

[Nico87]

Zut, mon problème n'intéresse pas grand monde. C'est peut être un peu vague. Je vais essayer d'être un peut plus clair. Je cherche le moyen de classer les nom dans une structure plus performante et plus intuitive qu'un simple tableau associatif.
Par exemple :
$MonTableau = array(

'1' => (#25,#30)

'2' => (#12,#321)

'3' => (#55,#14,#21...)

'...' => (...)

);

Ou les #... sont des identifiants de chevaux dont le nom est extrêmement proche voir identique.

Donc la structure je l'ai, mais c'est les clés qui me permette de trier les groupe que j'aimerais générer et sa

[Mac LAK]

Tu peux tout simplement utiliser un CRC32 (voire un CRC16) : vu les besoins que tu exprime, cela me semble amplement suffisant et répondrait correctement à tes besoins.

De plus, ce genre d'algorithme est vastement répandu, et sera facile à implémenter quel que soit le langage final que tu utilisera.

[Mac LAK]

Je viens de me rendre compte que j'ai écrit à côté de la plaque... Lu trop vite, un CRC isolerait fortement tes identifiants (ce qui est le but d'une fonction de hachage...). En fait, tu veux une fonction avec une forte collision (ce qui serait une "mauvaise" fonction de hachage...), cette collision dépendant de la distance lexicographique des entrées en collision.

Tu peux déjà commencer par séparer ta table de 16.000 entrées en fonction de l'initiale : tu passeras d'un ordre proche des 256 millions à (en gros) quelque chose de l'ordre de la dizaine de millions ( 16.000 / 26 = 615 entrées en moyenne, donc complexité O(26.(615²)) à peu près)... Tu gagnes quand même pas loin d'un facteur 25, c'est déjà un point de départ.

Ensuite, comme fonction de hachage, tu peux tenter d'utiliser la distance lexicographique par rapport à une forme de référence (ex : "esaitnrulodcpmvqfbghjxyzwk") : cette distance permet de repérer les formes potentiellement proches les unes des autres.

En effet, deux formes proches (ex : distance lexicographique de 2) auront forcément une distance par rapport à la forme de référence proches également. A noter que la réciproque est fausse : ce n'est pas parce que deux formes ont une distance à la forme de base proche que leur distance est proche elle aussi : on a pu s'éloigner de la forme de base dans deux directions "opposées"...

Par contre, deux formes ayant une distance par rapport à la forme de base très différentes ne peuvent pas avoir une distance entre elles similaire : c'est ce point qui te permettra d'avoir des coupes dans ton traitement.

[Nico87]

Je vais faire des recherche la dessus, mais pourrait tu m'expliquer succinctement le principe.

Merci beaucoup de ta réponse

[Mac LAK]

Je vais faire des recherche la dessus, mais pourrait tu m'expliquer succinctement le principe.

De la distance par rapport à une forme de référence ?

Le principe, c'est (en gros) la même chose que de choisir une origine dans un espace vectoriel, sauf que là, les vecteurs sont des formes lexicales et que l'origine est une forme lexicale arbitraire.

Ensuite, le but est de comparer les "vecteurs" deux à deux pour trouver les vecteurs "proches", sauf qu'au lieu de te taper toutes les paires possibles, tu limites tes recherches à une bande circulaire centrée sur "l'origine" de ton espace.

Est-ce plus clair expliqué ainsi ?

[Nico87]

Excuse moi, j'ai posté en même temps. Ton aide m'est précieuse. En effet je souhaite avoir beaucoup de collision pour pouvoir constituer des groupes. C'est donc une mauvaise fonction de hachage dont j'aurai besoin .

J'avais déjà l'idée du premier caractère. C'est sur que ça découpe largement le travail de recherche. J'avais aussi pensé à la longueur de la chaine de caractère pour sous-diviser à nouveau chaque groupe.

Enfin la distance lexicographique par rapport à une base de référence est une excellente idée. Par contre la chaine de référence "esaitnrulodcpmvqfbghjxyzwk", tu l'as mise au hasard ? Y-a-t'il une chaine de base judicieuse ?

[pseudocode]

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

Une idée comme ca: créer un hashcode par type de "mutation" que l'on désire accepter.

Ensuite, pour tester un mot "M" quelconque, if faut calculer les hashcodes de toutes "mutations" permises sur le mot M. Il faut donc construire des hashcodes qui permettent de trouver facilement ces mutations.

Un exemple simple pour un hashcode qui teste la présence d'une lettre dans un mot : un champs de 26 bits ou un bit "k" est à 1 si la lettre ascii(k) est présente dans le mot.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
 
           abcdefghijklmnopqrstuvwxyz
"cheval" = 10101001000100000000010000
"robert" = 01001000000000100101000000
"rober"  = 01001000000000100100000000
"toto"   = 00000000000000100001000000
"titi"   = 00000000100000100001000000

Les mutations de 1er niveau (1 lettre non-présente/supplémentaire) sont les hashcodes qui ont un seul bit de différent => 26 hascodes. On fait un premier SELECT dans la base pour remonter les mots candidats.

On peut ainsi créer autant de hashcode que de caracteristiques à tester, et réduire a chaque fois la liste des mots candidats pour lesquels il faudra, a la fin, calculer la distance de levenstein

[Mac LAK]

J'avais déjà l'idée du premier caractère. C'est sur que ça découpe largement le travail de recherche. J'avais aussi pensé à la longueur de la chaine de caractère pour sous-diviser à nouveau chaque groupe.

Surtout pas la longueur !!! Ton exemple "Robert" / "Rober" est significatif à ce sujet, d'ailleurs...

Enfin la distance lexicographique par rapport à une base de référence est une excellente idée. Par contre la chaine de référence "esaitnrulodcpmvqfbghjxyzwk", tu l'as mise au hasard ? Y-a-t'il une chaine de base judicieuse ?

Merci. C'est simplement la transposition d'un problème vectoriel, en fait, comme je l'ai expliqué au post précédent.

La chaîne "esaitnrulodcpmvqfbghjxyzwk" présente toutes les lettres de l'alphabet, dans l'ordre de fréquence usuel de la langue française... C'est pas forcément la meilleure, loin de là, c'est UNE forme de référence.

Il est possible (voire très probable) qu'il faille essayer, de façon empirique, plusieurs formes de base afin d'en trouver une "judicieuse" par rapport aux formes qui peuplent ta base de données.

Par exemple, une des formes possible peut être "aaaaaaaa" pour les formes débutant par "a" : si la longueur moyenne est de 8 caractères, tu prends une chaîne de 8 caractères de long et composée de "a".

Le but de cette passe est de réduire le plus fortement possible le nombre de formes à tester, le "n" afin de faire baisser le "n²" de la complexité.
Actuellement, tu peux t'en sortir avec un n de l'ordre de 600 environ : si tu peux le réduire de moitié via ce type d'algorithme, tu réduira par QUATRE ta complexité : c'est pas négligeable !!

Mais il te faudra tester, empiriquement, des formes de référence "valides" qui permettent un grand nombre de collisions justifiées et limitant au maximum les collisions aberrantes (le coup de "partir dans deux directions opposées").
Une fois une forme de référence convenable trouvée, tu pourras t'en servir pour initialiser l'algorithme, réduire les formes redondantes, et finir par une comparaison systématique MAIS sur un nombre de formes très très réduit par rapport aux 16.000 initiales.

Je te suggère de tester les formes de références suivantes :
- Contenant toutes les lettres de l'alphabet (26 caractères de long), penser aux caractères accentués s'il y en a.
- Contenant une lettre unique répétée N fois, N étant la longueur moyenne des mots débutant par cette lettre unique.
- Utiliser une forme "médiane" de ta liste en guise de forme de référence (ex : chercher un mot de longueur "moyenne" dans la liste des formes débutant par "A", le prendre arbitrairement).

[Nico87]

Franchement merci beaucoup. Tu m'a l'air vraiment calé sur le sujet. J'avoue que je n'ai pas tout tout compris mais j'ai retenu l'essentiel : faire baisser cette foutue complexité en définissant un niveau de granularité approprié. J'ai muri ça ce week-end et j'ai eu une idée.
Je vais essayer d'implémenter un petit algo qui va me générer un hashcode "maison" sur 30 ou 32 caractères grâce à tout les indices que tu ma donné.

- 2 caractères pour la 1er lettre
- 2 caractères pour la 2eme lettre
- J'avais pensé à la 3eme lettre mais l'idée de la distance par rapport à une chaine de référence me tente beaucoup. Je pourrais mettre les deux.

Grâce à la première lettre je réduit les groupes à environ 600 occurrences. Grâce à la deuxième lettre je divise chaque groupe par 26 soit 22 occurrences par groupe. Déjà un fort niveau de ressemblance. Ensuite soit la 3eme lettre soit la distance (ou les deux). J'aurais un niveau de similarité très important.
Mon maitre de stage me propose de rajouter le champs créer par cette algorithme dans la BDD. Ainsi, grâce à une requête et un "order by" je créer instantanément mes groupes pour alimenter mon tableau à 2 dimensions.

Penses-tu que c'est une bonne idée. Perso je crois que la création de se code peut être une opération lourde en BDD mais une fois réaliser, les requêtes seront très facilité.

[Mac LAK]

Franchement merci beaucoup. Tu m'a l'air vraiment calé sur le sujet.

De rien. Et sinon, au risque de te surprendre, je n'y connais rien en distance lexicographique... Par contre, je me débrouilles pas mal en algo effectivement. Un poil de documentation sur ce qu'est une distance lexicographique et zou : l'algo, c'est aussi trouver les similitudes entre deux problèmes qui n'ont à priori rien à voir entre eux mais qui, au final, sont proches dans leur résolution.
Pour simplifier à outrance : si tu sais couper des pommes, tu sais aussi couper des poires, les différences sont minimes...

J'avoue que je n'ai pas tout tout compris mais j'ai retenu l'essentiel : faire baisser cette foutue complexité en définissant un niveau de granularité approprié.

C'est bien ça, sauf que (bien sûr) il faut la réduire intelligemment, le but étant d'avoir de nombreuses collisions au hachage, mais des collisions "légitimes" et non pas des collisions entre, par exemple, "Canasson" et "Tréteau"...

Je vais essayer d'implémenter un petit algo qui va me générer un hashcode "maison" sur 30 ou 32 caractères grâce à tout les indices que tu ma donné.

30 / 32 caractères ?? Cela me parait un peu gros... 32 bits, ce serait mieux !

Mon maitre de stage me propose de rajouter le champs créer par cette algorithme dans la BDD. Ainsi, grâce à une requête et un "order by" je créer instantanément mes groupes pour alimenter mon tableau à 2 dimensions.

Il a tout à fait raison, sauf qu'il faut penser aussi à l'inclure lors d'un AJOUT en base, en plus bien sûr de le faire sur l'existant.
Ensuite, tu pourras toujours connecter un trigger sur la BDD afin de remonter à intervalles réguliers les fusions qui sembleraient nécessaires à faire (fautes de frappe, etc.).

[Nico87]

J'y est passé du temps mais je crois que j'ai résolu mon problème, et en grande partie grâce à toi.
J'ai créé ma fonction pour générer mon hashcode perso. Elle encode les 3 premiers caractères de chaque nom sur 6 chiffres, puis grâce à la fonction soundexfr() (qui encode une chaîne selon la phonétique de prononciation) j'encode la fin de la chaine. Je passe de 16000 unités à 11975 groupes dont 1976 contiennent au moins 2 occurrences.
Je peux ainsi alimenter très rapidement mon tableau en ne testant la distance levenshtein que si les groupes dépassent les 5 occurrences (il y en a que 90). J'ai pas totalement fini mais je peu déjà affirmer que le gain de temps sera monstrueux.

[Jean-Marc.Bourguet]

Cherche après soundex (si j'ai bonne mémoire, il y a une variante plus adaptée au français)