I'm working on pset6 similarities (more) and have a question about the edit distance algorithm.

If the edit distance algorithm returns more than one cost with the same value, which operation takes priority here?

For example, let's say you run edit distance for a particular square in the matrix and it returns the following 3 tuples: (2, D), (2, I), (3, S).

In this case, it has to be one of (2, D) or (2, I). Which one takes priority in this case?


The priority does not matter.

For the reference implementation, I tried with different inputs.

"aba" -> "bab" (0, None) -> (1, D) -> (1, S) -> (1, S) -> (2, I)

Since we walk backwards, it prefers I over D.

"a" -> "bb" (0, None) -> (1, I) -> (2, S)

So it prefers S over I.

Deriving from those tests, the reference implementation prioritizes them as

  1. substitution
  2. insertion
  3. deletion

But really, it doesn't matter as long as the path is a valid shortest path.

  • good to know. thank you! – doctopus Apr 9 '18 at 15:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .