Wagner – Algorithme Fischer – Wikipedia wiki

En informatique, le Algorithme Wagner – Fischer est un algorithme de programmation dynamique qui calcule la distance d’édition entre deux chaînes de caractères.

Histoire [ modifier ]]

L’algorithme Wagner – Fischer a une histoire d’invention multiple. Navarro en répertorie les inventeurs suivants, avec date de publication, et reconnaît que la liste est incomplète: ^{[d’abord] : 43}

Distance de calcul [ modifier ]]

L’algorithme Wagner – Fischer calcule la distance d’édition en fonction de l’observation que si nous réservons une matrice pour maintenir les distances d’édition entre tous les préfixes de la première chaîne et tous matrice, et trouvez ainsi la distance entre les deux chaînes complètes comme la dernière valeur calculée.

Une implémentation simple, en tant que pseudocode pour une fonction Distance qui prend deux cordes, s de longueur m , et t de longueur n et renvoie la distance de levenshtein entre eux, ressemble à ce qui suit. Les chaînes d’entrée sont indexées, tandis que la matrice d est indexé zéro, et [i..K] est une plage fermée.

fonction  Distance ( carboniser  s [ d'abord .. m ]] ,  carboniser  t [ d'abord .. n ]) :  // pour tous les i et j, d [i, j] tiendra la distance entre  // les premiers I Caractères de S et les premiers J personnages de T  // Notez que d a (m + 1) * (n + 1) valeurs  déclarer  int  d [ 0 .. m ,  0 .. n ]]  ensemble  chaque  élément  dans  d  pour  zéro  // Les préfixes source peuvent être transformés en chaîne vide par  // laisse tomber tous les caractères  pour  je  depuis  d'abord  pour  m :  d [ je ,  0 ]]  : =  je  // Les préfixes cibles peuvent être atteints à partir du préfixe de source vide  // en insérant chaque personnage  pour  J  depuis  d'abord  pour  n :  d [ 0 ,  J ]]  : =  J  pour  J  depuis  d'abord  pour  n :  pour  je  depuis  d'abord  pour  m :  si  s [ je ]]  =  t [ J ]] :  remplaçant  : =  0  autre :  remplaçant  : =  d'abord  d [ je ,  J ]]  : =  le minimum ( d [ je - d'abord ,  J ]]  +  d'abord ,  // Suppression  d [ je ,  J - d'abord ]]  +  d'abord ,  // insertion  d [ je - d'abord ,  J - d'abord ]]  +  remplaçant )  // substitution  retour  d [ m ,  n ]]  

Deux exemples de la matrice résultante (planant sur un nombre souligné révèle l’opération effectuée pour obtenir ce numéro):

L’invariant maintenu dans tout l’algorithme est que nous pouvons transformer le segment initial s [1..i] dans t [1..J] en utilisant un minimum de d [i, j] opérations. À la fin, l’élément inférieur droit du tableau contient la réponse.

Preuve d’exactitude [ modifier ]]

Comme mentionné précédemment, l’invariant est que nous pouvons transformer le segment initial s [1..i] dans t [1..J] en utilisant un minimum de d [i, j] opérations. Cet invariant tient depuis:

• Il est initialement vrai sur la ligne et la colonne 0 car s [1..i] peut être transformé en chaîne vide t [1..0] en laissant simplement tomber tout je personnages. De même, nous pouvons transformer s [1..0] pour t [1..J] en ajoutant simplement tout J personnages.
• Si s [i] = t [j] , et nous pouvons transformer s [1..i-1] pour t [1..j-1] dans k opérations, alors nous pouvons faire de même pour s [1..i] Et laissez juste le dernier personnage seul, donnant k opérations.
• Sinon, la distance est le minimum des trois façons possibles de faire la transformation:
  • Si nous pouvons nous transformer s [1..i] pour t [1..j-1] dans k opérations, alors nous pouvons simplement ajouter t [j] après avoir t [1..J] dans K + 1 opérations (insertion).
  • Si nous pouvons nous transformer s [1..i-1] pour t [1..J] dans k opérations, alors nous pouvons supprimer si] puis faire la même transformation, pour un total de K + 1 opérations (suppression).
  • Si nous pouvons nous transformer s [1..i-1] pour t [1..j-1] dans k opérations, alors nous pouvons faire de même pour s [1..i] et échanger l’original si] pour t [j] après, pour un total de K + 1 opérations (substitution).
• Les opérations nécessaires pour se transformer S [1..N] dans t [1..m] est bien sûr le nombre nécessaire pour transformer tout s dans tous t , et ainsi d [n, m] tient notre résultat.

Cette preuve ne parvient pas à valider que le nombre placé dans d [i, j] est en fait minime; Ceci est plus difficile à montrer et implique un argument par contradiction dans laquelle nous supposons d [i, j] est plus petit que le minimum des trois, et l’utiliser pour montrer que l’un des trois n’est pas minime.

Modifications possibles [ modifier ]]

Les modifications possibles de cet algorithme incluent:

• Nous pouvons adapter l’algorithme pour utiliser moins d’espace, O ( m ) au lieu de O ( MN ), car il faut seulement que la ligne et la ligne actuelle soient stockées à tout moment.
• Nous pouvons stocker le nombre d’insertions, de suppressions et de substitutions séparément, ou même les positions auxquelles elles se produisent, ce qui est toujours J .
• Nous pouvons normaliser la distance à l’intervalle [0.1] .
• Si nous ne sommes intéressés que par le loin s’il est plus petit qu’un seuil k , alors il suffit de calculer une bande de largeur diagonale 2k + 1 dans la matrice. De cette façon, l’algorithme peut être exécuté O ( à ) temps, où l est la longueur de la chaîne la plus courte. ^[2]
• Nous pouvons donner des frais de pénalité différents à l’insertion, à la suppression et à la substitution. Nous pouvons également donner des coûts de pénalité qui dépendent des caractères insérés, supprimés ou substitués.
• Cet algorithme parallélise mal, en raison d’un grand nombre de dépendances de données. Cependant, tous les coût Les valeurs peuvent être calculées en parallèle et l’algorithme peut être adapté pour effectuer le le minimum fonction en phases pour éliminer les dépendances.
• En examinant les diagonales au lieu des lignes, et en utilisant une évaluation paresseuse, nous pouvons trouver la distance de levenshtein dans O ( m (1 + d )) Temps (où d est la distance de Levenshtein), qui est beaucoup plus rapide que l’algorithme de programmation dynamique ordinaire si la distance est petite. ^[3]

Variante du vendeur pour la recherche de cordes [ modifier ]]

En initialisant la première ligne de la matrice avec des zéros, nous obtenons une variante de l’algorithme Wagner – Fischer qui peut être utilisé pour la recherche de chaîne floue d’une chaîne dans un texte. ^[d’abord] Cette modification donne la position finale des sous-chaînes correspondantes du texte. Pour déterminer la position de démarrage des sous-chaînes correspondantes, le nombre d’insertions et de suppressions peut être stocké séparément et utilisé pour calculer la position de démarrage à partir de la position finale. ^[4]

L’algorithme résultant n’est en aucun cas efficace, mais était au moment de sa publication (1980) l’un des premiers algorithmes qui a effectué une recherche approximative. ^[d’abord]

Les références [ modifier ]]