Discussion :

[virtuadrack]

Bonjour

j'ai une question théorique sur l'algo du string matching que je n'arrive pas a comprendre

comment est-on supposes aligner les strings par exemple "AB" et "AAB"
assumons que chaque matching (correspondance) a un coût 0
et que les insertions, effacement ont un coût de 1.

c'est ainsi qu'est remplit le graph d'alignement:




si quelqu'un a compris, merci de m'expliquer

[JulienDuSud]

Tu dois trouver le chemin avec le coût le moins élevé pour former ta chaine.

Je te conseille plutôt de te tourner vers le forum Algo, mais en gros une des manières d'y arriver serait d'aller du départ, trouver le chemin vers le 1er caractère avec le coût minimum, de là continuer et chercher le 2nd caractère avec le coût minimum, et ainsi de suite jusqu'au dernier caractère. Cependant, il se peut que cette méthode ne soit pas la moins coûteuse, donc il faut que tu réitère si jamais tu as une heuristique de coût départ->arrivée moindre en tentant les autres chemins.