Éditer l’algorithme récursif de distance – Skiena

Je lis le manuel de conception d’algorithmes de Steven Skiena et je suis au chapitre de la programmation dynamic. Il a quelques exemples de code pour la distance d’édition et utilise des fonctions qui ne sont expliquées ni dans le livre ni sur Internet. Alors je me demande

a) comment fonctionne cet algorithme?

b) que font les fonctions indel et match?

#define MATCH 0 /* enumerated type symbol for match */ #define INSERT 1 /* enumerated type symbol for insert */ #define DELETE 2 /* enumerated type symbol for delete */ int ssortingng_compare(char *s, char *t, int i, int j) { int k; /* counter */ int opt[3]; /* cost of the three options */ int lowest_cost; /* lowest cost */ if (i == 0) return(j * indel(' ')); if (j == 0) return(i * indel(' ')); opt[MATCH] = ssortingng_compare(s,t,i-1,j-1) + match(s[i],t[j]); opt[INSERT] = ssortingng_compare(s,t,i,j-1) + indel(t[j]); opt[DELETE] = ssortingng_compare(s,t,i-1,j) + indel(s[i]); lowest_cost = opt[MATCH]; for (k=INSERT; k<=DELETE; k++) if (opt[k] < lowest_cost) lowest_cost = opt[k]; return( lowest_cost ); } 

    À la page 287 du livre:

     int match(char c, char d) { if (c == d) return(0); else return(1); } int indel(char c) { return(1); } 

    Fondamentalement, il utilise la méthode de programmation dynamic pour résoudre des problèmes, où la solution du problème est construite en solutions de sous-problèmes, afin d’éviter un nouveau calcul, de bas en haut ou de haut en bas.

    La structure récursive du problème est donnée ici , où i,j sont les indices de début (ou de fin) dans les deux chaînes, respectivement.

    entrez la description de l'image ici

    Voici un extrait de cette page qui explique bien l’algorithme.

    Problème: Étant donné deux chaînes de taille m, n et un ensemble d’opérations remplacent (R), insère (I) et supprime (D), le tout à un coût égal. Trouver le nombre minimal de modifications (opérations) nécessaires pour convertir une chaîne en une autre.

    Identifier les méthodes récursives:

    Quel sera le sous-problème dans ce cas? Pensez à trouver la distance d’édition d’une partie des chaînes, dites petit préfixe. Notons-les comme [1 … i] et [1 … j] pour quelques 1

    Dans le préfixe, nous pouvons aligner les chaînes de trois manières différentes (i, -), (-, j) et (i, j). Le trait d’union (-) ne représentant aucun caractère. Un exemple peut le rendre plus clair.

    Compte tenu des cordes DIMANCHE et SAMEDI. Nous voulons convertir DIMANCHE en SAMEDI avec des modifications minimales. Choisissons i = 2 et j = 4, c’est-à-dire que les chaînes de préfixe sont respectivement SUN et SATU (supposons que les index des chaînes commencent à 1). La plupart des caractères peuvent être alignés de trois manières différentes.

    Cas 1: Alignez les caractères U et U. Ils sont égaux, aucune modification n’est requirejse. Nous sums encore partis avec le problème de i = 1 et j = 3, E (i-1, j-1).

    Cas 2: Alignez le caractère droit de la première chaîne et aucun caractère de la deuxième chaîne. Nous avons besoin d’une suppression (D) ici. Nous sums encore partis avec le problème de i = 1 et j = 4, E (i-1, j).

    Cas 3: Alignez le caractère droit de la deuxième chaîne et aucun caractère de la première chaîne. Nous avons besoin d’une insertion (I) ici. Nous sums encore partis avec le problème de i = 2 et j = 3, E (i, j-1).

    La combinaison de tous les sous-problèmes minimise le coût d’alignement des chaînes de préfixe se terminant par i et j données par

    E (i, j) = min ([E (i-1, j) + D], [E (i, j-1) + I], [E (i-1, j-1) + R si i , les caractères j ne sont pas identiques])

    Nous n’avons toujours pas encore fini. Quel sera le cas de base?

    Lorsque les deux chaînes ont une taille égale à 0, le coût est égal à 0. Lorsqu’une seule des chaînes est égale à zéro, nous avons besoin d’opérations d’édition comme celles d’une chaîne de longueur non nulle. Mathématiquement,

    E (0, 0) = 0, E (i, 0) = i, E (0, j) = j

    Je recommande de suivre cette conférence pour une bonne explication.

    La fonction match() renvoie 1 si les deux caractères ne correspondent pas (de sorte qu’un déplacement supplémentaire est ajouté à la réponse finale), sinon 0.

    Ils sont expliqués dans le livre. Veuillez lire la section 8.2.4 Variétés de distance d’édition

    Veuillez suivre ce lien: https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/styles/pages/editdistance.html

    le code implémentant l’algorithme ci-dessus est:

     int dpEdit(char *s1, char *s2 ,int len1,int len2) { if(len1==0) /// Base Case return len2; else if(len2==0) return len1; else { int add, remove,replace; int table[len1+1][len2+2]; for(int i=0;i<=len2;i++) table[0][i]=i; for(int i=0;i<=len1;i++) table[i][0]=i; for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { // Add // add = table[i][j-1]+1; remove = table[i-1][j]+1; if(s1[i-1]!=s2[j-1]) replace = table[i-1][j-1]+1; else replace =table[i-1][j-1]; table[i][j]= min(min(add,remove),replace); // Done :) } } 

    C’est un algorithme récursif, pas de programmation dynamic. Notez que les deux i et j pointent sur le dernier caractère de s & t respectivement lorsque l’algorithme démarre.

    indel retourne 1. match (a, b) retourne 0 si a = b (match) sinon retourne 1 (substitution)

     #define MATCH 0 /* enumerated type symbol for match */ #define INSERT 1 /* enumerated type symbol for insert */ #define DELETE 2 /* enumerated type symbol for delete */ int ssortingng_compare(char *s, char *t, int i, int j) { int k; /* counter */ int opt[3]; /* cost of the three options */ int lowest_cost; /* lowest cost */ // base case, if i is 0, then we reached start of s and // now it's empty, so there would be j * 1 edit distance between s & t // think of it if s is initially empty and t is not, how many // edits we need to perform on s to be similar to t? answer is where // we are at t right now which is j if (i == 0) return(j * indel(' ')); // same reasoning as above but for s instead of t if (j == 0) return(i * indel(' ')); // calculate opt[match] by checking if s[i] = t[j] which = 0 if true or 1 if not // then recursively do the same for s[i-1] & t[j-1] opt[MATCH] = ssortingng_compare(s,t,i-1,j-1) + match(s[i],t[j]); // calculate opt[insert] which is how many chars we need to insert // in s to make it looks like t, or look at it from the other way, // how many chars we need to delete from t to make it similar to s? // since we're deleting from t, we decrease j by 1 and leave i (pointer // in s) as is + indel(t[j]) which we deleted (always returns 1) opt[INSERT] = ssortingng_compare(s,t,i,j-1) + indel(t[j]); // same reasoning as before but deleting from s or inserting into t opt[DELETE] = ssortingng_compare(s,t,i-1,j) + indel(s[i]); // these lines are just to pick the min of opt[match], opt[insert], and // opt[delete] lowest_cost = opt[MATCH]; for (k=INSERT; k<=DELETE; k++) if (opt[k] < lowest_cost) lowest_cost = opt[k]; return( lowest_cost ); } 

    L'algorithme n'est pas difficile à comprendre, il vous suffit de le lire plusieurs fois. Ce qui m'amuse toujours, c’est la personne qui l’a inventée et la confiance que la récursion fera ce qui est bien.