distanza simmetrica di Levenshtein?

Question

Sono stato informato che la distanza di Levenshtein è simmetrica. Quando ho usato lo strumento diffMatchPatch di google che calcola la distanza di Levenshtein tra le altre cose, i risultati non implicano che la distanza di Levenshtein sia simmetrica. cioè Levenshtein (x1, x2) non è uguale a Levenshtein (x2, x1). Levenshtein non è simmetrico o c'è un problema con quella particolare implementazione? Grazie.

Answer 1

solo guardando l'algoritmo di base è sicuramente simmetrica dato lo stesso costo per le operazioni - il numero di aggiunte, cancellazioni e sostituzioni di ottenere da una parola Una ad una parola B è lo stesso di ottenere dalla parola B alla parola A.

Se c'è un costo diverso su una qualsiasi delle operazioni, può esserci una differenza, ad es. se l'aggiunta ha un costo di 2 e la cancellazione di un costo di 1 per ottenere da Zombie a Zombies risultati in una distanza di 2, il contrario sarebbe 1 - non simmetrica.

Answer 2

Sì, la distanza di levenshtein è una distanza nel senso proprio, ovvero dist(a,b)==dist(b,a) è una parte della definizione di distanza. Se una funzione non ha questa proprietà non è una funzione di distanza. Questo suggerisce un problema con questa implementazione.

Answer 3

Il classico algoritmo di Levenshtein è simmetrico: ciò che è un inserimento che va da x1 a x2 è una cancellazione che va da x2 a x1.

Sfortunatamente, l'algoritmo è O (lunghezza (x1) * lunghezza (x2)). Dopo un breve sguardo alla libreria di google, sembra che provi delle euristiche per assicurare che il runtime non sia troppo grande. Penso che ci sia la tua discrepanza.

Answer 4

si prega di seguire il codice che viene implmented da 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()); 
    } 

} 

}