Discussion :

[hfranck]

Salut à tous,

je cherche quelques conseils, idées pour résoudre le problème suivant : Je dois, comparer 2 chaines de caractères, et dire si elles sont identiques, quasi identiques (notion de pourcentage) ou non identiques.

Par exemple :
- chaine 1 = Arret de l'impression
- chaine 2 = Arret impression

Dans ce cas, je voudrais que l'algo me dise que les chaines sont quasi identiques.

Idées que j'ai eu :
- stocker dans un vecteur tous les mots de chaque chaine (tout mot séparé par espace, apostrophe)
- boucler sur le vecteur 1 et comparer aux mots du vecteurs 2
- Faire ça pour tous les mots du vecteur 1
- en fonction du nombre de mots max d'une des 2 chaines, faire le pourcentage


est-ce que vous trouvez cela raisonnable ou vous voyez autres choses ???

D'avance merci.

[keul85]

Bonjour,

Le problème que je vois avec ta solution, c'est que les chaînes "Arret de l'impression" et "de impression l' Arret" seraient considérées comme identiques, ce qui n'est pas le cas...

[hfranck]

Merci de ta réponse

Oui effectivement, maintenant que tu le dis

C'est pour ça que je crois que ça va être la merde comme algo.

Tu n'aurais pas une idée ?

[Invité]

Salut !

Peut être avec un map plutôt qu'un vecteur, par exemple

Map1 : clé/valeur <=> mot/position
Un/1
chien/2
bleu/3

Un/1
bleu/2
chien/3

@++

[hfranck]

On peut avoir plusieurs fois la même clé dans le Map, car, si cela se comporte comme une Hashtable, je vais avoir le problème, où je trouve plusieurs fois le même mots dans la chaine de caractère.

[Invité]

Excuse moi

c'est l'inverse, la position d'un mot est unique donc position/mot au lieu de mot/position.

@++

[hfranck]

ah OK

Bon, et bien, je vais essayer de me lancer dans cet algo, mais je le sens mal tout de mêm !

[keul85]

Un algo qui soit digne de ce nom, malheureusement non.

L'algo d'EtudiantJm est sans doute un peu mieux, mais là encore, il me semble qu'il y a des failles.

Ce -> 1
matin, -> 2
j' -> 3
ai -> 4
mangé -> 5
une -> 6
pomme -> 7

J' -> 1
ai -> 2
mangé -> 3
une -> 4
pomme -> 5

Les deux phrases sont quasi identiques mais si on dit que deux mots sont "identiques" lorsque un mot d'une phrase apparaît dans l'autre phrase à une position égale à + ou - 1 mot près, alors les deux phrases précédentes seront considérées comme totalement différentes...

[hfranck]

disons que c'est bien pour ça que je voulais utiliser un vecteur tout simple, car, effectivement, dans ton cas, les phrases ne seront pas considérées comme équivalentes.

D'où la notion de pourcentage que je voulais inclure.

Dans ton cas, :
- la première phrase est constituée de 7 mots
- la deuxième phrase est constituée de 5 mots

Dans la mesuren où on trouve 5 mots sur 7, "on peut" considérer que les chaines sont équivalentes

Il est clair que ce type d'algo ne peut être qu'approximatif !

[Invité]

Oui c'est vrai ! c'est pas simple comme problème...

[wiztricks]

Bonjour,
L'utilitaire U**X diff fait a peu près çà, vous pourriez vous en inspirer?
- W

[hfranck]

euh...c'est quoi au juste ??

[keul85]

Peut être qu'il faudrait faire en plusieurs fois :
- On regarde le nombre de mots en communs
- On regarde le nombre de mots bien placé dans les deux phrases (à un certain nombre de mots près)

A mon avis il faudrait refaire le deuxième algo plusieurs fois en augmentant petit à petit le nombre de mots de décalage entre les deux phrases.

Le pourcentage final serait alors le résultat d'un savant calcul selon les résultats des différents algos.

[hfranck]

Je vais découper mes deux chaines de caractères et stocker chaque mot dans un vecteur.

Je vais boucler sur le vecteur 1 et pour chaque entité du vecteur 2, je vais comparer les mots. De cette comparaison, je vais avoir le nombre de mots identiques (en sachant, qu'il vaut mieux que je fasse des indexOf, car, un equals va passer à côté du cas : "Utilisateur" et "Utilisateurs" avec un S)...

ensuite, je vais essayer de regarder la position des mots identiques de manière à faire ce que tu m'a suggéré, et là, peut être que ça pourrait à peu prés gazer !!

Un bon résultat ne pourrait être que le fruit du hasard !

[verbose]

En plus, ces deux phrases sont très proches :
-j'ai mangé une pomme
-j'ai mangé une pome

Il faut tenir compte de la "distance" entre les mots, et à partir de là mesurer la "distance" entre les phrases.

[hfranck]

ça se complique là....

est-ce que quelqu'un sait ce qu'est l'utilitaire :

"L'utilitaire U**X diff fait a peu près çà, vous pourriez vous en inspirer?"

mentionné par wiztricks

[verbose]

Oui, c'est un utilitaire qui fait une comparaison ligne à ligne et qui repère les lignes qui ne sont pas identiques. Ca ne permet pas de mesurer la différence entre deux phrases.

[hfranck]

Merci verbose pour l'info.

[Tommy31]

Il faut utiliser l'algo de calcul de la distance de Levenshtein entre 2 chaînes. Ce qui te permet au passage de calculer ton indicateur de ressemblance.

Tu as l'algo dans le lien que je t'ai fourni.

-> il faut que les chaînes à comparer soient courtes.

[Belmekki]

Bonjour a tous
Tu peux penser a l api REGEX! question de transformer la premiere phrase : Arret d'impression en Arret\s+d\W+impression et comparrer avec Arret impression ( qui va devenir ) arret\s+impression!
Tu peux garder la trace des motifs interpreté et voir a la fin ( compare entre le nombre des motifs qui font la difference entre les deux mots ) sans se soucier de la sematique qui restera verfié par defaut par la REGEX ! Arret\s+Impression est casiment differente de Impression\s+Arret !!