Левенштейн расстояние симметричное?

Question

Мне сообщили, что расстояние Левенштейна симметрично. Когда я использовал инструмент diffMatchPatch Google, который вычисляет расстояние Левенштейна между прочим, результаты не подразумевают, что расстояние Левенштейна симметрично. т. е. Левенштейн (x1, x2) не равен Левенштейну (x2, x1). Является ли Levenshtein несимметричным или существует проблема с этой конкретной реализацией? Благодарю.

Answer 1

Просто глядя на базовый алгоритм это, безусловно, является симметричным при той же стоимости для операций - количество добавлений, удалений и замен, чтобы получить от слова А к слову В то же самое, как получение от слова B к слову A.

Если существует какая-либо другая стоимость для любой из операций, может быть разница, например, если добавление имеет стоимость 2 и удаление стоимость 1, чтобы получить от Zombie до Zombies, результат на расстоянии 2, наоборот - 1 - несимметричный.

Answer 2

Да, расстояние levenshtein - это расстояние в собственном смысле, то есть dist(a,b)==dist(b,a) является частью определения расстояния. Если функция не обладает этим свойством, это не функция расстояния. Это говорит о проблеме с этой реализацией.

Answer 3

Классический алгоритм Левенштейна является симметричным - то, что является вставкой, идущей от x1 до x2, является удалением, идущим от x2 до x1.

К сожалению, алгоритм O (длина (x1) * длина (x2)). После краткого взгляда на библиотеку google, кажется, он пытается несколько эвристик, чтобы гарантировать, что время выполнения не слишком велико. Я думаю, там лежит ваше несоответствие.

Answer 4

, пожалуйста, следуйте код, который implmented по myselef

общественного класса 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()); 
    } 

} 

}