c# - 为什么我得到不正确的 Levenshtein 距离？

Question

我正在尝试在 C# 中实现 Levenshtein 距离算法(用于练习，因为它会很方便)。我使用了 Wikipedia page 中的一个实现但出于某种原因，我在一组单词上的距离错误。这是代码(来自 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(这是正确的)。我知道出了什么问题，但我不知道我错过了什么。

Answer 1

维基百科上的示例使用从 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];
}