Discussion :

[squalito]

Bonjour,

je cherche une solution algorithmique ou un début de source afin de comparer deux chaine pour trouver le nombre caractère qui diffère.
exemples :
ch1=>AAA ch2=>BAAA soit 1 caractère diffèrent
ch1=>AAA ch2=>ABA soit 1 caractère diffèrent
ch1=>AAA ch2=>ABAB soit 2 caractères diffèrents

Avez-vous une idée ou un début de raisonnement pour m'aider dans cette galère, merci d'avance.

[Médiat]

Il faudrait que tu précises les règles autorisées lorsque les chaînes sont de longueurs différentes.

Par exemple
ABCD et AEBCD ne diffèrent que d'une lettre si j'ai le droit de supprimer le E dans la deuxième chaîne avant de comparer, mais elles diffèrent de 4 si je ne peux supprimer que la dernière, et de 2 si je peux supprimer la première (je compte la suppression comme une différence).

[squalito]

pour vous quelle serez la méthode la plus correcte pour comptabiliser
le nombre de caractères différents d'une chaine à l'autre.

Car ma problématique est la suivante :
un utilisateur ne peux modifier que 15 caractères dans un texte par rapport au texte principale.

[2Eurocents]

Car ma problématique est la suivante :
un utilisateur ne peux modifier que 15 caractères dans un texte par rapport au texte principale.

S'agit-il de modifications en place (remplacement d'un caractère par un autre) ? Ou le texte peut-il avoir un "volume" variable (insertion ou suppression possible de caractères par rapport au texte initial) ?

[Trap D]

Salut
D'après ce que tu dis j'ai l'impression qu'il faut parcourir les deux chaînes, dès qu'un caractères différe dans la seconde, chaîne, on compte le nombre de caractères de la seconde chaîne à parcourir pour retrouver le caractère initial de la première et on recommence .

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
str1 // première chaine
str2 //deuxième chaine
len1 // longueur de str1
len2 // longueur de str2
i <- 1 // compteur pour parcourir la première chaine
j <- 1 // compteur pour parcourir la deuxième chaine
nb <- 0 // nombre de caractères différents
tant que i <= len1 et que j <= len2 faire
début
    si str1[i] = str2[j] alors   
       i <- i + 1
       j <- j + 1
    sinon
        nb <- nb + 1
        j <- j+1
    finsi
fin
// ici une des deux chaines est terminée les caractères restant dans la première ou la deuxième comptent donc comme différents
// on peut bien sur faire un calcul 
tant que i <= len1 ou que j <= len2 faire
debut
    nb <- nb + 1
    i <- i + 1
    j <- j + 1
fin
ecrire "il y a " nb " caractère(s) différents"

[squalito]

le problème de comptage est faussé quand on remplace un caractère

[Trap D]

Suite à un test , démarche fausse

[squalito]

En gros l'utilisateur peux tout faire enlever, ajouter.

[Trap D]

Changer de place aussi ?

[nicolas581]

Bonsoir,

Ce problème est connu comme la distance sur données séquentielles.

L'espace de représentation n'est pas fixe.
3 opérations :
- création
- destruction
- substitution
Distance entre deux mots : coût minimal en terme de nombre d'opérations
pour passer de a à b.

Indice de similarité entre deux mots :
S(M1, M2) = 1 - d_E(M1, M2)/ max (l(M1), l(M2))

La distance d'édition peut être calculée par l'algorithme de Wagner et Fisher. (Je n'ai pas envie de le retranscrire ici, une recherche sur le web devrait permettre de trouver l'algo)

http://c2.com/cgi/wiki?WagnerFisherAlgorithm

[squalito]

la place puet être changer

[squalito]

c'est un peu compliqué à mon niveau.
pourriez-vous m'aider car sa dépasse mes compétences.

[nicolas581]

c'est un peu compliqué à mon niveau.
pourriez-vous m'aider car ça dépasse mes compétences.

Ton problème n'est pas simple à résoudre quoique pas (NP)-difficile , donc
si tu veux comprendre cet algorithme tu as intérêt à connaître la
programmation dynamique comme joyeuseté.

http://www.merriampark.com/ld.htm pour de plus amples informations en anglais mais avec un exemple très documenté.

Sur le sql à proprement parlé :
http://sqlpro.developpez.com/cours/soundex/#L8
Il serait bien d'expliquer un peu plus ton problème car sinon celà risque d'être difficile de t'aider que veux tu faire, quels sont les problèmes autres que

c'est un peu compliqué à mon niveau.

[squalito]

ok c'est cette algo que je dois appliquer, merci pour l'info