Matching entre chaines de caractères

Bonjour,

J'ai effectué quelques recherches sans obtenir satisfaction et finalement j'ai pensé poser mon "problème" sur ce forum.

Je cherche des liens, des algos, du code, bref tout ce qui me premettrai d'atteindre mon but qui, en gros, de déterminer par exemple un pourcentage (0-100% donc) de "matching" entre 2 chaines de caractères (qui peuvent être des phrases, rarement un seul mot).

J'espère que ce peu d'informations est suffisant, je ne sais pas trop comment l'expliquer plus simplement.

Si vous avez des idées ou des informations je suis preneur.

Bonjour,

Pourrais-tu préciser ce que tu entends par "pourcentage" ?

Par exemple, si j'ai ces deux chaines : "aa" et "ab", alors elles sont "similaires" à 50% ?
Et en revanche, "aab" et "aac" sont similaires à 66.666666 % ?

Si c'est cela, est-ce que l'ordre compte ?
par exemple, est-ce que "aba" est 100 % similaire à "baa", ou bien à 33.33 % ?

Où bien souhaites-tu vérifier la concordance seulement entres les mots de la chaîne de caractères plutôt que les lettres.
Par exemple :

"Le gentil programmeur" comparé à "Le gentil développeur" concordent à 66,66 %?

C'est cela efficks, je cherche à mesurer (pas forcément avec un pourcentage, juste une idée qui me passait par le système central :roll: ) la concordance entre 2 chaines.

En fait, j'ai une liste de questions et une liste de réponses à ces questions, et je souhaite retrouver dans un dictionnaire les similitudes avec des questions/réponses qui ont déjà été utilisées afin de faire le lien entre des questionnaires, histoire de "macher" le travail de recherche je voudrai donc afficher les chaines du dictionnaire dans l'ordre "de la chaine qui concorde le plus à celle qui concorde le moins"

Dans la boite où je travail on a mis en place un FIC (Fichier Information Client), où nous avons du regroupper les personnes provenants de différentes sources. Nous avions plusieurs algorithmes mais la base était ce que l'on appelle le "soundex", pour comparer deux prononciations pareils.

Ex : Rémi et Rémy vont matcher avec un algo comme celui-ci.

L'algo de base ne donne pas de pourcentage mais il existe plusieurs versions (amélioré et adapter à une langue en particulier : Anglais, Français...) de cette algorithme que tu peux trouver sur le web.

Nous l'avons utiliser pour comparaison des adresses je ne sais pas son efficaté pour comparaison de question/réponse, ceci me semble beaucoup plus complexe.

Research

Merci Research, si tu retrouves le nom de cet algorithme, tu me fait signe stp ? :wink:

Sinon de mon côté j'ai trouvé un exemple d'implémentation de l'algorithme de Levenshtein qui ne me parait pas très probant pour des chaines de plusieurs mots après quelques tests mais j'en ai discuté avec un collègue et je pourrai faire un processus comme suis :

- Chaque chaine de caractère sera décomposée, chaque mot séparé par un espace sera comparé individuellement
- chaque mot sera passé au singulier (pas de 's' ou de 'x' à la fin par exemple) puis au masculin (pas de e à la fin)
- suppression des caractères spéciaux : accents, cédilles, étoiles, underscores, etc
- suppression des lettres doublons, par exemple le mot 'correction' deviendra "corection'
- comparaison de chaque mot de la chaine 1 avec chaque mot de la chaine 2 en utilisant l'algo de Levenshtein qui donne un indice de concordance entre les 2 chaines / mots
- calcul d'un taux de concordance en utilisant les indices donnés par l'algo, du travail à faire la dessus pour d"terminer la méthode la plus intéressante

voilà où j'en suis pour l'instant, qu'en pensez vous ?
si vous avez des conseils ou autre critique à faire n'hésitez pas, je suis preneur

Avis personnel :
Levenshtein est très bien (mais consommateurs de ressources) pour les mots, pour les phrases j'ai des doutes ; en tout état de cause, je commencerais par transformer les deux phrases en codage Métaphone (Google), qui me paraît plus adapté que SOUNDEX pour la suite, puis j'appliquerais Levenshtein sur les transformées.

Le Métaphone original étant basé sur le prononciation anglaise, il faut l'adapter (peut-être google) pour le français.

Citation:

---

Le terme Soundex remonte à 1918. Le premier algorithme de ce type a été inventé par Margaret O’Dell et Robert C. Russell, probablement à cause des problèmes liés au recensement américain.

---

http://sqlpro.developpez.com/cours/soundex/

À ce lien tu trouveras tous ce qui concerne le Soundex. L'algo Levenshtein et l'algo Metaphone sont un dérivés de Soundex. Mais aucun de ces algorythmes n'est utilisables sans modification au contexte des données et surtout ne donne aucun pourcentage. Habituellement de plus, on cré des fonctions de nettoyage avant d'appliquer un algo de type Soundex. Bref, c'est une base pour construire.

Research

Oui ça c'est excellent, Merci Research :D

je vais voir pour développer un process de découpage des chaines pour les comparer mot à mot en utilisant Soundex2 que je vais devoir adapter en C++

en tout cas super le cours, il est bien complet, bien détaillé et montre des résultats en application réelle donc on peut se faire une idée précise de ce que cela donne

merci encore, super le lien 8)