Micro-optimisation pour le calcul de la distance d'édition: est-ce valable?

Sur Wikipedia , une implémentation du schéma de programmation dynamique ascendant pour la distance d'édition est donnée. Il ne suit pas complètement la définition; les cellules internes sont calculées ainsi:

if s[i] = t[j] then  
  d[i, j] := d[i-1, j-1]       // no operation required
else
  d[i, j] := minimum
             (
               d[i-1, j] + 1,  // a deletion
               d[i, j-1] + 1,  // an insertion
               d[i-1, j-1] + 1 // a substitution
             )
}

Comme vous pouvez le voir, l'algorithme choisit toujours la valeur du voisin supérieur gauche s'il y a une correspondance, en sauvegardant certains accès à la mémoire, les opérations ALU et les comparaisons.

Cependant, la suppression (ou l'insertion) peut entraîner une valeur plus petite , donc l'algorithme est localement incorrect, c'est-à-dire qu'il rompt avec le critère d'optimalité. Mais peut-être que l'erreur ne change pas le résultat final - elle pourrait être annulée.

Cette micro-optimisation est-elle valable, et pourquoi (non)?

Je ne pense pas que l'algorithme soit défectueux. Si deux chaînes sont appariées, nous comparons d'abord ses deux derniers caractères (puis recuisons). S'ils sont identiques, nous pouvons les faire correspondre pour obtenir un alignement optimal. Par exemple, considérez les chaînes testet testat. Si vous ne faites pas correspondre les deux derniers ts, l'un des ts reste inégalé, car sinon votre correspondance ressemblerait à ceci:

C'est impossible, car les flèches ne sont pas autorisées à "traverser". L'apparié tinduit plusieurs insertions (cases vertes sur la figure), comme illustré à gauche:

Mais alors vous pouvez simplement trouver un alignement tout aussi bon, représenté à droite. Dans les deux cas, vous faites correspondre un tet vous avez deux insertions.

L'argument en faveur d'une substitution de l'un des derniers ts est le même. Donc, si vous remplacez l'un des derniers ts, vous pouvez alors faire correspondre les deux derniers t et obtenir un meilleur alignement (voir l'image).