Discussion :

[GuillaumeNcy]

Bonjour à tous,

Je souhaite calculer le % de ressemblance entre 2 chaînes de caractères. J'ai trouvé sur internet quelques discussions, quelques bout de codes, mais pour des chaines de caractères très courtes (1 mot, voir 2). (algorithme de Levenshtein, ou procédure visant à comparer des noms de famille...). Et la plupart ne comparent que la longueur des chaînes et non le contenu.

Mes chaînes de caractères,qui sont des résumés d'articles extraient de différentes bases de données, ont une longueur comprise entre 50 et 150 mots.
Malheureusement j'ai remarqué que sur 1000 résumés, venant 2 bases de données différentes, j'obtient une bonne 50ène de doublons...

Selon vous quel est le meilleur moyen de calculer le % de ressemblance entre eux, dans le but de supprimer les doublons?

Pour info les strings sont stockés dans des fichiers textes et je suis sur une winform.

Merci d'avance!

[Kropernic]

Je ne sais pas quelle base de données tu utilises mais avec SQL Server, on peut utiliser SOUNDEX pour comparer des chaines de caractères.

Il y a peut-être l'équivalent pour la tienne si ce n'est pas sql server. J'ignore si cet algorithme existe en .NET ...

[GuillaumeNcy]

Merci, non je ne travaille pas avec sql server, les articles sont issues de base de données privées appartenant à des laboratoires. Moi je les exportent en fichier textes pas le choix.

[Kropernic]

Dans ce cas, ce n'est surement pas la meilleure méthode mais voici (en gros) ce que je ferais :

1. ouvrir le premier fichier
2. lire un nombre de bits donné
3. ouvrir le second fichier
4. lire le même nombre de bits
5. retirer toutes les ponctuations et espaces de la chaîne obtenue en 2
6. retirer toutes les ponctuations et espaces de la chaîne obtenue en 4
7. si une des chaînes obtenues en 5 et 6 est plus petite que l'autre (sinon sauter cette étape) :
   
   1. extraire les x premiers caractères de la chaîne la plus longue où x est le nombre de caractère de la chaîne la plus courte
   2. réserver les caractères restant pour plus tard
   
   
8. si les chaînes obtenues en 5 et 6 sont de même longueurs, comparer leurs caractères. sinon, sauter cette étape
9. comparer les caractères de la chaîne obtenue en 7.1. avec la chaîne la plus courte de celles obtenues en 5 et 6
10. recommencer à partir de 2. jusqu'à la fin des fichiers.

[Pol63]

ca dépend de ce que tu appelles ressemblance
si c'est phrases identiques, des mots qui se suivent, des mots identiques dans une phrase qui ne se suivent pas forcément ...

et est-ce que tu veux calculer le % de ressemblance ou retirer des morceaux dans un texte

[GuillaumeNcy]

Le but final et de supprimer les doublons. Comparer 2 textes et dire si ils sont exactement identiques ou non serai simple.
Mais mes strings proviennent de sources différentes et peuvent contenir des petites annotations en plus du genre "vient de la base un-tel" ou de très légers changements, sans pour autant que le "vrai" contenu soit différent. C'est pour cela que j'aimerai calculer un genre de % de ressemblance : combien de terme dans le 1 sont contenus dans le 2. Peu importe l'ordre dans un premier temps.

Mais je pense pouvoir réaliser cette procédure tout seul (aussi fastidieux que ça soit), je venais surtout vers vous pour voir si il n'y avait pas une fonction spécialement conçu pour ce genre de chose (apportant peut etre de la rapidité et de l'efficacité, car j'ai des milliers de string a comparer).
Si ça n'existe pas, tant pis je ferai de mon mieux avec ce que je sais faire ^^

[Pol63]

je ne pense qu'il y ait quelque chose de tout fait
le mieux serait peut etre de découper (split) avec le caractère .
tu obtiendra x morceaux d'un côté et y de l'autre
ensuite tu compares chaque morceau avec tous les morceaux de l'autre (double boucle imbriquée) pour chercher le nombre de mots en commun (split sur espace), et après un algo arbitraire du genre si ca dépasse 70% du nombre de mots de la phrase et que le nombre de mot est supérieur à 5 alors considérer que cette phrase est un doublon

pour aller plus vite tu peux faire du parallel.foreach sur la 1èer boucle, ce qui utilise le multi threading pour gagner du temps

[DotNetMatt]

Sinon tu peux peut-être regarder du côté de Lucene.NET (portage .NET de Lucene dans le monde Java), qui propose plein d'add-ons en tout genre, dont Phonetix.NET, qui permet d'utiliser des algorithmes basés sur SOUNDEX, Metaphone et DoubleMetaphone...

Comme indiqué, il existe plein d'add-ons autour de Lucene.NET donc peut-être qu'en fouillant un peu sur Google tu trouveras quelque chose d'adapté à ce que tu veux faire.

[GuillaumeNcy]

Ok donc :
Je fixe un "seuil de ressemblance" (on va faire à tâtons ^^)
Je split mes 2 première strings en phrase.
J'obtiens x phrases dans la 1ere et y phrases dans la 2ème.
Je compare la 1ère des x phrases avec toute les phrases de la 2ème string. Puis la deuxième etc..
Si je seuil est atteint j'arrête et je passe au string suivante (car si deux résumé possèdent 2 phrases identiques pas besoin d'aller plus loin je pense.. a tester).
Un truc comme ça donc?
Pas bête en effet. Car le split avec le point permet de ne pas TOUT comparer d'un coup.

EDIT : je me renseigne sur lucene.net, merci pour l'info!