4 ms·
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 ed
by 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 agoIt'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 agoDon'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.