osaDistance function

int osaDistance(List<int> listA, List<int> listB)

Optimal string alignment (OSA) algorithm computes the number of edit operations needed to make the strings equal under the condition that no substring is edited more than once. Damerau–Levenshtein makes no such assumption. Thus this algorithm is less precise but faster.

Implementation

int osaDistance(List<int> listA, List<int> listB) {
  int lengthA = listA.length;
  int lengthB = listB.length;

  OffsetList<OffsetList<int>> d = OffsetList<OffsetList<int>>(offset: 0);
  for (int i = 0; i < lengthA + 1; i++) {
    d.add(OffsetList.filled(len: lengthB + 1, offset: 0, val: 0));
  }

  for (int i = 0; i <= lengthA; i++) {
    d[i][0] = i;
  }
  for (int j = 0; j <= lengthB; j++) {
    d[0][j] = j;
  }

  OffsetList<int> a = OffsetList.fromList(offset: 1, list: listA);
  OffsetList<int> b = OffsetList.fromList(offset: 1, list: listB);

  for (int i = 1; i <= lengthA; i++) {
    for (int j = 1; j <= lengthB; j++) {
      int cost = (a[i] == b[j]) ? 0 : 1;

      d[i][j] = [
        d[i - 1][j] + 1, // deletion
        d[i][j - 1] + 1, // insertion
        d[i - 1][j - 1] + cost // substitution
      ].reduce((value, element) => value < element ? value : element);

      if (i > 1 && j > 1 && a[i] == b[j - 1] && a[i - 1] == b[j]) {
        d[i][j] = [
          d[i][j],
          d[i - 2][j - 2] + 1 // transposition
        ].reduce((value, element) => value < element ? value : element);
      }
    }
  }

  return d[lengthA][lengthB];
}