Может ли кто-нибудь обнаружить ошибку в моей реализации Damerau-Levenshtein Distance?

Question

У меня фанковая ошибка, которая сводит меня с ума. Может ли кто-нибудь помочь мне найти его? Попробуйте вызвать функцию двумя словами, которые отличаются только отсутствующим последним символом («garble» vs «garbl»). Функция возвращает 0 вместо ожидаемого 1. Предполагается, что она вернется 1, правильно?

Я пробовал возиться с границами массива, но это вызывает только IndexOutOfRangeExceptions.

public static class FuzzyStringMatcher 
{ 
    private const int DELETION = 0; 
    private const int INSERTION = 1; 
    private const int SUBSTITUTION = 2; 
    private const int TRANSPOSITION = 3; 

    private const int COST_OF_DELETION = 1; 
    private const int COST_OF_INSERTION = 1; 
    private const int COST_OF_TRANSPOSITION = 1; 
    private const int COST_OF_SUBSTITUTION = 1; 

    public static int Compute_DamerauLevenshtein_Distance(string a, string b) 
    { 
     int[,] rows = new int[a.Length + 1, b.Length + 1]; 
     int cost_ratio; 
     int[] calculations = new int[4]; 

     // 
     // Init the array 
     // 
     for (int i = 0; i < rows.GetUpperBound(0); i++) 
      rows[i, 0] = i; 

     for (int i = 0; i < rows.GetUpperBound(1); i++) 
      rows[0, i] = i; 


     for (int aidx = 1; aidx < rows.GetUpperBound(0); aidx++) 
     { 
      for (int bidx = 1; bidx < rows.GetUpperBound(1); bidx++) 
      { 
       if (a[aidx - 1] == b[bidx - 1]) 
        cost_ratio = 0; 
       else 
        cost_ratio = 1; 

       calculations[DELETION] = rows[aidx - 1, bidx] + COST_OF_DELETION; 
       calculations[INSERTION] = rows[aidx, bidx - 1] + COST_OF_INSERTION; 
       calculations[SUBSTITUTION] = rows[aidx - 1, bidx - 1] + cost_ratio * COST_OF_SUBSTITUTION; 
       calculations[TRANSPOSITION] = int.MaxValue; 

       if (aidx > 1 && bidx > 1 && a[aidx] == b[bidx - 1] && a[aidx - 1] == b[bidx]) 
        calculations[TRANSPOSITION] = rows[aidx - 2, bidx - 2] + cost_ratio * COST_OF_TRANSPOSITION; 

       rows[aidx, bidx] = calculations.Min(); 
      } 
     } 

     int score = rows[rows.GetUpperBound(0) - 1, rows.GetUpperBound(1) - 1]; 
     if (a.Contains(b) || b.Contains(a)) 
      score = score/2; 
     return score; 
    } 
} 

Моя реализация базируется алгоритм, данный на странице Википедии на Damerau-Levenshtein-Distance

Answer 1

Это не в статье Википедии:

if (a.Contains(b) || b.Contains(a)) 
     score = score/2; 

Поскольку это верно для примера - и целочисленное деление 1/2 == 0, то это может быть оно.

Answer 2

+1 к Лу Франко. Но кроме того, похоже, что у вас много проблем с индексами (обратите внимание, что все 4 for циклов в образце вики включены, а когда 1 вычитается из helpx/bidx, вам действительно нужно вычесть 2, потому что в вики-образцах индексы в строках начинаются с 1). Моя версия:

public static int Compute_DamerauLevenshtein_Distance2(string a, string b) 
    { 
     int[,] rows = new int[a.Length + 1, b.Length + 1]; 
     int cost_ratio; 
     int[] calculations = new int[4]; 

     for(int i = 0; i <= rows.GetUpperBound(0); i++) 
      rows[i, 0] = i; 

     for(int i = 1; i <= rows.GetUpperBound(1); i++) 
      rows[0, i] = i; 


     for(int aidx = 1; aidx <= rows.GetUpperBound(0); aidx++) 
     { 
      for(int bidx = 1; bidx <= rows.GetUpperBound(1); bidx++) 
      { 
       if(a[aidx - 1] == b[bidx - 1]) 
        cost_ratio = 0; 
       else 
        cost_ratio = 1; 

       calculations[DELETION] = rows[aidx - 1, bidx] + COST_OF_DELETION; 
       calculations[INSERTION] = rows[aidx, bidx - 1] + COST_OF_INSERTION; 
       calculations[SUBSTITUTION] = rows[aidx - 1, bidx - 1] + cost_ratio * COST_OF_SUBSTITUTION; 
       calculations[TRANSPOSITION] = int.MaxValue; 

       if(aidx > 1 && bidx > 1 && a[aidx - 1] == b[bidx - 2] && a[aidx - 2] == b[bidx - 1]) 
        calculations[TRANSPOSITION] = rows[aidx - 2, bidx - 2] + cost_ratio * COST_OF_TRANSPOSITION; 

       rows[aidx, bidx] = calculations.Min(); 
      } 
     } 

     int score = rows[rows.GetUpperBound(0), rows.GetUpperBound(1)]; 
     return score; 
    }