Comparateur de chaine en pl/sql

Version imprimable

16/12/2004, 10h54
squalito

Comparateur de chaine en pl/sql

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.
16/12/2004, 11h18
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).
16/12/2004, 11h27
squalito

Comparateur de chaine en pl/sql

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.
16/12/2004, 12h49
2Eurocents

Re: Comparateur de chaine en pl/sql

Citation:

Envoyé par squalito

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) ?

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:

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"

16/12/2004, 17h34
squalito

le problème de comptage est faussé quand on remplace un caractère
16/12/2004, 17h48
Trap D

Suite à un test , démarche fausse :oops:
16/12/2004, 17h55
squalito

En gros l'utilisateur peux tout faire enlever, ajouter.
16/12/2004, 19h10
Trap D

Changer de place aussi ?
16/12/2004, 19h16
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
16/12/2004, 19h29
squalito

la place puet être changer
16/12/2004, 20h00
squalito

c'est un peu compliqué à mon niveau.
pourriez-vous m'aider car sa dépasse mes compétences.
16/12/2004, 20h31
nicolas581

Citation:

Envoyé par squalito

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

Citation:

Envoyé par squalito

c'est un peu compliqué à mon niveau.
17/12/2004, 09h51
squalito

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