3 ms·

Does a similar result hold, if we don't consider inserts, deletions and substitutions (definition of edit distance), but only inserts and deletions?

by wolfgke 11y ago

evandijk70 11y ago
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.
- greendestiny 11y ago
  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.
- wolfgke 11y ago
  > 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_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?
  - jongraehl 11y ago
    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.
jongraehl 11y ago
I don't know about the mathematical result (the conditional proof), but I do know that it's easy to expand or limit the edit operations, or change their costs, while keeping the dynamic program order the same (so not e.g. allowing 'move this whole phrase' type edits - that would probably be cubic or worse). If you're considering the generalized 'set any costs you like for the operations' problem then you could set the subst cost as 2 and the insert and delete as 1. Again, I know that's not precisely what you asked. I can't think of a reduction from "insert+delete only" problems to "insert+delete+subst" (all operations cost 1) problems (where solving the latter gives you a solution to the former, and the size is no more than k times the original).

Does a similar result hold, if we don't consider inserts, deletions and substitutions (definition of edit distance), but only inserts and deletions?

by wolfgke 11y ago

Does a similar result hold, if we don't consider inserts, deletions and substitutions (definition of edit distance), but only inserts and deletions?

evandijk70 11y ago

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.

greendestiny 11y ago
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.
wolfgke 11y ago
> 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_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?
- jongraehl 11y ago
  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.

jongraehl 11y ago

I don't know about the mathematical result (the conditional proof), but I do know that it's easy to expand or limit the edit operations, or change their costs, while keeping the dynamic program order the same (so not e.g. allowing 'move this whole phrase' type edits - that would probably be cubic or worse). If you're considering the generalized 'set any costs you like for the operations' problem then you could set the subst cost as 2 and the insert and delete as 1. Again, I know that's not precisely what you asked. I can't think of a reduction from "insert+delete only" problems to "insert+delete+subst" (all operations cost 1) problems (where solving the latter gives you a solution to the former, and the size is no more than k times the original).