Programa Java para implementar el algoritmo de computación a distancia de Levenshtein

La distancia de Levenshtein, también llamada distancia de edición , es el número mínimo de operaciones necesarias para transformar una string en otra.

Por lo general, se realizan tres tipos de operaciones (una a la vez):

• Reemplazar un personaje.
• Eliminar un personaje.
• Inserta un carácter.

Ejemplos:

Entrada: str1 = «glomax», str2 = «folmax» 

Salida: 3 

str1 se convierte en str2 reemplazando ‘g’ con ‘o’, eliminando la segunda ‘o’ e insertando ‘f’ al principio. No hay forma de hacerlo con menos de tres ediciones.

Entrada: s1 = «GIKY», s2 = «GEEKY» 

Salida: 2 

s1 se convierte en s2 insertando ‘E’ justo después de ‘G’ y reemplazando ‘I’ con ‘E’.

Este problema se puede hacer de dos maneras:

1. Uso de recursividad.
2. Usando Programación Dinámica.

Método 1: enfoque recursivo  

Consideremos tomando un ejemplo.

Dadas dos strings s1 = «domingo» y s2 = «sábado». Queremos convertir «domingo» en «sábado» con ediciones mínimas.

• Considere ‘i’ y ‘j’ como los índices de límite superior de las substrings generadas usando s1 y s2.
• Elijamos i = 2 y j = 4, es decir, las strings de prefijos son ‘su’ y ‘satu’ respectivamente (supongamos que los índices de las strings comienzan en 1). Los caracteres más a la derecha se pueden alinear de tres maneras posibles diferentes.
• Posible caso 1 : Alinee los caracteres ‘u’ y ‘u’. Son iguales, no se requiere edición. Todavía nos quedamos con el problema de i = 1 y j = 3, por lo que debemos proceder a encontrar la distancia de Levenshtein (i-1, j-1).
• Posible caso 2 (eliminación): alinee el carácter correcto de la primera string y ningún carácter de la segunda string. Necesitamos una eliminación aquí. Todavía nos quedamos con el problema de i = 1 y j = 4, por lo que debemos proceder a encontrar la distancia de Levenshtein (i-1, j).
• Posible caso 3 (inserción): alinee el carácter correcto de la segunda string y ningún carácter de la primera string. Necesitamos una inserción aquí. Todavía nos quedamos con el problema de i = 2 y j = 3, por lo que debemos proceder a encontrar la distancia de Levenshtein (i, j-1).
• Suponemos que el carácter que se insertará en la primera string es el mismo que el carácter derecho de la segunda string.
• Posible caso 4 (reemplazo): alinee los caracteres a la derecha de la primera string y de la segunda string. Necesitamos una sustitución aquí. Todavía nos quedamos con el problema de i = 1 y j = 3, por lo que debemos proceder a encontrar la distancia de Levenshtein (i-1, j-1).
• Suponemos que el carácter reemplazado en la primera string es el mismo que el carácter derecho de la segunda string.
• Tenemos que encontrar el mínimo de los tres casos posibles.

Implementación recursiva:

// Java implementation of recursive Levenshtein distance
// calculation
 
import java.util.*;
class LevenshteinDistanceRecursive {
 
    static int compute_Levenshtein_distance(String str1,
                                            String str2)
    {
        // If str1 is empty, all
        // characters of str2 are
        // inserted into str1, which is
        // of the only possible method of
        // conversion with minimum
        // operations.
 
        if (str1.isEmpty())
        {
            return str2.length();
        }
 
        // If str2 is empty, all
        // characters of str1 are
        // removed, which is the
        // only possible
        // method of conversion with minimum
        // operations.
 
        if (str2.isEmpty())
        {
            return str1.length();
        }
 
        // calculate the number of distinct characters to be
        // replaced in str1
        // by recursively traversing each substring
 
        int replace = compute_Levenshtein_distance(
              str1.substring(1), str2.substring(1))
              + NumOfReplacement(str1.charAt(0),str2.charAt(0));
 
        // calculate the number of insertions in str1
        // recursively
        int insert = compute_Levenshtein_distance(
                         str1, str2.substring(1))+ 1;
 
        // calculate the number of deletions in str1
        // recursively
        int delete = compute_Levenshtein_distance(
                         str1.substring(1), str2)+ 1;
 
        // returns minimum of three operations
       
        return minm_edits(replace, insert, delete);
    }
 
    static int NumOfReplacement(char c1, char c2)
    {
        // check for distinct characters
        // in str1 and str2
       
        return c1 == c2 ? 0 : 1;
    }
 
    static int minm_edits(int... nums)
    {
        // receives the count of different
        // operations performed and returns the
        // minimum value among them.
       
        return Arrays.stream(nums).min().orElse(
            Integer.MAX_VALUE);
    }
 
    // Driver Code
    public static void main(String args[])
    {
        String s1 = "glomax";
        String s2 = "folmax";
 
        System.out.println(compute_Levenshtein_distance(s1, s2));
    }
}

3

Complejidad de tiempo: O(3^n) porque en cada paso, nos bifurcamos en tres llamadas recursivas. Aquí, ‘n’ es la longitud de la primera string.

Método 2: enfoque de programación dinámica   

Si dibujamos el árbol de recurrencia de la solución anterior, podemos ver que los mismos subproblemas se calculan una y otra vez. Sabemos que la programación dinámica entra en escena cuando las soluciones de los subproblemas se pueden memorizar en lugar de calcularlas una y otra vez. 

• La versión Memoized sigue el enfoque de arriba hacia abajo, ya que primero dividimos los problemas en subproblemas y luego calculamos y almacenamos valores.
• También podemos resolver este problema con un enfoque ascendente. De manera ascendente, primero resolvemos los subproblemas y luego resolvemos los subproblemas más grandes a partir de ellos.

 Implementación de programación dinámica (enfoque optimizado)

// Java implementation of Levenshtein distance calculation
// Using Dynamic Programming (Optimised solution)
 
import java.util.*;
class LevenshteinDistanceDP {
 
    static int compute_Levenshtein_distanceDP(String str1,
                                              String str2)
    {
 
        // A 2-D matrix to store previously calculated
        // answers of subproblems in order
        // to obtain the final
 
        int[][] dp = new int[str1.length() + 1][str2.length() + 1];
 
        for (int i = 0; i <= str1.length(); i++)
        {
            for (int j = 0; j <= str2.length(); j++) {
 
                // If str1 is empty, all characters of
                // str2 are inserted into str1, which is of
                // the only possible method of conversion
                // with minimum operations.
                if (i == 0) {
                    dp[i][j] = j;
                }
 
                // If str2 is empty, all characters of str1
                // are removed, which is the only possible
                //  method of conversion with minimum
                //  operations.
                else if (j == 0) {
                    dp[i][j] = i;
                }
 
                else {
                    // find the minimum among three
                    // operations below
 
                     
                    dp[i][j] = minm_edits(dp[i - 1][j - 1]
                        + NumOfReplacement(str1.charAt(i - 1),str2.charAt(j - 1)), // replace
                        dp[i - 1][j] + 1, // delete
                        dp[i][j - 1] + 1); // insert
                }
            }
        }
 
        return dp[str1.length()][str2.length()];
    }
 
    // check for distinct characters
    // in str1 and str2
   
    static int NumOfReplacement(char c1, char c2)
    {
        return c1 == c2 ? 0 : 1;
    }
 
    // receives the count of different
    // operations performed and returns the
    // minimum value among them.
   
    static int minm_edits(int... nums)
    {
 
        return Arrays.stream(nums).min().orElse(
            Integer.MAX_VALUE);
    }
 
    // Driver Code
    public static void main(String args[])
    {
 
        String s1 = "glomax";
        String s2 = "folmax";
 
        System.out.println(compute_Levenshtein_distanceDP(s1, s2));
    }
}

3

Complejidad de tiempo: O(m*n), donde m es la longitud de la primera string y n es la longitud de la segunda string.

Espacio auxiliar: O(m*n), ya que la array utilizada en la implementación anterior tiene dimensiones m*n .

Aplicaciones: 

• Correctores ortográficos.
• Reconocimiento de voz.
• Análisis de ADN.