Je pense qu'on peut adapter l'algorithme de comparaison de chaines bruitées.
Soient deux chaines A et B.
On associe des pénalités:
D(A[i]) = poids de disparition d'un élément A[i]
P(B[j]) = poids d'apparition d'un élément B[j]
S(a,b) = poids de substitution de a par b
donc la distance entre deux chaines sera:
(X et Y sont des séquences de caractere, a et b sont des caracteres, e le caractere vide)
d(aX,bY) = min (S(a,b) + d(X,Y), // c'est soit la substitution de a et b
D(a) + d(X,bY), // .. soit disparition de a dans X
P(b) + d(aX,Y)) // .. soit l'apparition de b dans Y
d(aX,e) = D(a) + d(X,e)
d(e,bY) = P(b) + d(e,Y)
d(e,e) = 0
ce qui donne en une sorte de Ada:
distance(A[1..n], B[1..m],i,j){
if (j==m+1){
if(i==n+1){
return 0;
}
return D(A[i]) + distance (A,B,i+1,j);
} else {
if (i==n+1){
return P(B[j]) + distance (A,B,i,j+1);
}
return min (S(A[i],B[j]) + distance(A,B,i+1,j+1),
D(A[i]) + distance(A,B,i+1,j),
P(B[j]) + distance(A,B,i,j+1));
}
}
avec la programmation dynamique tu peux arriver à quelque chose de polynomial.
Ca c'est l'algo de base.
Maintenant, tu veux qu'il soit possible de trouver une permutation des lettres dans la chaine.
Donc à mon avis, il faut associer une distance du genre
d(aX,Ya) = ...
mais il va sans doute interferer avec d(aX,bY)..
donc il faudra prendre le min des deux. dis = min( d(aX,Ya) , d(aX,bY) )
Je ne garantis pas que ca marche, mais c'est la premiere idée qui me vient à l'esprit.
Je pense que si ca marche, tu tombera toujours sur un truc polynomial.
)
