Faster edit distance algorithm [closed]

Question

Problem: I know the trivial edit distance DP formulation and computation in O(mn) for 2 strings of size n and m respectively. But I recently came to know that if we only need to calculate the minimum value of edit distance f and it is bounded |f|<=s, then we can calculate it in O(min(m,n) + s^2) or O(s*min(m,n)) [wikipedia] time.

Please explain the dp formulation behind it if this is DP based or explain the algorithm .

Look at the improved algorithm section of the link: http://en.wikipedia.org/wiki/Edit_distance .

one more link about improved UKKONEN'S algorithm http://www.berghel.net/publications/asm/asm.php

Thanks in advance.

Answer 1

You can calculate edit distance in O(min(n, m) * s) time use next simple idea:

Consider the i-th string in DP-table.

So, if we know, that answer <= s, then we are intersted in cells with coordinates (i, i - s), (i, i - s + 1), ... ,(i, i + s). Because in other cells answer strictly greater than s.

For example, suppose we know, that edit distance between "abacaba" and "baadba" less than 3.

So, we can skip red cells, because they have value more than s.

Asymptotic of the algorithm O(min(n, m) * s) because we calculate s cells to the left and right of the main diagonal.