1. Introducción
En este artículo, describimos la distancia de Levenshtein, también conocida como distancia de edición. El algoritmo que se explica aquí fue diseñado por un científico ruso, Vladimir Levenshtein, en 1965.
Proporcionaremos una implementación Java iterativa y recursiva de este algoritmo.
2. ¿Qué es la distancia de Levenshtein?
La distancia de Levenshtein es una medida de disimilitud entre dos cadenas. Matemáticamente, dados dos cadenas X e Y , las medidas de distancia el número mínimo de ediciones caracteres necesarios para transformar x en y .
Normalmente se permiten tres tipos de ediciones:
- Inserción de un carácter c
- Supresión de un carácter c
- Sustitución de un carácter c por c '
Ejemplo: Si x = 'shot' y y = 'spot' , la distancia de edición entre los dos es 1 porque 'shot' se puede convertir en 'punto' sustituyendo ' h ' a ' p '.
En ciertas subclases del problema, el costo asociado con cada tipo de edición puede ser diferente.
Por ejemplo, menos costo para la sustitución con un carácter ubicado cerca en el teclado y más costo en caso contrario. Para simplificar, consideraremos que todos los costos son iguales en este artículo.
Algunas de las aplicaciones de la distancia de edición son:
- Correctores ortográficos: detectan errores ortográficos en el texto y encuentran la ortografía correcta más cercana en el diccionario.
- Detección de plagio (consulte - Documento IEEE)
- Análisis de ADN: encontrar similitudes entre dos secuencias
- Reconocimiento de voz (consulte - Microsoft Research)
3. Formulación de algoritmos
Tomemos dos cadenas x y y de longitudes de m y n respectivamente. Podemos denotar cada Cadena como x [1: m] e y [1: n].
Sabemos que al final de la transformación, ambas cadenas tendrán la misma longitud y tendrán caracteres coincidentes en cada posición. Entonces, si consideramos el primer carácter de cada Cadena, tenemos tres opciones:
- Sustitución:
- Determine el costo ( D1 ) de sustituir x [1] por y [1] . El costo de este paso sería cero si ambos personajes son iguales. Si no, entonces el costo sería uno
- Después del paso 1.1, sabemos que ambas cadenas comienzan con el mismo carácter. Por lo tanto, el costo total ahora sería la suma del costo del paso 1.1 y el costo de transformar el resto de la Cadena x [2: m] en y [2: n]
- Inserción:
- Inserte un carácter en x para que coincida con el primer carácter en y , el costo de este paso sería uno
- Después de 2.1, hemos procesado un carácter de y . Por lo tanto, el costo total ahora sería la suma del costo del paso 2.1 (es decir, 1) y el costo de transformar el x [1: m] completo en y restante (y [2: n])
- Supresión:
- Elimina el primer carácter de x , el costo de este paso sería uno
- Después de 3.1, hemos procesado un carácter de x , pero queda por procesar la y completa . El costo total sería la suma del costo de 3.1 (es decir, 1) y el costo de transformar la x restante en la y completa
La siguiente parte de la solución es averiguar qué opción elegir entre estas tres. Como no sabemos qué opción daría lugar a un coste mínimo al final, debemos probar todas las opciones y elegir la mejor.
4. Implementación recursiva ingenua
Podemos ver que el segundo paso de cada opción en la sección # 3 es principalmente el mismo problema de distancia de edición pero en subcadenas de las cadenas originales . Esto significa que después de cada iteración terminamos con el mismo problema pero con cadenas más pequeñas .
Esta observación es la clave para formular un algoritmo recursivo. La relación de recurrencia se puede definir como:
D (x [1: m], y [1: n]) = min {
D (x [2: m], y [2: n]) + Costo de reemplazo de x [1] ay [1],
D (x [1: m], y [2: n]) + 1,
D (x [2: m], y [1: n]) + 1
}
También debemos definir casos base para nuestro algoritmo recursivo, que en nuestro caso es cuando una o ambas cadenas quedan vacías:
- Cuando ambas cadenas están vacías, la distancia entre ellas es cero
- Cuando una de las cadenas está vacía, la distancia de edición entre ellas es la longitud de la otra cadena, ya que necesitamos esa cantidad de inserciones / eliminaciones para transformar una en la otra:
- Ejemplo: si una Cadena es "perro" y otra Cadena es "" (vacía), necesitamos tres inserciones en Cadena vacía para convertirla en "perro" , o necesitamos tres eliminaciones en "perro" para dejarla vacía. Por lo tanto, la distancia de edición entre ellos es 3
Una implementación recursiva ingenua de este algoritmo:
public class EditDistanceRecursive { static int calculate(String x, String y) { if (x.isEmpty()) { return y.length(); } if (y.isEmpty()) { return x.length(); } int substitution = calculate(x.substring(1), y.substring(1)) + costOfSubstitution(x.charAt(0), y.charAt(0)); int insertion = calculate(x, y.substring(1)) + 1; int deletion = calculate(x.substring(1), y) + 1; return min(substitution, insertion, deletion); } public static int costOfSubstitution(char a, char b) { return a == b ? 0 : 1; } public static int min(int... numbers) { return Arrays.stream(numbers) .min().orElse(Integer.MAX_VALUE); } }Este algoritmo tiene la complejidad exponencial. En cada paso, nos ramificamos en tres llamadas recursivas, creando una complejidad O (3 ^ n) .
En la siguiente sección, veremos cómo mejorar esto.
5. Enfoque de programación dinámica
Al analizar las llamadas recursivas, observamos que los argumentos de los subproblemas son sufijos de las cadenas originales . Esto significa que no sólo puede ser m * n llamadas recursivas únicas (donde m y n son un número de sufijos de x y y ). Por tanto, la complejidad de la solución óptima debería ser cuadrática, O (m * n) .
Veamos algunos de los subproblemas (según la relación de recurrencia definida en la sección # 4):
- Los subproblemas de D (x [1: m], y [1: n]) son D (x [2: m], y [2: n]), D (x [1: m], y [2 : n]) y D (x [2: m], y [1: n])
- Los subproblemas de D (x [1: m], y [2: n]) son D (x [2: m], y [3: n]), D (x [1: m], y [3 : n]) y D (x [2: m], y [2: n])
- Los subproblemas de D (x [2: m], y [1: n]) son D (x [3: m], y [2: n]), D (x [2: m], y [2 : n]) y D (x [3: m], y [1: n])
En los tres casos, uno de los subproblemas es D (x [2: m], y [2: n]). En lugar de calcular esto tres veces como lo hacemos en la implementación ingenua, podemos calcular esto una vez y reutilizar el resultado cuando sea necesario.
Este problema tiene muchos subproblemas superpuestos, pero si conocemos la solución a los subproblemas, podemos encontrar fácilmente la respuesta al problema original. Por lo tanto, tenemos las dos propiedades necesarias para formular una solución de programación dinámica, es decir, subproblemas superpuestos y subestructura óptima.
Podemos optimizar la implementación ingenua introduciendo memorización, es decir, almacenar el resultado de los subproblemas en una matriz y reutilizar los resultados en caché.
Alternativamente, también podemos implementar esto iterativamente usando un enfoque basado en tablas:
static int calculate(String x, String y) { int[][] dp = new int[x.length() + 1][y.length() + 1]; for (int i = 0; i <= x.length(); i++) { for (int j = 0; j <= y.length(); j++) { if (i == 0) { dp[i][j] = j; } else if (j == 0) { dp[i][j] = i; } else { dp[i][j] = min(dp[i - 1][j - 1] + costOfSubstitution(x.charAt(i - 1), y.charAt(j - 1)), dp[i - 1][j] + 1, dp[i][j - 1] + 1); } } } return dp[x.length()][y.length()]; } Este algoritmo funciona significativamente mejor que la implementación recursiva. Sin embargo, implica un consumo de memoria significativo.
Esto se puede optimizar aún más observando que solo necesitamos el valor de tres celdas adyacentes en la tabla para encontrar el valor de la celda actual.
6. Conclusión
En este artículo, describimos qué es la distancia de Levenshtein y cómo se puede calcular utilizando un enfoque recursivo y basado en programación dinámica.
La distancia de Levenshtein es solo una de las medidas de similitud de cadenas, algunas de las otras métricas son Similitud de coseno (que utiliza un enfoque basado en fichas y considera las cadenas como vectores), Coeficiente de dados, etc.
Como siempre, la implementación completa de los ejemplos se puede encontrar en GitHub.