Programa Java para implementar el algoritmo de Wagner y Fisher para la coincidencia de strings en línea

El Algoritmo de Wagner-Fischer es un algoritmo de programación dinámica que mide la distancia de Levenshtein o la distancia de edición entre dos strings de caracteres. La distancia de Levenshtein (LD) calcula qué tan similares son las dos strings. La distancia se calcula mediante tres parámetros para transformar la string1 en string2.

Los parámetros son:

• Número de eliminaciones
• Número de inserciones
• Número de sustituciones

Por ejemplo

 Input:  str1="cat"  str2="cat"
 Output: 0
 
 The levenshtein distance i.e. LD(str1,str2)=0, because both the strings 
 are equal and no changes are needed.
 
 
 Input:  str1="bat"   str2="cat"
 Output: 1
 
 The levenshtein distance i.e. LD(str1,str2)=1, because we need to 
 substitute 'b' with 'c' to transform the string1 to string2.
 
 
 Input:  str1="bat"   str2="ball"
 Output: 2
 
 The levenshtein distance i.e. LD(str1,str2)=2, because there is 
 one substitution of 't' to 'l' and one insertion of 'l' needed to
 transform "bat" to "ball".

Algoritmo:

• Almacene las longitudes de las strings str1 y str2 en algunas variables, digamos n y m respectivamente.
• Si n==0 devuelve m
• Si m==0 devuelve n
• Construya una array de m filas y n columnas e inicialice la primera fila de 0 a n y la primera columna de 0 a m.
• Compruebe cada carácter de str1 y cada carácter de str2.
• Si el carácter en str1[i] es igual al carácter en str2[j] entonces m es 0 y si ambos no son iguales entonces m es 1.
• Establezca el elemento en arr[i][j] de la array como el mínimo de los siguientes: (arr[i-1][j]+1, arr[i][j-1]+1, arr[i- 1][j-1]+m)
• Después de iterar a través de los pasos 5, 6, 7, la distancia se encuentra en arr[n][m].

Código:

// Java Program to Implement Wagner and Fisher
// Algorithm for online String Matching
  
import java.util.*;
  
class GFG {
    public static int getDistance(String str1, String str2)
    {
  
        int l1 = str1.length();
        int l2 = str2.length();
  
        if (l1 == 0)
            return l2;
  
        if (l2 == 0)
            return l1;
  
        int arr[][] = new int[l1 + 1][l2 + 1];
  
        for (int i = 0; i <= l1; i++)
            arr[i][0] = i;
  
        for (int j = 0; j <= l2; j++)
            arr[0][j] = j;
  
        for (int i = 1; i <= l1; i++) {
            char ch1 = str1.charAt(i - 1);
  
            for (int j = 1; j <= l2; j++) {
                char ch2 = str2.charAt(j - 1);
  
                int m = ch1 == ch2 ? 0 : 1;
  
                arr[i][j] = Math.min(
                    Math.min((arr[i - 1][j] + 1),
                             (arr[i][j - 1] + 1)),
                    arr[i - 1][j - 1] + m);
            }
        }
  
        return arr[l1][l2];
    }
  
    public static void main(String[] args)
    {
  
        String str1, str2;
  
        str1 = "bat";
        str2 = "ball";
  
        System.out.println(getDistance(str1, str2));
    }
}

2

Complejidad temporal: O(m*n).