editDistance method

int editDistance(String other)

Returns the Damerau–Levenshtein distance, the minimum number of single-character edits (transpositions, insertions, deletions or substitutions) required to change one word into another other.

The String and other are converted to lower-case and trimmed for the comparison.

Not case-sensitive. See https://en.wikipedia.org/wiki/Damerau%E2%80%93Levenshtein_distance.

Implementation

int editDistance(String other) {
  //
  other = other.trim().toLowerCase();

  final term = trim().toLowerCase();

  // initialize a 1-based array of 26 integers with all values set to 0
  final da = _Da();

  // initialize a 1-based character array for this
  final a = _CharArray(term);

  // initialize a 1-based character array for other
  final b = _CharArray(other);

  // initialize the -1 based edit distance matrix, filling it with zeros
  final dList = <List<int>>[];
  for (var i = 0; i < b.length + 2; i++) {
    dList.add(List.filled(a.length + 2, i * 0, growable: false));
  }
  final d = _Matrix.from(dList, i: -1, j: -1);

  // compute the maximum distance
  // (remove all the charcters in this and insert with all characters in other)
  final maxDist = a.length + b.length;

  // add maxDist at the top-left of matrix
  d.setAt(-1, -1, maxDist);

  for (var i = 0; i <= a.length; i++) {
    // set the entire top row to maxDist
    d.setAt(i, -1, maxDist);
    // set the second row to [0, 0, 1, 2 ...]
    d.setAt(i, 0, i);
  }

  for (var j = 0; j <= b.length; j++) {
    // set the entire first column to maxDist
    d.setAt(-1, j, maxDist);
    // set the second column to
    d.setAt(0, j, j);
  }

  for (var i = 1; i <= a.length; i++) {
    var db = 0;
    final charA = a.get(i);

    for (var j = 1; j <= b.length; j++) {
      // print('Start with $i - $j');
      final charB = b.get(j);
      final k = da.get(charB);
      final l = db;
      int cost = 0;
      if (charA == charB) {
        cost = 0;
        db = j;
      } else {
        cost = 1;
      }
      final costs = <int>[
        //substitution cost
        d.get(i - 1, j - 1) + cost,
        //insertion cost
        d.get(i, j - 1) + 1,
        //deletion cost
        d.get(i - 1, j) + 1,
        //transposition cost
        d.get(k - 1, l - 1) + (i - k - 1) + 1 + (j - l - 1)
      ];
      // print(costs);
      costs.sort(((a, b) => a.compareTo(b)));
      d.setAt(i, j, costs.first);
      // for (var i = 0; i < d.elements.length; i++) {
      //   final arr = d.elements.elements[i];
      //   print(arr.elements);
      // }
      // print('Done with $i - $j');
    }
    da.setAt(charA, i);
  }

  // return the value from the edit distance matrix matrix
  return d.get(a.length, b.length);
}