Tengo una duda, ese valor 2 que marqué en amarillo, ¿no debería ser un 1?
Tenía entendido que como E es distinta de O coloco en el casillero amarillo el mínimo entre 0+1, 1+1 y 1+1 que sería 1
Gracias!
Creo que hay que sumar 2 verdad? Me entreveré con eso de que el reemplazo cuenta por 2. Es así? Cuando difieren las letras debo sumar 2 al casillero (i-1,j-1)?
Gracias!
Gracias!
En respuesta a Gabriela Gaggero Bracco
Re: Distancia Mínima de Edición
Hola, Gabriela,
Si, creo que hay que sumar 2 en caso de diferencia de letras. Te dejo un código en JS que calcula esto:
const levenshteinDistance = (s, t) => {
if (!s.length) return t.length;
if (!t.length) return s.length;
const arr = [];
for (let i = 0; i <= t.length; i++) {
arr[i] = [i];
for (let j = 1; j <= s.length; j++) {
arr[i][j] =
i === 0
? j
: Math.min(
arr[i - 1][j] + 1,
arr[i][j - 1] + 1,
arr[i - 1][j - 1] + (s[j - 1] === t[i - 1] ? 0 : 2)
);
}
}
return arr[t.length][s.length];
};
console.log('distance: ' + levenshteinDistance('AMIGO', 'ACASO'));
Si, creo que hay que sumar 2 en caso de diferencia de letras. Te dejo un código en JS que calcula esto:
const levenshteinDistance = (s, t) => {
if (!s.length) return t.length;
if (!t.length) return s.length;
const arr = [];
for (let i = 0; i <= t.length; i++) {
arr[i] = [i];
for (let j = 1; j <= s.length; j++) {
arr[i][j] =
i === 0
? j
: Math.min(
arr[i - 1][j] + 1,
arr[i][j - 1] + 1,
arr[i - 1][j - 1] + (s[j - 1] === t[i - 1] ? 0 : 2)
);
}
}
return arr[t.length][s.length];
};
console.log('distance: ' + levenshteinDistance('AMIGO', 'ACASO'));
Hola.
La explicación de porqué da 2 ese casillero es que lo que dice el algoritmo es que se toma el menor de los valores de:
(i-1,j) + 1
(i,j-1) +1
(i-1,j-1) +2 - si las letras son distintas - o (i-1,j-1) si las letras son iguales
En ese caso, sería: min{1+1, 1+1, 0+2} = 2
Saludos
Juanjo
La explicación de porqué da 2 ese casillero es que lo que dice el algoritmo es que se toma el menor de los valores de:
(i-1,j) + 1
(i,j-1) +1
(i-1,j-1) +2 - si las letras son distintas - o (i-1,j-1) si las letras son iguales
En ese caso, sería: min{1+1, 1+1, 0+2} = 2
Saludos
Juanjo