Coincidencia de subcadenas y la subsecuencia común más larga como una variante del problema de distancia de edición — Skiena
En el libro “Manual de Diseño de Algoritmos”, la distancia de edición se resuelve mediante el siguiente algoritmo.
#define MATCH 0 /* símbolo del tipo enumerado para coincidencia */
#define INSERT 1 /* símbolo del tipo enumerado para inserción */
#define DELETE 2 /* símbolo del tipo enumerado para eliminación */
int string_compare(char *s, char *t, int i, int j)
{
int k; /* contador */
int opt[3]; /* costo de las tres opciones */
int lowest_cost; /* costo más bajo */
if (i == 0) return(j * indel(' '));
if (j == 0) return(i * indel(' '));
opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);
opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
opt[DELETE] = string_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);
}
Entiendo todo hasta este punto, pero me cuesta entender la siguiente sección donde se resuelven los problemas de coincidencia de subcadenas y la subsecuencia común más larga como variaciones del problema de distancia de edición. Creo que entiendo la intuición detrás de ellos, donde la menor cantidad de ediciones significa preservar las “secuencias de interés”. En el caso de la coincidencia de subcadenas, es la subcadena; en el caso de la subsecuencia común más larga, es esa subsecuencia común. Sin embargo, no entiendo exactamente cómo se resuelve cada problema.
Para la coincidencia de subcadenas, se realizan los siguientes cambios:
row_init(int i)
{
m[0][i].cost = 0; /* nota de cambio */
m[0][i].parent = -1; /* nota de cambio */
}
goal_cell(char *s, char *t, int *i, int *j)
{
int k; /* contador */
*i = strlen(s) - 1;
*j = 0;
for (k=1; k<strlen(t); k++)
if (m[*i][k].cost < m[*i][*j].cost) *j = k;
}
}
para la subsecuencia común más larga, se realiza el siguiente cambio:
int match(char c, char d)
{
if (c == d) return(0);
else return(maxlen);
}
¿podría alguien explicarlo y ayudarme a entenderlo mejor? k++)=”” if=”” (m[i][k].cost=”” <=”” m[i][j].cost)=”” *j=”k;” }=”” }=”” ="" para="" la="" subsecuencia="" común="" más="" larga,="" se="" realiza="" el="" siguiente="" cambio:=""c=”” int=”” match(char=”” c,=”” char=”” d)=”” {=”” if=”” (c=”=” d)=”” return(0);=”” else=”” return(maxlen);=”” }=”” “`=”” ¿podría=”” alguien=”” explicarlo=”” y=”” ayudarme=”” a=”” entenderlo=””></strlen(t); k++)
if (m[i][k].cost < m[i][j].cost) *j = k;
}
}
para la subsecuencia común más larga, se realiza el siguiente cambio:
```c
int match(char c, char d)
{
if (c == d) return(0);
else return(maxlen);
}
¿podría alguien explicarlo y ayudarme a entenderlo mejor?>
davy.ai
El algoritmo de distancia de edición se utiliza como base para resolver los problemas de coincidencia de subcadenas y subsecuencia común más larga. Para resolver el problema de coincidencia de subcadenas, se modifica la función row_init() para establecer los valores de costo y padre en 0 en lugar del valor indel(). Esto corresponde al hecho de que no necesitamos realizar ningún cambio si la subcadena ya está presente en la cadena principal. También se modifica la función goal_cell() para buscar la celda de costo más bajo en la última fila de la matriz en lugar de la última columna. Esto corresponde a encontrar el final de la subcadena en la cadena principal.
Para resolver el problema de la subsecuencia común más larga, se modifica la función match() para devolver un costo de 0 si los caracteres coinciden y un costo de MAXLEN de lo contrario. Esto corresponde a penalizar los cambios y favorecer las coincidencias. La subsecuencia común más larga se puede encontrar siguiendo el rastro desde la celda objetivo hasta la celda de inicio y agregando cada carácter que corresponda a una coincidencia.
En general, la intuición detrás de estas modificaciones es sesgar el algoritmo de distancia de edición hacia la preservación de la subsecuencia relevante en lugar de minimizar el número de cambios. Al modificar los costos y objetivos, obligamos al algoritmo a dar prioridad a preservar la subsecuencia relevante y solo realizar cambios cuando sea necesario.