什么是C#完全模拟PHP函数“similar_text()”？

Question

int ComputeLevenshteinDistance(string source, string target)
{
    if ((source == null) || (target == null)) return 0;
    if ((source.Length == 0) || (target.Length == 0)) return 0;
    if (source == target) return source.Length;

    int sourceWordCount = source.Length;
    int targetWordCount = target.Length;

    // Step 1
    if (sourceWordCount == 0)
        return targetWordCount;

    if (targetWordCount == 0)
        return sourceWordCount;

    int[,] distance = new int[sourceWordCount + 1, targetWordCount + 1];

    // Step 2
    for (int i = 0; i <= sourceWordCount; distance[i, 0] = i++) ;
    for (int j = 0; j <= targetWordCount; distance[0, j] = j++) ;

    for (int i = 1; i <= sourceWordCount; i++)
    {
        for (int j = 1; j <= targetWordCount; j++)
        {
            // Step 3
            int cost = (target[j - 1] == source[i - 1]) ? 0 : 1;

            // Step 4
            distance[i, j] = Math.Min(Math.Min(distance[i - 1, j] + 1, distance[i, j - 1] + 1), distance[i - 1, j - 1] + cost);
        }
    }

    return distance[sourceWordCount, targetWordCount];
}

double CalculateSimilarity(string source, string target)
{
    if ((source == null) || (target == null)) return 0.0;
    if ((source.Length == 0) || (target.Length == 0)) return 0.0;
    if (source == target) return 1.0;

    int stepsToSame = ComputeLevenshteinDistance(source, target);
    return (1.0 - ((double)stepsToSame / (double)Math.Max(source.Length, target.Length)));
}

结果值不是等效的PHP。

PHP Similar_text()函数：它计算两个字符串之间的相似性，如

编程经典：实现世界上最好的算法

Answer 1

首先，您必须实现编辑距离，比如说，Levenstein一；让我们尽可能地把它做得更通用：

请参见检测两个字符串之间的差异

有关编辑序列和更多细节。

using System.Linq;

...

private static double EditDistance<T>(IEnumerable<T> from,
                                      IEnumerable<T> to,
                                      Func<T, double> insertCost,
                                      Func<T, double> deleteCost,
                                      Func<T, T, double> editCost) {
  T[] source = from.ToArray();
  T[] target = to.ToArray();

  // Minimum cost so far
  double[][] D = Enumerable
    .Range(0, source.Length + 1)
    .Select(line => new double[target.Length + 1])
    .ToArray();

  // Edge: all removes
  double sum = 0.0;

  for (int i = 1; i <= source.Length; ++i)
    D[i][0] = (sum += deleteCost(source[i - 1]));

  // Edge: all inserts
  sum = 0.0;

  for (int i = 1; i <= target.Length; ++i)
    D[0][i] = (sum += insertCost(target[i - 1]));

  // Having fit N - 1, K - 1 characters let's fit N, K
  for (int i = 1; i <= source.Length; ++i)
    for (int j = 1; j <= target.Length; ++j) {
      // here we choose the operation with the least cost
      double insert = D[i][j - 1] + insertCost(target[j - 1]);
      double delete = D[i - 1][j] + deleteCost(source[i - 1]);
      double edit   = D[i - 1][j - 1] + editCost(source[i - 1], target[j - 1]);

      D[i][j] = Math.Min(Math.Min(insert, delete), edit);
    }

  return D[source.Length][target.Length];
}

public static double Similar_text(string left, string right) {
  left = left ?? "";
  right = right ?? "";

  return left.Equals(right)
    ? 1.0
    : 1.0 - EditDistance(left, right, 
              insert => 1.0, 
              delete => 1.0, 
          (from, to) => from == to ? 0.0 : 2.0) 
      / Math.Max(left.Length, right.Length);
}