Discussion :

[kain_tn]

Bonjour.

Mon problème est le suivant:

Je possède une liste de chaînes de 22 caractères (choisis parmis 35 caractères différents). Pour l'instant, cette liste est stockée en base de données, afin de pouvoir manipuler les données assez facilement.

Je voudrais avoir une distance minimale de k entre chaque chaîne et donc supprimer les chaînes ne remplissant pas cette condition.

Je pensais regarder du côté des distances de Levenstein ou de Hamming, mais malheureusement, le nombre de chaînes a traiter est très élevé (quelques millions) et comparer chaque chaîne à toutes les autres risque de me prendre énormément de temps et des ressources.

Voyez vous une meilleure solution?

Merci d'avance!

[Mac LAK]

On a pas mal parlé d'un sujet similaire sur ce topic.

Je te conseille d'aller lire ce qui a été dit là-bas, puis si tu as d'autres questions et/ou particularités liées à ton problème actuel, on pourra alors en débattre plus en avant.

[kain_tn]

Merci, ce post avait échappé à ma recherche!

Je vais le lire avant de continuer sur ce post-ci!

[kain_tn]

OK, alors la première chose que je vois c'est que l'ensemble des chaînes est découpé selon la première lettre.

Donc dans mon cas, cela réparti les millions de chaînes entre 35 tables ( => alphabet de 35 caractères).

Le premier problème c'est que si deux chaînes ne diffèrent que par leur première lettre, alors je n'ai aucun moyen de le savoir. Du coup, pour éviter ça je dois recommencer le même découpage sur l'ensemble des chaînes en prenant par exemple le dernier caractère non? (en gros, faire une deuxième passe sur mon algorithme, une fois la première terminée)


Le second est au niveau des chaînes de référence. Mon alphabet étant de 35 caractères pour des chaînes de 22, il m'est impossible de trouver une seule chaîne utilisant tous les caractères de mon alphabet... si je veux qu'elle ait la même longueur que les autres. Sinon, comme elle contiendrait 13 caractères de plus que les autres chaînes, alors en calculant la distance de levenstein entre cette chaîne et n'importe quelle autre, j'aurais une distance minimale de 13, si les 22 premiers caractères sont identiques...

Pour ce qui est de la suite, je ne pense pas pouvoir utiliser une soundex pour la simple et bonne raison que tous les caractères de l'alphabet ne sont pas prononçables! :p Vois-tu une alternative?


Dans tous les cas, la première partie de l'algorithme devrait s'appliquer à mon cas: au bout de plusieurs tris selon une lettre, je peux tomber à une dizaine de milliers de chaînes par table, ce qui me permettrait de paralléliser mes calculs de distances. 15 à 20 minutes, ça peut être acceptable comme temps de traitement. Maintenant, si tu vois mieux, je suis évidement preneur!!!


Merci pour ton aide!

[Mac LAK]

OK, alors la première chose que je vois c'est que l'ensemble des chaînes est découpé selon la première lettre.

En effet, bien que dans ton cas particulier tu puisses aussi les regrouper par sonorité, graphie, etc. bref, n'importe quel critère "convenable" qui te permet de réduire significativement l'ensemble de départ.

Le premier problème c'est que si deux chaînes ne diffèrent que par leur première lettre, alors je n'ai aucun moyen de le savoir.

N'oublie pas que le but de ce pré-filtrage, c'est d'éliminer les chaînes ayant une possibilité d'être "identiques" (à un facteur K près bien sûr) le plus vite possible, afin de réduire leur nombre global le plus possible.
Cela ne te décharge pas, hélas, d'une comparaison systématique par la suite si cela s'avère nécessaire, ou d'utiliser un deuxième filtrage... Tout dépend, en fait, du niveau de redondances de ta base de données initiale.

Si, par exemple, tu "sais" qu'il y a au moins 50% de chaînes qui seront éliminées, le premier filtrage va déjà très lourdement alléger ta base, réduisant d'autant la complexité (et le temps de calcul !!) pour un parcours systématique.

Du coup, pour éviter ça je dois recommencer le même découpage sur l'ensemble des chaînes en prenant par exemple le dernier caractère non? (en gros, faire une deuxième passe sur mon algorithme, une fois la première terminée)

Tu peux aussi le faire sur la 2ème lettre, ou n'importe quelle position de lettre "aléatoire" parmi les 22.
Quel que soit le cas, deux chaînes "identiques" devront bien être, à un moment, dans un même sous-ensemble... Sinon, elles auraient une distance d'au minimum 22, ce qui n'est pas "acceptable" pour qualifier deux chaînes d'identiques.

Le second est au niveau des chaînes de référence. Mon alphabet étant de 35 caractères pour des chaînes de 22, il m'est impossible de trouver une seule chaîne utilisant tous les caractères de mon alphabet... si je veux qu'elle ait la même longueur que les autres.

Facile, pourtant : tu prends simplement les 22 plus fréquentes, et/ou tu prends une chaîne de 22 caractères identiques parmi les 35 de l'alphabet.
J'explicite un peu ce point dans l'autre topic, je pense que dans ton cas la chaîne "constante" serait plus adaptée.

En exagérant volontairement, si tu stockes en base, avec CHAQUE chaîne, sa distance avec chacune des 35 "chaînes de référence constantes", tu obtiens donc un tuple de 36 valeurs en BDD.
Via de simples requêtes SQL, tu peux alors regrouper, trier, filtrer en fonction de ces données, et une fois un sous-ensemble réduit obtenu, tu appliques une comparaison systématique deux à deux pour éliminer les redondances.

Pour ce qui est de la suite, je ne pense pas pouvoir utiliser une soundex pour la simple et bonne raison que tous les caractères de l'alphabet ne sont pas prononçables! :p Vois-tu une alternative?

Si ce n'est pas un "vrai" langage, il n'y a pas d'alternative à part écrire un équivalent de soundex toi-même...

15 à 20 minutes, ça peut être acceptable comme temps de traitement. Maintenant, si tu vois mieux, je suis évidement preneur!!!

Si les traitements longs ne sont pas un problème ET que tu peux paralléliser, je te conseille de calculer systématiquement 35 distances par chaine, stocker ça en base, filtrer puis expédier des bouts de comparaisons systématiques vers des stations de calcul pour paralléliser le tout.

Si le temps de calcul est trop long, réduire le nombre de chaînes de référence constantes (ex : seulement via les 10 caractères les plus fréquents).

[kain_tn]

Tu peux aussi le faire sur la 2ème lettre, ou n'importe quelle position de lettre "aléatoire" parmi les 22.
Quel que soit le cas, deux chaînes "identiques" devront bien être, à un moment, dans un même sous-ensemble... Sinon, elles auraient une distance d'au minimum 22, ce qui n'est pas "acceptable" pour qualifier deux chaînes d'identiques.

c'est ce que je sous-entendais par "une fois la première terminée"

Facile, pourtant : tu prends simplement les 22 plus fréquentes, et/ou tu prends une chaîne de 22 caractères identiques parmi les 35 de l'alphabet.
J'explicite un peu ce point dans l'autre topic, je pense que dans ton cas la

En exagérant volontairement, si tu stockes en base, avec CHAQUE chaîne, sa distance avec chacune des 35 "chaînes de référence constantes", tu obtiens donc un tuple de 36 valeurs en BDD.
Via de simples requêtes SQL, tu peux alors regrouper, trier, filtrer en fonction de ces données, et une fois un sous-ensemble réduit obtenu, tu appliques une comparaison systématique deux à deux pour éliminer les redondances.

ok

Si ce n'est pas un "vrai" langage, il n'y a pas d'alternative à part écrire un équivalent de soundex toi-même...

J'espérais ne pas en arriver là

Si les traitements longs ne sont pas un problème ET que tu peux paralléliser, je te conseille de calculer systématiquement 35 distances par chaine, stocker ça en base, filtrer puis expédier des bouts de comparaisons systématiques vers des stations de calcul pour paralléliser le tout.

Si le temps de calcul est trop long, réduire le nombre de chaînes de référence constantes (ex : seulement via les 10 caractères les plus fréquents).

Merci encore!


(Je passe le post en résolu mais si vous avez des idées, n'hésitez pas!)

[Mac LAK]

Éventuellement, tiens-nous au courant de l'avancée, du gain de temps de calcul estimé, enfin les détails dans ce genre... Au pire, ça servira pour le prochain qui aura un problème similaire et qui fera une recherche forum.

En ce qui me concerne, c'est juste de la curiosité, j'aime bien savoir comment ça se termine...

[kain_tn]

Ok, j'essayerai