Почему я получаю неправильное расстояние Левенштейна? - PullRequest
Новая
       17

Почему я получаю неправильное расстояние Левенштейна?

1 голос
/ 28 мая 2019

Я пытаюсь реализовать алгоритм расстояния Левенштейна в C # (для практики и потому, что это было бы удобно иметь).Я использовал реализацию со страницы Википедии , но по какой-то причине я получаю неправильное расстояние для одного набора слов.Вот код (из LinqPad): 

void Main()
{
   var ld = new LevenshteinDistance();
   int dist = ld.LevenshteinDistanceCalc("sitting","kitten");
   dist.Dump();
}

// Define other methods and classes here
public class LevenshteinDistance
{
   private int[,] distance;

   public int LevenshteinDistanceCalc(string source, string target)
   {
      int sourceSize = source.Length, targetSize = target.Length;
      distance = new int[sourceSize, targetSize];
      for (int sIndex = 0; sIndex < sourceSize; sIndex++)
      {
         distance[sIndex, 0] = sIndex;
      }
      for (int tIndex = 0; tIndex < targetSize; tIndex++)
      {
         distance[0,tIndex] = tIndex;
      }
      //      for j from 1 to n:
      //      for i from 1 to m:
      //          if s[i] = t[j]:
      //            substitutionCost:= 0
      //          else:
      //            substitutionCost:= 1
      //          d[i, j] := minimum(d[i - 1, j] + 1,                   // deletion
      //                             d[i, j - 1] + 1,                   // insertion
      //                             d[i - 1, j - 1] + substitutionCost)  // substitution
      //
      //
      //      return d[m, n]

      for (int tIndex = 1; tIndex < targetSize; tIndex++)
      {
         for (int sIndex = 1; sIndex < sourceSize; sIndex++)
         {
            int substitutionCost = source[sIndex] == target[tIndex] ? 0 : 1;
            int deletion = distance[sIndex-1, tIndex]+1;
            int insertion = distance[sIndex,tIndex-1]+1;
            int substitution = distance[sIndex-1, tIndex-1] + substitutionCost;

            distance[sIndex, tIndex] = leastOfThree(deletion, insertion, substitution);

         }
      }
      return distance[sourceSize-1,targetSize-1];
   }

   private int leastOfThree(int a, int b, int c)
   {
      return Math.Min(a,(Math.Min(b,c)));
   }
}

Когда я пытаюсь "сидеть" и "котенок", я получаю LD 2 (должно быть 3).Тем не менее, когда я пробую "субботу" и "воскресенье", я получаю LD 3 (что правильно).Я знаю, что что-то не так, но я не могу понять, что мне не хватает.

Ответы [ 2 ]

2 голосов
/ 28 мая 2019

В примере в Википедии используются строки на основе 1.В C # мы используем строки, основанные на 0.

В их матрице 0-строка и 0-столбец существуют.Таким образом, размер их матрицы [source.Length + 1, source.Length + 1] в вашем коде не существует. 

public int LevenshteinDistanceCalc(string source, string target)
{
  int sourceSize = source.Length, targetSize = target.Length;
  distance = new int[sourceSize + 1, targetSize + 1];
  for (int sIndex = 1; sIndex <= sourceSize; sIndex++)
    distance[sIndex, 0] = sIndex;

  for (int tIndex = 1; tIndex <= targetSize; tIndex++)
    distance[0, tIndex] = tIndex;

  for (int tIndex = 1; tIndex <= targetSize; tIndex++)
  {
    for (int sIndex = 1; sIndex <= sourceSize; sIndex++)
    {
      int substitutionCost = source[sIndex-1] == target[tIndex-1] ? 0 : 1;
      int deletion = distance[sIndex - 1, tIndex] + 1;
      int insertion = distance[sIndex, tIndex - 1] + 1;
      int substitution = distance[sIndex - 1, tIndex - 1] + substitutionCost;

      distance[sIndex, tIndex] = leastOfThree(deletion, insertion, substitution);
    }
  }
  return distance[sourceSize, targetSize];
}
1 голос
/ 28 мая 2019

Ваша матрица недостаточно велика.

В псевдокоде s и t имеют длины m и n соответственно (char s[1..m], char t[1..n]). Матрица, однако, имеет размеры [0..m, 0..n], то есть на единицу больше, чем длина строк в каждом направлении. Вы можете увидеть это в таблицах под псевдокодом.

Таким образом, матрица для «сидения» и «котенка» - 7x8, а ваша матрица - только 6x7.

Вы также неправильно индексируете строки, потому что строки в псевдокоде индексируются 1, а строки C # индексируются 0.

После исправления вы получите этот код, который работает с «сидячим» и «котенком»: 

public static class LevenshteinDistance
{
    public static int LevenshteinDistanceCalc(string source, string target)
    {
        int sourceSize = source.Length + 1, targetSize = target.Length + 1;
        int[,] distance = new int[sourceSize, targetSize];
        for (int sIndex = 0; sIndex < sourceSize; sIndex++)
        {
            distance[sIndex, 0] = sIndex;
        }
        for (int tIndex = 0; tIndex < targetSize; tIndex++)
        {
            distance[0, tIndex] = tIndex;
        }
        //      for j from 1 to n:
        //      for i from 1 to m:
        //          if s[i] = t[j]:
        //            substitutionCost:= 0
        //          else:
        //            substitutionCost:= 1
        //          d[i, j] := minimum(d[i - 1, j] + 1,                   // deletion
        //                             d[i, j - 1] + 1,                   // insertion
        //                             d[i - 1, j - 1] + substitutionCost)  // substitution
        //
        //
        //      return d[m, n]

        for (int tIndex = 1; tIndex < targetSize; tIndex++)
        {
            for (int sIndex = 1; sIndex < sourceSize; sIndex++)
            {
                int substitutionCost = source[sIndex - 1] == target[tIndex - 1] ? 0 : 1;
                int deletion = distance[sIndex - 1, tIndex] + 1;
                int insertion = distance[sIndex, tIndex - 1] + 1;
                int substitution = distance[sIndex - 1, tIndex - 1] + substitutionCost;

                distance[sIndex, tIndex] = leastOfThree(deletion, insertion, substitution);
            }
        }
        return distance[sourceSize - 1, targetSize - 1];
    }

    private static int leastOfThree(int a, int b, int c)
    {
        return Math.Min(a, (Math.Min(b, c)));
    }
}

(я также взял на себя смелость сделать distance локальной переменной, так как нет необходимости, чтобы она была полем (это делает ваш класс не поточно-безопасным), а также сделать его статическим, чтобы избежать ненужной реализации).

Для отладки я поставил точку останова на return distance[sourceSize - 1, targetSize - 1] и сравнил distance с таблицей в Википедии. Было очень очевидно, что это было слишком мало.

...