source: branches/2895_PushGP_GenealogyAnalysis/HeuristicLab.Problems.ProgramSynthesis/Push.Base/Extensions/StringExtensions.cs @ 17511

using System;

namespace HeuristicLab.Problems.ProgramSynthesis {
  public static class StringExtensions {
    public static bool IsNumeric(this string str) {
      int n;
      return int.TryParse(str, out n);
    }

    /// <summary>
    /// https://github.com/DanHarltey/Fastenshtein
    /// </summary>
    public static int LevenshteinDistance(this string source, string target) {
      if (target.Length == 0) {
        return source.Length;
      }

      int[] costs = new int[target.Length];

      // Add indexing for insertion to first row
      for (int i = 0; i < costs.Length;) {
        costs[i] = ++i;
      }

      for (int i = 0; i < source.Length; i++) {
        // cost of the first index
        int cost = i;
        int addationCost = i;

        // cache value for inner loop to avoid index lookup and bonds checking, profiled this is quicker
        char value1Char = source[i];

        for (int j = 0; j < target.Length; j++) {
          int insertionCost = cost;

          cost = addationCost;

          // assigning this here reduces the array reads we do, improvement of the old version
          addationCost = costs[j];

          if (value1Char != target[j]) {
            if (insertionCost < cost) {
              cost = insertionCost;
            }

            if (addationCost < cost) {
              cost = addationCost;
            }

            ++cost;
          }

          costs[j] = cost;
        }
      }

      return costs[costs.Length - 1];
    }

    /// <summary>
    /// https://www.dotnetperls.com/levenshtein
    /// </summary>
    public static int LevenshteinDistance2(this string source, string target) {
      if (source == null && target == null) return 0;
      if (source == null) return target.Length;
      if (target == null) return source.Length;

      int n = source.Length;
      int m = target.Length;
      int[,] d = new int[n + 1, m + 1];

      // Step 1
      if (n == 0) {
        return m;
      }

      if (m == 0) {
        return n;
      }

      // Step 2
      for (int i = 0; i <= n; d[i, 0] = i++) {
      }

      for (int j = 0; j <= m; d[0, j] = j++) {
      }

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

          // Step 6
          d[i, j] = Math.Min(
              Math.Min(d[i - 1, j] + 1, d[i, j - 1] + 1),
              d[i - 1, j - 1] + cost);
        }
      }
      // Step 7
      return d[n, m];
    }
  }
}