Levenshtein distancia simétrica?

Question

Me informaron que la distancia de Levenshtein es simétrica. Cuando utilicé la herramienta diffMatchPatch de Google, que calcula la distancia de Levenshtein entre otras cosas, los resultados no implican que la distancia de Levenshtein sea simétrica. es decir, Levenshtein (x1, x2) no es igual a Levenshtein (x2, x1). ¿Levenshtein no es simétrico o hay algún problema con esa implementación en particular? Gracias.

Answer 1

sólo mirar el algoritmo básico que sin duda es simétrica dado el mismo costo para las operaciones - el número de adiciones, eliminaciones y sustituciones para llegar de una palabra de A a una palabra B es lo mismo que ir de la palabra B a la palabra A.

Si hay un costo diferente en cualquiera de las operaciones, puede haber una diferencia, por ejemplo, si la suma tiene un costo de 2 y la eliminación un costo de 1 para obtener de Zombie a Zombies resulta en una distancia de 2, a la inversa sería 1 - no simétrica.

Answer 2

Sí, la distancia levenshtein es una distancia en el sentido correcto, es decir dist(a,b)==dist(b,a) es una parte de la definición de una distancia. Si una función no tiene esta propiedad, no es una función de distancia. Esto sugiere un problema con esa implementación.

Answer 3

El algoritmo clásico de Levenshtein es simétrico; lo que es una inserción que va de x1 a x2 es una eliminación que va de x2 a x1.

Lamentablemente, el algoritmo es O (longitud (x1) * longitud (x2)). Después de una breve mirada a la biblioteca de Google, parece que intenta algunas heurísticas para asegurar que el tiempo de ejecución no sea demasiado grande. Creo que yace tu discrepancia.

Answer 4

siga el código que se implmented por myselef

public class {ReadTextFile

static void readFile(String filepath){ 
    CharSequence sequence1 = null; 
    CharSequence sequence2 = null; 

    int levenshteinDistance = 0; 

    String line1 = ""; 
    String line2 = ""; 
    int minLevenshteinDistance = -1; 

    try { 
     BufferedReader br = new BufferedReader(new FileReader(filepath)); 
     String line = ""; 
     while((line=br.readLine())!=null) 
     {    

      if(sequence1==null){ 
       line = line.split(" ")[1]; 
       sequence1 = line;     

       if((line=br.readLine())!=null){     
        line = line.split(" ")[1]; 
        sequence2 = line;     
       } 
      }else{ 
       sequence1 = sequence2; 
       line = line.split(" ")[1]; 
       sequence2 = line;     
      } 


      if(null!=sequence1 && null!=sequence2){ 

       levenshteinDistance = StringUtils.getLevenshteinDistance(sequence1,sequence2); 

       if(minLevenshteinDistance==-1){ 
        minLevenshteinDistance = levenshteinDistance; 
        line1= sequence1.toString(); 
        line2= sequence2.toString(); 
       }else if(levenshteinDistance < minLevenshteinDistance){ 
        minLevenshteinDistance = levenshteinDistance; 
        line1= sequence1.toString(); 
        line2= sequence2.toString(); 
       } 

      } 


     } 

     br.close(); 
     System.out.println("line1 "+line1); 
     System.out.println("line2 "+line2); 
     System.out.println("minlevenshteinDistance "+minLevenshteinDistance); 

    }catch (IOException e) { 
     System.out.println(e.getMessage()); 
    } 

} 

}