Optimizing travel double for loop using swift

Question

I used minimum edit distance algorithm to find the bundle of the most similar strings in an array.

So, I have to travel double for loop to compare all element.

If the data is large enough, this algorithm is Inefficient.

Is there a way to optimize?

let data = [
  "10000", // count
  "asdfqwerty", "asdfzxcvgh", "asdfpoiuyt",
  ...
]

for i in 1..<data.count {
  let string = data[i]
  for j in (i + 1)..<data.count {
    let newMin = string.minimumEditDistance(other: data[j])

    if min >= newMin {
      // some logic
    }
  }
}

extension String {
  public func minimumEditDistance(other: String, `default`: Int = 10) -> Int {
    let m = self.count
    let n = other.count

    if m == 0 || n == 0 {
      return `default`
    }

    var matrix = [[Int]](repeating: [Int](repeating: 0, count: n + 1), count: m + 1)

    // initialize matrix
    for index in 1...m {
      // the distance of any first string to an empty second string
      matrix[index][0] = index
    }

    for index in 1...n {
      // the distance of any second string to an empty first string
      matrix[0][index] = index
    }

    // compute Levenshtein distance
    for (i, selfChar) in self.enumerated() {
      for (j, otherChar) in other.enumerated() {
        if otherChar == selfChar {
          // substitution of equal symbols with cost 0
          matrix[i + 1][j + 1] = matrix[i][j]
        } else {
          // minimum of the cost of insertion, deletion, or substitution
          // added to the already computed costs in the corresponding cells
          matrix[i + 1][j + 1] = Swift.min(matrix[i][j] + 1, matrix[i + 1][j] + 1, matrix[i][j + 1] + 1)
        }
      }
    }
    return matrix[m][n]
  }
}

Answer 1

You can achieve desired behaviour by sorting your array using your minimumEditDistance as a sorting function and then taking first or last element (depends on how you define sorting) and what you need - min or max. It will likely run in O(N*log(N)) time. Which is already better than exponential.

As @Sultan mentioned, it will work not for all distances, as transitivity is applicable only to Metrics (functions that define a distance between each element of the set). You're using Levenstain distance as an editing distance algorithm, which is indeed a metric. The solution I mentioned should help to optimise in some circumstances.