"Vicnent" <Vicnent @ Gmail dot Com> a écrit dans le message de news:
473dd48e$0$21148$7a628cd7@news.club-internet.fr...

"Olivier Miakinen" <om+news@miakinen.net> a écrit dans le message de news:
473c621a$1@neottia.net...

Le 14/11/2007 22:47, Armel a écrit :

je suis à la recherche d'un algorithme de calcul de séquence la plus
longue
ente deux chaines mais avec poids (c'est à dire, qu'à chaque symbole on
associe un poids et la séquence la plus longue est donc celle pour
laquelle
la somme des poids des symboles en commun est maximale).
lorsqu'il n'y a pas de poids, l'algorithme de Myers est bon mais pas
dans ce
cas ci...

auriez-vous une idée??

Si la chaîne n'est pas trop longue et les poids de petits nombres
entiers, une idée pourrait être de remplacer chaque symbole par une
séquence de « poids » symboles identiques, non ?

je n'ai pas trop réfléchi à ton problème mais ta proposition ne tient pas
la route : en mofiant les séquences en fonction de leur poids, tu modifies
les séquences (et donc les sous chaines).
En fait, tu fais comme si tu agréger les deux contraintes (plus longue,
plus de poids) : ce n'est plus le même problème.

D'autre part, (Pour Armel) : quelle est la fonction à optimsier ? la plus
longue sous chaine ou celle de plus grand poids ? Tel que c'est présenté,
ça sent le multicritère !

l'idée est de trouver la différence la moins longue. si on repette les
symboles autant de fois que le poids qui leur est affecté (poids constant
pour un symbole, entier positif non nul), minimiser cette longueur
représente la minimisation du poids de la différence. bien sûr, il pourrait
bien y avoir des problèmes d'alignements, mais l'optimisation en vue de la
différence la plus faible devrait favoriser des alignements exacts puisque
seules ces solutions peuvent etre minimales (les autres provoquant
nécessairement des insertions et suppressions inutiles). il faudra cependant
s'assurer de cet alignement, puis recompresser les marqueurs
d'insertion/suppression, chaque action étant répétée autant de fois que le
poids du symbole inséré/supprimé (l'index de l'action est aussi concerné).

Armel
(mon accent circonflexe ne veut pas marcher, RDC sans Mac ne marche pas trop
bien)