Levenshtein odległość symetryczna?

Question

Zostałem poinformowany, że odległość Levenshteina jest symetryczna. Kiedy używałem narzędzia google diffMatchPatch, które wylicza odległość między Levenshtein, wyniki nie sugerują, że odległość Levenshteina jest symetryczna. tj. Levenshtein (x1, x2) nie jest równy Levenshtein (x2, x1). Czy Levenshtein nie jest symetryczny lub czy istnieje problem z tą konkretną implementacją? Dzięki.

Answer 1

Po prostu patrząc na algorytmu podstawowego to na pewno jest symetryczny biorąc pod uwagę sam koszt operacji - liczba uzupełnień, usunięć i substytucji, aby uzyskać od słowie do słowa B jest taka sama, jak się od słowa B na słowo A.

Jeśli na którymkolwiek z działań występuje inny koszt, może to być różnica, np. jeśli dodatek ma koszt 2 i usunięcie koszt 1, aby uzyskać od Zombie do Zombies wyników w odległości 2, odwrotnie byłoby 1 - nie symetryczne.

Answer 2

Tak, odległość levenshtein to odległość we właściwym znaczeniu, czyli dist(a,b)==dist(b,a) jest częścią definicji odległości. Jeśli funkcja nie ma tej właściwości, nie jest funkcją odległościową. Sugeruje to problem z tą implementacją.

Answer 3

Klasyczny algorytm Levenshteina jest symetryczny - to, co jest wprowadzaniem od x1 do x2, to usuwanie od x2 do x1.

Niestety, algorytm ma postać O (długość (x1) * długość (x2)). Po krótkim przyjrzeniu się bibliotece Google'a, wygląda na to, że próbuje heurystyki, aby upewnić się, że środowisko wykonawcze nie jest zbyt duże. Myślę, że leży Twoja rozbieżność.

Answer 4

należy wykonać kod, który jest implmented przez 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()); 
    } 

} 

}