Hacker News Reader

Comment by evandijk70 | Hacker News Reader

How do you define an edit distance (the number of operations required to transform one string to the other) if you don't allow substitutions?

Eg. what's the edit distance between these two strings?

AAAA BBBB

Traditionally, it would be 4, but it's unclear if you allow only inserts and deletions.

View on HN

  > Eg. what's the edit distance between these two strings?
  > 
  > AAAA BBBB
  > 
  > Traditionally, it would be 4, but it's unclear if you
  > allow only inserts and deletions.

It is >= 8, since you surely have to remove 4 As and insert 4 Bs. Since these 8 transformations indeed transform AAAA into BBBB, it is exactly 8.

It is very easy to generalize the Wagner-Fisher algorithm (https://en.wikipedia.org/wiki/Wagner%E2%80%93Fischer_algorit...) to this "simpler" variant of edit distance, but this algorithm will still have a (worst-case) runtime of O(m*n), where m, n are the lengths of the two strings.

Of course, the question remains: Is there a (worst-case) faster algorithm?

Don't know, but you still end up aligning common subsequences (advanced monotonically in both seqs) and you still have the same order-of-computing-cells allowed in the standard m*n dynamic program. Your restricted problem is basically asking for the standard unix line-diff.

It's not unclear, any substitution can be replicated by a deletion and insertion. I have no idea if that leads to a simpler case of the edit distance algorithm.

Reply on news.ycombinator.com