Что такое C# полный аналог PHP функции «Similar_text ()»?

Question

Что такое C# полный аналог PHP функция similar_text()?

Я пробовал этот код

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 () : вычисляет сходство между двумя string с, как описано в

Классика программирования: Реализация лучших в мире алгоритмов Оливером

(ISBN 0-131-00413-1).

Обратите внимание, что эта реализация не использует стек, как в псевдокоде Оливера, но рекурсивные вызовы , которые могут или не могут ускорить весь процесс. Также обратите внимание, что сложность этого алгоритма составляет O(N**3), где N - длина самой длинной строки.

Answer 1

Во-первых, вы должны реализовать редактировать расстояние , скажем, Levenstein one; давайте сделаем это как можно больше generi c:

См. Обнаружение различий между двумя строками

для последовательность редактирования и более подробная информация.

Код:

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];
}

Теперь легко написать Similar_text

Подпрограмма:

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);
}

Сложность времени равна O(left.Length * right.Length) или O(N**2), если обе строки имеют примерно одинаковую длину (N)