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.

@++

[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...

[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.